Efficient methods of algebraic cryptanalysis and protection against them | Applied Discrete Mathematics. Supplement. 2019. № 12. DOI: 10.17223/2226308X/12/36

Efficient methods of algebraic cryptanalysis and protection against them

The paper contains the basic information about methods of cryptanalysis used in algebraic cryptography. Main elements of linear and non-linear decomposition attacks by the author and so-called span-method by B. Tsaban are described as well as the examples of using them. To protect existing cryptographic algorithms against the cryptanalytic attacks, some improvements of this algorithms are proposed. For this purpose, the author has introduced the concept of a marginal set and with the use of it has protected the widely known key distibution protocol AAG against the attack by the span-method.

Download file

Counter downloads: 144

Keywords

алгебраическая криптография, алгебраический криптоанализ, algebraic cryptography, algebraic cryptanalysis

Authors

Name	Organization	E-mail
Roman'kov V.A.	F.M. Dostoevsky Omsk State University	romankov48@mail.ru

Всего: 1

References

Романьков В. А. Криптографический анализ некоторых схем шифрования, использующих автоморфизмы // Прикладная дискретная математика. 2013. №3(21). С. 35-51.

Романьков В. А. Алгебраическая криптография. Омск: ОмГУ, 2013.

Myasnikov A. and Roman'kov V. A linear decomposition attack // Groups, Complexity, Cryptology. 2015. V.7. P. 81-94.

Романьков В. А., Обзор А. А. Общая алгебраическая схема распределения криптографических ключей и её криптоанализ // Прикладная дискретная математика. 2017. №37. С.52-61.

Романьков В. А., Обзор А А. Метод нелинейного разложения для анализа криптографических схем, использующих автоморфизмы групп // Прикладная дискретная математика. 2018. №41. С. 38-45.

Roman'kov V. A. Essays in Algebra and Cryptology. Algebraic Cryptanalysis. Omsk: OmSU, 2018.

Tsaban B. Polynomial-time solutions of computational problems in noncommutative-algebraic cryptography // J. Cryptology. 2015. V.28. P. 601-622.

Ben-Zvi A., KalkaA., and Tsaban B. Cryptanalysis via algebraic spans // CRYPTO 2018. LNCS. 2018. V. 10991. P. 1-20.

Cheon J. H. and Jun B. A polynomial time algorithm for the braid Diffie - Hellman Conjugacy Problem // CRYPT0-2003. LNCS. 2003. V. 2729. P. 212-225.

Tsaban B. The Conjugacy Problem: Cryptoanalytic Approaches to a Problem of Dehn. Minicourse, Dusseldorf University, Germany, July-August 2012. http://reh.math. uni-duesseldorf.de/gagta/slides/Tsabanminicourses.pdf.

Roman'kov V. A non-linear decomposition attack // Groups, Complexity, Cryptology. 2015. V. 8. P. 197-207.

Романьков В. А. Криптографический анализ модифицированной матричной модулярной криптосистемы // Вестник Омского ун-та. 2018. Т. 23. С. 44-50.

Roman'kov V. Two general schemes of algebraic cryptography // Groups, Complexity, Cryptology. 2018. V. 10. P. 83-98.

Roman'kov V. A. A Polynomial Time Algorithm for the Braid Double Shielded Public Key Cryptosystems. Bulletin of the Karaganda University. Mathematics Ser. 2016. No. 4(84). P. 110-115. arXiv math.:1412.5277v1 [math.GR], 17 Dec. 2014. 7p.

Горнова М. Н., Кукина Е. Г., Романьков В. А. Криптографический анализ протокола аутентификации Ушакова - Шпильрайна, основанного на проблеме бинарно скрученной сопряжённости // Прикладная дискретная математика. 2015. №2(28). С. 46-53.

Романьков В. А. Метод линейного разложения анализа протоколов скрытой информации на алгебраических платформах // Алгебра и логика. 2015. Т. 54. №1. С. 119-128.

Roman'kov V. A. and Menshov A. V. Cryptanalysis of Andrecut's Public Key Cryptosystem. arXiv math.: 1507.01496v1 [math.GR], 6 Jul 2015, 5p.

Andrecut M. A Matrix Public Key Cryptosystem. arXiv math.:1506.00277v1 [cs.CR], 31 May 2015. 11 p.

Gu L., Wang L., Ota K., et al. New public key cryptosystems based on non-abelian factorization problems // Security and Communication Networks. 2013. V. 6. P. 912-922.

Gu L. and Zheng S. Conjugacy systems based on nonabelian factorization problems and their applications in cryptography // J. Appl. Math. 2014. Article ID 630607. 10 p.

Hurley B. and Hurley T. Group Ring Cryptography. arXiv math.: 1104.17.24v1 [math.GR] 9 Apr 2011. 20 p.

Hurley T. Cryptographic schemes, key exchange, public key. arXiv math.: 1305.4063v1 [cs.CR] May 2013. 19 p.

Shpilrain V. and Ushakov A. A new key exchange protocol based on the decomposition problem // Algebraic Methods in Cryptography. Contemp. Math. 2006. V. 418. P. 161-167.

Stickel E. A new method for exchanging secret keys // Proc. Third Intern. Conf. ICITA 05. Contemp. Math. 2005. V. 2. P. 426-430.

Wang X., Xu C., Li G., et al. Double shielded public key cryptosystems. Cryptology ePrint Archive. Report 2014/558. Version 20140718:185200, 2014. P. 1-14. https://eprint.iacr. org/2014/558.

Myasnikov A., Shpilrain V., and Ushakov A. Group-Based Cryptography. Barselona, Basel: CRM, 2008 (Advances Courses in Math.).

Myasnikov A., Shpilrain V., and Ushakov A. Non-Commutative Cryptography and Complexity of Group-Theoretic Problems. Math. Surveys and Monographs. V. 177. Providence RI: AMS, 2011.

Ko K. H., Lee S. J., Cheon J. H., et al. New public-key cryptosystem using braid groups // CRYPTO 2000. LNCS. 2000. V. 1880. P. 166-183.

Романьков В. А. Введение в криптографию. М.: Форум, 2012.

Bigelow S. Braid groups are linear // J. Amer. Math. Soc. 2001. V. 14. P. 471-486.

Krammer D. Braid groups are linear // Ann. Math. 2002. V. 155. P. 131-156.

Mahalanobis A. The Diffie - Hellman key exchange protocol and non-abelian nilpotent groups // Israel J. Math. 2008. V. 165. P. 161-187.

Roman'kov V. A. An improved version of the AAG cryptographic protocol // Groups, Complexity, Cryptology. 2019. V. 11.

AnshelI., AnshelM., and Goldfeld D. An algebraic method for public-key cryptography // Math. Res. Lett. 1999. V. 6. P. 287-291.