Rounding in lattices and its cryptographic applications
Authors: D. Boneh and R. Venkatesan
Abstract:
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.
Reference:
In Proceedings of SODA 1997, pp. 675--681
Full paper: gzipped-PostScript [first posted 11/1997 ]