Article

A sieve algorithm for the shortest lattice vector problem

Authors:

Miklós Ajtai,

Ravi Kumar,

D. SivakumarAuthors Info & Claims

STOC '01: Proceedings of the thirty-third annual ACM symposium on Theory of computing

Pages 601 - 610

https://doi.org/10.1145/380752.380857

Published: 06 July 2001 Publication History

Get Access

Abstract

We present a randomized 2^{O(n)} time algorithm to compute a shortest non-zero vector in an n-dimensional rational lattice. The best known time upper bound for this problem was 2^{O(n\log n)} first given by Kannan [7] in 1983. We obtain several consequences of this algorithm for related problems on lattices and codes, including an improvement for polynomial time approximations to the shortest vector problem. In this improvement we gain a factor of log log n in the exponent of the approximating factor.

References

[1]

M. Ajtai. Generating hard instances of lattice problems. Proc. 28th ACM Symposium on Theory of Computing, pp. 99-108, 1996. Full version available as ECCC Technical Report TR96-007 at www.eccc.uni-trier.de/eccc/ .

Digital Library

Google Scholar

[2]

M. Ajtai. The shortest vector problem in L2 is NP-hard for randomized reductions. Proc. 30th ACM Symposium on Theory of Computing, pp. 10-19, 1998.

Digital Library

Google Scholar

[3]

A. Blum, A. Kalai, and H. Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. Proc. 32nd ACM Symposium on Theory of Computing, pp. 435-440, 2000.

Digital Library

Google Scholar

[4]

P. van Emde Boas. Another NP-complete partition problem and the complexity of computing short vectors in lattices. Mathematics Department, University of Amsterdam, TR 81-04, 1981.

Google Scholar

[5]

O. Goldreich and S. Goldwasser. On the limits of nonapproximability of lattice problems. Journal of Computer and System Sciences, 60(3):540-563, 2000.

Digital Library

Google Scholar

[6]

B. Helfrich. Algorithms to construct Minkowski reduced and Hermite reduced bases. Theoretical Computer Science, 41:125-139, 1985.

Digital Library

Google Scholar

[7]

R. Kannan. Minkowski's convex body theorem and integer programming. Mathematics of Operations Research, 12:415-440, 1987. Preliminary version in ACM Symposium on Theory of Computing 1983.

Digital Library

Google Scholar

[8]

P. Klein. Finding the closest lattice vector when it's unusually close. Proc. 11th Symposium on Discrete Algorithms, 2000.

Digital Library

Google Scholar

[9]

R. Kumar and D. Sivakumar. On polynomial approximations to the shortest lattice vector length. Proc. 12th Symposium on Discrete Algorithms, 2001. To appear.

Digital Library

Google Scholar

[10]

A. K. Lenstra, H. W. Lenstra, and L. Lovasz. Factoring polynomials with rational coefficients. Mathematische Annalen, 261:515-534, 1982.

Crossref

Google Scholar

[11]

L. Lovasz. An Algorithmic Theory of Numbers, Graphs and Convexity. CBMS-NSF Regional Conference Series on Applied Mathematics, SIAM, 1986.

Google Scholar

[12]

D. Micciancio. The shortest vector in a lattice is hard to approximate to within some constant. Proc. 39th IEEE Symposium on Foundations of Computer Science, pp. 92-98, 1998.

Digital Library

Google Scholar

[13]

C. P. Schnorr. A hierarchy of polynomial time basis reduction algorithms. Theoretical Computer Science, 53:201-224, 1987.

Digital Library

Google Scholar

Cited By

View all

Salleh NKamarulhaili H(2024)On the Properties of Reduced Basis Related to Lattice-Reduced AlgorithmMalaysian Journal of Mathematical Sciences10.47836/mjms.18.2.0518:2(287-300)Online publication date: 27-Jun-2024
https://doi.org/10.47836/mjms.18.2.05
Yu HZheng Q(2024)A Lattice-Based Method for Recovering the Unknown Parameters of Truncated Multiple Recursive Generators with ConstantChinese Journal of Electronics10.23919/cje.2022.00.38733:6(1458-1467)Online publication date: Nov-2024
https://doi.org/10.23919/cje.2022.00.387
Sameer KNeha Kishor JJawar SDilip SAnjan Kumar S(2024)Quantum-Resistant Encryption For Secure End-to-End Communication2024 ITU Kaleidoscope: Innovation and Digital Transformation for a Sustainable World (ITU K)10.23919/ITUK62727.2024.10772922(1-8)Online publication date: 21-Oct-2024
https://doi.org/10.23919/ITUK62727.2024.10772922
Show More Cited By

Index Terms

A sieve algorithm for the shortest lattice vector problem
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Hardness of approximating the shortest vector problem in lattices

