Title :
An improved worst-case to average-case connection for lattice problems
Author :
Cai, Jin-Yi ; Nerurkar, Ajay P.
Author_Institution :
Dept. of Comput. Sci., State Univ. of New York, Buffalo, NY, USA
Abstract :
We improve a connection of the worst-case complexity and the average-case complexity of some well-known lattice problems. This fascinating connection was first discovered by Ajtai (1995). We improve the exponent of this connection from 8 to 3.5+ε
Keywords :
computational complexity; group theory; average-case complexity; discrete additive subgroup; lattice problems; worst-case complexity; Bridges; Computer science; Cryptographic protocols; Cryptography; Gaussian processes; Geometry; Lattices; Microwave integrated circuits; Polynomials; Security;
Conference_Titel :
Foundations of Computer Science, 1997. Proceedings., 38th Annual Symposium on
Conference_Location :
Miami Beach, FL
Print_ISBN :
0-8186-8197-7
DOI :
10.1109/SFCS.1997.646135
