Welcome to the resource topic for 2018/393
Title:
AN ATTACK ON THE WALNUT DIGITAL SIGNATURE ALGORITHM
Authors: Matvei Kotov, Anton Menshov, Alexander Ushakov
Abstract:In this paper, we analyze security properties of the WalnutDSA, a digital signature algorithm recently proposed by I. Anshel, D. Atkins, D. Goldfeld, and P. Gunnels,that has been accepted by the National Institute of Standards and Technology for evaluation as a standard for quantum-resistant public-key cryptography. At the core of the algorithm is an action, named E-multiplication, of a braid group on some finite set. The protocol assigns a pair of braids to the signer as a private key. A signature of a message m is a specially constructed braid that is obtained as a product of private keys, the hash value of m encoded as a braid, and three specially designed cloaking elements. We present a heuristic algorithm that allows a passive eavesdropper to recover a substitute for the signer’s private key by removing cloaking elements and then solving a system of conjugacy equations in braids. Our attack has 100\% success rate on randomly generated instances of the protocol. It works with braids only and its success rate is not affected by a choice of the base finite field. In particular, it has the same 100\% success rate for recently suggested parameters values (including a new way to generate cloaking elements, see NIST PQC forum Redirecting to Google Groups). Implementation of our attack in C++, as well as our implementation of the WalnutDSA protocol, is available on GitHub (GitHub - stevens-crag/crag: The repostiroty containing the source code of http://www.stevens.edu/algebraic/downloads.php).
ePrint: https://eprint.iacr.org/2018/393
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .