Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

Published in: Designs, Codes and Cryptography 1/2022

14-11-2021

An improvement of the Diffie–Hellman noncommutative protocol

Author: Vitaly Roman’kov

Published in: Designs, Codes and Cryptography | Issue 1/2022

Login to get access
share
SHARE

Abstract

The main purpose of this paper is to propose a new version of the Diffie–Hellman noncommutative key exchange protocol invented in 2000 by Ko, Lee, Cheon, Han, Kang, and Park. This new version is resistant to linear algebra attacks. It is based on a new complex algorithmic problem using the concept of a marginal set. In particular, it is resistant to attacks by the methods of Cheon and Jun and Tsaban, as well as to attacks by the methods of linear and nonlinear decompositions, developed by the author.
Literature
1.
go back to reference Anshel I., Anshel M., Goldfeld D.: An algebraic method for public-key cryptography. Math. Res. Lett. 6(3), 287–291 (1999). Anshel I., Anshel M., Goldfeld D.: An algebraic method for public-key cryptography. Math. Res. Lett. 6(3), 287–291 (1999).
2.
go back to reference Anshel I., Anshel M., Goldfeld D.: Non-abelian key agreement protocols, Discrete Appl. Math. 130 (1), 312 (2003). The 2000 Com 2MaC Workshop on Cryptography (Pohang). Anshel I., Anshel M., Goldfeld D.: Non-abelian key agreement protocols, Discrete Appl. Math. 130 (1), 312 (2003). The 2000 Com 2MaC Workshop on Cryptography (Pohang).
4.
go back to reference Ben-Zvi A., Kalka A., Tsaban B.: Cryptanalysis via algebraic span. In: Shacham H., Boldyreva A. (eds.) Advances in Cryptology—CRYPTO 2018—38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19–23, 2018, Proceedings, Part I, vol. 10991, pp. 255–274. Springer, Cham (2018). Ben-Zvi A., Kalka A., Tsaban B.: Cryptanalysis via algebraic span. In: Shacham H., Boldyreva A. (eds.) Advances in Cryptology—CRYPTO 2018—38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19–23, 2018, Proceedings, Part I, vol. 10991, pp. 255–274. Springer, Cham (2018).
6.
go back to reference Cha J., Ko K., Lee S., Han J., Cheon J.: An Efficient Implementations of Braid Groups. In: Proc. of Asiacrypt 2001, Lecture Notes in Computer Science, Vol. 2248, Springer-Verlag, pp. 144-156 (2001). Cha J., Ko K., Lee S., Han J., Cheon J.: An Efficient Implementations of Braid Groups. In: Proc. of Asiacrypt 2001, Lecture Notes in Computer Science, Vol. 2248, Springer-Verlag, pp. 144-156 (2001).
7.
go back to reference Cheon J.H., Jun B.: A polynomial time algorithm for the braid Diffie–Hellman conjugacy problem. In: Boneh D. (ed.) Advances in Cryptology—CRYPTO 2003, vol. 2729, pp. 212–25. Lecture Notes in Comp. Sci. Springer, Heidelberg (2003). CrossRef Cheon J.H., Jun B.: A polynomial time algorithm for the braid Diffie–Hellman conjugacy problem. In: Boneh D. (ed.) Advances in Cryptology—CRYPTO 2003, vol. 2729, pp. 212–25. Lecture Notes in Comp. Sci. Springer, Heidelberg (2003). CrossRef
9.
go back to reference Hall P.: Verbal and marginal subgroups, Journal f \(\ddot{\rm u}\)r die reine und angewandte Mathematik 182, 156–157 (1940). Hall P.: Verbal and marginal subgroups, Journal f \(\ddot{\rm u}\)r die reine und angewandte Mathematik 182, 156–157 (1940).
10.
go back to reference Hofheinz D., Steinwandt R.: A practical attack on some braid group based cryptography primitives. In: Proc. of PKC 2003, Lexture Notes in Computer Science, vol. 2567, Springer, pp. 187–198 (2003). Hofheinz D., Steinwandt R.: A practical attack on some braid group based cryptography primitives. In: Proc. of PKC 2003, Lexture Notes in Computer Science, vol. 2567, Springer, pp. 187–198 (2003).
12.
go back to reference Kalka A.: Non-associative Public-Key Cryptography, Algebra and Computer Science, Contemp. Math., vol. 677, pp. 85–112. Amer. Math. Soc, Providence (2016). MATH Kalka A.: Non-associative Public-Key Cryptography, Algebra and Computer Science, Contemp. Math., vol. 677, pp. 85–112. Amer. Math. Soc, Providence (2016). MATH
13.
go back to reference Kalka A., Teicher M.: Non-associative key establishment for left distributive systems. Groups Complex. Cryptol. 5(2), 169–191 (2013). MathSciNetCrossRef Kalka A., Teicher M.: Non-associative key establishment for left distributive systems. Groups Complex. Cryptol. 5(2), 169–191 (2013). MathSciNetCrossRef
14.
go back to reference Kalka A., Teicher M.: Non-associative key establishment protocols and their implementation. In: Algebra and Computer Science, Contemp. Math., vol. 677, pp. 112–128. Amer. Math. Soc, Providence (2016). Kalka A., Teicher M.: Non-associative key establishment protocols and their implementation. In: Algebra and Computer Science, Contemp. Math., vol. 677, pp. 112–128. Amer. Math. Soc, Providence (2016).
15.
go back to reference Ko K.H., Lee S.J., Cheon J.H., Han J.W., Kang J.V., Park C.: New public-key cryptosystem using braid groups. In: Bellare M. (ed.) Advances in Cryptology—CRYPTO 2000, Lecture Notes in Comp. Sci., vol. 1880, pp. 166–183. Springer, Berlin, Heidelberg (2000). CrossRef Ko K.H., Lee S.J., Cheon J.H., Han J.W., Kang J.V., Park C.: New public-key cryptosystem using braid groups. In: Bellare M. (ed.) Advances in Cryptology—CRYPTO 2000, Lecture Notes in Comp. Sci., vol. 1880, pp. 166–183. Springer, Berlin, Heidelberg (2000). CrossRef
17.
go back to reference Lee E., Park J.: Cryptanalysis of the public-key encryption based on braid groups. In: Advances in Cryptology—EUROCRYPT 2003. International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, May 4-8, 2003 Proceedings, pp. 477–490 (2003). Lee E., Park J.: Cryptanalysis of the public-key encryption based on braid groups. In: Advances in Cryptology—EUROCRYPT 2003. International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, May 4-8, 2003 Proceedings, pp. 477–490 (2003).
19.
go back to reference Myasnikov A., Roman’kov V.: A linear decomposition attack. Groups Complex. Cryptol. 7(1), 81–94 (2015). Myasnikov A., Roman’kov V.: A linear decomposition attack. Groups Complex. Cryptol. 7(1), 81–94 (2015).
20.
go back to reference Robinson D.J.S.: A Course in the Group Theory, p. 481. Springer, New York, Heidelberg, Berlin (1982). CrossRef Robinson D.J.S.: A Course in the Group Theory, p. 481. Springer, New York, Heidelberg, Berlin (1982). CrossRef
21.
go back to reference Roman’kov V.A.: Cryptanalysis of some schemes applying automorphisms (in Russian). Prikladnaya Discretnaya Matematika 3, 35–51 (2013). Roman’kov V.A.: Cryptanalysis of some schemes applying automorphisms (in Russian). Prikladnaya Discretnaya Matematika 3, 35–51 (2013).
22.
go back to reference Roman’kov V.A.: Algebraic Cryptography (in Russian), p. 136. Omsk State University, Omsk (2013). Roman’kov V.A.: Algebraic Cryptography (in Russian), p. 136. Omsk State University, Omsk (2013).
23.
go back to reference Roman’kov V.: A nonlinear decomposition attack. Groups Complex. Cryptol. 8(2), 197–207 (2016). Roman’kov V.: A nonlinear decomposition attack. Groups Complex. Cryptol. 8(2), 197–207 (2016).
24.
go back to reference Roman’kov V.A.: Essays in Algebra and Cryptology: Algebraic Cryptanalysis, p. 207. Omsk State University, Omsk (2018). Roman’kov V.A.: Essays in Algebra and Cryptology: Algebraic Cryptanalysis, p. 207. Omsk State University, Omsk (2018).
25.
go back to reference Roman’kov V.: Two general schemes of algebraic cryptography. Groups Complex. Cryptol. 10(2), 83–98 (2018). Roman’kov V.: Two general schemes of algebraic cryptography. Groups Complex. Cryptol. 10(2), 83–98 (2018).
26.
go back to reference Roman’kov V.: An improved version of the AAG cryptographic protocol. Groups Complex. Cryptol. 11(1), 35–42 (2019). Roman’kov V.: An improved version of the AAG cryptographic protocol. Groups Complex. Cryptol. 11(1), 35–42 (2019).
27.
go back to reference Tsaban B.: Polynomial-time solutions of computational problems in noncommutative-algebraic cryptography. J. Cryptol. 28(3), 601–622 (2015). MathSciNetCrossRef Tsaban B.: Polynomial-time solutions of computational problems in noncommutative-algebraic cryptography. J. Cryptol. 28(3), 601–622 (2015). MathSciNetCrossRef
Metadata
Title
An improvement of the Diffie–Hellman noncommutative protocol
Author
Vitaly Roman’kov
Publication date
14-11-2021
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 1/2022
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-021-00969-2

Other articles of this Issue 1/2022

Designs, Codes and Cryptography 1/2022 Go to the issue

Premium Partner