Symmetric-group Regularity in the Distribution of Minima of Positive Quadratic Forms Reduced By Korkin-Zolotarev

M.A. Lyalin

Abstract


Creation of cryptographic systems based on lattice theory is a promising direction of postquantum cryptography. The purpose of this work is to obtain new properties of lattices and related objects. As a result, a regularity in the distribution of the minima of positive quadratic forms, reduced by Korkin-Zolotaryov, was revealed. Their correspondence to the heights of fundamental parallelepipeds of n-dimensional lattices has been established. The obtained result is of practical importance in the construction of dense lattice packs of balls, in solving problems of the lattice theory, researching of Hermit’s constant. The result should be taken into account when creating new cryptographic systems based on lattice theory

Full Text:

PDF (Russian)

References


Bernstein D.J., Buchmann J., Dahmen E., «Introduction to post-quantum cryptography» Post-Quantum Cryptography, pp. 1-14, 2009.

Berlekamp, Elwyn R., Robert J. McEliece, Henk C. A. van Tilborg, «On the inherent intractability of certain coding problems» IEEE Transactions on Information Theory, № 24 (3), p. 384–386, 1978.

Ding, Jintai & Schmidt, Dieter, «Multivariable public-key cryptosystems» IACR Cryptology ePrint Archive, p. 350, 2004.

Micciancio D. Regev O., «Lattice-based Cryptography» Post-Quantum Cryptography, 2009.

Buchmann J., Dahmen E., Szydlo M., «Hash-based digital signature schemes» Post-quantum cryptography, pp. 35-93, 2009.

Lagrange J.L., «Recherches d'arithmetique» Nouveaux Memoires de l'Academie royal des Sciences et Belles-Lettres de Berlin, pp. 265-312, 1773.

Dirichlet L.G.P., «Verallgemeinerung eines Satzes aus der Lehre von den Kettenbruchen nebst» S. B. Preuss. Akad. Wiss., pp. 93-95, 1842.

Minkovski H., «Geometrie der Zahlen Teubner» 1896.

Вороной Г. Ф., «Собр. соч., том 2,» 1952.

Boas P. van E., «Another NP-complete problem and the complexity of computing short vectors in a lattice» Technical Report 81-04, 1981.

Lenstra A.K. Lenstra H.W. Lovász L., «Factoring polynomials with rational coefficients» № 261, pp. 515-534, 1982.

Ajtai M., «Generating Hard Instances of Lattice Problem» Proc. of 28th ACM Symp. on Theory of Comp, pp. 99-108, 1996.

Korkine A. Zolotareff G., «Sur les formes quadratiques positives quaternaires» № 5, pp. 581-583, 1872.

Korkine A. Zolotareff G., «Sur les formes quadratiques» № 6, p. 366-389, 1873.

Korkine А. Zolotareff G., «Sur les formes quadratiques positives» № 11, p. 242-292, 1877.

Золотарёв Е.И., Полное собр. соч., вып. 1, Изд-во АН, 1931.

Делоне Б.Н., Петербургская школа теории чисел, Ленинград: Изд-во АН СССР, 1947.

Ryshkov S.S. Baranovskii E.P., «Classical metthods in the theory of lattice packings» т. 34, № 4, pp. 1-68, 1979.

Конвэй Д. Слоэн Н., Упаковки шаров, решетки и группы, пер. с англ. - М., т. 1, Москва: Мир, 1990.

Bliсhfeldt H.F., The minimum values of positive quadratic formes in six, seven and eight variables, Math. Z. 39, 1934-1935, pp. 1-15.

Cohn H. and Kumar A., «The densest lattice in twenty-four dimensions» pp. 58-67, 2004.

Gabriele N. Sloane N.J.A., «Table of Densest Packings Presently Known» Available: https://www.math.rwth-aachen.de/~Gabriele.Nebe/LATTICES/density.html.


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность MoNeTec 2024

ISSN: 2307-8162