skip to main content
10.1145/1250790.1250859acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
Article

Tensor-based hardness of the shortest vector problem to within almost polynomial factors

Published: 11 June 2007 Publication History

Abstract

We show that unless NP ⊆ RTIME (2poly(log n)), for any ε > 0 there is no polynomial-time algorithm approximating the Shortest Vector Problem (SVP) on n-dimensional lattices inthe lp norm (1 ≤q p<∞) to within a factor of 2(log n)1-ε. This improves the previous best factor of 2(logn)1/2-ε under the same complexity assumption due to Khot. Under the stronger assumption NP ࣰ RSUBEXP, we obtain a hardness factor of nc/log log n for some c > 0.
Our proof starts with Khot's SVP instances from that are hard to approximate to within some constant. To boost the hardness factor we simply apply the standard tensor product oflattices. The main novel part is in the analysis, where we show that Khot's lattices behave nicely under tensorization. At the heart of the analysis is a certain matrix inequality which was first used in the context of lattices by de Shalit and Parzanchevski.

References

[1]
D. Aharonov and O. Regev. Lattice problems in NP intersect coNP. Journal of the ACM, 52(5):749--765, 2005. Preliminary version in FOCS'04.
[2]
M. Ajtai. The shortest vector problem in l2 is NP-hard for randomized reductions (extended abstract). In Proceedings of the thirtieth annual ACM symposium on theory of computing - STOC '98, pages 10--19, Dallas, Texas, USA, May 1998.
[3]
M. Ajtai. Generating hard instances of lattice problems. In Complexity of computations and proofs, volume 13 of Quad. Mat., pages 1--32. Dept. Math., Seconda Univ. Napoli, Caserta, 2004.
[4]
M. Ajtai, R. Kumar, and D. Sivakumar. A sieve algorithm for the shortest lattice vector problem. In Proc. 33th ACM Symp. on Theory of Computing (STOC), pages 601--610, 2001.
[5]
N. Alon and J.H. Spencer. The probabilistic method. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience {John Wiley & Sons}, New York, second edition, 2000.
[6]
S. Arora, L. Babai, J. Stern, and E.Z. Sweedyk. The hardness of approximate optima in lattices, codes, and systems of linear equations. Journal of Computer and System Sciences, 54(2):317--331, Apr. 1997. Preliminary version in FOCS 1993.
[7]
L. Babai. On Lovász lattice reduction and the nearest lattice point problem. Combinatorica, 6(1):1--13, 1986.
[8]
M. Bellare, S. Goldwasser, C. Lund, and A. Russell. Efficient probabilistically checkable proofs and applications to approximation. In Proc. 25th ACM Symposium on Theory of Computing (STOC), pages 294--304, 1993.
[9]
R. Bhatia. Matrix Analysis. Springer, 1997.
[10]
J.-Y. Cai and A. Nerurkar. Approximating the SVP to within a factor (1+1/dimε) is NP-hard under randomized reductions. J. Comput. Syst. Sci., 59(2):221--239, 1999.
[11]
H. Cohen. A course in computational algebraic number theory, volume 138 of Graduate Texts in Mathematics. Springer-Verlag, Berlin, 1993.
[12]
E. de Shalit and O. Parzanchevski. On tensor products of semistable lattices. Preprint, 2006.
[13]
I. Dinur. Approximating SVP to within almost-polynomial factors is NP-hard. Theoretical Computer Science, 285(1):55--71, 2002.
[14]
I. Dinur, G. Kindler, R. Raz, and S. Safra. Approximating CVP to within almost-polynomial factors is NP-hard. Combinatorica, 23(2):205--243, 2003. Preliminary version in FOCS 1998.
[15]
I. Dumer, D. Micciancio, and M. Sudan. Hardness of approximating the minimum distance of a linear code. IEEE Trans. Inform. Theory, 49(1):22--37, 2003.
[16]
O. Goldreich and S. Goldwasser. On the limits of nonapproximability of lattice problems. J. Comput. System Sci., 60(3):540--563, 2000.
[17]
R. Kannan. Minkowski's convex body theorem and integer programming. Math. Oper. Res., 12:415--440, 1987.
[18]
S. Khot. Hardness of approximating the shortest vector problem in lattices. Journal of the ACM, 52(5):789--808, Sept. 2005. Preliminary version in FOCS 2004.
[19]
A. Lenstra, H. Lenstra, and L. Lovász. Factoring polynomials with rational coefficients. Math. Ann., 261:515--534, 1982.
[20]
D. Micciancio. The shortest vector problem is NP-hard to approximate to within some constant. SIAM Journal on Computing, 30(6):2008--2035, Mar. 2001. Preliminary version in FOCS 1998.
[21]
D. Micciancio and S. Goldwasser. Complexity of Lattice Problems: A Cryptographic Perspective, volume 671 of The Kluwer International Series in Engineering and Computer Science. Kluwer Academic Publishers, Boston, MA, 2002.
[22]
J. Milnor and D. Husemoller. Symmetric bilinear forms. Springer-Verlag, Berlin, 1973.
[23]
H. Minkowski. Geometrie der Zahlen. I@. B. G. Teubner, Leipzig, 1896.
[24]
O. Regev and R. Rosen. Lattice problems and norm embeddings. In Proc. 38th ACM Symp. on Theory of Computing (STOC), pages 447--456, 2006.
[25]
C.-P. Schnorr. A hierarchy of polynomial time lattice basis reduction algorithms. Theoretical Computer Science, 53(2-3):201--224, 1987.
[26]
P. van Emde Boas. Another NP-complete problem and the complexity of computing short vectors in a lattice. Technical Report 81-04, Math Inst., University Of Amsterdam, Amsterdam, 1981.

