Cryptology ePrint Archive: Report 2018/1111
Cryptanalysis of the Wave Signature Scheme
Paulo S. L. M. Barreto and Edoardo Persichetti
Abstract: In this paper, we cryptanalyze the signature scheme Wave, which has recently appeared as a preprint.
In this paper, we cryptanalyze the signature scheme \textsc{Wave}, which has recently appeared as a preprint.
First, we show that there is a severe information leakage occurring from honestly-generated signatures.
Then, we illustrate how to exploit this leakage to retrieve an alternative private key, which enables efficiently forging signatures for arbitrary messages.
Our attack manages to break the proposed 128-bit secure \textsc{Wave} parameters in just over a minute, most of which is actually spent collecting genuine signatures.
We also explain how our attack applies to generalized versions of the scheme which could potentially be achieved using generalized admissible $(U,U+V)$ codes and larger field characteristics.
Finally, as a target for further cryptanalysis, we describe a variant of \textsc{Wave} that we call \textsc{Tsunami}, which appears to thwart our attacks while keeping the positive aspects of that scheme.
Category / Keywords: public-key cryptography / code-based cryptosystems, digital signatures, cryptanalysis
Date: received 15 Nov 2018, last revised 17 Nov 2018
Contact author: pbarreto at uw edu
Available format(s): PDF | BibTeX Citation
Version: 20181118:051049 (All versions of this report)
Short URL: ia.cr/2018/1111
[ Cryptology ePrint archive ]