Rounding in lattices and its cryptographic applications
Dan Boneh, Ramarathnam Venkatesan · 1997
We analyze a lattice rounding technique using a natural matrix norm. We present its application to proving in a non-uniform model the hardness of computing 2 log log p bits of the secret keys of Diffie-Hellman and related protocols from the public keys. Earlier in [2] it was shown that p log p bits are hard to compute. 1 Introduction Lattice basis reduction techniques have proven to be very useful in diverse areas. Examples include cryptography, settling number theoretic conjectures, and diophantine approximation. Rounding a given vector to an approximately closest vector in a given lattice was first studied in this context by Babai [1]. Recently in [2] rounding in lattices was used to study the hardness of computing the most significant bits of secret keys obtained using the Diffie-Hellman protocol and related schemes. Motivated by this, we study a new lattice rounding technique which is used to improve on the results of [2] in a non-uniform model. The Diffie-Hellman protocol [3] ena...