Document Open Access Logo

Local Testing for Membership in Lattices

Authors Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, Elena Grigorescu

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2016.46.pdf
  • Filesize: 473 kB
  • 14 pages

Document Identifiers

Author Details

Karthekeyan Chandrasekaran
Mahdi Cheraghchi
Venkata Gandikota
Elena Grigorescu

Cite As Get BibTex

Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, and Elena Grigorescu. Local Testing for Membership in Lattices. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.FSTTCS.2016.46

Abstract

Testing membership in lattices is of practical relevance, with applications to integer programming, error detection in lattice-based communication and cryptography. In this work, we initiate a systematic study of local testing for membership in lattices, complementing and building upon the extensive body of work on locally testable codes. In particular, we formally define the notion of local tests for lattices and present the following:

1. We show that in order to achieve low query complexity, it is sufficient to design one-sided non-adaptive canonical tests. This result is akin to, and based on an analogous result for error-correcting codes due to Ben-Sasson et al. (SIAM J. Computing, 35(1):1-21).

2. We demonstrate upper and lower bounds on the query complexity of local testing for membership in code formula lattices. We instantiate our results for code formula lattices constructed from Reed-Muller codes to obtain nearly-matching upper and lower bounds on the query complexity of testing such lattices. 

3. We contrast lattice testing from code testing by showing lower bounds on the query complexity of testing low-dimensional lattices. This illustrates large lower bounds on the query complexity of testing membership in  knapsack lattices. On the other hand, we show that knapsack lattices with bounded coefficients have low-query testers if the inputs are promised to lie in the span of the lattice.

Subject Classification

