AXI hardware accelerator for McEliece on FPGA embedded systems

IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING, VOL. 22, NO. 2, MARCH/APRIL 2025 1477 AXI Hardware Accelerator for McEliece on FPGA Embedded Systems Enrique Cantó-Navarro and Mariano López-García Abstract—This article presents a McEliece hardware accelerator designed to be attached to an AXI infrastructure, addressing the efficient implementation of a flexible post-quantum cryptoprocessor on FPGA-based embedded systems. The complexity of the arithmetic circuits, combined with the adaptability to different applications by configurable parameters and run-time reprogramming, presents challenging issues for integrating the accelerator into these systems. The architecture of the accelerator is based on an application-specific instruction processor, which executes a set of constant-time instructions from an internal register file and memories. The role of the embedded processor is reduced to the initial writing of the instruction memory of the accelerator, the launching of the required set of instructions and configuring the Direct Memory Access controller to retrieve and store data from external memory. The run-time programming of the accelerator provides high flexibility in applications that requires post-quantum cryptography. A set of configurable parameters permits to adapt the security level of the McEliece encryption-decryption and the area-performance tradeoff imposed by the target device. Thus, the accelerator can be implemented from low-cost to high-end FPGAs by configuring the data-width of DMA buses or the parallelism level of the Galois-Field adder-multiplier. Experimental results show the accelerator is suited for implementing efficiently the highest security parameters of the Classic McEliece, achieving a McEliece decryption speed-up from x370 to x556 and occupying a small number of resources on a low-cost FPGA. In high-end FPGAs, the accelerator can be configured using higher security parameters not achieved in previous related cryptoprocessors, providing even higher accelerations. Index Terms—Public key cryptosystem, real-time and embedded systems, reconfigurable hardware. I. INTRODUCTION ASYMMETRIC cryptography provides confidentiality on communications by distributing a public key from a partnerwhichisusedtoencryptmessagesfromotherparties,butthey can only be decrypted by the paired private key. Public key (PK) cryptography is widely used in online services that ensure confidentiality, integrity, authentication, or non-repudiation. However, algorithms for quantum computing have been proposed to Manuscript received 24 July 2023; revised 23 July 2024; accepted 13 August 2024. Date of publication 16 August 2024; date of current version 14 March 2025. This work was supported by MCIN/AEI/ 10.13039/501100011033 under Grant PID2019-107274RB-I00. (Corresponding author: Enrique CantóNavarro.) Enrique Cantó-Navarro is with the Electrics, Electronic and Automatic Department, University Rovira i Virgili, 43007 Tarragona, Spain (e-mail: enrique. [email protected]). Mariano López-García is with the Department of Electronics, Universitat Politécnica de Catalunya, 08800 Vilanova i la Geltrú, Spain (e-mail: mariano. [email protected]). Digital Object Identifier 10.1109/TDSC.2024.3445181 defeat the security of widely used PK algorithms, such as the RSA or those based on Elliptic-Curve Cryptography (ECC). Post-quantum (PQ) algorithms applied on PK cryptography are believed to be secured against quantum computers. They can be classified into five categories: code-based, lattice-based, hash-based, based on multivariate-quadratic-equation, or based on supersingular isogenies of elliptic curves. Each category has its advantages and drawbacks that are under investigation, but generally, the complexity of PQ suffers from efficiency, which has promoted the development of hardware solutions to improve the execution time. Code-based cryptography, represented by the McEliece and its variants, is well-understood and provides reasonably efficient systems that have been developed. Many implementations have been developed for the Classic McEliece (CMcE), which should not be confused with the original McEliece (McE) from 1978. Despite the name, the Classic McEliece is a NIST standard candidate for Key Encapsulation Mechanism (KEM), initially proposed in 2017 for the NIST competition. It is based on the Niederreiter algorithm, which is a syndrome-based dual variant of the McE. The CMcE replaces the Reed-Solomon (RS) as the error-correction mechanism by binary Goppa codes. Binary Goppa codes are believed to be post-quantum safe, whereas RS has been proven to be insecure. The CMcE provides an efficient KEM, mainly due to shorter keys, simpler key generation, and syndrome-based decoding, when compared with McE. Nevertheless, McE enables larger plaintext blocks (thousands of bits) than in Niederreiter or CMcE (hundreds of bits) using the same security parameters. Previous works in hardware implementations for McE are quite scarce, whereas developments on CMcE are much larger due to the promising results for the NIST competition. Moreover, most of the previously presented systems are stand-alone cryptoprocessors on FPGAs built from very specific and fixed computational blocks, limiting their adaptability to applications other than KEM. They usually assume that keys are already loaded into internal FPGA memory, enhancing the processing speed by parallel accessing to keys and data. The connectivity withan embeddedmicroprocessor andexternalmemory,permitting changes of keys and algorithms, is not considered in their architecture and experimental results. FPGAs are widely used as prototyping platforms for digital systems. After validation, designs may be ported to ASIC technology if high-volume production is justifiable. However, FPGAs offer the possibility of updating designs if weaknesses are discovered. Furthermore, partially reconfigurable FPGAs permit the mapping of different © 2024 The Authors. This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License. For more information, see https://creativecommons.org/licenses/by-nc-nd/4.0/ 1478 IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING, VOL. 22, NO. 2, MARCH/APRIL 2025 accelerators, sharing the same hardware resources in a timemultiplexed manner. The present work proposes a McE accelerator that provides interfaces to AXI buses to be integrated into an FPGA-based embedded system. The accelerator has been designed from scratch using a Hardware Description Language (HDL) to make low-level architectural decisions focused on reducing the clock cycles and hardware resources. It provides a set of instructions on binary vectors, matrices, Galois-Field F2melements, and polynomials F2m[Z]to accelerate the steps typically used in McE encryption-decryption. Internal memories are dedicated to the storing of binary vectors and polynomials that can be read or written from an AXI-Stream interface. The contributions are summarized as: 1. Hardware accelerator for McEliece that attaches to the AXI infrastructure, addressing limitations of previous works by providing run-time programmability and connectivity to external memory. It is suitable for securitysensitive applications, not restricted to KEM, such as biometric recognition. 2. Efficient use of hardware resources and significant performance improvements are achieved. It provides configurable parameters that allow the selection of the area-performance tradeoff suited to the target FPGA and security levels that overcome previous works. The next section describes the main related works. Section III describes an overview of the architecture, internal memories, cores, and instruction set of the accelerator. Section IV describes the McE encryption and decryption focusing on the programming of the accelerator. Experiments results are reported and commented on in Section V. Finally, conclusions are presented. II. PREVIOUS WORKS Most publications, the cryptoprocessor connectivity with an embedded microprocessor and external memory is not considered. Therefore, the experimental results are theoretical execution times, assuming data and keys are already loaded in the FPGA. Additionally, hardware resources used as interface with external busses are not included. Most CMcE hardware implementationsincludethekeygenerationsinceitisrequiredin KEMcryptosystems.Onthecontrary,McEhardwareimplementations are devoted to accelerating PK encryption-decryption, relying on an external system to generate keys since it is an intensive task that runs only once for each of the parties and does not benefit as much from the hardware [1]. The system presented in [2] is a Niederreiter cryptoprocessor, which provides high-rate encryption-decryption on Virtex-6 FPGA, but security parameters are limited to 80-bit (n=2048, t=27,m=11).InternalBlockRAM(BRAM)memories storethe matrices of keys by row-wise addressing, computing an entire row per clock cycle to enhance the hypothetical performance. The reported simulation results show as encryption and decryption take 200 and 14.5·103clock cycles, respectively, assuming that both the public and private keys are already stored in the internal BRAMs. However, this is an unrealistic test since keys must be able to change, and the authors recognize that there is an open problem with the interface’s ability to transfer keys into the FPGA memory at such high rates. Some works optimize the C-code of software implementation of the CMcE, such as the McBits [3],[4] and the specific ARM Cortex-M4 implementation [5]. The authors describe several alternatives toreplaceinternal algorithms andtovectorizecalculations, thereby providing efficient execution on microprocessors with SIMD instructions. The hardware CMcE implementations showed in [6],[7], [8],[9] are based on algorithms taken from the previously commentedsoftwareoptimizations.Theypresentedacryptoprocessor built from very specialized blocks targeted to accelerate the steps involved in the KEM application. The architectures are described in Verilog, and they are very efficient in execution time for CMcE, but not as much in hardware resources. For instance, the time-optimized version for the highest security level (n=8912, t=128, m=13) [8] reports 123·103LookUp Tables (LUTs), 190·103Flip-Flops (FFs), 589 BRAMs on a high-end Virtex-7, taking 1.28·106clock cycles to generate a key and 6.5·103and 26.2·103clock cycles for encryption and decryption, respectively, assuming data is not read or written to external memory. The area-optimized version reduces the number of FPGA resources to 45·103LUTs and 88·103FFs but still requires a large number of 525 BRAMs. The number of clock cycles is the same for encryption and increases to 48.8·103 for decryption. The system [9] accelerates the matrix systemizer during the key generation by processing a portion of the matrix. It is based on the systemizer of [10], but permitting the early aborting when it detects that the matrix is not systemizable. The large number of BRAMs does not allow its implementation on low-cost FPGAs, lacking the flexibility to be adaptable to other applications different than KEM since it does not provide external memory access shared with an embedded microprocessor. A hardware-software (Hw/Sw) codesign for the CMcE is presented in [11] on a Zynq-UltraScale+device, a high-end programmable system on chip. The algorithm was described by the C-based High-Level Synthesis (HLS) to get the optimal Hw/Sw partitioning based on the execution times. The HLS synthesises the hardware accelerator and AXI interfaces to the embedded microprocessor and DMA. The experimental results are reported in relative values and percentage of FPGA resources. The execution time includes the overhead of transferring keys and data between external memory and BRAMs. For the highest security level (n=8192, t=128, m=13) the acceleration for key generationreachesx55.2,x3.3forencodingandx8fordecoding. The total number of devoted FPGA resources is very large, taking about 80% (219·103) of the total available LUTs, 62% (340·103) of the FFs, 38% (958) of the DSPs, and 205% (1870) of BRAMs. Although authors recognise that fully-hardware implementations can naturally surpass the proposed system, the Hw/Sw codesign provides an end-to-end KEM implementation and it has the potential to be adapted to future changes. The CMcE cryptosystem [12] was implemented in SpinalHDL, improving the execution time and drastically reducing the hardware resources compared to the previously mentioned work for the same security parameters (n=8192, t=128, m=13). However, it does not provide interfaces with a microprocessor CANTÓ-NAVARRO AND LÓPEZ-GARCÍA: AXI HARDWARE ACCELERATOR FOR MCELIECE ON FPGA EMBEDDED SYSTEMS 1479 bus and external memory, limiting its adaptability. The experimental results report 1.2·106clock cycles for key generation, 4.5·103and 36.5·103for encryption and decryption, devoting 45.7·103LUTs, 39.6·103FFs, 183 BRAMs on a high-end Virtex UltraScale+. In general terms, HLS improves productivity by a faster development cycle by isolating the developer from low-level details and decisions. On the other hand, hardware description languages (HDL), such as VHDL or Verilog, require significant hardware design knowledge, but they can be targeted to provide higher performance on lower resources. It can be found research works that embrace HLS versus HDL or vice versa [13],[14]. The efficiency of the HDL design depends on the skill level and development effort, but it has the potential to create more efficient designs than HLS. A much smaller number of implementations have been developed for the McE encryption-decryption, and most are standalone designs. Moreover, some of them replace the Goppa codes with other codes to improve the implementation efficiency. The work [10] was the first implementation of McE on FPGA. Itiscomposedof three customcircuits:keygenerator,encryptor, and decryptor based on the Patterson algorithm. The security parameters were fixed to a low-security level (n=2048, t=50, m=11) on a high-end Virtex-5 FPGA, integrated into a PCI card on a host personal computer (PC). The encryption and decryption take 0.5 ms and 1.29 ms, respectively, including communications with the host PC, achieving x20 and x42 speedup factor at 164 MHz when compared with the software implementation. The cryptoprocessor consumes a significant amount of FPGA resources: 84% of available slices and 50% of BRAMs. Another work [15] presents a lightweight McE encryptor and decryptor on FPGA, which replaces Goppa codes with quasicyclic moderate density parity-check codes (QC-MDPC). The security level provided is limited to 80-bit, and the theoretical encryption-decryption takes 3.4 ms (73.5·103clock cycles) and 23 ms (4.27·106clock cycles), employing just 64 and 159 slices on a low-cost Spartan-6 device. The authors claim QC-MDPC provides a very efficient encryption-decryption, but further cryptanalysis for weakness should be investigated. They also recognize encoding and decoding these codes is very different from Goppa codes and cannot be fairly compared with other McE hardware systems. The McE decryptor shown in [1] is scalable from 80-bit to 256-bit security. It was developed in VHDL, and it can operate, not only with Goppa codes, but also with quasi-dyadic (QD) Goppa codes. QD-Goppa codes provide simpler calculations, but some parameters of these codes have been weakened by cryptoanalysis. The highest security level achieved for Goppa codes is 128-bit (n=3307, t=66, m=12), taking 27·103clock cycles to decrypt at the highest performance and using 16153 LUTs, 2603 FFs, and 25 BRAMs on a low-cost Spartan-3AN. The cryptoprocessor cannot encrypt and does not provide connectivity to external memory, assuming the keys are already loaded in the FPGA programming bitstream. A quite different approach is the Galois-Field (GF) instruction set extension for RISC-V processors [16], which supports specific computing instructions. The experimental results show encryption and decryption take 4.33·106and 44.2·106clock cycles, respectively, reducing by 8% and 75% the execution time for the CMcE (n=3488, t=64, m=12) running on a RISC-V at 25 MHz. Although this approach provides high flexibility to be used in several applications, not only for CMcE, its performance is far from that obtained by the previous custom cryptoprocessors. The present work proposes a McE run-time programmable accelerator that provides AXI buses for integration into embedded systems. The design was initially based on the hardwaresoftware codesign presented in [17], which uses 77357 LUTs and 41338 FFs and accelerates decryption by x21 (47.4 ms). The presented accelerator has been redesigned from scratch in VHDL, permitting better control of hardware resources and required clock cycles for computations. It provides a set of constant-time instructions to accelerate computations on Goppa codes and binary vectors and matrices. The microprocessor can write at run-time the set of instructions to accelerate encryption or decryption of the McEliece algorithm, or even other algorithms. Moreover, the accelerator provides a set of parameters that allow configuring the security level and the area-performance tradeoff suitable to the target device. The McE accelerator can be used in classical applications of PK cryptosystem, such as the encryption/decryption of messages, the exchange of session keys, and digital signatures. Moreover, PK can also be used in blockchain and biometric applications. For instance, the iris-code digital signatures based on RSA[18] or the distributed biometric authentication secured by ECC-based blockchain [19]. A few works focus on biometrics using McE cryptosystems, such as the protection of templates [20] or the non-device-centric facial authentication [21]. In the latter, the authors propose performing the matching in the encrypted domain, providing quantum resistance to the biometric templates and featuring irreversibility, unlinkability, and revocability. The high flexibility provided by the proposed McE accelerator makes it suitable for these applications. III. ARCHITECTURE The accelerator is an application-specific instruction processor. The set of instructions are related to the one of the two provided arithmetic cores: the polynomial F2m[Z]unit and the vector core, as shown in Fig. 1. The polynomial F2m[Z] arithmetic core is connected to a register file to retrieve or save polynomials. The vector core devotes an internal memory to store the resulting binary vector from a computation involving a source vector or matrix retrieved from external memory. The instructions are stored in an internal memory, which can be programmed at run-time to change the operations launched to the cores. The accelerator provides AXI-Stream interfaces to transfer data efficiently between the external RAM and the internal memories through an AXI-DMA. Finally, the Slave-AXI interface permits the control of the accelerator from a microprocessor, setting up the AXI-Stream interfaces to retrieve or store data into the internal memories, launching a computation, and retrieving the status of the cores. 1480 IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING, VOL. 22, NO. 2, MARCH/APRIL 2025 Fig. 1. Overview of the architecture. . The security parameters (nMAX,m,t) of the McEliece are configured at synthesis time and they affect the polynomial core and its registers. Indeed, the error-correction capability (t) can be any valid value, and the dimension (m) of the Galois-Field F2mcan be selected from 8 to 15. The code length (n)is programmable at run-time accomplishing n≤nMAX, where nMAX is a configurable parameter that affects the vector core and memory. Another set of parameters is used to configuring the depth of the instruction’s memory (NUM_INST) and the number of polynomial registers (NUM_REGS). It is recommended that both parameters are configured as powers of two for better use of the internal memories. The default values NUM_INST=256 and NUM_REGS=16 are enough for implementing the McE encryption and decryption. Finally, the area-performance tradeoff can be managed by selecting the appropriate values for a set of parameters. The width of the AXI-Stream interfaces (AXIS_WIDTH) is selectable to 32/64/128/256-bit. Depending on the external DDRx memories and connection with the FPGA, a higher AXIS_WIDTH improves the read/write throughput but requires higher parallelization and resources. This parameter affects the vector core since 64-bit to 256-bit width data from matrices must be aligned in several 32-bit words to perform properly in parallel. Another parameter is the parallelism factor of the Galois-Field F2madder-multiplier (GF2MULT_FACTOR), which affects the polynomial core. A. Register File for Polynomials The architecture provides a register file to read polynomial operands and write results of instructions, eliminating accesses to external DDR memory to perform a computation. Each register stores a polynomial p(Z)∈F2m[Z], which is composed of t+1coeficients in Galois-Field F2m, following the notation p(Z)=ptZt+...+p1Z+p0.Theregisterfileisasingle-port distributed memory since it can be efficiently implemented on LUTs. Fig. 2shows the architecture of the memory, which provides a single address bus to read/write one of the registers. Fig. 2. Distributed memory for the polynomial registers. TABLE I IRREDUCIBLE POLYNOMIALS IN GALOIS FIELD The degree deg(p(Z)) of a polynomial is the highest index with non-zero coefficient, and it is computed when a polynomial is read. The number of registers is configurable, and in our case, we took NUM_REGS=16 by default, devoting a single LUT to store one bit of one of the coefficients for all the registers. This way, all the registers share the same set of (t+1)·mLUTs. The registers are named from r0 to r15, permitting polynomial instructions to read operands and store the results in any of these registers. There are two special-purpose registers. The r0 is a read-only register, which allocates the zero polynomial, and it can be used by the instructions as an input operand or to avoid storing a result into the register file. The register r15 stores the irreducible polynomial g(Z)∈F2m[Z], which is used by the core when reducing a polynomial. The AXI interfaces provide have access to the polynomial registers from the microprocessor andexternalmemorytoreadresultsortochangetheprivateg(Z) at run-time. B. Polynomial Core The polynomial core is built around a paralleled F2maddermultiplier. It is composed of t+1independent combinational F2marithmetic circuits, mi(y)=op1i(y)·op2i(y)+opxi(y), 0≤y≤t. The reduction polynomial g(x)∈F2mis fixed according to Table I. The F2madder-multiplier can perform t+1 additionmultiplications at every clock cycle by attaching three inner registers (po,pq,pb), as depicted in Fig. 3. Each inner register is built of a large set of (t+1)·mflip-flops (FFs) and stores all the F2mcoefficients of a polynomial F2m[Z]. Large bit-width CANTÓ-NAVARRO AND LÓPEZ-GARCÍA: AXI HARDWARE ACCELERATOR FOR MCELIECE ON FPGA EMBEDDED SYSTEMS 1481 Fig. 3. Overview of the polynomial core.. multiplexers connect the polynomial register file, the inner registers, and adder-multiplier in several ways, depending on the running state. The registers and multiplexers are controlled by a Finite State Machine (FSM), which changes the states based on the starting mode (encoded in the instruction) and an internal counter (cnt). The start and ready ports are used for handshaking with the external circuitry. The number of inputs of the large multiplexers has been minimized since each one is composed of (t+1)·mbits. The output of the F2madder-multiplier (m) is shifted one coefficient to the left (m<<1) or to the right (m>>1) before storing it in an inner register. An inner register pcan be written from a polynomial a(Z)∈ F2m[Z], which is read from the register file in a single clock cycle, denoted as p←a(Z). The registers can be shifted one coefficient to the left or right, denoted as p<<1or p>>1 that are equivalent to a(Z)·Zor a(Z)·Z−1. Operations over polynomials can be accelerated by the paralleled F2maddermultiplier, and by 1-bit shifting on registers to avoid much more complex barrel shifters. The steps carried out on the po,pq, pb registers and the F2madder-multiplier are kept as similar as possible for the different instructions to avoid incrementing the number of inputs of multiplexers. For instance, instruction r8←r7∗r4+r12 computes a polynomial addition-multiplication from three registers, returning the result in the fourth register. Concretely, it computes r(Z)=a(Z)·b(Z)+c(Z)in four states, as depicted in Fig. 4. The instruction starts from an initial idle state by writing the three inner registers from polynomials stored in the register file. Due to the single-port register file, po ←c(Z),pq← a(Z),pb←b(Z)require three clock cycles. A fourth cycle is required to start the operation, deasserting the ready port and decoding the operation mode, which is encoded as 01CL (C=0, L=1) for the modular multiplication and addition of polynomials. Fig. 4. States of the polynomial operation r(Z)=a(Z)·b(Z)+c(Z). In the second state, the F2madder-multiplier performs po + pb ·pq(0) and the result is 1-bit shifted to the right (m>>1) before storing it into two registers. The pq is right-shifted, and the lowest coefficient of the result is appended at the left side, denoted as pq ←m(0) & (pq 1). Concurrently, the register po stores the remaining coefficients of m, appending the coefficient 0 to the left side, according to po ←0&(m1).The state is repeated t+1clock cycles to compute the not reduced result r(Z). After completing, pq stores the lowest (t+1) coefficients, and po stores the remaining highest tcoefficients at the right side. In other words, {po, pq}=r(Z), with po(t)=0. The register pb remains constant, except at the last cycle that loads the irreducible Goppa polynomial g(Z)from the register file, denoted as pb ←g(Z). The third state reduces r(Z)by performing po +pb ·po(t), adding to the register po the multiplication of its highest coefficient po(t)with g(Z).Theresultmis left-shifted before storing it into po, appending the left size coefficient stored in pq, according to po ←(m1) & pq(t). Therefore, the degree of the result is reduced when po(t)=0or the result is simply left-shifted when po(t)=0. The reduction state is repeated t+2 clock cycles, since at the first cycle po(t)=0.After completing the rest of cycles, pq =0and po stores the result r(Z)mod g(Z)=r(Z)but left-shifted as po =r(Z)<< 1. Since po =r(Z)<< 1and pq =0, the second state is executed once again to perform the right-shifting of po, finally obtaining po =r(Z)where deg(r(Z)) <t. The final state transfers the instruction result, which is stored in po, to the register file and asserts the ready port. Therefore, the total number of clock cycles devoted is 5+2·(t+2), since 2·(t+2)cycles are required for the second and third states and 5 clock cycles for the initial and final states. 1482 IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING, VOL. 22, NO. 2, MARCH/APRIL 2025 The previous addition-multiplication instruction works for any input polynomials, resulting in deg(r(Z)) <t. In the case of being a(Z)a constant polynomial, the mode changes to 011L (C=1), which slightly changes the execution of the state graph to perform faster, depending on the deg(a(Z)). Additionally, the last reduction and right-shifting can be avoided if L=0, resulting in deg(r(Z)) ≤t. For instance, assuming r1 stores the polynomial a(Z)=1, the reduction of b(Z), which is stored in r7, can be computed by the instruction r5←r1∗ r7+r0, taking 5+2·(deg(a(Z)) + 2)=9 clock cycles since deg(a(Z)) = 0 and L=1. Another example, if r12 stores c(Z), the addition b(Z)+c(Z)is stored in r5(deg(r5) ≤twhen L=0) by executing the instruction r5←r1∗r7+r12, taking 5+2·(deg(a(Z)) + 1) =7 clock cycles. A final example is the operation b(Z)·Zby the instruction r14 ←r2∗r7+r0, assuming r2stores the constant polynomial a(Z)=Z, which takes 5+2·(deg(a(Z)) + 1) = 9 clock cycles since L=0. Obviously, the described procedure for the additionmultiplication could be reduced by 2 clock cycles by disabling the shifting on mand on the registers po,pq at the last cycle of the second and third states. However, this solution increments significantly the hardware resources due to the additional input inferred on the multiplexers to attach m. Another way to reduce clock cycles is by simultaneously writing to the three inner registers using a three-port memory for the register file. Considering the parameter tis a large number, reducing a few clock cycles does not have a great impact on the overall performance, although it significantly increments the hardware resources. The traditional way to multiply and reduce at each step requires a fourth inner register storing g(Z)during all the cycles, and an additional input at one of the multiplexers. However, the execution time cannot be reduced since a single mcan be performed at every clock cycle, and therefore, this solution only provides disadvantages. The operation v=roots(c(Z),N), which is used to find the roots of the polynomial, is slightly different from others because the result is a binary vector FN 2that will be stored in the vector memory (v). The erroloc circuit depicted in Fig. 3is a simple m-bit comparator attached to a register, which connects to the AXI-Stream bus to share the same interface used to write internal memories. For instance, the instruction roots(r8,8192) computes the roots of the polynomial stored in the register r8, resulting in an 8192-bit binary vector. At the idle state, the instruction initializes the inner register po with the polynomial c(Z), and loads pq with r0to initialize all its coefficients to zero, as shown in Fig. 5. Then, the internal FSM register max is initialized to 8191 to evaluate c(Z) from Z=0to Z= 8191. Since the F2madder-multiplier is composed of independent arithmetic blocks, it can concurrently compute t+1partial evaluations of c(Z)at each clock cycle. The counter cnt is the Zthat is going to be evaluated, requiring (t+1)clock cycles to complete. As shown in the second state, by right shifting pq and writing cnt at the left side, the registerstorespq(t)=Z,pq(t−1) = Z−1,pq(t−2) = Z− 2, ..., pq(0) = Z−t. Since pb stores m>>1with pb(t)=0 at each clock cycle, the results from the F2madder-multiplier are m(t)=ct+Z·0=ct,m(t−1) = ct−1+(Z−1) ·ct, Fig. 5. States of the operation v=roots(c(Z),N). m(t−2) = ct−2+(Z−2) ·(ct−1+(Z−2) ·ct), and so on. During the first tclock cycles, the m(0) does not provide a valid value, but after this initial latency m(0) = c0+Z·(c1+ Z·(c2+···(Z·ct−1+ct)···)), which is the evaluation c(Z) by the Horner’s method. The evaluations m(0) = c(Z),from Z=0to Z=N−1are obtained in sequential order, being the throughputofone evaluation perclockcycle.Therefore, thetotal computation time, including the initial state, is 3+(t+1)+N clock cycles. The errorloc circuit compares m(0) with 0∈F2m, resulting in a single bit, which is serially stored in a shift register to interface the AXI-Stream bus that writes the vector memory. As it is shown in the previous operations, the procedures taken in the states are very similar. Moreover, all the instructions that can be performed by the polynomial core (Table II) follow a similar approach. All of them reuse the three inner registers and connections to the F2madder-multiplier through the same multiplexers, saving FPGA resources. The main difference is the states carried out by the FSM according to each instruction. The copy instruction just copies a register into another one. The division a(Z)/b(Z)returns two polynomials accomplishing q(Z)·b(Z)+r(Z)=a(Z). Similarly, the split(a(Z)) returns two polynomials composed of the even e(Z)and odd o(Z)coefficients. The GF Mult instruction is the Galois Field F2mmultiplication of the composing coefficients ri=ai· bi(0 ≤i≤t). These last two instructions can be used to compute the a(Z). Finally, the last instruction returns by the AXI interface the degree of the polynomial stored in a register. The polynomial core devotes a large number of resources to theparallel F2madder-multiplieranditsassociatedmultiplexers. The fully parallelized core does not fit in low-cost devices for the larger security parameters (m,t), but the core provides the parameter GF2MULT_FACTOR (denoted as F), which defines the parallelism factor. The number of paralleled arithmetic circuits in the F2madder-multiplier is reduced to (t+1)/F (F≥2), and the width of inputs of the multiplexers depicted in Fig. 3is reduced to m·(t+1)/F. The instructions execute the same states described before, but each cycle is divided into Fclock cycles. Each of the inner registers are divided into CANTÓ-NAVARRO AND LÓPEZ-GARCÍA: AXI HARDWARE ACCELERATOR FOR MCELIECE ON FPGA EMBEDDED SYSTEMS 1483 TABLE II POLYNOMIAL INSTRUCTION SET Fig. 6. Slices for the inner register pb for t=256 and F=3. Fslices of (t+1)/F coefficients, which are continuously rotated. Fig. 6shows the slices of the register pb for the case t= 256 and F=3. Each slice stores 86 coefficients, padding pb(j)=0when j>t. The slice-0 attaches to the op1port of the F2madder-multiplier. In the next clock cycle the result m1 is stored in the slice-2, and the contents of slices are rotated to perform with the next coefficients, maintaining the same connectivity with the F2madder-multiplier. After completing Fig. 7. Vector memory. the Fclock cycles, the inner registers store the same contents as in a single cycle of the fully parallelized core. The obvious inconvenience is the clock cycles needed by the instructions carried out by the F2madder-multiplier are incremented by the factor F. For instance, the instruction for addition-multiplication of polynomials takes 5+F·2·(t+2) clock cycles, or the instruction for finding roots takes 3+F·(t+1+n). C. Vector Memory The maximum number of bits that can be allocated in the vector memory is a configurable parameter (nMAX), which is provided at synthesis time to be implemented by using internal BRAMs. Instructions that use the vector memory provide the bit-size of operands, such as the code length (n)or the code dimension (k). The bit-size is programmable at run-time, permitting the vector core to work with different code lengths that accomplish n≤nMAX. The BRAMs are configured as a dual port memory with independent read and write ports, as depicted in Fig. 7.The width of the ports (denoted W) matches the AXI-Stream width (parameter AXIS_WIDTH) to provide faster processing with data retrieved from external DDRx RAM. The memory is arranged in 2·nMAX/WxW-bit words, providing a total capacity of 2·nMAX bits to enable doublebuffering during processing. The core automatically swaps the base address of both buffers before starting a new instruction that requires simultaneous read/write access to BRAMs. If nMAX is a power of 2, the addition to obtain the extended address is replaced with a simple bit concatenation of the buffer address with the most significant bit of the base address. D. Vector Core Table III resumes the instructions provided by the core, which is depicted in Fig. 8. All the instructions perform a computation from a binary vector vretrieved from the read buffer, writing the resulting vector vin the write buffer of the same memory. Therefore, these instructions do not specify the voperator, but they require specifying an argument N≤nMAX, which is the number of bits considered in the binary vector v∈FN 2. As in the polynomial core, the procedures carried out by the states to execute instructions are very similar, reducing hardware resources. 1484 IEEE TRANSACTIONS ON DEPENDABLE AND SECURE COMPUTING, VOL. 22, NO. 2, MARCH/APRIL 2025 TABLE III VECTOR INSTRUCTION SET Fig. 8. Architecture of the vector core (top) and the addition/multiplication (bottom-left) and bit-ordering (bottom-right) subcircuits. . For instance, the instructions for vector addition v←V+v and for matrix multiplication v←M·vare very similar, sharing the same logic to read data from external memory, 32-bit alignment with retrieved data from BRAMs, and storage of partial results. The result is temporally stored in a W-bit register (R) before writing the result word into BRAM, taking N/W clock cycles per row to perform the computation, where N is the number of bits for columns. The alignment circuit is required when the AXI-Stream is larger than 32-bit to align data retrieved from external memory with BRAM into 32-bit words. The external DMA must be properly configured to point to the base address of Vor M, and the total number of words to read from DDRx RAM. The real execution time is higher than the theoretical one since the DMA introduces wait-states between burst transactions to access data stored in shared external memory. The remaining instructions are the permutation v(i)← v(P(i)) and the transformation of Nbits from vto Goppa code r(Z)←to_goppa(v,N). Both instructions are very similar since they basically read a single bit from vat every clock cycle at different locations, serially storing the resulting bits into the temporal register R. The location index of the bit to read from vis retrieved either from a permutation vector P stored in external memory or from the counter cnt for the other instruction. The register is sequentially stored in BRAM for the first instruction, or in one of the registers of the polynomial file for the last instruction. The permutation of vby using a vector P∈FN 232 is equivalent to the expression v·P, where P∈FN×N 2is a permutation binary matrix with exactly one 1 every row and column, but it requires lower accesses to memory. The instruction to transform vto Goppa code could be executed in a single clock cycle by adding a large multiplexer at the input of the polynomial registers. However, the FPGA resources would be greatly increased, whereas the overall performance of McE decryption is very slightly improved since it is not frequently used. Notice the benefit in the execution time for the vector addition and matrix multiplication when W is larger, but neither the permutation nor the Goppa transformation. By using similar procedures in the states carried out for all the instructions, hardware resources are minimized. IV. MCELIECE The McEliece (McE) is a code-based PK encryption system. Encryption is simple, but decryption is far more complex since it involves several algorithms based on operations with binary matrices, Galois-Field F2mand polynomials F2m[Z]. The key generation, encryption, and decryption described in the CMcE differ from the McE. The CMcE is a recent NIST standard candidate for Key Encapsulation Mechanism (KEM), which can efficiently implement the key generation and decoding. It is based on a syndrome-based variant of the McE, which encodes a message on a t-weight error string ∈Fn 2, encrypting it as the syndrome c=H·e∈Fmt 2, since H∈Fmt×n 2is the parity-check matrix that is used as the public key. A. Key Generation Although the presented accelerator is not intended for key generation, we provide a brief description. A binary Goppa code is defined by a polynomial g(Z)and a set of distinct elements Lfrom a finite field, providing a high error correction capacity from a parity-check matrix H[22],[23], which is undistinguishable from random matrices. The key generation starts by computing a random irreducible Goppa polynomial g(Z)F2m[Z]. Then, the generator matrix G∈Fk×n 2is computed for a Goppa code that meets the minimum distance criterion d≥2t+1. The generator matrix is perturbated with two random invertible matrices: the non-singularity matrix S∈Fk×k 2and the permutation matrix P∈Fn×n 2. Finally, the public key Gpub ∈Fk×n 2 is obtained from the multiplication of the three matrices as Gpub =S·G·P. CANTÓ-NAVARRO AND LÓPEZ-GARCÍA: AXI HARDWARE ACCELERATOR FOR MCELIECE ON FPGA EMBEDDED SYSTEMS 1485 Algorithm 1: Pseudo-C code for Encryption. Input:(Gpub)T∈Fn×k 2,m∈Fk 2,e∈Fn 2(t−weight) Result:c∈Fn 2 inst_enc ={mult_M(k); add_V(n);} McE_LoadVector(m, k); //v ←m McE_Launch(inst_enc); DMA_Read((Gpub)T,n,k)//v ←(Gpub)T·v DMA_Read(e, 1,n)//v ←e+v McE_SaveVector(c, n); //c ←v We developed the key generation as in the Flexiprovider library, which uses an auxiliary vector P1∈Fn 232 to permute the columns of the parity-check matrix H, helping the systematization of G. The transposed parity-check matrix HT∈Fn×mt 2is stored as part of the private key along with the transposed inverse matrix (S−1)T, the permutation vectors P−1,(P1·P)−1, and the irreducible Goppa polynomial g(Z). At the starting time, the embedded microprocessor writes all the instructions that are going to be carried out by the accelerator for encryption and decryption. It also initializes the polynomial registers r1=1 F2m[Z],r2=ZF2m[Z], r15 = g(Z)F2m[Z], and r14 = √ZF2m[Z]. B. Encryption The encryption transforms a plain text m∈Fk 2and a randomly generated t-weight error e∈Fn 2to a ciphertext c∈Fn 2 by using the public key matrix Gpub ∈Fk×n 2, according to: c=m·Gpub +e=GpubT·m+e(1) The instruction memory of the accelerator contains two instructions to perform the encryption, pointed by inst_enc (Algorithm 1). After loading the internal memory vwith m,the microprocessor can launch the encryption on the accelerator. Then, the microprocessor configures the DMA to the addresses that store (Gpub)Tand e, and sets the number of rows and columns to start the reading of data from external memory. After completing the encryption, vstores the cyphertext cand writes it to external memory. C. Decryption After receiving the ciphertext c∈Fn 2, a set of steps are carried out to get the located errors εand recover the plain text m.The steps followed are: 1. c=c·(P1·P)−1 2. ε=Decode(c) 3. y=c+ε 4. y=truncate(y·P1−1,k) 5. m=y·S−1=(S−1)T·y Since (P1·P)−1=P−1·P−1 1, the first step removes the permutation Pfrom the ciphertext. Notice the resulting vector c∈Fn 2is not only required in the next step but also after the decoding. Therefore, cis stored in external memory for later use, as shown in Algorithm 2. The Patterson algorithm decodes Algorithm 2: Pseudo-C code for Decryption. Input:c∈Fn 2,(P1·P)−1∈Fn 232 ,P1∈Fn 232 , (S−1)T∈Fk×k 2 Result:m∈Fkn 2,ε∈Fn 2 inst_dec1={permute_P(n); } inst_dec2= {add_V(n); permute_P(k); mult_M(k); } McE_LoadVector(c,n); //v ←c McE_Launch(inst_dec1); DMA_Read((P1·P)−1,1,n);//v ←v·(P1·P)−1 McE_SaveVector(c,n); //c←v Patterson( ); //v ←Patterson(v) McE_SaveVector(ε, n); //ε ←v McE_Launch(inst_dec2); DMA_Read(c,1,n); //v ←c+v DMA_Read(P1−1,1,k); //v ←truncate(v·P−1,k) DMA_Read((S−1)T,k,k); //v ←(S−1)T·v McE_SaveVector(m, k); //m ←v the location of errors, storing them into the binary vector ε∈Fn 2 of t-weight. Then, the previously stored c’ is retrieved from external memory and added to ε, obtaining y∈Fn 2. The auxiliary permutation P1is removed from y’, resulting in the subvector y∈Fk 2. Finally, the matrix (S−1)T∈Fk×k 2is multiplied with the subvector y∈Fk 2, writing the computed plaintext m∈Fk 2 into external memory. 1) Patterson Algorithm: The commonly used algorithms for decoding are the Patterson and the Berlekamp-Massey (BM). The BM is faster and simpler, although it can correct up to t/2 errors by default. The modified BM algorithm can recover the required terrors by the computation of the double-size parity matrix H(2) and syndrome S(2). The Patterson algorithm can correct the terrors by operating in binary Goppa codes and it has been thoroughly analyzed for side-channel attacks [23]. However, the algorithm is significantly more complex than the BM, requiring a larger variety of computations in Galois-Field F2mand polynomials F2m[Z]. The Patterson algorithm computes the location of errors from c∈Fn 2, storing them into ε∈Fn 2. It is divided into six steps, starting with the syndrome calculation from the parity matrix H∈Fmt×n 2.The syndromeis storedin aregister(r4) toperform a set of polynomial operations. The Error Location Polynomial (ELP), denoted as σ(Z), is obtained after two executions of the Extended Euclidean Algorithm (EEA) and a square root computation. Finally, the finding of roots provides the locations of the errors, storing them in a binary vector ε∈Fn 2. 1. Sc(Z)=HT·c’ 2. 1≡T(Z)·Sc(Z)mod g(Z)(by EEA) 3. R(Z)=T(Z)+Z 4. a(Z)≡b(Z)·R(Z)mod g(Z)(by EEA) 5. σ(Z)=a(Z)2+Z·b(Z)2 6. ε=roots(σ(Z)) As in the previous codes, the microprocessor (Algorithm 3) launches the execution of two sets of instructions on the