Efficient architecture and method for arithmetic computations in post-quantum cryptography

A computer processing system for reducing a processing footprint in cryptosystems utilizing quadratic extension field arithmetic such as pairing-based cryptography, elliptic curve cryptography, code-based cryptography and post-quantum elliptic curve cryptography that includes at least one computer processor having a register file with three processor registers operably configured to implement quadratic extension field arithmetic equations in a finite field of Fp2 and a multiplexer operably configured to selectively shift from each of the three processor registers in sequential order to generate modular additional results and modular multiplication results from the three processor registers.

FIELD OF THE INVENTION

The present invention relates generally to systems and methods directed toward post-quantum cryptosystems, and, more particularly, relates to cryptosystems utilizing quadratic extension field arithmetic such as pairing-based cryptography, elliptic curve cryptography, code-based cryptography and post-quantum elliptic curve cryptography.

BACKGROUND OF THE INVENTION

Cryptology is the practice and study of techniques for secure communication in the presence of third parties called adversaries. More generally, cryptography is about constructing and analyzing protocols that prevent third parties or the public from reading private messages and includes various aspects in information security such as data confidentiality, data integrity, authentication, and non-repudiation. Applications of cryptography include electronic commerce, chip-based payment cards, digital currencies, computer passwords, and military communications. Cryptosystems are a suite of cryptographic algorithms needed to implement a particular security service, most commonly for achieving confidentiality. Due to the typical amount and time of computations required for a cryptography session, namely one utilizing post-quantum cryptography, the hardware or processing footprint is quite expansive. As such, utilizing such methods and systems is made impossible or commercially impracticable when desired for use in smaller devices, such as IoT devices.

Therefore, those known systems and methods fail to address small implementations of post-quantum cryptosystems, particularly those which utilize quadratic extension field arithmetic. As these cryptosystems have only just been gaining popularity and acceptance in the cryptographic community, implementations of arithmetic computations for cryptosystems have also made its deployment problematic. More specifically, the primary deficiency with post-quantum cryptosystems has typically been their efficiency. As such, much of the research community has focused on making high-speed implementations. These efforts, however, have resulted in the creation of systems generating large processing footprints that are often inefficient.

In addition, the naive way to implement quadratic extension field arithmetic is to use a random-access register file with a modular addition and multiplication unit. As discussed above, however, these configurations are spatially inefficient and not commercially practicable when smaller devices are the targeted implementation environment. As such, there are no known lightweight implementations of elliptic curve or post-quantum cryptography. Some known hardware implementations target very high performance with very large register files and replicated arithmetic units. Other known implementations of finite-field arithmetic that attempt to target a small processing footprint environment are not versatile and still commercially impracticable in that they utilize binary fields and elliptic curve cryptography.

SUMMARY OF THE INVENTION

The invention provides a system and method for reducing the processing footprint in cryptosystems utilizing quadratic extension field arithmetic that overcomes the hereinbefore-mentioned disadvantages of the heretofore-known devices and methods of this general type and that creates a cryptosystem utilizing quadratic extension field arithmetic implemented with a protocol having a much smaller processing footprint. Specifically, one embodiment of the present invention implements a circular-access register file with three registers operably configured to implement all necessary quadratic extension field arithmetic. The present invention is also directed toward a small accelerator for quadratic extension field arithmetic, or arithmetic in Fp2. The goal of this architecture is to perform these arithmetic operations with as small processing area as possible. By reducing the processing area, the system and process achieves a much smaller resource footprint as well as reduce the necessary power and energy for computing various cryptographic primitives. Additionally, the present invention includes a system and method beneficially operably configured to (1) perform quadratic extension field addition, multiplication, squaring, and inversion in a constrained environment; (2) minimize the number of registers needed to hold intermediate values; (3) minimize the register complexity; (4) minimize the number of arithmetic operations required for extension field arithmetic; and (5) select small arithmetic units to perform extension field arithmetic.

