Attack on Kayawood protocol: uncloaking private keys | Sciact - Система учета научной деятельности ИМ СО РАН

Attack on Kayawood protocol: uncloaking private keys Научная публикация

Журнал

Journal of Mathematical Cryptology
ISSN: 1862-2976 , E-ISSN: 1862-2984

Вых. Данные

Год: 2021, Том: 15, Номер: 1, Страницы: 237-249 Страниц : 13 DOI: 10.1515/jmc-2019-0015

Ключевые слова

Algebraic eraser; Braid group; Cloaking problem; Colored Burau presentation; E-multiplication; Group-based cryptography; Kayawood protocol; Key agreement

Авторы

Kotov Matvei ^1,2 , Menshov Anton ^1,2 , Ushakov Alexander ¹

Организации

1	Department of Mathematical Sciences, Stevens Institute of Technology, Hoboken, 07030, NJ, United States of America
2	Sobolev Institute of Mathematics, Pevtsova 13, Omsk, 644043, Russia

Информация о финансировании (1)

Министерство науки и высшего образования РФ
Математический центр в Академгородке

075-15-2019-1613, 075-15-2022-281

We analyze security properties of a two-party key-agreement protocol recently proposed by I. Anshel, D. Atkins, D. Goldfeld, and P. Gunnels, called Kayawood protocol. At the core of the protocol is an action (called E-multiplication) of a braid group on some finite set. The protocol assigns a secret element of a braid group to each party (private key). To disguise those elements, the protocol uses a so-called cloaking method that multiplies private keys on the left and on the right by specially designed elements (stabilizers for E-multiplication). We present a heuristic algorithm that allows a passive eavesdropper to recover Alice’s private key by removing cloaking elements. Our attack has 100% success rate on randomly generated instances of the protocol for the originally proposed parameter values and for recent proposals that suggest to insert many cloaking elements at random positions of the private key. Implementation of the attack is available on GitHub

Kotov M. , Menshov A. , Ushakov A.
Attack on Kayawood protocol: uncloaking private keys
Journal of Mathematical Cryptology. 2021. V.15. N1. P.237-249. DOI: 10.1515/jmc-2019-0015 WOS Scopus OpenAlex

Поступила в редакцию:	26 апр. 2019 г.
Принята к публикации:	4 мар. 2020 г.
Опубликована в печати:	1 дек. 2020 г.

Web of science:	WOS:000594868700018
Scopus:	2-s2.0-85097662325
OpenAlex:	W3111981975

БД	Цитирований
OpenAlex	1