Cryptology ePrint Archive: Report 2022/205

Fiat-Shamir signatures without aborts using Ring-and-Noise assumptions

Dipayan Das and Antoine Joux and Anand Kumar Narayanan

Abstract: Lattice and code based hard problems such as Learning With Errors (LWE) or syndrome decoding (SD) form cornerstones of post-quantum cryptography. However, signature schemes built on these assumptions remain rather complicated. Indeed, signature schemes from LWE problems are built on the Fiat-Shamir with abort paradigm with no apparent means for knowledge extraction. On the code side, signature schemes mainly stem from Stern's zero-knowledge identification scheme. However, because of its large soundness error of $2/3$, it is costly to turn into a signature scheme. The latest developments rely on complicated cut-and-choose and multiparty-in-the-head techniques. As a consequence, they apply the Fiat-Shamir transformation on protocols with at least 5 rounds, leading to additional complexity and degraded security parameters. In the present paper, we propose an alternative approach to build a simple zero-knowledge $\Sigma$-protocol with a small soundness error, based on the hardness of Ring-and-Noise assumptions, a general family of assumptions that encompasses both lattices and codes. With such a $\Sigma$-protocol at hand, signatures can directly be derived by invoking the standard Fiat-Shamir transform, without the need for aborts. The main novel tool that allows us to achieve this is the use of specifically tailored locality sensitive hash functions. We outline our schemes for general Ring-and-Noise assumptions and present them in detail for the ring of residues modulo Mersenne numbers endowed with the Hamming metric. This Mersenne setting is ideal to illustrate our schemes, since it is close in spirit to both lattice and code based assumptions.

Category / Keywords: public-key cryptography / digital signatures, identification protocols, lattice techniques, zero knowledge

Date: received 18 Feb 2022

Contact author: dipayan das at cispa de, joux at cispa de, anand narayanan at cispa de

Available format(s): PDF | BibTeX Citation

Version: 20220220:204533 (All versions of this report)

Short URL: ia.cr/2022/205


[ Cryptology ePrint archive ]