Keywords
  • Lattices
  • Property Testing
  • Locally Testable Codes
  • Complexity Theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Dorit Aharonov and Oded Regev. Lattice problems in NP ∩ coNP. J. ACM, 52(5):749-765, 2005. Google Scholar
  2. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. J. ACM, 45(3):501-555, 1998. Google Scholar
  3. Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. J. ACM, 45(1):70-122, 1998. Google Scholar
  4. E. Ben-Sasson, P. Harsha, and S. Raskhodnikova. Some 3CNF properties are hard to test. SIAM Journal on Computing, 35(1):1-21, 2005. Earlier version in STOC'03. Google Scholar
  5. Piotr Berman, Sofya Raskhodnikova, and Grigory Yaroslavtsev. L_p-testing. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 164-173, 2014. Google Scholar
  6. Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, and David Zuckerman. Optimal testing of Reed-Muller codes. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 488-497, 2010. Google Scholar
  7. M. Blum, M. Luby, and R. Rubinfeld. Self-testing/correcting with applications to numerical problems. Journal of Computer and System Sciences, 47:549-595, 1993. Google Scholar
  8. Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, and Elena Grigorescu. Local testing for membership in lattices. arXiv preprint arXiv:1608.00180, 2016. Google Scholar
  9. J. Conway, N. J. A. Sloane, and E. Bannai. Sphere Packings, Lattices and Groups. A series of comprehensive studies in mathematics. Springer, 1999. Google Scholar
  10. Friedrich Eisenbrand. Fast integer programming in fixed dimension. In Algorithms - ESA 2003, 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003, Proceedings, pages 196-207, 2003. Google Scholar
  11. Uri Erez, Simon Litsyn, and Ram Zamir. Lattices which are good for (almost) everything. IEEE Transactions on Information Theory, 51(10):3401-3416, 2005. Google Scholar
  12. G. D. Forney. Coset codes-I: Introduction and geometrical classification. IEEE Transactions on Information Theory, 34(5):1123-1151, 1988. Google Scholar
  13. K. Friedl and M. Sudan. Some improvements to low-degree tests. In Proceedings of the 3rd Annual Israel Symposium on Theory and Computing Systems, 1995. Google Scholar
  14. Philippe Gaborit and Gilles Zémor. On the construction of dense lattices with a given automorphisms group. Annales de l'institut Fourier, 57(4):1051-1062, 2007. Google Scholar
  15. Oded Goldreich. Short locally testable codes and proofs: A survey in two parts. In Property Testing - Current Research and Surveys, pages 65-104, 2010. Google Scholar
  16. Venkatesan Guruswami and Atri Rudra. Tolerant locally testable codes. In Proceedings of RANDOM/APPROX 2005, pages 306-317, 2005. Google Scholar
  17. Ravi Kannan. Minkowski’s convex body theorem and integer programming. Math. Oper. Res., 12(3):415-440, August 1987. Google Scholar
  18. Richard M. Karp. Reducibility among combinatorial problems. In Proceedings of a symposium on the Complexity of Computer Computations, pages 85-103, 1972. Google Scholar
  19. T. Kaufman and M. Sudan. Algebraic property testing: The role of invariance. In STOC, pages 403-412, 2008. Google Scholar
  20. Swastik Kopparty and Shubhangi Saraf. Tolerant linearity testing and locally testable codes. In Proceedings of RANDOM, pages 601-614, 2009. Google Scholar
  21. Wittawat Kositwattanarerk and Frédérique E. Oggier. Connections between construction D and related constructions of lattices. Des. Codes Cryptography, 73(2):441-455, 2014. Google Scholar
  22. John Leech and N. J. A. Sloane. Sphere packings and error-correcting codes. Canad. J. Math, 23(4):718-745, 1971. Google Scholar
  23. H. W. Lenstra Jr. Integer programming with a fixed number of variables. Mathematics of Operations Research, 8(4):538-548, 1983. Google Scholar
  24. Yi-Kai Liu, Vadim Lyubashevsky, and Daniele Micciancio. On bounded distance decoding for general lattices. In Proceedings of RANDOM, pages 450-461, 2006. Google Scholar
  25. Ralph C. Merkle and Martin E. Hellman. Hiding information and signatures in trapdoor knapsacks. IEEE Transactions on Information Theory, 24(5):525-530, 1978. Google Scholar
  26. Daniele Micciancio. The LLL Algorithm: Survey and Applications, chapter Cryptographic functions from worst-case complexity assumptions, pages 427-452. Information Security and Cryptography. Springer, December 2009. Prelim. version in Proc. of LLL25, 2007. Google Scholar
  27. Daniele Micciancio. Lecture notes on lattice algorithms and applications, Winter 2012, Lecture 2, 2012. Google Scholar
  28. Daniele Micciancio and Shafi Goldwasser. Complexity of Lattice Problems: a cryptographic perspective, volume 671 of The Kluwer International Series in Engineering and Computer Science. Kluwer Academic Publishers, Boston, Massachusetts, March 2002. Google Scholar
  29. Andrew M. Odlyzko. The rise and fall of knapsack cryptosystems. Cryptology and computational number theory, 42:75-88, 1990. Google Scholar
  30. M. Parnas, D. Ron, and R. Rubinfeld. Tolerant property testing and distance approximation. Journal of Computer and System Sciences, 72(6):1012–1042, 2006. Google Scholar
  31. Oded Regev. Lattice-based cryptography. In Advances in Cryptology - CRYPTO 2006, 26th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 2006, Proceedings, pages 131-141, 2006. Google Scholar
  32. Oded Regev. The learning with errors problem (invited survey). In IEEE Conference on Computational Complexity, pages 191-204, 2010. Google Scholar
  33. R. Rubinfeld and M. Sudan. Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing, 25:252-271, 1996. Google Scholar
  34. Adi Shamir. A polynomial time algorithm for breaking the basic merkle-hellman cryptosystem. In Advances in Cryptology, pages 279-288. Springer, 1983. Google Scholar
  35. Laurence A. Wolsey and George L. Nemhauser. Integer and combinatorial optimization. John Wiley &Sons, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact