Approximating shortest lattice vectors is not harder than approximating closest lattice vectors
From MaRDI portal
Publication:1606967
DOI10.1016/S0020-0190(99)00083-6zbMath0999.68085WikidataQ57567990 ScholiaQ57567990MaRDI QIDQ1606967
Oded Goldreich, Daniele Micciancio, Jean-Pierre Seifert, Shmuel Safra
Publication date: 25 July 2002
Published in: Information Processing Letters (Search for Journal in Brave)
Related Items
Approximate CVP in time \(2^{0.802 n}\) -- now in any norm! ⋮ The Efficiency of Embedding-Based Attacks on the GGH Lattice-Based Cryptosystem ⋮ Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP) ⋮ A randomized sieving algorithm for approximate integer programming ⋮ Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH ⋮ Approximate CVP_p in Time 2^{0.802 n} ⋮ Algorithms for the Shortest and Closest Lattice Vector Problems ⋮ Using the Inhomogeneous Simultaneous Approximation Problem for Cryptographic Design ⋮ Non-standard approaches to integer programming ⋮ Cryptographic Functions from Worst-Case Complexity Assumptions ⋮ Unnamed Item ⋮ A Digital Signature Scheme Based on CVP ∞ ⋮ Algorithmic Problems for Metrics on Permutation Groups ⋮ Approximate CVP\(_p\) in time \(2^{0.802n}\) ⋮ Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle ⋮ A note on BDD problems with \(\lambda_2\)-gap
This page was built for publication: Approximating shortest lattice vectors is not harder than approximating closest lattice vectors
