Geodesic
Discrete logarithm for nilpotent groups and cryptanalysis of polylinear cryptographic system
Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 154-160.

Voir la notice de l'article provenant de la source Math-Net.Ru

We present an efficient algorithm to compute a discrete logarithm in a finite nilpotent group, or more generally, in a finitely generated nilpotent group. Special cases of a finite $p$-group ($p$ is a prime) and a finitely generated torsion free nilpotent group are considered. Then we show how the derived algorithm can be generalized to an arbitrary finite or finitely generated nilpotent group respectively. We suppose that group is presented by generating elements and defining relators or like a subgroup of a triangular matrix group over a prime finite field (in finite case) or over the ring of integers (in torsion-free case). On the base of the derived algorithm we give a cryptanalysis of some schemes of polylinear cryptography known in the literature.
Keywords: discrete logarithm, nilpotent group, polylinear system
Mots-clés : cryptanalysis. 
@article{PDMA_2019_12_a43,
     author = {V. A. Roman'kov},
     title = {Discrete logarithm for nilpotent groups and cryptanalysis of polylinear cryptographic system},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {154--160},
     publisher = {mathdoc},
     number = {12},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2019_12_a43/}
}
TY  - JOUR
AU  - V. A. Roman'kov
TI  - Discrete logarithm for nilpotent groups and cryptanalysis of polylinear cryptographic system
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2019
SP  - 154
EP  - 160
IS  - 12
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2019_12_a43/
LA  - en
ID  - PDMA_2019_12_a43
ER  - 
%0 Journal Article
%A V. A. Roman'kov
%T Discrete logarithm for nilpotent groups and cryptanalysis of polylinear cryptographic system
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2019
%P 154-160
%N 12
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2019_12_a43/
%G en
%F PDMA_2019_12_a43
V. A. Roman'kov. Discrete logarithm for nilpotent groups and cryptanalysis of polylinear cryptographic system. Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 154-160. http://geodesic.mathdoc.fr/item/PDMA_2019_12_a43/

[1] Menezes A. J., van Oorchot P. C., Vanstone S. A., Handbook of Applied Cryptography, CRC Press, N.Y., 1997 | MR | Zbl

[2] Koblitz N., A Course in Number Theory and Cryptography, Springer, N.Y., 1987 | MR | Zbl

[3] Roman'kov V. A., Introduction to Cryptography, Forum Publ., M., 2012 (in Russian)

[4] Shor P., “Polynomial-time algorithm for prime factorization and discrete logarithms on a quantum computer”, SIAM J. Comput., 1997, no. 5, 1484–1509 | DOI | MR | Zbl

[5] Grover L. K., “A fast quantum mechanical algorithm for database search”, Proc. 28th Ann. ACM Symp. on Theory of Comput., 1997, 212–219 | MR

[6] Myasnikov A., Shpilrain V., Ushakov A., Group-Based Cryptography, Advances Courses in Math., CRM, Barselona–Basel, 2008 | MR | Zbl

[7] Myasnikov A., Shpilrain V., Ushakov A., Non-commutative Cryptography and Complexity of Group-Theoretic Problems, With Appendix by Natalia Mosina, Math. Surveys and Monographs, 177, AMS, Providence, RI, 2011 | DOI | MR | Zbl

[8] Roman'kov V. A., Algebraic cryptography, OmSU Publ., Omsk, 2013 (in Russian)

[9] Myasnikov A., Roman'kov V., “A linear decomposition attack”, Groups, Complexity, Cryptology, 7 (2015), 81–94 | DOI | MR | Zbl

[10] Roman'kov V., “A non-linear decomposition attack”, Groups, Complexity, Cryptology, 8 (2015), 197–207 | MR

[11] Roman'kov V. A., Essays in Algebra and Cryptology. Algebraic Cryptanalysis, OmSU Publ., Omsk, 2018 | MR

[12] Tsaban B., “Polynomial-time solutions of computational problems in noncommutative-algebraic cryptography”, J. Cryptology, 28 (2015), 601–622 | DOI | MR | Zbl

[13] Ben-Zvi A., Kalka A., Tsaban B., “Cryptanalysis via algebraic spans”, LNCS, 10991, 2018, 1–20 | MR

[14] Kargapolov M. I., Merzlyakov Y. I., Fundamentals of the Theory of Groups, Springer Verlag, N.Y., 1979 | MR | Zbl

[15] Hall P., Nilpotent Groups, Edmonton Notes on Nilpotent Groups. Queen Mary College Math. Notes, Math. Dept., Queen Mary College, London, 1969 | MR | Zbl

[16] Lennox J. C., Robinson D. J. S., The Theory of Infinite Soluble Groups, Oxford Math. Monographs, Clarendon Press, Oxford, 2004 | MR | Zbl

[17] Roman'kov V. A., Khisamiev N. G., Nilpotent Groups, EKSTU Publ., Ust-Kamenogorsk, 2013 (in Russian)

[18] Menezes A. J., Vanstone S. A., “A note on cyclic groups, finite fields and discrete logarithm problem”, AAECC, 3 (1992), 67–74 | DOI | MR | Zbl

[19] Boneh D., Silverberg A., “Applications of multilinear forms in cryptography”, Contemporary Math., 324, 2003, 71–90 | DOI | MR | Zbl

[20] Lin H., Tessaro S., Indistinguishability Obfuscation from Trilinear Maps and Block-Wise Local PRGs, Cryptology ePrint Archive, Report 2017/250, , 2017 https://eprint.iacr.org/2017/250 | MR

[21] Huang M. A., Trilinear Maps for Cryptography, 2018, arXiv: 1803.10325

[22] Mahalanobis A., “The Diffie — Hellman key exchange protocol and non-abelian nilpotent groups”, Israel J. Math., 165 (2008), 161–187 | DOI | MR | Zbl

[23] Kahrobaei D., Tortora A., Tota M., Multilinear Cryptography Using Nilpotent Groups, 23 Feb 2019, 8 pp., arXiv: 1902.08777v1 [cs.CR]