We design, implement, and deploy post-quantum secure systems.

  • The team investigates post-quantum secure computing systems and cryptosystems, examines their security vulnerabilities, advances algorithmic modifications for efficient hardware implementations, and performs cryptanalysis of these systems.

  • Post-Quantum Cryptography

  • Post-Quantum Hardware Library

  • Lattice-Based Cryptography

  • Code-Based Cryptography

  • Cryptographic Agility

  • Homomorphic Encryption Hardware

  • Zero Knowledge Proof

  • Post-Quantum Transition

  • Post-Quantum Cryptosystems Training

.

Quantum-Proof Lightweight McEliece Cryptosystem

Error correcting code-based cryptosystems have reemerged as a highly desirable coding technique. The decoding of linear codes remains NP-hard even on quantum computers. Therefore, code-based cryptosystems are still secure against these computing systems. One such codebased cryptosystem was proposed by McEliece. The classic McEliece cryptosystem uses binary Goppa code, which is known for its good code rate and error correction capability. However, its key generation and decoding procedures have a high computation complexity.

Under this research and development effort, we are investigating the design of a public-key encryption and decryption coprocessor based on a new variant of the McEliece cryptosystem.

Background

Our approach takes advantage of non-binary Orthogonal Latin Square Code to achieve much smaller computation complexity and key size. We also propose a hardware-cost efficient, fully parameterized FPGA-based implementation of the cryptosystem to perform fast encoding and decoding operations. When compared to an existing classic McEliece cryptosystem, we observe a speed up of about 3.3x.

Since its formulation by Robert McEliece in 1978, the McEliece code-based technique has so far proven to be cryptanalysis resistant (although sometimes increasing the key size is necessary to meet a desired security level). The conventional McEliece cryptosystem uses binary Goppa code, which has good code rate and error correction capability. However, compared to other binary codes, the encoding and decoding (error correction) of binary Goppa codes have relatively high complexity.

Capabilities

This is because they involve intensive computations over finite fields, including modulo polynomial operations. Moreover, the key size of McEliece systems is usually large. For a binary Goppa code with a k × n generating matrix, the key size is kn with k, n in thousands of bits. Therefore, to address these issues, we propose the design of a new variant of the McEliece cryptosystem and its encryption-decryption co-processor. The proposed system is based on the generalized non-binary Orthogonal Latin Square Code (OLSC), which is known for its simple encoding and decoding algorithms, leading to an efficient hardware implementation. In addition, the nonbinary OLSC is able to work with non-binary messages through binary matrices. Hence, a long message can be processed using relatively small matrices, reducing the key size significantly.

Major contributions of this work are two-fold:
  • Design: McEliece cryptosystem encryption-decryption coprocessor design based on non-binary Orthogonal Latin Square Code.
  • Implementation: A fully optimized and parameterized FPGA-based implementation of the proposed co-processor design to perform fast operations.
To the best of our knowledge, this work is the first proposal of McEliece cryptosystem based on Orthogonal Latin Square Codes, and so is its hardware implementation. We should also note that we are still performing the cryptanalysis of the scheme to ensure of its security level.

Orthogonal Latin Square Code (OLSC)

Orthogonal latin square (OLS) based code, introduced by Hsiao et al., is a new class of multiple error correcting code. The codes are obtained from a set of mutually orthogonal Latin squares by systematically adding high redundancy to the decoding matrix. High speed and simple decoding is achieved through this additional redundancy.

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.

algorithm

OLSC Cryptosystem Hardware Design

The main advantage of the proposed design scheme is its hardware implementation. Encoding and decoding, for Goppa codes, involve long polynomial division and solving equations over finite fields, which can be expensive to implement in hardware.
For orthogonal Latin square codes, we just need to perform the binary matrix and vector operations, which leads to an inexpensive hardware implementation. Furthermore, we precompute and store the non-singular matrix S and its inverse, the permutation matrix P and its inverse, and the encoding matrix G which reduces the hardware cost significantly. We would like to highlight, though, that if a different key needs to be generated, then all these matrices will have to be regenerated as well. The amount of memory required to store the matrices will depend on the chosen parameters for the cryptosystem.

architecture

Main Hardware Modules

The basic operations in our algorithm are matrix-vector multiplication, matrix multiplication, vector addition, and error correction.

Matrix-vector Multiplication

The matrix-vector multiplication is the most frequently used submodule as it is required in both the encryption and decryption modules. However, matrix-vector multiplication will be required in two variants i.e. binary and non-binary versions. The encryption module requires only the binary version, whereas the decryption module requires both versions. The elements of the matrix are accessed in column-major order and the message vector is treated as a row. So we have access to all the elements of a column from a matrix at once and also all the elements of the vector.

Next, we perform element-wise multiplication using the AND operation, and the summation of the multiplication is performed using unary XOR operation on the result of the multiplication. This is possible because both the matrix and the vector are binary and the resultant vector elements are required to be binary. Thus, we reduce the hardware cost significantly by performing multiplication and addition operations without using any multipliers and adders.

Vector Addition

Vector addition is only required to perfom the encryption operation. Its function is to add a random error vector to the encoded message for further obfuscation. The codeword and error vector are both binary and we further lower the hardware cost by performing additions without using adders. We leverage XOR to implement the required bit-wise vector addition operation.

operations

Error Correction

error

We leverage the conditional operator, MUX, to perform error correction through one-step majority voting. 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

For evaluating the performance of the proposed McEliece cryptosystem, we implemented our design in Verilog and carried out synthesis using Xilinx Vivado design suite on a Xilinx FPGA board.

evaluations

evaluations2

Hardware Downloads

A zip file of the source code for this project is available for download by clicking on the download sign on the right. First, we would like to thank our sponsors who have generously supported these efforts for multiple years now. Second, many thanks to the STAM Center researchers and students, both present and former, who have contributed to the code base. These are open-source projects provided under the MIT License. 
One can also access the project code through the github directory by clicking on the github icon.

Authors

Image

PQC Secure is developed and maintained as a collaborative effort between the members of the Secure Micro Technologies crypto team and members of the Secure, Trusted, and Assured Microelectronics (STAM) Center in the Ira A. Fulton Schools of Engineering at Arizona State University.

Navigations

Copyright ©2025. All Rights Reserved — Secure Micro Technologies