FuLeeca: A Lee-based Signature Scheme

Stefan Ritterhoff; Georg Maringer; Sebastian Bitzer; Violetta Weger; Patrick Karl; Thomas Schamberger; Jonas Schupp; Antonia Wachter-Zeh

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 \textsf{FuLeeca}, based on the NP-hard problem of finding codewords of given Lee-weight. The scheme follows the Hash-and-Sign approach applied to quasi-cyclic codes. Similar approaches in the Hamming metric have suffered statistical attacks, which revealed 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 \textsf{FuLeeca}~and compare them to an extensive list of proposed post-quantum secure signature schemes including the ones already standardized by NIST. This comparison reveals that \textsf{FuLeeca}~is competitive. For example, for NIST category I, i.e., 160 bit of classical security, we obtain an average signature size of 1100 bytes and public key sizes of 1318 bytes. Comparing the total communication cost, i.e., the sum of the signature and public key size, we see that \textsf{FuLeeca} is only outperformed by Falcon while the other standardized schemes Dilithium and SPHINCS+ show larger communication costs than \textsf{FuLeeca}.

Note: Compared to the previous version of this eprint-paper the parameters of the scheme have changed. This is because we take the conservative approach of considering lattice based attacks in comparison to the previous version. For more information see also Section 4.3.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Post-Quantum Cryptography Signature scheme Code-Based Cryptography Lee 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-06-29: revised; 2023-03-15: received; See all versions
Short URL: https://ia.cr/2023/377
License: 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}
}