FuLeeca: A Lee-based Signature Scheme

[Doge Protocol]

https://eprint.iacr.org/2023/377

2023-03-16

From the whitepaper:

(For NIST Security Level 1)

PubKey size = 389 bytes

Signature size = 276 bytes

The performance characteristics (sign/verify key gen time) is not clear from the paper. Would be nice if the authors can share some details on this and also if they would be submitting for the NIST additional signatures round.

Abstract:

In this work we introduce a new code-based signature scheme, called FuLeeca, based on the NP-hard problem of finding low Lee-weight codewords. The scheme follows the Hash-and Sign approach applied to quasi-cyclic codes of small Lee-weight density. Similar approaches in the Hamming metric have suffered statistical attacks, which reveal the small support of the secret basis. Using the Lee metric we are able to thwart such attacks. We use existing hardness results on the underlying problem and study adapted statistical attacks. We propose parameters for FuLeeca and compare them to the best known post-quantum signature schemes. This comparison reveals that FuLeeca is extremely competitive. For example, for NIST category I, i.e., 160 bit of classical security, we obtain an average signature size of 276 bytes and public key sizes of 389 bytes. This not only outperforms all known code-based signature schemes, but also the signature schemes Dilithium, Falcon and SPHINCS+ selected by NIST for standardization.

Authors:

Stefan Ritterhoff, Georg Maringer, Sebastian Bitzer, Violetta Weger, Patrick Karl, Thomas Schamberger, Jonas Schupp, and Antonia Wachter-Zeh Technical University of Munich, Germany TUM School of Computation, Information and Technology† {stefan.ritterhoff, georg.maringer, sebastian.bitzer, violetta.weger, patrick.karl, t.schamberger, jonas.schupp, antonia.wachter-zeh}