FuLeeca: A Lee-Based Signature Scheme

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

TL;DR

This paper introduces FuLeeca, a novel post-quantum digital signature scheme based on the Lee metric. By leveraging the Lee metric, FuLeeca aims to overcome specific vulnerabilities found in existing code-based signature schemes, offering competitive signature and public key sizes compared to NIST-selected candidates.

What Problem Does This Paper Address?

The ongoing transition to quantum computing necessitates the development of cryptographic algorithms resistant to quantum attacks. NIST has been leading a standardization process for post-quantum cryptography, including digital signatures. While several promising schemes have emerged, there's a continuous need for a diverse set of secure and efficient options. Code-based cryptography, which relies on the hardness of problems in coding theory, is a strong candidate for post-quantum security. However, many existing code-based signature schemes, particularly those using the Hamming metric and a "Hash-and-Sign" approach, have faced cryptanalytic attacks. These attacks often exploit the structure of the secret key, such as a small support (few non-zero entries). The paper aims to address this by proposing a new code-based signature scheme that uses the Lee metric, which is less susceptible to these specific types of attacks.

Methods

FuLeeca is a "Hash-and-Sign" signature scheme built upon quasi-cyclic codes in the Lee metric. The core idea is to use the hardness of finding codewords with a specific Lee weight.

  • Lee Metric: Unlike the traditional Hamming metric (counting non-zero entries), the Lee metric considers the "distance" of an element to zero within a finite field modulo $p$. This metric is less sensitive to the sparsity of vectors, which is a key advantage for security.
  • Hash-and-Sign Approach: The scheme follows a standard paradigm where a message is hashed, and this hash is used to derive a signature.
  • Secret Key: The secret key is a quasi-cyclic generator matrix whose rows have a specific Lee weight, chosen to be close to the Gilbert-Varshamov (GV) bound. This choice aims to make the code behave like a random code, thwarting attacks that exploit structure.
  • Public Key: The public key is a systematic form of the secret generator matrix.
  • Signature Generation: The signing process involves using the secret key to find a codeword with a specific Lee weight and a certain number of "sign matches" with a target vector derived from the message hash. The "sign match" property is crucial for binding the signature to the message.
  • Concentrating Procedure: To prevent leakage of information about the secret key through published signatures, a "Concentrating procedure" is integrated into the signing algorithm. This procedure aims to ensure that signatures have a consistent Lee weight and sign match distribution, making it harder for an attacker to infer the secret key from multiple signatures.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and performance evaluation of the proposed scheme, not on training or evaluating against specific datasets.

Key Insights and Ideas

  • Lee Metric as a Security Feature: The paper's central insight is that the Lee metric, by its nature, makes it harder for attackers to exploit the sparsity of secret keys or signatures, a common vulnerability in Hamming-metric code-based schemes.
  • GV Bound for Randomness: Setting the secret generator weights close to the Lee-metric Gilbert-Varshamov (GV) bound is a strategic choice to make the underlying code behave like a random code, further hindering structural attacks.
  • Sign Matches for Message Binding: The novel use of "sign matches" in conjunction with Lee weight provides a mechanism to bind the signature to the message hash, a key requirement for digital signatures.
  • Concentrating Procedure for Leakage Mitigation: The introduction of the "Concentrating procedure" is a crucial step to address potential leakage from multiple signature uses, a common challenge for Hash-and-Sign schemes. This procedure aims to normalize signature properties, making them less revealing.

Key Results

  • Competitive Parameter Sizes: For NIST security level I, FuLeeca achieves a signature size of 1100 bytes and a public key size of 1318 bytes. This is competitive with, and in some cases better than, other NIST-selected schemes like Dilithium and SPHINCS+.
  • Performance: The paper provides runtime analysis showing that FuLeeca is efficient, with key generation, signing, and verification times comparable to other post-quantum signature schemes.
  • Security Analysis: The security is based on the hardness of the "Finding Codeword of Given Lee Weight" problem, which is related to the decoding problem and is known to be NP-hard. The paper analyzes potential attacks, including those exploiting leakage from published signatures, and argues that the Lee metric and the Concentrating procedure mitigate these.

Limitations and Future Work

  • EUF-CMA Security Proof: The authors acknowledge that providing a formal EUF-CMA (Existential Unforgeability under Chosen Message Attacks) security proof for FuLeeca is challenging for Hash-and-Sign schemes and is left as an open problem. They believe such a proof would be "immature" given the current state of affairs and the novelty of the underlying problem.
  • Potential for Further Compression: While the signature size is competitive, the paper mentions that further compression techniques could be applied.
  • Exploration of Lattice-Based Attacks: While the paper analyzes the impact of lattice-based attacks, it notes that the exact relationship between L1 (Lee) and L2 (Euclidean) norm problems in this context is not fully understood, and further research might be needed.
  • Parameter Optimization: Future work could involve further optimization of parameters to balance security and efficiency.

Summary updated

BibTeX
@article{ritterhoff2023fuleeca,
  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}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2023},
}

Loading related content...

Figure