With the foregoing and other objects in view, there is provided, in accordance with the invention, a computer processing system for reducing a processing footprint in cryptosystems utilizing quadratic extension field arithmetic having at least one computer processor with a register file including three processor registers operably configured to implement quadratic extension field arithmetic equations in a finite field of Fp2and a multiplexer operably configured to selectively shift from each of the three processor registers in sequential order to generate modular addition results and modular multiplication results from the three processor registers.

In accordance with a further feature of the present invention, the register file is of a circular-access register file block.

In accordance with another feature, an embodiment of the present invention includes the three processor registers consisting essentially of a first work processor register, a second work processor register, and an accumulator register.

In accordance with another feature, an embodiment of the present invention includes a digit-serial adder unit operably coupled to the first work processor register and a constant prime number for which the finite field of Fp2is defined and a modular multiplication unit operably coupled to the second work processor register and the constant prime number for which the finite field of Fp2is defined.

In accordance with a further feature of the present invention, wherein the digit-serial adder unit and modular multiplication unit are single units.

In accordance with yet another feature of the present invention, the quadratic extension field arithmetic equations have an irreducible polynomial of i2+1. That is, the finite field of Fp2is defined as Fp[i]/(i2+1). Or in other words, the polynomial field in i, modulo the irreducible polynomial i2+1 yields a finite field containing p2elements, namely Fp2.

In accordance with another feature, an embodiment of the present invention includes the register file having five processor registers operably configured to implement quadratic extension field arithmetic equations in a finite field of Fp2, wherein the five processor registers consist essentially of a first work processor register, a second work processor register, a third work processor register, a first accumulator register, and a second accumulator register.

In accordance with the present invention, a method for reducing a processing footprint in cryptosystems utilizing quadratic extension field arithmetic comprising the steps of providing at least one computer processor having a register file with a first work processor register, a second work processor register, and an accumulator register and initiating, through the least one computer processor, a cryptography session. The cryptography session includes selecting a constant prime number p for which a finite field of Fp2is defined, receiving numerical data into the first and second work processor registers sequentially and executing quadratic extension field arithmetic equations in the finite field of Fp2using the numerical data to generate arithmetic results from each of the first and second work processor registers, receiving the arithmetic results into the accumulator register and providing the arithmetic results from the accumulator register to the first work processor register to define a circular-access register file block, and outputting the arithmetic results through the first work processor register.

In accordance with another feature, an embodiment of the present invention also includes receiving numerical data into the first and second work processor registers sequentially through a one-way data flow.

In accordance with yet another feature, an embodiment of the present invention includes the cryptography session also having the steps of sequentially shifting from first and second work processor registers and the accumulator register through a multiplexer and choosing a quadratic extension field with an irreducible polynomial of i2+1 after the constant prime number p has been defined.

Before the present invention is disclosed and described, it is to be understood that the terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting. The terms “a” or “an,” as used herein, are defined as one or more than one. The term “plurality,” as used herein, is defined as two or more than two. The term “another,” as used herein, is defined as at least a second or more. The terms “including” and/or “having,” as used herein, are defined as comprising (i.e., open language). The term “coupled,” as used herein, is defined as connected, although not necessarily directly, and not necessarily mechanically. The term “providing” is defined herein in its broadest sense, e.g., bringing/coming into physical existence, making available, and/or supplying to someone or something, in whole or in multiple parts at once or over a period of time. Also, for purposes of description herein, the terms “upper”, “lower”, “left,” “rear,” “right,” “front,” “vertical,” “horizontal,” and derivatives thereof relate to the invention as oriented in the figures and is not to be construed as limiting any feature to be a particular orientation, as said orientation may be changed based on the user's perspective of the device. Furthermore, there is no intention to be bound by any expressed or implied theory presented in the preceding technical field, background, brief summary or the following detailed description.

