×

A new transference theorem in the geometry of numbers and new bounds for Ajtai’s connection factor. (English) Zbl 1116.11050

Summary: We prove a new transference theorem in the geometry of numbers, giving optimal bounds relating the successive minima of a lattice with the minimal length of generating vectors of its dual. It generalizes the transference theorem due to W. Banaszczyk [Math. Ann. 296, No. 4, 625–635 (1993; Zbl 0786.11035)]. We also prove a stronger bound for the special class of lattices possessing \(n^\varepsilon\)-unique shortest lattice vectors. The theorem imply consequent improvement of the Ajtai connection factors in the connection of average-case to worst-case complexity of the shortest lattice vector problem. Our proofs are non-constructive, based on discrete Fourier transform.

MSC:

11H60 Mean value and transfer theorems
11H31 Lattice packing and covering (number-theoretic aspects)

Citations:

Zbl 0786.11035
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M. Ajtai, Generating hard instances of lattice problems, in: Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, 1996. Full version available from ECCC, Electronic Colloquium on Computational Complexity TR96-007, http://www.eccc.uni-trier.de/eccc/; M. Ajtai, Generating hard instances of lattice problems, in: Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, 1996. Full version available from ECCC, Electronic Colloquium on Computational Complexity TR96-007, http://www.eccc.uni-trier.de/eccc/ · Zbl 0921.11071
[2] M. Ajtai, The shortest vector problem in \(L_2\) http://www.eccc.uni-trier.de/eccc/; M. Ajtai, The shortest vector problem in \(L_2\) http://www.eccc.uni-trier.de/eccc/ · Zbl 1027.68609
[3] M. Ajtai, C. Dwork, A public-key cryptosystem with worst-case/average-case equivalence, 1996, Available from ECCC, Electronic Colloquium on Computational Complexity TR96-065, http://www.eccc.uni-trier.de/eccc/; M. Ajtai, C. Dwork, A public-key cryptosystem with worst-case/average-case equivalence, 1996, Available from ECCC, Electronic Colloquium on Computational Complexity TR96-065, http://www.eccc.uni-trier.de/eccc/ · Zbl 0962.68055
[4] S. Arora, L. Babai, J. Stern, Z. Sweedyk, The hardness of approximate optima in lattices, codes, and systems of linear equations, in: Proceedings of the 34th IEEE Symposium on Foundations of Computer Science (FOCS), 1993, pp. 724-733.; S. Arora, L. Babai, J. Stern, Z. Sweedyk, The hardness of approximate optima in lattices, codes, and systems of linear equations, in: Proceedings of the 34th IEEE Symposium on Foundations of Computer Science (FOCS), 1993, pp. 724-733. · Zbl 0877.68067
[5] Babai, L., On Lovász’ lattice reduction and the nearest lattice point problem, Combinatorica, 6, 1-13 (1986) · Zbl 0593.68030
[6] Banaszczyk, W., New bounds in some transference theorems in the geometry of numbers, Math. Ann., 296, 625-635 (1993) · Zbl 0786.11035
[7] Banaszczyk, W., Inequalities for convex bodies and polar reciprocal lattices in \(R^n\) IIapplication of \(K\)-convexity, Discrete Comput. Geom., 16, 305-311 (1996) · Zbl 0868.52002
[8] Cai, J.-Y., A relation of primal-dual lattices and the complexity of shortest lattice vector problem, Theoret. Comput. Sci., 207, 105-116 (1998) · Zbl 0926.11047
[9] J.-Y. Cai, A. Nerurkar, An improved worst-case to average-case connection for lattice problems, in: Proceedings of the 38th IEEE Symposium on Foundations of Computer Science (FOCS), 1997, pp. 468-477.; J.-Y. Cai, A. Nerurkar, An improved worst-case to average-case connection for lattice problems, in: Proceedings of the 38th IEEE Symposium on Foundations of Computer Science (FOCS), 1997, pp. 468-477.
[10] J.-Y. Cai, A. Nerurkar, Approximating the SVP to within a factor \((1+1 dimi\); J.-Y. Cai, A. Nerurkar, Approximating the SVP to within a factor \((1+1 dimi\) · Zbl 0947.68065
[11] Cassels, J. W.S., An Introduction to the Geometry of Numbers (1959), Springer: Springer Berlin, Göttingen Heidelberg · Zbl 0086.26203
[12] I. Dinur, Approximating \(SVP_∞\); I. Dinur, Approximating \(SVP_∞\)
[13] I. Dinur, G. Kindler, R. Raz, S. Safra, Approximating CVP to within almost-polynomial factors is NP-hard, manuscript, 1999.; I. Dinur, G. Kindler, R. Raz, S. Safra, Approximating CVP to within almost-polynomial factors is NP-hard, manuscript, 1999. · Zbl 1049.68072
[14] I. Dinur, G. Kindler, S. Safra, Approximating CVP to within almost-polynomial factors is NP-hard, Available from ECCC, Electronic Colloquium on Computational Complexity TR98-048, http://www.eccc.uni-trier.de/eccc/; I. Dinur, G. Kindler, S. Safra, Approximating CVP to within almost-polynomial factors is NP-hard, Available from ECCC, Electronic Colloquium on Computational Complexity TR98-048, http://www.eccc.uni-trier.de/eccc/ · Zbl 1049.68072
[15] P. van Emde Boas, Another NP-complete partition problem and the complexity of computing short vectors in lattices, Technical Report 81-04, Mathematics Department, University of Amsterdam, 1981.; P. van Emde Boas, Another NP-complete partition problem and the complexity of computing short vectors in lattices, Technical Report 81-04, Mathematics Department, University of Amsterdam, 1981.
[16] Even, S.; Selman, A. L.; Yacobi, Y., The complexity of promise problems with applications to public-key cryptography, Inform. Control, 61, 159-173 (1984) · Zbl 0592.94012
[17] O. Goldreich, S. Goldwasser, On the limits of non-approximability of lattice problems, Electronic Colloquium on Computational Complexity TR97-031, http://www.eccc.uni-trier.de/eccc/; O. Goldreich, S. Goldwasser, On the limits of non-approximability of lattice problems, Electronic Colloquium on Computational Complexity TR97-031, http://www.eccc.uni-trier.de/eccc/ · Zbl 1011.68512
[18] O. Goldreich, S. Goldwasser, S. Halevi, Collision-free hashing from lattice problems, 1996, Available from ECCC, Electronic Colloquium on Computational Complexity TR96-042, http://www.eccc.uni-trier.de/eccc/; O. Goldreich, S. Goldwasser, S. Halevi, Collision-free hashing from lattice problems, 1996, Available from ECCC, Electronic Colloquium on Computational Complexity TR96-042, http://www.eccc.uni-trier.de/eccc/ · Zbl 1343.94055
[19] O. Goldreich, S. Goldwasser, S. Halevi, Public-key cryptosystems from lattice reduction problems, 1996, Available from ECCC, Electronic Colloquium on Computational Complexity TR96-056, http://www.eccc.uni-trier.de/eccc/; O. Goldreich, S. Goldwasser, S. Halevi, Public-key cryptosystems from lattice reduction problems, 1996, Available from ECCC, Electronic Colloquium on Computational Complexity TR96-056, http://www.eccc.uni-trier.de/eccc/ · Zbl 0889.94011
[20] Grötschel, M.; Lovász, L.; Schrijver, A., Geometric Algorithms and Combinatorial Optimization (1988), Springer: Springer Berlin · Zbl 0634.05001
[21] Gruber, P. M., Handbook of Convex Geometry (1993), Elsevier: Elsevier Amsterdam · Zbl 0777.52001
[22] Gruber, P. M.; Lekkerkerker, C. G., Geometry of Numbers (1987), North-Holland: North-Holland Amsterdam · Zbl 0611.10017
[23] Håstad, J., Dual vectors and lower bounds for the nearest lattice point problem, Combinatorica, 8, 75-81 (1988) · Zbl 0653.10026
[24] E. Hewitt, K.A. Ross, Abstract Harmonic Analysis, Vol II. Springer, Berlin, Göttingen Heidelberg, 1970.; E. Hewitt, K.A. Ross, Abstract Harmonic Analysis, Vol II. Springer, Berlin, Göttingen Heidelberg, 1970. · Zbl 0213.40103
[25] Korkin, A.; Zolotarev, G., Sur les formes quadratiques positives quaternaires, Math. Ann., 5, 581-583 (1872) · JFM 04.0081.03
[26] Lagarias, J. C., The computational complexity of simultaneous diophantine approximation problems, SIAM J. Comput., 14, 196-209 (1985) · Zbl 0563.10025
[27] Lagarias, J. C.; Lenstra, H. W.; Schnorr, C. P., Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice, Combinatorica, 10, 4, 333-348 (1990) · Zbl 0723.11029
[28] Lenstra, H. W., Integer programming with a fixed number of variables, Math. Oper. Res., 8, 538-548 (1983) · Zbl 0524.90067
[29] Lenstra, A. K.; Lenstra, H. W.; Lovász, L., Factoring polynomials with rational coefficients, Math. Ann., 261, 515-534 (1982) · Zbl 0488.12001
[30] Lovász, L., An Algorithmic Theory of Numbers, Graphs and Convexity (1986), SIAM: SIAM Philadelphia · Zbl 0606.68039
[31] Mahler, K., Ein Übertragungsprinzip für konvexe Körper, Čas. Pěstovänı́ Mat. Fys., 68, 93-102 (1939) · JFM 65.0175.02
[32] D. Micciancio, The shortest vector in a lattice is hard to approximate to within some constant, Available from ECCC, Electronic Colloquium on Computational Complexity TR98-016, http://www.eccc.uni-trier.de/eccc/; D. Micciancio, The shortest vector in a lattice is hard to approximate to within some constant, Available from ECCC, Electronic Colloquium on Computational Complexity TR98-016, http://www.eccc.uni-trier.de/eccc/ · Zbl 0980.68054
[33] Milnor, J.; Husemoller, D., Symmetric Bilinear Forms (1973), Springer: Springer Berlin, Heidelberg, New York · Zbl 0292.10016
[34] Odlyzko, A.; te Riele, H. J.J., Disproof of the Mertens conjecture, J. für die Reine und Angew. Math., 357, 138-160 (1985) · Zbl 0544.10047
[35] C.P. Schnorr, A hierarchy of polynomial time basis reduction algorithms, Theory Algor. (1985) 375-386.; C.P. Schnorr, A hierarchy of polynomial time basis reduction algorithms, Theory Algor. (1985) 375-386.
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.