Quantum-Proof Lightweight McEliece Cryptosystem
Code-based cryptographic systems have regained prominence due to their resilience against quantum attacks. The decoding of linear codes remains computationally intractable, even for quantum computers, making these systems a strong candidate for post-quantum security. One of the most notable examples is the McEliece cryptosystem, which traditionally employs binary Goppa codes known for their robust error correction and favorable code rates. However, its key generation and decoding processes are computationally intensive.
Background
Our approach leverages non-binary Orthogonal Latin Square Codes (OLSC) to significantly reduce computational complexity and key size. We propose a fully parameterized, hardware-efficient FPGA implementation capable of high-speed encoding and decoding. Compared to the classic McEliece system, our design achieves a performance improvement of approximately 3.3x.
Since its introduction by Robert McEliece in 1978, the McEliece cryptosystem has demonstrated strong resistance to cryptanalysis. While binary Goppa codes offer excellent error correction, their encoding and decoding involve complex operations over finite fields, contributing to high hardware costs.
Capabilities
The high computational demands of McEliece stem from polynomial operations over finite fields and large key sizes. For example, a binary Goppa code with a k × n generating matrix, the key size is kn with k, n in thousands of bits.
To address these challenges, we introduce a new variant of the McEliece cryptosystem based on generalized non-binary OLSC, which supports:- Simplified encoding and decoding, enabling efficient hardware implementation.
- Compact key representation, allowing long messages to be processed using smaller matrices.
Major contributions of this work are two-fold:
- Design: A novel encryption-decryption coprocessor built on non-binary Orthogonal Latin Square Codes.
- Implementation: A fully optimized, parameterizable FPGA-based architecture for high-speed cryptographic operations.
Orthogonal Latin Square Code (OLSC)
Formally, the OLSC technique is a t-error-correcting binary code with its decoding matrix H = [M|I], where M consists of 2tq orthogonal Latin squares sized q×q, and I an identity matrix. Its generating matrix is G = [I |M⊤], where ⊤ stands for transpose. Once constructed, the columns of generating matrices can be permuted to create different OLSCs with the same parameters.
OLSC Cryptosystem Hardware Design
The primary advantage of our proposed system lies in its hardware efficiency. Unlike Goppa codes, which require complex polynomial division and finite field arithmetic, OLSC-based encoding and decoding rely on simple binary matrix and vector operations.
We further optimize hardware cost by precomputing and storing:
- Non-singular matrix S and its inverse,
- Permutation matrix P and its inverse,
- Encoding matrix G.
Note: If a new key is required, all matrices must be regenerated. Memory requirements depend on the selected cryptosystem parameters.
Main Hardware Modules
Our cryptosystem relies on a set of core operations: matrix-vector multiplication, matrix multiplication, vector addition, and error correction.
- Binary version: Required for encryption.
- Binary and non-binary versions: Required for decryption./li>
The matrix is accessed in column-major order, while the message vector is treated as a row. This allows simultaneous access to all elements of a matrix column and the entire vector. Element-wise multiplication is performed using logical AND, followed by summation via XOR, eliminating the need for traditional multipliers and adders, significantly reducing hardware cost.
Used exclusively during encryption, this operation adds a random error vector to the encoded message for obfuscation. Since both vectors are binary, we implement addition using bitwise XOR, avoiding the use of adders and further optimizing hardware efficiency.
We implement error correction using a MUX-based one-step majority voting mechanism. The hardware circuit is shown below. Error correction is performed by comparing the non-binary elements in vector u to a scalar with value floor(q/2). Here, q is the prime number chosen while setting up the OLS codes for the cryptosystem. If an element in the ith position in u is greater than floor(q/2), then the corresponding ith element in the codeword is erroneous. Error-correction is performed on this element by flipping it. Likewise, if the ith element in u is less than floor(q/2) then the corresponding ith element in the codeword is correct and needs to be accepted as is. Error-correction performed this way is known as error correction through one-step majority voting.
Design Evaluations
