Cryptology ePrint Archive: Report 2018/1142

On the (non) obfuscating power of Garside Normal Forms

Simon-Philipp Merz and Christophe Petit

Abstract: Braid groups are infinite non-abelian groups naturally arising from geometric braids that have been used in cryptography for the last two decades. In braid group cryptography public braids often contain secret braids as a factor and it is hoped that rewriting the product of braid words hides the individual factors. We provide experimental evidence that this is in general not the case and argue that under certain conditions parts of the Garside normal form of factors can be found in the Garside normal form of their product. This observation can be exploited to decompose products in braid groups of the form $ABC$ when only $B$ is known. Our decomposition algorithm yields a universal forgery attack on WalnutDSA^TM, which is one of the 20 proposed signature schemes that are being considered by NIST for standardization of quantum-resistant public-key cryptographic algorithms. Our attack on WalnutDSA^TM can universally forge signatures within seconds for both the 128-bit and 256-bit security level, given one random message-signature pair. The attack worked on 99.8% and 100% of signatures for the 128-bit and 256-bit security levels in our experiments. Furthermore, we show that the decomposition algorithm can be used to solve instances of the conjugacy search problem and decomposition search problem in braid groups. These problems are at the heart of other cryptographic schemes based on braid groups.

Category / Keywords: public-key cryptography / group based cryptography, post-quantum digital signatures, conjugacy search problem, cryptanalysis

Date: received 23 Nov 2018, last revised 23 Nov 2018

Contact author: simon-philipp merz 2018 at live rhul ac uk

Available format(s): PDF | BibTeX Citation

Version: 20181129:151205 (All versions of this report)

Short URL: ia.cr/2018/1142


[ Cryptology ePrint archive ]