Quasi-cyclic Linear Error-Block Code-based Post-quantum Signature
I. Cherkaoui, S. Belabssir, J. Horgan, I. Dey · 2025
Read Quasi-cyclic Linear Error-Block Code-based Post-quantum Signature by I. Cherkaoui, S. Belabssir, J. Horgan, I. Dey (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-23405.txt.
Introduction
Cherkaoui, Belabssir, Horgan, and Dey propose a post quantum signature scheme in twenty twenty-five. Quantum computers could break many current cryptosystems with a known algorithm. Post quantum cryptography seeks schemes that stay secure in that future. Error correcting codes are one source of such schemes.
The authors use a family of linear error block codes with a quasi cyclic structure. They define this family in algebraic terms during the work. Random codes of this type can reach a known bound that balances rate and distance well. The signature builds on those strong algebraic properties. The authors present the scheme as quantum resistant and efficient. It adds a code based option to the set of candidate signature designs.
Catalog record
| CREATOR | I. Cherkaoui, S. Belabssir, J. Horgan, I. Dey |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 79 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-23405
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Quasi-cyclic Linear Error-Block Code-based Post-quantum Signature Thanks: This material is based upon work supported by Higher Education Authority (HEA), Ireland. ©2025 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. I. Cherkaoui, S. Belabssir, J. Horgan, I. Dey Abstract Shor’s quantum algorithm led to the discovery of multiple vulnerabilities in a number of cryptosystems. As a result, post-quantum cryptography attempts to provide cryptographic solutions that can face these attacks, ensuring the security of sensitive data in a future where quantum computers are assumed to exist. Error correcting codes are a source for efficiency when it comes to signatures, especially random ones described in this paper, being quantum-resistant and reaching the Gilbert-Varshamov bound, thus offering a good trade-off between rate and distance. In the light of this discussion, we introduce a signature based on a family of linear error-block codes (LEB), with strong algebraic properties: it is the family of quasi-cyclic LEB codes that we do define algebraically during this work. K eywords Cryptography \cdot Cyclic codes \cdot Quasi-cyclic codes \cdot Linear-error block codes \cdot Post-quantum signature. 1 Introduction Nowadays, much cryptography relies on error-correcting codes and lattices. In particular, digital signature algorithms attract the attention of several researchers when compared with other schemes of cryptography. This is not only due to the interesting algebraic and arithmetic properties of linear error-correcting codes, but also since Shor’s theorem [ 2 ] showed that with the advent of quantum computers, cryptosystems based on some theoretical theorems can be broken in polynomial time. This makes it very important to have proper, provably secure post-quantum signature schemes. A great number of schemes based on the theory of coding have been advanced over the years. However, a lot of them were broken, while the secure ones suffered either from huge public keys, large signatures, or slow signing algorithms. The first paper describing proposed a code-based signature scheme in the Lee metric was Fuleeca [ 6 ] with an aim to providing resistance against quantum attack while at the same time offering small key/signature sizes. Unlike conventional code-based schemes (for instance, CFS, Wave) that mention Hamming or rank metrics, Fuleeca works with the Lee metric. The Lee metric is Manhattan-like distance over integers modulo p and complicates attacks that rely on sparsity or low supports because low Lee-weight vectors may correspond to large Hamming weights. Also underpinning security claims Fuleeca made was the NP-hard decoding problem for the Lee metric [ 4 ] . It implemented the hash-and-sign paradigm, using quasi-cyclic codes. The secret key was a generator matrix with circulant blocks, while the public key was its systematic form. Signatures were codewords with a controlled Lee weight such that a large sign match with the hashed message binds signatures to messages. Fuleeca has claimed 1,318-byte public keys and 1,100-byte signatures with NIST Level I being their performance criterion, which translates to total communication costs (public key + signature) lower than those for Dilithium and SPHINCS+. Rejecting sampling, as were Falcon/Wave, was avoided in the designs, and limits were put in place by use of a heuristic concentration step to further reduce signature leakage. In doing so, the following paper [ 5 ] indicated three fatal attacks that bring down Fuleeca’s back-security claims to untenable levels. Leaked-Sublattice Attack: The signatures lie in a low-dimensional sublattice spanned by the generator matrix rather than in the full code lattice so an attacker could recover secret vectors via BKZ lattice reduction, having reconstructed the sublattice from almost 100 signatures. This reduced security for Fuleeca-I/III/V from 160/224/288 bits down to 111/155/199 bits, respectively. Worst-Case Lattice Attack (Quantum): The generator matrix having a circulant structure is mapped to an ideal lattice. Quantum algorithms [ 3 ] will recover short generators of principal ideals in polynomial time. In quantum polynomial time with only a few signatures, full key recovery is possible. The learning attack: The concentration step put a bias into signature coefficients, leaking the secret-key structure. By averaging the outer products of the signatures, the attackers constructed an approximation of the secret circulant vector and refined it with rounding. Full key recovery with 90,000-175,000 signatures (practical for NIST Level I/V). Thus, to mitigate the following issues due to heuristic defenses the choice of our proposed signature is based on LEB quasi-cyclic codes and a \pi metric allowing the use of their algebraic properties and makes the scheme viable in practice. Linear error-block codes or LEB codes for short, were introduced by Feng, Xu and Hickernell in [ 1 ] to be a generalization of classical linear codes. Feng et al. [ 1 ] have claimed that LEB codes have applications in experimental design since they yield mixed-level orthogonal arrays, and in high-dimensional numerical integration. In order to allow their application in cryptography, especially in a McEliece-like cryptosystem, Dariti et al. [ 8 ] presented a method for decoding linear error-block codes inspired from the standard array classical method. The same authors presented in [ 9 ] some solutions on the use of LEB codes in codes-based cryptosystems, namely, the McEliece-like and Niederreiter cryptosystems, and realized that these solutions keep the size of the public key unchanged while they preserve, or even enhance, security parameters of the cryptosystem. They have also proposed a generalization to the Courtois-Finiasz-Sendrier (CFS) digital signature scheme [ 9 ] , which may increase the efficiency of this scheme. In particular, the LEB codes allow the number of attempts required to find a decodable hash to be reduced. In the same work [ 9 ] , a channel model which enables LEB codes to be used in correcting errors raised from transmission over a noisy channel was designed. LEB codes have application in the field of steganography, where Dariti et al. [ 10 ] have introduced a protocol of steganography based on LEB codes. They have shown that employing convenient codes enhances the reliability of this protocol compared to other known steganography protocols. The method developed by the authors generalizes the classic idea of Crandall, and allows more data from the cover object to be exploited. They took the example of hiding information in a greyscale image. The proposed method makes it possible to use not only the least significant bits, but also the most significant bits. The likelihood of a bit being changed is related to its influence on the image quality. The LEB codes make it possible, thanks to their block structure, to manage the different types of bits at the same time. This scheme was ameliorated in [ 7 ] . In [ 11 ] , an algebraic study of cyclic LEB codes and some related results are discussed. In [ 13 ] , the authors give the existence conditions of infinite families of perfect LEB codes, and extended the notions of Hamming and simplex codes to linear error-block codes. In [ 16 ] , the tensor product of LEB codes was investigated. In [ 12 ] ,