Rounding in lattices and its cryptographic applications

Authors: D. Boneh and R. Venkatesan

We analyze a technique for rounding in lattices 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 results only show that (in a uniform model) \sqrt{\log p} bits are hard to compute.

In Proceedings of SODA 1997, pp. 675--681

Full paper: gzipped-PostScript         [first posted 11/1997 ]