Cryptology ePrint Archive: Report 2018/318

Practical attacks against the Walnut digital signature scheme

Ward Beullens and Simon R. Blackburn

Abstract: Recently, NIST started the process of standardizing quantum- resistant public-key cryptographic algorithms. WalnutDSA, the subject of this paper, is one of the 20 proposed signature schemes that are being considered for standardization. Walnut relies on a one-way function called E-Multiplication, which has a rich algebraic structure. This paper shows that this structure can be exploited to launch several practical attacks against the Walnut cryptosystem. The attacks work very well in practice; it is possible to forge signatures and compute equivalent secret keys for the 128-bit and 256-bit security parameters submitted to NIST in less than a second and in less than a minute respectively.

Category / Keywords: public-key cryptography / NIST PQC, post-quantum digital signatures, cryptanalysis, group based cryptography

Date: received 3 Apr 2018, last revised 4 Apr 2018

Contact author: ward at beullens com

Available format(s): PDF | BibTeX Citation

Version: 20180404:153741 (All versions of this report)

Short URL: ia.cr/2018/318


[ Cryptology ePrint archive ]