FuLeeca: A Lee-Based Signature Scheme

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

Abstract

In this work, we introduce a new code-based signature scheme, called 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 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 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 FuLeeca is only outperformed by Falcon while the other standardized schemes Dilithium and SPHINCS+ show higher communication costs than FuLeeca.

Original languageEnglish
Title of host publicationCode-Based Cryptography - 11th International Workshop, CBCrypto 2023, Revised Selected Papers
EditorsAndre Esser, Paolo Santini
PublisherSpringer Science and Business Media Deutschland GmbH
Pages56-83
Number of pages28
ISBN (Print)9783031464942
DOIs
StatePublished - 2023
Event11th International Workshop on Code-Based Cryptography, CBCrypto 2023 - Lyon, France
Duration: 22 Apr 202323 Apr 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14311 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference11th International Workshop on Code-Based Cryptography, CBCrypto 2023
Country/TerritoryFrance
CityLyon
Period22/04/2323/04/23

Keywords

  • Code-Based cryptography
  • Lee metric
  • Post-Quantum cryptography
  • Signature scheme

Fingerprint

Dive into the research topics of 'FuLeeca: A Lee-Based Signature Scheme'. Together they form a unique fingerprint.

Cite this