Let p > 1 be any fixed real. We show that assuming NP ⊈ RP, there is no polynomial time algorithm that approximates the Shortest Vector Problem (SVP) in ℓ_p norm within a constant factor. Under the stronger assumption NP ⊈ RTIME(2^{poly(log n)}), we show ...
The worst-case behavior of schnorr's algorithm approximating the shortest nonzero vector in a lattice
STOC '03: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing

Schnorr's algorithm for finding an approximation for the shortest nonzero vector in an n dimensional lattice depends on a parameter k. He proved that for a fixed k ≤ n his algorithm (block 2k-reduction) provides a lattice vector whose length is greater ...
Faster exponential time algorithms for the shortest vector problem
SODA '10: Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms

We present new faster algorithms for the exact solution of the shortest vector problem in arbitrary lattices. Our main result shows that the shortest vector in any n-dimensional lattice can be found in time 2^3.199n (and space 2^1.325n), or in space 2^...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '01: Proceedings of the thirty-third annual ACM symposium on Theory of computing

July 2001

755 pages

ISBN:1581133499

DOI:10.1145/380752

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 July 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC01

Sponsor:

SIGACT

STOC01: 33rd ACM Symposium on Theory of Computing

Hersonissos, Greece

Acceptance Rates

STOC '01 Paper Acceptance Rate 83 of 230 submissions, 36%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

326
Total Citations
View Citations
709
Total Downloads

Downloads (Last 12 months)175
Downloads (Last 6 weeks)12

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Salleh NKamarulhaili H(2024)On the Properties of Reduced Basis Related to Lattice-Reduced AlgorithmMalaysian Journal of Mathematical Sciences10.47836/mjms.18.2.0518:2(287-300)Online publication date: 27-Jun-2024
https://doi.org/10.47836/mjms.18.2.05
Yu HZheng Q(2024)A Lattice-Based Method for Recovering the Unknown Parameters of Truncated Multiple Recursive Generators with ConstantChinese Journal of Electronics10.23919/cje.2022.00.38733:6(1458-1467)Online publication date: Nov-2024
https://doi.org/10.23919/cje.2022.00.387
Sameer KNeha Kishor JJawar SDilip SAnjan Kumar S(2024)Quantum-Resistant Encryption For Secure End-to-End Communication2024 ITU Kaleidoscope: Innovation and Digital Transformation for a Sustainable World (ITU K)10.23919/ITUK62727.2024.10772922(1-8)Online publication date: 21-Oct-2024
https://doi.org/10.23919/ITUK62727.2024.10772922
Liu FZheng ZGong ZTian KZhang YHu ZLi JXu Q(2024)A survey on lattice-based digital signatureCybersecurity10.1186/s42400-023-00198-17:1Online publication date: 1-Apr-2024
https://doi.org/10.1186/s42400-023-00198-1
Malygina EKutsenko ANovoselov SKolesnikov NBakharev AKhilchuk IShaporenko ATokareva N(2024)Post-Quantum Cryptosystems: Open Problems and Solutions. Lattice-Based CryptosystemsJournal of Applied and Industrial Mathematics10.1134/S199047892304008717:4(767-790)Online publication date: 16-Feb-2024
https://doi.org/10.1134/S1990478923040087
Guo QJohansson TNguyen V(2024)A New Sieving-Style Information-Set Decoding AlgorithmIEEE Transactions on Information Theory10.1109/TIT.2024.345715070:11(8303-8319)Online publication date: Nov-2024
https://doi.org/10.1109/TIT.2024.3457150
Yu HZheng Q(2024)Predicting Truncated Galois Linear Feedback Shift RegistersIEEE Transactions on Information Theory10.1109/TIT.2024.344287070:12(9179-9194)Online publication date: Dec-2024
https://doi.org/10.1109/TIT.2024.3442870
Lee YBoche HKutyniok G(2024)Computability of OptimizersIEEE Transactions on Information Theory10.1109/TIT.2023.334707170:4(2967-2983)Online publication date: Apr-2024
https://doi.org/10.1109/TIT.2023.3347071
Pan YJiang RPei BChen G(2024)Pump-BSKZ: A Novel Sieve Algorithm to Solve Shortest Vector Problem2024 7th International Conference on Computer Information Science and Application Technology (CISAT)10.1109/CISAT62382.2024.10695403(1-6)Online publication date: 12-Jul-2024
https://doi.org/10.1109/CISAT62382.2024.10695403
Ajitha Shenoy K(2024)A Novel Approximation Algorithm for the Shortest Vector ProblemIEEE Access10.1109/ACCESS.2024.346936812(141026-141031)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3469368
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Hardness of approximating the shortest vector problem in lattices

The worst-case behavior of schnorr's algorithm approximating the shortest nonzero vector in a lattice

Faster exponential time algorithms for the shortest vector problem