Design And Improvement Of Finite Field Arithmetic And Multivariate Public Key Cryptographic Hardware

Most public key cryptographic schemes are based on the hardness of factoring large num-bers or discrete logarithm problems. However, a potential powerful quantum computer couldputthoseschemesinjeopardy. Multivariatepublickeycryptographyisoneofthebestalternateswhich has the potential to resist quantum computer attacks. Although the design and analysisof multivariate public key cryptography is one of the focuses of the researchers, hardware de-sign of those schemes has not received considerable attention. Compared with RSA and ECCcryptography, the applications of multivariate public key cryptography is much less than theirs.The focus of this paper is to design and improve multivariate public key cryptographichardware. Finite field arithmetic is the fundamental operation in those cryptographic schemes,e.g. multiplication, inversion and solving systems of linear equations. The optimization ofsuch arithmetic can improve the overall performance of cryptographic hardware. Therefore, wedesign three kinds of finite field operations.The first design is a fast inverter over finite fields. It speeds up finite field inversions oversmall finite fields remarkably, e.g. GF(2n) and GF (p), where2n1<p <2n. Our design isbased on binary tree, which is a novel revolution compared with other algebra-based designsof finite fields. Our design increases the throughput of inversions dramatically with the aidof pipelining, which is also a novel revolution compared with other non-pipelined designs offinite fields. Our design requires (n1)(TAND+TXOR) to compute an inversion, where TANDand TXORare the latency of AND gates and XOR gates respectively. The pipelined versionof our design computes inversions in TANDor TXOR. Therefore, the time complexity of thenon-pipelined version and pipelined version of our design is O(n) and O(1) respectively. OurdesignonlyusesAND gatesandXOR gatesforinversionsoverfinitefields. Itcanbeobservedthat, our design achieves a better performance when the field size increases. We implement ourdesign on Altera, Xilinx FPGA and TSMC-0.18μm standard cell CMOS ASIC respectively.The implementation and comparison results show that our design is much faster and better thanother inversions over finite fields. Besides, our design can be used in exponentiations over finitefields and inversions over subfields GF(2n) for inversions over composite fields GF ((2m)n).The second design is a fast multiplier with multiple elements over finite fields. It speeds up multiplications of two elements and multiplications of three elements over small finite fieldsremarkably. Since multivariate public key cryptography requires both multiplications of twoelements and multiplications of three elements, optimization of multiplications of multiple el-ements over finite fields can improve the overall performance of cryptographic hardware. Theresearch of multiplication of multiple elements is brand new. Therefore, we design a versatilemultiplier with multiple inputs, which can use different methods over different finite fields, e.g.GF (2n) and GF ((2n)2). We adapt multiplications on polynomial basis and multiplication withtable look-up in our design. The implementation and comparison results show that our designis much faster than other multipliers when computing multiplications of three elements. Fur-thermore, we use our design to speed up Gaussian elimination over finite fields and multivariatepublic key cryptography. Our design can be improved, e.g. using multiplications on normabasis and dual basis. It can be extended to GF((2n)m).The third design is a fast method to solve systems of linear equations over finite fields.It speeds up solving systems of linear equations over GF(2n) remarkably, where the matrixsize is m×m. Since multivariate public key cryptography requires solving systems of linearequations over finite fields in central map transformations, our design can reduce the latencyof such computation in half, i.e. we only require m clock cycles for solving systems of linearequations. We compute multiplications of three elements in one clock cycle. Then we proposepartial inversions in our design. Besides, we use index in our design. Finally, we combinepivoting, normalization and elimination in a parallel way. By integrating the above designsand other optimization, we implement our design on a Altera FPGA. The implementation andcomparisonresultsshowthatourdesignismuchfasterthanothermethodswhensolvingsystemsof linear equations. The achieved count of clock cycles is independent of the size of finite fieldsbut only related to the matrix size. Thus our design with the same matrix size can be achievedthe same count of clock cycles on different kinds of FPGAs. On the other hand, the achievedclock frequency of our design is independent of the matrix size but only related to the size offinite fields. Therefore, our design is also suitable for solving system of linear equations withvery large matrix sizes. Moreover, our design can be used in other kinds of fields, e.g. floatpoint fields.The above algorithms can be used to design hardware, which leads to an improvement of economic value and industrial value. By combining such algorithms and proposing newmethods, we design two kinds of hardware of Rainbow signatures.The first design is a fast Rainbow signature hardware. It speeds up Rainbow signatureremarkably. Our design uses optimized multiplications of multiple elements, partial inversionsand fast solving systems of linear equations. By combining other optimizations, our designtakes only198clock cycles to generate a Rainbow signature, a new record in generating digitalsignatures and four times faster than the relate implementations. The comparison result showsthat our design is much faster than other public key cryptographic systems, e.g. RSA and ECC.Our design demonstrates that multivariate public key cryptography can be used in time-limitedapplications.The second design is an efficient Rainbow signature hardware. It improves the overall per-formance of Rainbow signature remarkably. Time and area are both crucial for a cryptographicsystem. Time-areaproductisusedtoevaluatetheperformanceofhardware. Ourdesignisbasedon the reduction of both time and area. We design Rainbow signature hardware based on an op-timized irreducible polynomial over a finite field. We optimize multiplication, inversion andsolving systems of linear equations over a finite field. The comparison results show that our de-sign reduces the time-area product of Rainbow signature and is much efficient than other publickey cryptographic systems. Our design demonstrates that multivariate public key cryptographycan be used in efficient applications.Our design increases the economic value and industrial value of Rainbow signature sinceit is a popular candidate of applications of industry.Finally, we design a small-area multivariate public key cryptographic processor. Since wewant to use multivariate public key cryptography in resource limited environment, e.g. sensors,smart card and RFID, our design is based on the optimization of area. First, we design a mod-ular arithmetic logic cell for addition, multiplication and inversion over GF((24)2). Then wedesign a compact instruction set and decoder. Finally we reuse the registers. By integrating theabove designs and other optimization, we propose a small-area multivariate public key crypto-graphic processor. We implement three different kinds of multivariate public key cryptographicsystems on our processor, i.e. UOV, Rainbow and en-TTS. They achieve a moderate speed onour processor. The comparison results show that our design is one of the smallest multivariate public key cryptographic systems and is much smaller than other public key systems, e.g. RSAand ECC. Our design demonstrates that multivariate public key cryptography can be used inresource-limited applications.