Cited By

View all
  • (2024)Fast white-box adversarial streaming without a random oracleProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692600(13199-13224)Online publication date: 21-Jul-2024
  • (2024)Fine-grained hardness of the unique shortest vector problem in latticesSCIENTIA SINICA Informationis10.1360/SSI-2024-014554:12(2727)Online publication date: 22-Nov-2024
  • (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
  • Show More Cited By

Index Terms

  1. Tensor-based hardness of the shortest vector problem to within almost polynomial factors

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing
    June 2007
    734 pages
    ISBN:9781595936318
    DOI:10.1145/1250790
    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]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 11 June 2007

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. hardness of approximation
    2. lattices
    3. tensor product

    Qualifiers

    • Article

    Conference

    STOC07
    Sponsor:
    STOC07: Symposium on Theory of Computing
    June 11 - 13, 2007
    California, San Diego, USA

    Acceptance Rates

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

    Upcoming Conference

    STOC '25
    57th Annual ACM Symposium on Theory of Computing (STOC 2025)
    June 23 - 27, 2025
    Prague , Czech Republic

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)14
    • Downloads (Last 6 weeks)3
    Reflects downloads up to 27 Jan 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Fast white-box adversarial streaming without a random oracleProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692600(13199-13224)Online publication date: 21-Jul-2024
    • (2024)Fine-grained hardness of the unique shortest vector problem in latticesSCIENTIA SINICA Informationis10.1360/SSI-2024-014554:12(2727)Online publication date: 22-Nov-2024
    • (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
    • (2023)Revisiting lower dimension lattice attacks on NTRUInformation Processing Letters10.1016/j.ipl.2022.106353181(106353)Online publication date: Mar-2023
    • (2023)Improving convergence and practicality of slide-type reductionsInformation and Computation10.1016/j.ic.2023.105012291(105012)Online publication date: Mar-2023
    • (2023)Verification of NP-Hardness Reduction Functions for Exact Lattice ProblemsAutomated Deduction – CADE 2910.1007/978-3-031-38499-8_21(365-381)Online publication date: 2-Sep-2023
    • (2022)Approximate $$\mathrm {CVP}_{}$$ in Time $$2^{0.802 n}$$ - Now in Any Norm!Integer Programming and Combinatorial Optimization10.1007/978-3-031-06901-7_33(440-453)Online publication date: 27-May-2022
    • (2021)Dimension-preserving reductions between SVP and CVP in different p-normsProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458209(2444-2462)Online publication date: 10-Jan-2021
    • (2021)Parameterized Intractability of Even Set and Shortest Vector ProblemJournal of the ACM10.1145/344494268:3(1-40)Online publication date: 22-Mar-2021
    • (2021)Approximate CVP in time 20.802Journal of Computer and System Sciences10.1016/j.jcss.2021.09.006Online publication date: Sep-2021
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media