A nonlinear decomposition method in analysis of some encryption schemes using group automorphisms

V. A. Roman'kov ; A. A. Obzor

Prikladnaâ diskretnaâ matematika, no. 3 (2018), pp. 38-45.

Résumé

This paper shows how the nonlinear decomposition method, that had been invented by the first author, works against two cryptographic schemes based on group automorphisms. In some cases we can find the secret data and break the scheme without solving the algorithmic problem on which scheme is based. More exactly, let $G$ be a group and $A$ be a finitely generated subgroup of the automorphism group $\mathrm{Aut}(G)$. Suppose, that the membership search problem for $G$ is efficiently solvable for any subgroup of the form $\langle g^A\rangle$ generated by the all images of $g$ under automorphisms of $A$, and every subgroup $\langle g^A\rangle$ is finitely generated. Then there exists an efficient algorithm to construct a finite generating set of $\langle g^A\rangle$ and the nonlinear decomposition method can be applied. In particular, if the elements $g, f=g^\alpha,h=f^\beta\in G$ are public, $\alpha,\beta\in\mathrm{Aut}(G)$, $\alpha\beta=\beta\alpha$, and $\alpha,\beta$ are private, then one can efficiently compute $h^\alpha$ without computing $\alpha$ or $\beta$. The method efficiently works for a Noetherian group with efficiently solvable membership search problem. In particular, finitely generated nilpotent (more generally, polycyclic) groups, that are frequently used in the modern algebraic cryptography, share this property.

Détail

Keywords: cryptography, key exchange, nonlinear decomposition, membership search problem.
Mots-clés : cryptanalysis

Bibliographie

[1] Roman'kov V. A., “A nonlinear decomposition attack”, Groups Complexity Cryptology, 8 (2017), 197–207 | MR

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

[3] Mahalanobis A., “A simple generalization of El-Gamal cryptosystem to non-abelian groups”, Communications in Algebra, 36 (2008), 3878–3889 | DOI | MR | Zbl

[4] Mahalanobis A., “A simple generalization of El-Gamal cryptosystem to non-abelian groups. II”, Communications in Algebra, 40 (2012), 171–186 | DOI | MR

[5] Roman'kov V. A., Introduction to Cryptography, Lecture Course, Forum Publ., Moscow, 2012, 240 pp. (in Russian)

[6] Roman'kov V. A., Algebraic Cryptography, Dostoevsky Omsk State University Publ., Omsk, 2013, 135 pp. (in Russian)

[7] Roman'kov V. A., “Cryptographic analysis of some known encryption schemes using automorphisms”, Prikladnaya Diskretnaya Matematika, 2013, no. 3(21), 35–51 (in Russian)

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

[9] Eick B., Kahrobaei D., Polycyclic groups: A new platform for cryptology?, arXiv: math/0411077[math.GR]

[10] Gryak K. J., Kahrobaei D., “The status of polycyclic group-based cryptography: A survey and open problems”, Groups Complexity Cryptology, 8 (2017), 171–186 | MR

[11] Cavallo B., Kahrobaei D., A family of polycyclic groups over which the conjugacy problem is NP-complete, 19 Mar 2014, 14 pp., arXiv: 1403.4153v2[math. GR] | MR

[12] Macdonald J., Miasnikov A., Nikolaev A., Vassileva S., Logspace and compressed-word computations in nilpotentgroups, 2015, arXiv: 1503.03888[math.GR]

[13] Macdonald J., Miasnikov A., Ovchinnikov D., Low-complexity computations for nilpotent subgroup theorem, 4 Jul. 2017, 23 pp., arXiv: 1706.01092v2[math. GR]

[14] Myasnikov A., Weiß A., “$\mathrm{TC}^0$ circuits for algorithmic problems in nilpotent groups”, 42nd Intern. Symp. MFCS, 2017, Article No. 23 | MR