As used herein, the terms “about” or “approximately” apply to all numeric values, whether or not explicitly indicated. These terms generally refer to a range of numbers that one of skill in the art would consider equivalent to the recited values (i.e., having the same function or result). In many instances these terms may include numbers that are rounded to the nearest significant figure. In this document, the term “longitudinal” should be understood to mean in a direction corresponding to an elongated direction of any processing chip. The terms “program,” “software application,” and the like as used herein, are defined as a sequence of instructions designed for execution on a computer system. A “program,” “computer program,” or “software application” may include a subroutine, a function, a procedure, an object method, an object implementation, an executable application, an applet, a servlet, a source code, an object code, a shared library/dynamic load library and/or other sequence of instructions designed for execution on a computer system.

DETAILED DESCRIPTION

The present invention provides a novel and efficient system and method for reducing the processing footprint of arithmetic computations for cryptosystems. More specifically, the system and method is directed toward a cryptosystem having a lightweight accelerator for arithmetic operations in Fp2(hereinafter “Fp2accelerator”) containing p2elements, wherein “p” is a prime number, preferably a constant prime number for which Fp2field is defined. The system is lightweight in that it is structurally and operably configured to minimize the number of processor registers, namely intermediate registers, uses a circular work register block, and includes a digit-serial adder and modular multiplier. Specifically, the system is configured with hardware and instructions to target prime fields where extension field arithmetic can be defined over an irreducible polynomial i2+1, wherein this characteristic is specifically targeted to design the Fp2accelerator.

One embodiment of the present invention is shown schematically through a block diagram inFIG. 1.FIG. 1, along with other figures herein, show several advantageous features of the present invention, but, as will be described below, the invention can be provided in several shapes, sizes, combinations of features and components, and varying numbers and functions of the components. The first example of an Fp2accelerator architecture100utilized in the aforementioned system and method, as shown inFIG. 1and with reference toFIG. 3, includes a register file102having three processor registers104,106,108operably configured to implement quadratic extension field arithmetic equations in a finite field of Fp2and a multiplexer select110operably configured to selectively shift from each of the three processor registers104,106,108in sequential order. The register file102is resident, housed on, and/or operably connected to at least one computer processor (represented schematically as element118inFIG. 1). Each of the three processor registers104,106,108may also be referred to or defined as the first work processor register R0, the second work processor register R1, and an accumulator register R2, respectively.

As those of skill in the art will appreciate, a register file is an array of processor registers in a central processing unit (CPU). In one embodiment, the processor registers104,106,108are circuit-based register files and may be implemented by way of fast static random access memories (RAMs) with multiple ports. Such RAMs are distinguished by having dedicated read and write ports, whereas ordinary multi-ported RAMs will usually read and write through the same ports. In other embodiments, the processor registers104,106,108may be implemented by way of fast dynamic RAMs. The instruction set architecture of a CPU will almost always define a set of registers which are used to stage data between memory and the functional units on the chip. In simpler CPUs, these architectural registers correspond one-for-one to the entries in a physical register file (PRF) within the CPU. More complicated CPUs use register renaming, so that the mapping of which physical entry stores a particular architectural register changes dynamically during execution.

FIGS. 1 and 2will be described in conjunction with the process flow chart ofFIG. 3. AlthoughFIG. 3shows a specific order of executing the process steps, the order of executing the steps may be changed relative to the order shown in certain embodiments. Also, two or more blocks shown in succession may be executed concurrently or with partial concurrence in some embodiments. Certain steps may also be omitted inFIG. 3for the sake of brevity. In some embodiments, some or all of the process steps included inFIG. 3can be combined into a single process.

In the embodiment shown inFIG. 1, the Fp2accelerator utilizes the first and second work registers104,106and the accumulator register108to perform all Fp2operations. The process may start at step300and immediately proceed to step302, which includes providing the structural hardware utilized to implement the process as described herein, e.g., at least one computer processor having a register file102with a first work processor register104, a second work processor register106, and an accumulator register108. Next, step304may include initiating, through the least one computer processor118, a cryptography session. Said another way, a circular register file array102may be used to move data between registers104,106,108in one direction, i.e., through a one-way data flow. All data may flow in and out through work register R0.

