Paper 2019/118

Defeating the Hart, Kim, Micheli, Pascuel-Perez, Petit, Quek Attack on WalnutDSA(TM)

Iris Anshel, Derek Atkins, Dorian Goldfeld, and Paul E Gunnells

Abstract

The Walnut Digital Signature Algorithm (WalnutDSA) is a group-theoretic, public-key method that is part of the NIST Post-Quantum Cryptography standardization process. Prior to its submission to NIST, Hart et al published an attack that, when it produces a signature forgery, it is found to be orders of magnitude longer than a valid signature making it invalid due to its length. In addition to being identified as a forgery by our current method, we show that with a modest parameter-only increase we can block this attack to the desired security level without a significant impact on the performance while making WalnutDSA completely secure against this attack.