Zum Inhalt springen
Technische Universität München

FuLeeca: A Lee-based Signature Scheme

Official Statement

The FuLeeca team acknowledges the attack on the PQC forum posted on July 21, 2023 by Felicitas Hörmann and Wessel van Woerden. We want to point out that the attack does not break all Lee-based systems, but is specific to our scheme. Specifically, it exploits the choice of the information vector x, used to obtain the signature v=xG. As this vector is chosen to have small entries, an attacker can simply consider the integer lattice L(G). Additionally, having chosen G=(A | B) to be a quasi-cyclic code, this allows an attacker to work in the circulant lattice L(A).

We have considered simple countermeasures, which unfortunately lead to vulnerabilities with respect to forgery attacks and to impractical public key sizes. We thus, do advise against the use of FuLeeca in its current form. Since there is no simple countermeasure that fixes the above issues, we believe that the scheme needs more research before we are able to deem it secure. Nevertheless, we hope that FuLeeca was able to show the potential of Lee-based cryptography and are open to collaborations with anyone interested in working on fixing the scheme or on Lee-based cryptography in general.

For more details, refer to our presentation at the 2nd Oxford Post-Quantum Cryptography Summit 2023.

Submission

We propose a code-based signature scheme in the Lee metric.
The main features of the submission are:

  • Alternative Metric: The already standardized signature schemes are either based on structured lattices or on hash functions. While classical code-based cryptography considers vector spaces endowed with the Hamming metric, other metrics have attracted attention in the context of cryptography, e.g., the rank metric. This work marks the first Lee-metric-based cryptographic primitive.
  • Small Signatures: FuLeeca achieves small communication costs, i.e., small signature size plus public key size. This is an important quantity for certificate chains. When comparing with the to be standarized schemes, the combined size of signature and public key of FuLeeca is slightly larger than the one of Falcon but smaller than the ones of Dilithium and SPHINCS+. For NIST security level I, we achieve a public key size of 1318 bytes and a signature size of 1100 bytes. The public key size is basically the same is in Dilithium (for level II), but larger than the one for the hash-based scheme SPHINCS+. However, SPHINCS+’s signature size is significantly larger than the one of FuLeeca. In fact, the signature size of FuLeeca is only 14% of the signature size of SPHINCS+ and about 50% smaller than for Dilithium.

Project Team

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

Documentation

To top