More specifically, the cryptography session may include step306defining a constant prime number, p, for which a finite field of Fp2is defined. The prime number p may be predefined or dynamically and selectively defined by the user and/or the processor. Next, step308may include receiving numerical data into the first and second work processor registers104,106sequentially and executing quadratic extension field arithmetic equations (represented schematically inFIG. 1as arrow112) in the finite field of Fp2using the numerical data to generate arithmetic results from each of the first and second work processor registers104,106. The multiplexer select or “sel”110on the left side of the block diagram may be utilized to select and save from new modular addition results114(depicted as “mod_add” inFIG. 1) and modular multiplication results116(depicted as “mod_mult” inFIG. 1) generated from each respective work processor register104,106. The multiplexer110is also operably configured to cause register shifts from register R2,108to register104. As such, a circular-access register file is created, whereby the three registers104,106,108are operably configured to implement all necessary quadratic extension field arithmetic. This circular access reduces the quadratic complexity of register multiplexers to a constant cost, thus reducing processing area in exchange for some control logic.

As those of skill in the art will appreciate, the multiplexer110is a device that selects one of several analog or digital input signals and forwards the selected input into a single line. A multiplexer of 2ninputs has n select lines, which are used to select which input line to send the output. A multiplexer can also be used to implement Boolean functions of multiple variables.

The system may also include a digit-serial adder unit114operably coupled to the first work processor register104and a constant prime number p (depicted inFIG. 1) for which the finite field of Fp2is defined. The system may also include a modular multiplication unit116operably coupled to the second work processor register106and the constant prime number p for which the finite field of Fp2is defined. The digit-serial adder unit114and modular multiplication unit116may also be single units.

The quadratic extension field arithmetic equations operably configured to be carried out by the Fp2accelerator can include modular addition, subtraction, squaring, multiplication, and inversion in the finite field Fp2. More specifically, elements in Fp2are represented in the form of A=a0+ia1, wherein i is a non-quadratic residue and a0and a1are elements of Fp. When the irreducible polynomial is selected as i2+1, where i=√{square root over (−1)} in Fp2, certain finite field operations can be defined in Fp2with specific formulas involving Fp2operations:
A+B=a0+b0+i(a1+b1)
A−B=a0−b0+i(a1−b1)
A×B=(a0+a1)(b0−b1)+a0b1−a1b0+i(a0b1+a1b0)
A2=(a0+a1)(a0−a1)+i2a0a1
A−1=a0(a02+a12)−1−ia1(a02+a12)−1

Thus, an addition and subtraction require 2 Fpadditions, a multiplication requires 3 Fpmultiplications and 5 Fpadditions, a squaring requires 2 Fpmultiplications and 3 Fpadditions, and an inversion requires 1 Fpinversion, 2 Fpmultiplications, 2 Fpsquarings, and 2 Fpadditions. Table 1, below, exemplifies the Fp2accelerator carrying out Fp2squaring. More specifically, assume that we are squaring the value A=a0+ia1to get A2=(a0+a1)(a0−a1)+i2a0a1. This architecture uses an accumulate-based approach. It is also assumed the file register is of a circular register buffer in the order register R0to R1to R2to R0and that R0and R1are work registers. Therefore, A2and A×B with the controls shown in Tables 1-2, respectively. Said another way, one register, e.g., register108is temporary to accumulate the intermediate results and perform operations sequentially in the work registers, e.g., registers104,106.

