2022/11/21 by Divesh Aggarwal, Aggarwal, Divesh, Huck Bennett +15
Computer Science · #Coding theory and cryptography #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2211.11693
openalex publication_date 2022/11/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the complexity of lattice problems in a world where algorithms, reductions, and protocols can run in superpolynomial time, revisiting four foundational results: two worst-case to average-case reductions and two protocols. We also show a novel protocol. 1. We prove that secret-key cryptography exists if \widetildeO(√(n))-approximate SVP is hard for 2ε n-time algorithms. I.e., we extend to our setting (Micciancio and Regev's improved version of) Ajtai's celebrated polynomial-time worst-case to average-case reduction from \widetildeO(n)-approximate SVP to SIS. 2. We prove that public-key cryptography exists if \widetildeO(n)-approximate SVP is hard for 2ε n-time algorithms. This extends to our setting Regev's celebrated polynomial-time worst-case to average-case reduction from \widetildeO(n1.5)-approximate SVP to LWE. In fact, Regev's reduction is quantum, but ours is classical, generalizing Peikert's polynomial-time classical reduction from \widetildeO(n2)-approximate SVP. 3. We show a 2ε n-time coAM protocol for O(1)-approximate CVP, generalizing the celebrated polynomial-time protocol for O(√(n/log n))-CVP due to Goldreich and Goldwasser. These results show complexity-theoretic barriers to extending the recent line of fine-grained hardness results for CVP and SVP to larger approximation factors. (This result also extends to arbitrary norms.) 4. We show a 2ε n-time co-non-deterministic protocol for O(√(log n))-approximate SVP, generalizing the (also celebrated!) polynomial-time protocol for O(√(n))-CVP due to Aharonov and Regev. 5. We give a novel coMA protocol for O(1)-approximate CVP with a 2ε n-time verifier. All of the results described above are special cases of more general theorems that achieve time-approximation factor tradeoffs.