WalnutDSA™: a group theoretic digital signature algorithm

ABSTRACT

This paper presents an in depth discussion of WalnutDSA, a quantum resistant public-key digital signature method based on the one-way function E-multiplication. A key feature of WalnutDSA is that it provides very efficient means of validating digital signatures which is essential for low-powered and constrained devices. This paper presents an in-depth discussion of the construction of the digital signature algorithm, and delves deeply into the underlying mathematics that facilitates analysing the security of the scheme. When implemented using parameters that defeat all known attacks, WalnutDSA is among the fastest quantum resistant signature verification methods; it performs orders of magnitude faster than ECC, even on low-end embedded hardware. WalnutDSA delivers a 12–25× speed improvement over ECDSA on most platforms, and a 31× speed improvement on a 16-bit microcontroller, making it an ideal solution for low-resource processors found in the Internet of Things (IoT).

Keywords:

• Group theoretic cryptography
• digital signature
• e-multiplication
• braids
• internet of things
• IoT

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 For a weak hash $H_1$ and a strong hash $H_2$, which has twice the output size of $H_1$, an attacker would need to find two messages m and $m^{\mathrm{\prime }}$ that are preimages to the halves of $H_2$ of the desired forgery and then get the signer to use $H_1$ and sign both m and $m^{\mathrm{\prime }}$. For example, the attacker would need to take his or her desired forged message, hash it using SHA2-256, find two preimages with MD5, get the signer to sign those MD5 preimages, and only then can he or she compose a message that would verify with SHA2-256.

2 In practice 128-bit signatures average around $2^{11}$ generators, but different rewriting techniques could extend that. Because the braid group is infinite there are many ways to represent the same signature, however all those ways are well beyond the $2^{14}$ limit.

3 We also think this explains why the Kotov–Menshov–Ushakov attack was as successful as it was.