One benefit to the architecture depicted inFIG. 1is that each Fp2operation will always require the same sequence of instructions in the same amount of time, thus providing resistance to some timing and power side channel attacks. Although many cryptographic primitives are strong in black-box models of algorithms, physical implementations of these algorithms will inadvertently leak other information, such as timing, power, or electromagnetic residues. When cryptographic primitives are implemented naively, these side channels can be analyzed to recover critical information, such as a party's secret key(s). Therefore, to help protect against such attacks, this architecture forces constant-time and a constant set of operations for each Fp2and Fpcomputation. Advantages in this architecture include minimizing the number of intermediate registers for Fp2operations, the number of work registers, the number of Fpoperations, and the multiplexer interaction of these three registers with the register file. Each of these characteristics correspond to reduced processing area with only a small impact on the timing. As Table 3, above, demonstrates, one Fpmultiplication is exchanged for three Fpadditions in Fp2multiplication and one Fpaddition in Fp2squaring, which generally reduces the latency of these operations. Assuming that each load, store, and shift only requires a single cycle, the control style of computations also greatly reduces the processing area cost of implementing the Fp2operations for a small latency overhead. For a lightweight ASIC, minimizing the processing area and size is key to creating a small co-processor for cryptographic applications.

Therefore, to minimize the register footprint, the present inventions preferably utilizes two work registers104,106and an accumulator register108, which is sufficient for all necessary Fp2operations. The number of arithmetic operations needed is then minimized by choosing a quadratic extension field with the irreducible polynomial i2+1. In the resulting architecture, digit-serial addition and modular multiplication units114,116may also be utilized to perform the necessary prime field arithmetic in series, using circular register shifts and loads, implemented through the multiplexer as needed.

Beneficially, some principal applications of the present invention may include reducing the processing area overhead (i.e., the number of gates in a digital circuit) to perform Fp2arithmetic. As such, features such as providing a circular register file, an accumulator-based flow with minimum register complexity, the choice of special form for primes in quadratic extension fields, and small digit-serial arithmetic units to create a separated Fp2arithmetic unit generates the advantageous small processing footprint in hardware. Another goal or target of the aforementioned system and method is in post-quantum cryptography use, which also translates to uses in elliptic curve cryptography. Other applications include pairing-based cryptography, elliptic curves with isomorphisms (such as 4Q), code-based cryptography, and lattices. With reference now toFIG. 2, another example of an Fp2accelerator architecture200utilized in the aforementioned system and method is depicted.FIG. 2depicts many of the same components and features references above with respect toFIG. 1. However, the Fp2accelerator200is instantiated and includes a bit-parallel modular multiplier unit202and a digit-serial adder/subtractor204unit. The instantiated Fp2accelerator, however, uses three work registers206,208,210, for the bit-parallel modular multiplier and two accumulators212,214to perform Fp2addition, multiplication, squaring, and inversion. Said another way, whether implemented into the Fp2accelerator embodiments ofFIG. 1 or 2, step310of the method may include receiving the arithmetic results, during the cryptography session, into one or more accumulator registers and providing the arithmetic results from one or more accumulator registers to the first work processor register to define a circular-access register file block. As seen below, step312may include outputting the arithmetic results through the first work processor register for use by the processor118and/or memory operably connected thereto. The process may terminate in step314.

More specifically, the Fp2accelerator architecture200utilizes the bit-parallel modular multiplier202and a digit-serial adder204with a 32-bit adder/subtractor. In this embodiment, two additional work registers208,210(also depicted inFIG. 2as ps and pc) are utilized and they hold intermediate carry/save adder values for, by way of example, a Montgomery modular multiplication algorithm utilized in the multiplier unit202. Additionally, register212(also depicted as R1) is no longer used for addition and subtraction; rather, register208performs addition and subtraction through use of the unit204. A complexity analysis for the Fp2accelerator depicted inFIG. 2is shown in Table 4, below. Specifically, the instantiated Fp2complexity (disregards control signals) with a bit-parallel multiplier and digit-serial (d=32) adder. FF=Flip-Flop, FA=Full Adder. For the final row, m is the number of bits in the prime for the quadratic field. There are also 3 half adders and 3 XOR gates in these results.

Table 5, below, depicts implementation results of instantiated Fp2accelerator on Artix-7 FPGA.

