Paper 2023/377

FuLeeca: A Lee-based Signature Scheme

Stefan Ritterhoff, Technical University of Munich
Georg Maringer, Technical University of Munich
Sebastian Bitzer, Technical University of Munich
Violetta Weger, Technical University of Munich
Patrick Karl, Technical University of Munich
Thomas Schamberger, Technical University of Munich
Jonas Schupp, Technical University of Munich
Antonia Wachter-Zeh, Technical University of Munich
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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Post-Quantum CryptographySignature schemeCode-Based CryptographyLee metric
Contact author(s)
stefan ritterhoff @ tum de
georg maringer @ tum de
sebastian bitzer @ tum de
violetta weger @ tum de
patrick karl @ tum de
t schamberger @ tum de
jonas schupp @ tum de
antonia wachter-zeh @ tum de
History
2023-03-16: approved
2023-03-15: received
See all versions
Short URL
https://ia.cr/2023/377
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/377,
      author = {Stefan Ritterhoff and Georg Maringer and Sebastian Bitzer and Violetta Weger and Patrick Karl and Thomas Schamberger and Jonas Schupp and Antonia Wachter-Zeh},
      title = {FuLeeca: A Lee-based Signature Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2023/377},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/377}},
      url = {https://eprint.iacr.org/2023/377}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.