×

Local testing of lattices. (English) Zbl 1422.11147

Summary: 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 \(1\)-sided nonadaptive canonical tests. This result is akin to, and based on, an analogous result for error-correcting codes due to E. Ben-Sasson et al. [SIAM J. Comput. 35, No. 1, 1–21 (2005; Zbl 1086.68045)]. 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 to 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 the well-known 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.

MSC:

11H31 Lattice packing and covering (number-theoretic aspects)
94B05 Linear codes (general theory)

Citations:

Zbl 1086.68045
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn, and D. Ron, {\it Testing Reed-Muller codes}, IEEE Trans. Inform. Theory, 51 (2005), pp. 4032-4039, . · Zbl 1247.94057
[2] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, {\it Proof verification and the hardness of approximation problems}, J. ACM, 45 (1998), pp. 501-555, . · Zbl 1065.68570
[3] S. Arora and S. Safra, {\it Probabilistic checking of proofs: A new characterization of NP}, J. ACM, 45 (1998), pp. 70-122, . · Zbl 0903.68076
[4] E. Ben-Sasson, P. Harsha, and S. Raskhodnikova, {\it Some \(3\) CNF properties are hard to test}, SIAM J. Comput., 35 (2005), pp. 1-21, . · Zbl 1086.68045
[5] P. Berman, S. Raskhodnikova, and G. Yaroslavtsev, {\it \(L_p\)-testing}, in Proceedings of the 46th ACM Symposium on Theory of Computing, STOC 2014, ACM, New York, 2014, pp. 164-173, . · Zbl 1315.68278
[6] A. Bhattacharyya, S. Kopparty, G. Schoenebeck, M. Sudan, and D. Zuckerman, {\it Optimal testing of Reed-Muller codes}, in Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, Las Vegas, NV, 2010, pp. 488-497, . · Zbl 1310.68227
[7] M. Blum, M. Luby, and R. Rubinfeld, {\it Self-testing/correcting with applications to numerical problems}, J. Comput. System Sci., 47 (1993), pp. 549-595. · Zbl 0795.68131
[8] J. Conway and N. Sloane, {\it Sphere Packings, Lattices and Groups}, 3rd ed., Grundlehren Math. Wiss. 290, Springer, New York, 1999, . · Zbl 0915.52003
[9] F. Eisenbrand, {\it Fast integer programming in fixed dimension}, in Proceedings of the 11th Annual European Symposium on Algorithms, ESA 2003, Budapest, Hungary, 2003, pp. 196-207, . · Zbl 1266.90130
[10] U. Erez, S. Litsyn, and R. Zamir, {\it Lattices which are good for (almost) everything}, IEEE Trans. Inform. Theory, 51 (2005), pp. 3401-3416. · Zbl 1293.94040
[11] G. D. Forney, {\it Coset codes. I. Introduction and geometrical classification}, IEEE Trans. Inform. Theory, 34 (1988), pp. 1123-1151, . · Zbl 0665.94018
[12] K. Friedl and M. Sudan, {\it Some improvements to low-degree tests}, in Proceedings of the 3rd Annual Israel Symposium on Theory and Computing Systems, 1995.
[13] P. Gaborit and G. Zémor, {\it On the construction of dense lattices with a given automorphisms group}, Ann. Inst. Fourier (Grenoble), 57 (2007), pp. 1051-1062. · Zbl 1172.11021
[14] O. Goldreich, {\it Short locally testable codes and proofs: A survey in two parts}, in Property Testing: Current Research and Surveys, Springer, Berlin, 2010, pp. 65-104, . · Zbl 1309.68218
[15] V. Guruswami and A. Rudra, {\it Tolerant locally testable codes}, in Proceedings of RANDOM/APPROX 2005, Springer, Berlin, 2005, pp. 306-317, . · Zbl 1105.68347
[16] R. Kannan, {\it Minkowski’s convex body theorem and integer programming}, Math. Oper. Res., 12 (1987), pp. 415-440, . · Zbl 0639.90069
[17] R. M. Karp, {\it Reducibility among combinatorial problems}, in Proceedings of a Symposium on the Complexity of Computer Computations, 1972, pp. 85-103, . · Zbl 1467.68065
[18] T. Kaufman and M. Sudan, {\it Algebraic property testing: The role of invariance}, in Proceedings of the 40th ACM Symposium on Theory of Computing, STOC 2008, ACM, New York, 2008, pp. 403-412. · Zbl 1231.68290
[19] S. Kopparty and S. Saraf, {\it Tolerant linearity testing and locally testable codes}, in Proceedings of RANDOM, Springer, Berlin, 2009, pp. 601-614. · Zbl 1255.68293
[20] W. Kositwattanarerk and F. E. Oggier, {\it Connections between Construction D and related constructions of lattices}, Des. Codes Cryptogr., 73 (2014), pp. 441-455, . · Zbl 1335.94096
[21] J. Leech and N. Sloane, {\it Sphere packings and error-correcting codes}, Canad. J. Math, 23 (1971), pp. 718-745. · Zbl 0207.52205
[22] H. Lenstra Jr., {\it Integer programming with a fixed number of variables}, Math. Oper. Res., 8 (1983), pp. 538-548, . · Zbl 0524.90067
[23] R. C. Merkle and M. E. Hellman, {\it Hiding information and signatures in trapdoor knapsacks}, IEEE Trans. Inform. Theory, 24 (1978), pp. 525-530. · Zbl 1487.94132
[24] D. Micciancio, {\it Cryptographic functions from worst-case complexity assumptions}, in The LLL Algorithm: Survey and Applications, Information Security and Cryptography, Springer, Berlin, 2009, pp. 427-452. · Zbl 1191.94098
[25] D. Micciancio, {\it Lecture Notes on Lattice Algorithms and Applications. Lecture 2: The Dual Lattice}, 2012, .
[26] D. Micciancio and S. Goldwasser, {\it Complexity of Lattice Problems: A Cryptographic Perspective}, Kluwer Internat. Ser. Engrg. Comput. Sci. 671, Kluwer Academic Publishers, Boston, MA, 2002. · Zbl 1140.94010
[27] A. M. Odlyzko, {\it The rise and fall of knapsack cryptosystems}, Cryptol. Comput. Number Theory, 42 (1990), pp. 75-88. · Zbl 0733.94012
[28] M. Parnas, D. Ron, and R. Rubinfeld, {\it Tolerant property testing and distance approximation}, J. Comput. System Sci., 72 (2006), pp. 1012-1042. · Zbl 1100.68109
[29] O. Regev, {\it Lattice-based cryptography}, in Advances in Cryptology (CRYPTO 2006), Proceedings of the 26th Annual International Cryptology Conference, Santa Barbara, CA, 2006, pp. 131-141, . · Zbl 1161.94425
[30] O. Regev, {\it The learning with errors problem (invited survey)}, in Proceedings of the IEEE Conference on Computational Complexity, IEEE, Washington, DC, 2010, pp. 191-204.
[31] R. Rubinfeld and M. Sudan, {\it Robust characterizations of polynomials with applications to program testing}, SIAM J. Comput., 25 (1996), pp. 252-271, . · Zbl 0844.68062
[32] A. Shamir, {\it A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem}, in Advances in Cryptology, Springer, Berlin, 1983, pp. 279-288. · Zbl 0543.94010
[33] L. A. Wolsey and G. L. Nemhauser, {\it Integer and Combinatorial Optimization}, John Wiley & Sons, New York, 2014. · Zbl 0944.90001
[34] A. Yao, {\it Probabilistic computations: Toward a unified measure of complexity}, in Proceedings of the Annual IEEE Symposium on Foundations of Computer Science, IEEE, Washington, DC, 1977, pp. 222-227.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.