The primary source of gates come from the bit-parallel multiplier and there are also many 2:1 multiplexers as a result of interfacing between the registers for various operations. As reflected in Table 5, above, the efficacy of the Fp2architecture in an Artix-7 FPGA can be seen. This implementation, however, did not include additional control signals, which would constitute an extremely small additional area overhead. The processing area and time complexities are also shown in Table 5 and it can be seen that the Fp2time complexity uses the operation counts in Table 3. The critical path is the digit-serial adder, which was a 32-bit adder in this case. When discussing the complexity of this instantiated Fp2accelerator, it is important to note the naive approach. From Table 5, again, it becomes readily apparent that performing extra multiplications becomes very costly.

Thus, by using the formulas we provide for Fp2operations, the aforementioned system and method are saving many cycles by replacing a modular multiplication with a few modular additions or subtractions. In Table 6, below, a timing comparison between the present invention's Fp2multiplication and squaring formulas versus naive formulas are shown. It can be seen that Fp2multiplication is approximately 20% faster and Fp2squaring is 30% faster when compared to naive formulas. However, the choice of modular multiplier and modular adder were combined in three work registers. This adds additional multiplexers for interfacing logic, but also reduces multiplexers that would be used to initialize these registers. The logical flow of the registers in the circular buffer eliminates the need for excess 2:1 multiplexers.

TABLE 7ControlR0pscarryInitial conditions70450Initial conditions in binary8b0100_01108b0010_11010Add lowest digit and store to ps8b0100_01108b0010_00111Shift d bits8b0110_01008b0011_00101Add lowest digit with carry to ps8b0110_01008b0011_01110Shift d bits8b0100_01108b0111_00110Final result is ps701150

By way of example utilizing the Fp2accelerator depicted inFIG. 2, Table 7, above, depicts said accelerator performing addition. In Table 7, p=71 and the results reflect the performance of simple addition of a=70 and b=45 to produce the result c=70+45=115. Table 7, however, illustrates the step-by-step computations with an adder digit size of d=4. This means that system and method described herein processes 4 bits of the result at a time. For this architecture, we produce the result by adding ps=R0+ps over multiple cycles. We load R0=a=70 and ps=b=45. Since the prime p is 7 bits and we add 4 bits at a time, we have the result after two cycles (an add and shift would be performed simultaneously, but it is specifically listed to illustrate what the hardware executes).

Table 8, above, depicts an example of modular multiplication in depth. This performs a bit-parallel modular multiplier based on the Montgomery multiplication algorithm. For this, the system will calculate m smaller modular multiplications for an m-bit prime p. For p=71, we have a 7-bit prime, so we perform 7 smaller modular multiplications for the final result. The idea of a multiplier is that it is based on the carry-save adder technique, where we perform very fast additions in parallel without worrying about carry propagations. Algorithm 1, below, shows the algorithm that the multiplier follows. Table 8 shows a cycle-by-cycle breakdown of what the 7 cycles will be in Table 8. We perform the multiplication with a=13 and b=5, which when using R=27, will produce the result c=abR−1mod 71=41.

Algorithm 1—Bit-serial CSA Montgomery multiplication. Sc and Ss refer to the carry and sum bits of the result S, respectfully. Specifically, the input may be a Modulus M, R=2k>M, operands x, y<M The output may be z=xyR−1mod M Therefore, an exemplary software-based algorithm to effectuate the same is depicted below:

2. for i in 0 to (k)−1 do

5. end for

Table 9, below, depicts exemplary results of the Fp2accelerator generating computations and depicting what the registers hold when implementing exemplary quadratic extension field arithmetic equations in a finite field of Fp2. For this example, p=71 and perform an Fp2multiplication (with irreducible polynomial i2+1) between A=5+3i and B=13+9i to produce the result C. What is not shown, for brevity, are the cycle-by-cycle contents of the modular multiplier or addition, as exemplary results of these are depicted in Tables 7 and 8, respectively. The values are converted to the Montgomery form by performing the computation ajR mod p and bjR mod p with R=27for j=0; 1. Thus, the inputs in the Montgomery domain are A=1+29i and B=31+16i. The final value for C=36+31i, so the normal representation of this result is C=38+13i, which can be recovered in a simple way by performing the computations C=(5×13−3×9)+(5×9+3×13)=38+13i.