skip to main content
article

Lattice problems in NP ∩ coNP

Published: 01 September 2005 Publication History

Abstract

We show that the problems of approximating the shortest and closest vector in a lattice to within a factor of √n lie in NP intersect coNP. The result (almost) subsumes the three mutually-incomparable previous results regarding these lattice problems: Banaszczyk [1993], Goldreich and Goldwasser [2000], and Aharonov and Regev [2003]. Our technique is based on a simple fact regarding succinct approximation of functions using their Fourier series over the lattice. This technique might be useful elsewhere---we demonstrate this by giving a simple and efficient algorithm for one other lattice problem (CVPP) improving on a previous result of Regev[2003]. An interesting fact is that our result emerged from a “dequantization” of our previous quantum result in Aharonov and Regev [2003]. This route to proving purely classical results might be beneficial elsewhere.

References

[1]
Aaronson, S. 2004. Lower bounds for local search by quantum arguments. In Proceedings of the 36th ACM Symposium on Theory of Computing (STOC). ACM, New York, 465--474.
[2]
Aharonov, D., and Regev, O. 2003. A lattice problem in quantum NP. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, Calif., 210--219.
[3]
Ajtai, M. 1996. Generating hard instances of lattice problems (extended abstract). In Proceedings of the 28th ACM Symposium on Theory of Computing (STOC). ACM, New York, 99--108.
[4]
Ajtai, M. 1998. The shortest vector problem in l_2 is NP-hard for randomized reductions (extended abstract) 10-19. In Proceedings of the 30th ACM Symposium on Theory of Computing (STOC). ACM, New York, 10--19.
[5]
Ajtai, M., and Dwork, C. 1997. A public-key cryptosystem with worst-case/average-case equivalence. In Proceedings of the 29th ACM Symposium on Theory of Computing (STOC). ACM, New York, 284--293.
[6]
Ajtai, M., Kumar, R., and Sivakumar, D. 2001. A sieve algorithm for the shortest lattice vector problem. In Proceedings of the 33rd ACM Symposium on Theory of Computing. ACM, New York, 601--610.
[7]
Banaszczyk, W. 1993. New bounds in some transference theorems in the geometry of numbers. Math. Ann. 296, 4, 625--635.
[8]
Bruck, J., and Smolensky, R. 1992. Polynomial threshold functions, AC0 functions, and spectral norms. SIAM J. Comput. 21, 1, 33--42.
[9]
Cai, J.-Y., and Nerurkar, A. 2000. A note on the non-NP-hardness of approximate lattice problems under general Cook reductions. Inform. Process. Lett. 76, 1-2, 61--66.
[10]
Dinur, I., Kindler, G., Raz, R., and Safra, S. 2003. Approximating CVP to within almost-polynomial factors is NP-hard. Combinatorica 23, 2, 205--243.
[11]
Feige, U., and Micciancio, D. 2002. The inapproximability of lattice and coding problems with preprocessing. In Computational Complexity. IEEE Computer Society Press, Los Alamitos, Calif., 44--52.
[12]
Gauss, C. F. 1801. Disquisitiones Arithmeticae. Gerh. Fleischer Iun.
[13]
Goldreich, O. 2003. A comment available online at http://www.wisdom.weizmann.ac.il/~oded/p_lp.html.
[14]
Goldreich, O., and Goldwasser, S. 2000. On the limits of nonapproximability of lattice problems. J. Comput. System Sci. 60, 3, 540--563.
[15]
Goldreich, O., Micciancio, D., Safra, S., and Seifert, J.-P. 1999. Approximating shortest lattice vectors is not harder than approximating closest lattice vectors. Inform. Process. Lett. 71, 2, 55--61.
[16]
HÅstad, J., Just, B., Lagarias, J. C., and Schnorr, C.-P. 1989. Polynomial time algorithms for finding integer relations among real numbers. SIAM J. Comput. 18, 5, 859--881.
[17]
Hoeffding, W. 1963. Probability inequalities for sums of bounded random variables. J. Amer. Stat. Assoc. 58, 13--30.
[18]
Kannan, R. 1983. Improved algorithms for integer programming and related lattice problems. In Proceedings of the 15th ACM Symposium on Theory of Computing (STOC). ACM, New York, 193--206.
[19]
Kerenidis, I., and de Wolf, R. 2003. Exponential lower bound for 2-query locally decodable codes via a quantum argument. In Proceedings of the 35th ACM Symposium on Theory of Computing (STOC). ACM, New York, 106--115.
[20]
Khot, S. 2004. Hardness of approximating the shortest vector problem in lattices. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, Calif., 126--135.
[21]
Kushilevitz, E., and Mansour, Y. 1993. Learning decision trees using the fourier spectrum. SIAM J. Comput. 22, 6, 1331--1348.
[22]
Lagarias, J. C., Lenstra, Jr., H. W., and Schnorr, C.-P. 1990. Korkin--Zolotarev bases and successive minima of a lattice and its reciprocal lattice. Combinatorica 10, 4, 333--348.
[23]
Lenstra, A. K., Lenstra, H. W., and Lovász, L. 1982. Factoring polynomials with rational coefficients. Math. Ann. 261, 515--534.
[24]
Micciancio, D. 2001. The shortest vector problem is NP-hard to approximate to within some constant. SIAM J. Comput. 30, 6 (Mar.), 2008--2035. (Preliminary version in FOCS 1998.)
[25]
Micciancio, D., and Goldwasser, S. 2002. Complexity of Lattice Problems: A cryptographic perspective. The Kluwer International Series in Engineering and Computer Science, vol. 671. Kluwer Academic Publishers, Boston, Mass.
[26]
Regev, O. 2003. Improved inapproximability of lattice and coding problems with preprocessing. In Proceedings of the of 18th IEEE Annual Conference on Computational Complexity (CCC). IEEE Computer Society Press, Los Alamitos, Calif., 363--370.
[27]
Schnorr, C.-P. 1987. A hierarchy of polynomial time lattice basis reduction algorithms. Theoret. Comput. Sci. 53, 2-3, 201--224.
[28]
Schnorr, C.-P. 1991. Factoring integers and computing discrete logarithms via diophantine approximation. In Proceedings of the of Eurocrypt '91. Vol. 547. Springer-Verlag, New York, 171--181.
[29]
Stein, E. M., and Weiss, G. 1971. Introduction to Fourier analysis on Euclidean spaces. Princeton University Press, Princeton, N.J. (Princeton Mathematical Series, No. 32.)
[30]
van Emde Boas, P. 1981. Another NP-complete problem and the complexity of computing short vectors in a lattice. Tech. rep., University of Amsterdam, Department of Mathematics, Netherlands. Technical Report 8104.
[31]
Štefankovič, D. 2002. Fourier transforms in computer science. Master's Thesis, University of Chicago, Department of Computer Science, TR-2002-03.

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)Planted Clique Conjectures Are EquivalentProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649751(358-366)Online publication date: 10-Jun-2024
  • Show More Cited By

Index Terms

  1. Lattice problems in NP ∩ coNP

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image Journal of the ACM
    Journal of the ACM  Volume 52, Issue 5
    September 2005
    120 pages
    ISSN:0004-5411
    EISSN:1557-735X
    DOI:10.1145/1089023
    Issue’s Table of Contents

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 01 September 2005
    Published in JACM Volume 52, Issue 5

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. Algorithms
    2. Fourier series
    3. approximation
    4. lattices

    Qualifiers

    • Article

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)82
    • Downloads (Last 6 weeks)9
    Reflects downloads up to 28 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)Planted Clique Conjectures Are EquivalentProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649751(358-366)Online publication date: 10-Jun-2024
    • (2024)Hardness of Range Avoidance and Remote Point for Restricted Circuits via CryptographyProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649602(620-629)Online publication date: 10-Jun-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
    • (2024)Probabilistic Searching for MIMO Detection Based on Lattice Gaussian DistributionIEEE Transactions on Communications10.1109/TCOMM.2023.327873272:1(85-100)Online publication date: Jan-2024
    • (2024)Adaptive Secure Homomorphic Encryption Scheme2024 IEEE 2nd International Conference on Control, Electronics and Computer Technology (ICCECT)10.1109/ICCECT60629.2024.10546172(1-5)Online publication date: 26-Apr-2024
    • (2024)Provable Dual Attacks on Learning with ErrorsAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58754-2_10(256-285)Online publication date: 26-May-2024
    • (2023)The Complexity of the Shortest Vector ProblemACM SIGACT News10.1145/3586165.358617254:1(37-61)Online publication date: 1-Mar-2023
    • (2023)Lattice Problems beyond Polynomial TimeProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585227(1516-1526)Online publication date: 2-Jun-2023
    • Show More Cited By

    View Options

    Login options

    Full Access

    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