Search

Arithmetic operations over finite fields are widely used in coding theory and cryptography. In both of these applications, there is a need to design low complexity finite field arithmetic units. The complexity of such a unit largely depends on how the field elements are represented. Among them, representation of elements using a optimal normal basis is quite attractive. Using an algorithm minimizing the number of 1`s of multiplication matrix, in this paper, we propose a multiplier which is time and area efficient over finite fields with optimal normal basis.

Subquadratic space complexity multipliers for optimal normal bases (ONBs) have been proposed for practical applications. However, for the Gaussian normal basis (GNB) of type t > 2 as well as the normal basis (NB), there is no known subquadratic space complexity multiplier. In this paper, we propose the first subquadratic space complexity multipliers for the type 4 GNB. The idea is based on the fact that the finite field GF(2 n ) with the type 4 GNB can be embedded into fields with an ONB.

Multiplication is one important finite field arithmetic operation in cryptographic computations. Dual basis multipliers over Galois field GF(2 m ) have been widely applied in this kind of computations because of its advantage of small chip area. Nevertheless, up to date, there are only few methods that can keep balance of low space complexity and low time complexity at the same time. In order to achieve such an efficient aim, this study presents a novel digit-serial dual basis multiplier that is different from existing ones with a modified cut-set method using Karatsuba algorithm as well as Hankel matrix. As a result, the proposed multiplier can save much space and thus be particularly suitable for some hand held devices equipped with only limited resources. The proposed digit-serial dual basis multiplier saves 55% space complexity as compared with existing similar studies with National Institute of Standards and Technology (NIST) suggested values for elliptic curve cryptosystem.

Finite field multiplier is widely applied in many domains such as coding theory and cryptography. In this paper, it is purposed to propose a concurrent all-cell error detection semi-systolic polynomial basis multiplier based on coding theory which can realize high-speed calculation and high efficient error detection with low resource consumption. First, our method is created to choose an appreciate generator polynomial for a linear code and an irreducible polynomial generating the finite field. Then the finite field arithmetic multiplication with error detection is simplified on a residue class ring resulted from linearly coding. Second, a semi-systolic array is compressed to realize our multiplier which is suitable for almost anyfinitefield with low time and area complexity. Furthermore, our method breaks through the key technical bottleneck of unacceptable time and area overheads in the coding, decoding and checking process. Additionally, the paper creatively builds an all-cell error model for systolic or semi-systolic multipliers more practical than the conventional single stuck-at or single-cell error model. Finally, based on the all-cell error model, the proposed multiplier is only with 2:088% extra time overhead and 4:978% extra area overhead, and its probability of concurrent error detection reaches to 99:999999%.

Finite field arithmetic has been extensively used in error correcting codes and cryptography. Among the arithmetic operations of finite fields, multiplication is important building block of various applications. This is because the time-consuming operations such as exponentiation, division, and multiplicative inversion can be decomposed into repeated AB or AB2 multiplications. Therefore, we require an efficient algorithm and architecture for multiplication over finite fields. In this paper, we propose an efficient Montgomery AB2 multiplier over finite fields defined by irreducible all-one polynomials. The proposed AB2 multiplier has less space and time complexities compared to related multipliers. As compared to the corresponding existing structures, the proposed AB2 multiplier saves at least 59% area, 50%time, and 79% area-time (AT) complexity. Accordingly, it is well suited for VLSI implementation and can be easily applied as a basic component for computing complex operations over finite field.

We present a new method for solving nonlinear integer arithmetic constraints. The method relies on the MCSat approach to solving nonlinear constraints, while using branch and bound in a conflict-directed manner. We report encouraging experimental results where the new procedure outperforms state-of-the-art SMT solvers based on bit-blasting.

Public-key cryptography makes it possible to create digital signatures and do key negotiation, which is inevitable for today’s commercial and governmental online computer systems. Elliptic curve cryptography (ECC) is a preferred method to implement these services, due to its low computational complexity compared to other modular arithmetic systems such as the Rivest-Shamir-Adleman algorithm (RSA). This thesis investigates how the use of different curve representations impact the performance of the Elliptic Curve Discrete Signing Algorithm (ECDSA) and the Elliptic Curve Diffie-Hellman (ECDH) key-exchange. This thesis developes a point compression method for Hessian curves over both binary and odd prime characteristic fields, and an addition-subtraction formula for twisted Hessian curves. Using these mechnanisms, the thesis gives a full C implementation of twisted Hessian curves, binary Hessian curves, and binary Edwards curves as an extension to the open source library Miracl. To performance test these curve representations the thesis gives several random curves and presents a detailed test methodology. This methodology lets us compare the complexity of a scalar multiplication in the different curve representations as a number of field multiplications. Applying this methodology, the thesis compares the already implemented Weierstrass curves and twisted inverted Edwards curves in Miracl with the added curve representations. From these results, twisted inverted Edwards curves over odd prime characteristic fields clearly excel as the best performing curve representation for ECDSA-signature verification. For ECDSA-signature generation and ECDH key-exchange, projective Weierstrass over binary fields using Koblitz curves stands out as the best performing. Furthermore, the thesis evaluates the implementation of these curve representations in regards of simple side-channel attack protection.

Addition chain calculations play a critical role in determining the efficiency of cryptosystems based on isogenies on elliptic curves. However, finding a minimal length addition chain is not easy; a generalized version of the problem, in which one must find a chain that simultaneously forms each of a sequence of values, is NP-complete. For the special primes used in such cryptosystems, finding fast addition chains for finite field arithmetic such as inversion and square root is also not easy. In this paper, we investigate the shape of smooth isogeny primes and propose new methods to calculate fast addition chains. Further, we also provide techniques to reduce the temporary register consumption of these large exponentials, applicable to both software and hardware implementations utilizing addition chains. Lastly, we utilize our procedures to compare multiple isogeny primes by the complexity of the addition chains.

In this paper, we propose a parallel multiplier over arbitrary finite field GF(p^m). In particular, we apply the proposed multiplier to GF(3^m) defined by irreducible trinomial which has received a great interest recently. The proposed GF(3^m) multiplier is not only the first parallel multiplier with explicit complexities, but its complexities also match with generalized forms of the complexities of the most efficient GF(2^m) multiplier.

Barreto-Naehrig (BN) curve is a well studied pairing friendly curve of embedding degree 12, that uses arithmetic in F p i2. Therefore the arithmetic of F p 12 extension field is well studied. In this paper, we have proposed an efficient approach of arithmetic operation over the extension field of degree 18 by towering. F p 18 extension field arithmetic is considered to be the basis of implementing the next generation pairing based security protocols. We have proposed to use F p element to construct irreducible binomial for building tower of extension field up to F p 6, where conventional approach uses the root of previous irreducible polynomial to create next irreducible polynomials. Therefore using Fp elements in irreducible binomial construction, reduces the number of multiplications in Fp to calculate inversion and multiplication over F p 18, which effects acceleration in total arithmetic operation over F p 18.

Arb is a C library for arbitrary-precision interval arithmetic using the midpoint-radius representation, also known as ball arithmetic. It supports real and complex numbers, polynomials, power series, matrices, and evaluation of many special functions. The core number types are designed for versatility and speed in a range of scenarios, allowing performance that is competitive with non-interval arbitrary-precision types such as MPFR and MPC floating-point numbers. We discuss the low-level number representation, strategies for precision and error bounds, and the implementation of efficient polynomial arithmetic with interval coefficients., 12 pages, 1 figure

Recently, pairing based cryptography has drawn a lot of attention since it is the key technology to construct identity based encryption schemes. Major operations of pairing are elliptic curve computations defined upon finite field arithmetic. Hardware implementation of large prime field operation is critical to improve the practicality of pairing based cryptography. In this paper, we present a parallel processing architecture of cryptoprocessor for optimal ate pairings over BN-curves in prime field. The proposed design contains two arithmetic processing engines to complete prime field operations in parallel. Each engine is designed by the unified Fp arithmetic unit to save hardware resources. This architecture can also be used to implement RSA and ECC cryptography schemes in parallel to satisfy industry demand. The design is implemented on a Virtex-5 FPGA device. The result shows our design consumes 10592 Slices and computes optimal-ate pairing within 283,111 clock cycles, achieving a better balance between speed and area than other designs.

Elliptic curve cryptography (ECC) is widely used as an efficient mechanism to secure private data using public-key protocols. This paper focuses on ECC over prime fields (GF(p)). We present a novel hardware architecture that calculates the elliptic curve point multiplication (ECPM). Our processor supports arbitrary prime fields with sizes up to 1024 bits. Different standards, which use curves in short Weierstrass form are supported. A Xilinx Virtex-7 implementation of the proposed hardware architecture takes from 0.69 ms for a 192-bit point multiplication up to 9.7 ms for 512-bit. The implementation takes only 20 DSP slices and 6816 LUTs. To the authors knowledge, this is the best performance reported so far for ECC point multiplication for arbitrary prime field curves without the use of FPGA reconfiguration.

Finite fields are widely used in constructing error-correcting codes and cryptographic algorithms. In practice, error-correcting codes use small finite fields to achieve high-throughput encoding and decoding. Conversely, cryptographic systems employ considerably larger finite fields to achieve high levels of security. We focus on developing efficient software implementations of arithmetic operations in reasonably large finite fields as needed by secure storage applications. In this article, we study several arithmetic operation implementations for finite fields ranging from GF (2 32 ) to GF (2 128 ). We implement multiplication and division in these finite fields by making use of precomputed tables in smaller fields, and several techniques of extending smaller field arithmetic into larger field operations. We show that by exploiting known techniques, as well as new optimizations, we are able to efficiently support operations over finite fields of interest. We perform a detailed evaluation of several techniques, and show that we achieve very practical performance for both multiplication and division. Finally, we show how these techniques find applications in the implementation of HAIL, a highly available distributed cloud storage layer. Using the newly implemented arithmetic operations in GF (2 64 ), HAIL improves its performance by a factor of two, while simultaneously providing a higher level of security.

In this paper, we present a new method to compute the Mastrovito matrix for GF(2m) generated by an arbitrary irreducible polynomial using weakly dual basis of shifted polynomial basis. In particular, we derive the explicit formulas of the proposed multiplier for special type of irreducible pentanomial xm+xk3+xk2+xk1+1 with k1

Finite field multiplication is one of the most important operations in the finite field arithmetic. In this paper, we study semi-systolic and systolic implementations of the shifted polynomial basis multiplication and propose low time complexity semi-systolic and systolic array structures. We show that our proposed semi-systolic multiplier is faster than its existing counterparts available in the literature. Our application-specified integrated circuit (ASIC) implementation of the proposed semi-systolic multiplier demonstrates that reduction in time complexity is achieved without imposing hardware overhead. Furthermore, our proposed systolic array shifted polynomial basis (SPB) multiplier has a low time complexity for general irreducible polynomials.

The availability of a new carry-less multiplication instruction in the latest Intel desktop processors significantly accelerates multiplication in binary fields and hence presents the opportunity for reevaluating algorithms for binary field arithmetic and scalar multiplication over elliptic curves. We describe how to best employ this instruction in field multiplication and the effect on performance of doubling and halving operations. Alternate strategies for implementing inversion and half-trace are examined to restore most of their competitiveness relative to the new multiplier. These improvements in field arithmetic are complemented by a study on serial and parallel approaches for Koblitz and random curves, where parallelization strategies are implemented and compared. The contributions are illustrated with experimental results improving the state-of-the-art performance of halving and doubling-based scalar multiplication on NIST curves at the 112- and 192-bit security levels and a new speed record for side-channel-resistant scalar multiplication in a random curve at the 128-bit security level. The algorithms presented in this work were implemented on Westmere and Sandy Bridge processors, the latest generation Intel microarchitectures.

Multiplication is one of the most important operations in finite field arithmetic. It is used in cryptographic and coding applications, such as elliptic curve cryptography and Reed-Solomon codes. In this paper, we consider the finite field multiplication used in elliptic curve cryptography and design concurrent error detection circuits. It is shown in the literature that the Montgomery multiplication can be used in cryptography to accelerate the scalar multiplication. Here, we use a parity-based concurrent error detection approach to increase the reliability of different Montgomery multipliers available in the literature. First, we consider bit-serial Montgomery multiplication and propose an error detection circuit. Then, we apply the same technique on the digit-serial Montgomery multiplication. Finally, we consider low time-complexity bit-parallel Montgomery multiplication and design the required components to implement the concurrent error detection circuits. ASIC implementations have been completed to analyze the time and area overheads of the proposed schemes. Also, the error detection capability is investigated by software simulations. We show that our approach results in efficient error detection schemes with small time and area overheads.

Hardware implementations of finite field arithmetic using normal basis are advantageous due to the fact that the squaring operation can be done at almost no cost. In this paper, a new word-level finite field multiplier using normal basis is proposed. The proposed architecture takes d clock cycles to compute the product bits, where the value for d, 1 ≤ d ≤ m, can be arbitrarily selected by the designer to set the tradeoff between area and speed. When there exists an optimal normal basis, it is shown that the proposed design has a smaller critical path delay than other word-level normal basis multipliers found in the literature, while its circuit complexities are moderate and comparable to the others. Different word size multipliers were implemented in hardware, and implementation results are also presented.

Finite field GF(2m) arithmetic is becoming increasingly important for a variety of different applications including cryptography, coding theory and computer algebra. Among finite field arithmetic operations, GF(2m) multiplication is of special interest because it is considered the most important building block. This contribution describes a new low latency parallel-in/parallel-out sequential polynomial basis multiplier over GF(2m). For irreducible GF(2m) generating polynomials f(x)=xm+xkt+xkt-1+⋯+xk1+1 with m ≥ 2kt-1, the proposed multiplier has a theoretical latency of 2kt+1 cycles . This latency is the lowest one found in the literature for GF(2m) multipliers. Furthermore, the condition m ≥ 2kt-1 is specially important because the five binary irreducible polynomials recommended by NIST for elliptic curve cryptography (ECC) implementation verify this condition.

We present low complexity formulae for the computation of cubing and cube root over IF3m constructed using special classes of irreducible trinomials, tetranomials and pentanomials. We show that for all those special classes of polynomials, field cubing and field cube root operation have the same computational complexity when implemented in hardware or software platforms. As one of the main applications of these two field arithmetic operations lies in pairing-based cryptography, we also give in this paper a selection of irreducible polynomials that lead to low cost field cubing and field cube root computations for supersingular elliptic curves defined over IF3m, where m is a prime number in the pairing-based cryptographic range of interest, namely, m ∈ [47, 541].

Optimal extension fields (OEF) are a class of finite fields used to achieve efficient field arithmetic, especially required by elliptic curve cryptosystems (ECC). In software environment, OEFs are preferable to other methods in performance and memory requirement. However, the irreducible binomials required by OEFs are quite rare. Sometimes irreducible trinomials are alternative choices when irreducible binomials do not exist. Unfortunately, trinomials require more operations for field multiplication and thereby affect the efficiency of OEF. To solve this problem, we propose a new type of irreducible polynomials that are more abundant and still efficient for field multiplication. The proposed polynomial takes the advantage of polynomial residue arithmetic to achieve high performance for field multiplication which costs O(m 3/2) operations in $${\mathbb{F}_p}$$ . Extensive simulation results demonstrate that the proposed polynomials roughly outperform irreducible binomials by 20% in some finite fields of medium prime characteristic. So this work presents an interesting alternative for OEFs.

The deployment of cryptography in sensor networks is a challenging task, given the limited computational power and the resource-constrained nature of the sensoring devices. This paper presents the implementation of elliptic curve cryptography in the MICAz Mote, a popular sensor platform. We present optimization techniques for arithmetic in binary fields, including squaring, multiplication and modular reduction at two different security levels. Our implementation of field multiplication and modular reduction algorithms focuses on the reduction of memory accesses and appears as the fastest result for this platform. Finite field arithmetic was implemented in C and Assembly and elliptic curve arithmetic was implemented in Koblitz and generic binary curves. We illustrate the performance of our implementation with timings for key agreement and digital signature protocols. In particular, a key agreement can be computed in 0.40 seconds and a digital signature can be computed and verified in 1 second at the 163-bit security level. Our results strongly indicate that binary curves are the most efficient alternative for the implementation of elliptic curve cryptography in this platform.

Cryptography is one of the most prominent application areas of the finite field arithmetic. Almost all public-key cryptographic algorithms including the recent algorithms such as elliptic curve and pairing-based cryptography rely heavily on finite field arithmetic, which needs to be performed efficiently to meet the execution speed and design space constraints. These objectives constitute massive challenges that necessitate interdisciplinary research efforts that will render the best algorithms, architectures, implementations, and design practices. This paper aims to provide a concise perspective on designing architectures for efficient finite field arithmetic for usage in cryptography. We present different architectures, methods and techniques for fast execution of cryptographic operations as well as high utilization of resources in the realization of cryptographic algorithms. While it is difficult to have a complete coverage of all related work, this paper aims to reflect the current trends and important implementation issues of finite field arithmetic in the context of cryptography.

In this work, we consider detection of errors in polynomial, dual, and normal bases arithmetic operations. Error detection is performed by recomputing with the shifted operand method, while the operation unit is in use. This scheme is efficient for pipelined architectures, particularly systolic arrays. Additionally, one semisystolic multiplier for each of the polynomial, dual, type I, and type II optimal normal bases is presented. The results show that for having better or similar space and time overheads compared to a number of related previous work, the multipliers have generally a higher error-detection capability, e.g., the error-detection capability of the RESO-based scheme for single and multiple stuck-at faults in a polynomial basis multiplier is 100 percent. Finally, we also comment on how RESO can be used for concurrent error correction to deal with transient faults.

In this paper, a high-speed word level finite field multiplier in F2 m using redundant representation is proposed. For the class of fields that there exists a type I optimal normal basis, the new architecture has significantly higher speed compared to previously proposed architectures using either normal basis or redundant representation at the expense of moderately higher area complexity. One of the unique features of the proposed multiplier is that the critical path delay is not a function of the field size nor the word size. It is shown that the new multiplier outperforms all the other multipliers in comparison when considering the product of area and delay as a measure of performance. VLSI implementation of the proposed multiplier in a 0.18- mum complimentary metal-oxide-semiconductor (CMOS) process is also presented.

This paper presents a survey of hardware/software co-design implementations of elliptic curve cryptosystems. A critical study of the underlying finite field, the representation basis, and the partitioning schemes of these implementations is conducted. The study shows that all implementations are implemented over binary fields GF(2) and the implementations that use polynomial basis are more than implementations that use normal basis for finite field arithmetic. The study also shows that the best partitioning scheme, among the surveyed implementations

Successful implementation of elliptic curve cryptographic systems primarily depends on the efficient and reliable arithmetic circuits for finite fields with very large orders. Thus, the robust encryption/decryption algorithms are elegantly needed. Multiplication would be the most important finite field arithmetic operation. It is much more complex compared to the finite field addition. It is also frequently used in performing point operations in elliptic curve groups. The hardware implementation of a multiplication operation may require millions of logic gates and may thus lead to erroneous outputs. To obtain reliable cryptographic applications, a novel concurrent error detection (CED) architecture to detect erroneous outputs in multiplexer-based normal basis (NB) multiplier over GF(2 m ) using the parity prediction scheme is proposed in this article. Although various NB multipliers, depending on $$ \alpha \alpha^{{2^i }} = \sum\limits_{j = 0}^{m - 1} {t_{i,j} } \alpha^{{2^j }} $$ , have different time and space complexities, NB multipliers will have the same structure if they use a parity prediction function. By using the structure of the proposed CED NB multiplier, a CED scalable multiplier over composite fields with 100% error detection rate is also presented.

Finite field accumulation is the simplest of all the finite field operations, but at the same time, it is one of the most frequently encountered operations in finite field arithmetic. In this paper, we present a simple but highly useful modification of the conventional hardware implementation of accumulation in finite field over GF(2m) . The critical path, as well as, the hardware-complexity are reduced in the proposed design by performing the accumulation operation using m number of T flip-flops instead of using a combination of m number of XOR gates with equal number of D flip-flops in dependent loop structures. The conventional design is found to involve nearly 39% more area, 53% more delay, and 40% more maximum ac power consumption compared with the proposed accumulator. The proposed finite field accumulator is used further for the implementation of serial/parallel polynomial-basis finite field multiplication and bit-serial inter-conversion between polynomial basis representation and normal basis representation over GF(2m). The area-time complexity of the proposed bit-serial/parallel multiplier is less than half of the best of the corresponding existing structures. The structure proposed for digit-serial/parallel multiplication for trinomials is found to involve nearly 56% less area-time complexity compared with the best of the corresponding existing multipliers; and the existing design of bit-serial basis conversion is found to involve nearly twice area-time complexity compared with the proposed design using the proposed finite field accumulator.

Fault-based side-channel cryptanalysis is a useful technique against symmetrical and asymmetrical encryption/decryption algorithms. Thus, eliminating cryptographic computation errors become critical in preventing such kind of attacks. A simple way to eliminating cryptographic computation errors is to output correct or corrected ciphers. Multiplication is the most important finite field arithmetic operation in the cryptographic computations. By using time redundancy technique, a novel dual basis (DB) multiplier over Galois fields (2 m ) will be presented with lower space complexity and feedback-free property. Based on the proposed feedback-free DB multiplier, the DB multiplier with a concurrent error detection (CED) capability is also easily developed. Compared with the existing DB multiplier with CED capability, the proposed one saves about 90% of time-area complexity. No existing DB multiplier in the literature has concurrent error correction (CEC) capability. Based on the proposed DB multiplier, a novel DB multiplier with CEC capability is easily designed. The proposed DB multiplier with CEC capability requires only about 3% of extra space complexity and 15% of time complexity when compared with the proposed DB multiplier without CEC.

In this paper we consider the problem of constructing a small arithmetic circuit for a polynomial for which we have oracle access. Our focus is on n-variate polynomials, over a finite field F, that have depth-3 arithmetic circuits (with an addition gate at the top) with two multiplication gates of degree at most d. We obtain the following results: 1. Multilinear case: When the circuit is multilinear (multiplication gates compute multilinear polynomials) we give an algorithm that outputs, with probability 1 − o(1), all the depth-3 circuits with two multiplication gates computing the polynomial. The running time of the algorithm is poly(n, |F|). 2. General case: When the circuit is not multilinear we give a quasi-polynomial (in n, d, |F|) time algorithm that outputs, with probability 1 − o(1), a succinct representation of the polynomial. In particular, if the depth-3 circuit for the polynomial is not of small depth-3 rank (namely, after removing the g.c.d. of the two multiplication gates, the remaining linear functions span a not too small linear space) then we output the depth-3 circuit itself. In case that the rank is small we output a depth-3 circuit with a quasi-polynomial number of multiplication gates. Prior to our work there have been several interpolation algorithms for restricted models. However, all the techniques used there completely fail when dealing with depth-3 circuits with even just two multiplication gates. Our proof technique is new and relies on the factorization algorithm for multivariate black-box polynomials, on lower bounds on the length of linear locally decodable codes with 2 queries, and on a theorem regarding the structure of identically zero depth-3 circuits with four multiplication gates. ∗Preliminary version appeared in [Shp07]. †Faculty of Computer Science, Technion, Haifa 32000, Israel. Email: shpilka@cs.technion.ac.il. This research was supported by the Israel Science Foundation (grant number 439/06).

The hardware - software codesign of cryptosistems, is the best solution to reach a reasonable yield in systems with resources limitation. In the last years, the cryptosistems based on elliptic curves (CEE) have acquired an increasing importance, managing at present to form a part of the industrial standards. In the underlying finite field of an CEE squaring and field multiplication is the next computational costly operations other than field inversion. This paper presents an algorithm for multiplication in binary fields GF(2^m) using a polynomial basis representation and with interleaving reduction. The finite field multiplier operates over a variety of binary fields and it is scalable.

In the past two decades, some major efforts have been made to reduce exact (e.g. integer, rational, polynomial) linear algebra problems to matrix multiplication in order to provide algorithms with optimal asymptotic complexity. To provide efficient implementations of such algorithms one need to be careful with the underlying arithmetic. It is well known that modular techniques such as the Chinese remainder algorithm or the p -adic lifting allow very good practical performance, especially when word size arithmetic is used. Therefore, finite field arithmetic becomes an important core for efficient exact linear algebra libraries. In this article, we study high performance implementations of basic linear algebra routines over word size prime fields: especially matrix multiplication; our goal being to provide an exact alternate to the numerical BLAS library. We show that this is made possible by a careful combination of numerical computations and asymptotically faster algorithms. Our kernel has several symbolic linear algebra applications enabled by diverse matrix multiplication reductions: symbolic triangularization, system solving, determinant, and matrix inverse implementations are thus studied.

We present a method for computing pth roots using a polynomial basis over finite fields $${\mathbb F_q}$$ of odd characteristic p, p ? 5, by taking advantage of a binomial reduction polynomial. For a finite field extension $${\mathbb F_{q^m}}$$ of $${\mathbb F_q}$$ our method requires p ? 1 scalar multiplications of elements in $${\mathbb F_{q^m}}$$ by elements in $${\mathbb F_q}$$ . In addition, our method requires at most $${(p-1)\lceil m/p \rceil}$$ additions in the extension field. In certain cases, these additions are not required. If z is a root of the irreducible reduction polynomial, then the number of terms in the polynomial basis expansion of z 1/p , defined as the Hamming weight of z 1/p or $${{\rm wt}\left(z^{1/p} \right)}$$ , is directly related to the computational cost of the pth root computation. Using trinomials in characteristic 3, Ahmadi et al. (Discrete Appl Math 155:260---270, 2007) give $${{\rm wt}\left(z^{1/3} \right)}$$ is greater than 1 in nearly all cases. Using a binomial reduction polynomial over odd characteristic p, p ? 5, we find $${{\rm wt}\left(z^{1/p}\right) = 1}$$ always.

This paper aims at surveying multipliers based on Horner's rule for finite field arithmetic. We present a generic architecture based on five processing elements and introduce a classification of several algorithms based on our model. We provide the readers with a detailed description of each scheme which should allow them to write a VHDL description or a VHDL code generator.

In this paper, we extend previously known results on the complexities of normal elements. Using algorithms that exhaustively test field elements, we are able to provide the distribution of the complexity of normal elements for binary fields with degree extensions up to 39. We also provide current results on the smallest known complexity for the remaining degree extensions up to 512 by using a combination of constructive theorems and known exact values. We give an algorithm to exhaustively search field elements by using Gray codes, which allows us to reuse previous computations. We compare this with a standard method. We analyze this algorithm and show both experimentally and asymptotically that the Gray code optimization gives substantial savings. The total computation of the distribution of the complexity of normal elements for degrees up to 39 in our experiments allows us to draw several conjectures. In particular, our data provides remarkable evidence for the conjecture that the complexity of normal elements follows a normal distribution. Finally, we conjecture that there is no linear bound on the minimum complexity with respect to the degree of the extension.

In this contribution, we introduce a low-complexity bit-parallel algorithm for computing square roots over binary extension fields. Our proposed method can be applied to any type of irreducible polynomials. We derive explicit formulas for the space and time complexities associated with the square root operator when working with binary extension fields generated using irreducible trinomials. We show that, for those finite fields, it is possible to compute the square root of an arbitrary field element with equal or better hardware efficiency than the one associated with the field squaring operation. Furthermore, a practical application of the square root operator in the domain of field exponentiation computation is presented.

We investigate the efficiency of implementing the Jao and De Feo isogeny-based post-quantum key exchange protocol (from PQCrypto 2011) on ARM-powered embedded platforms. In this work we propose new primes to speed up constant-time finite field arithmetic and perform isogenies quickly. Montgomery multiplication and reduction are employed to produce a speedup of 3 over the GNU Multiprecision Library. We analyze the recent projective isogeny formulas presented in Costello et al. (Crypto 2016) and conclude that affine isogeny formulas are much faster in ARM devices. We provide fast affine SIDH libraries over 512, 768, and 1024-bit primes. We provide timing results for emerging embedded ARM platforms using the ARMv7A architecture for the 85-, 128-, and 170-bit quantum security levels. Our assembly-optimized arithmetic cuts the computation time for the protocol by 50 % in comparison to our portable C implementation and performs approximately 3 times faster than the only other ARMv7 results found in the literature. The goal of this paper is to show that isogeny-based cryptosystems can be implemented further and be used as an alternative to classical cryptosystems on embedded devices.

Finite field arithmetic operations have received much attention in error-control codes, cryptography, etc. Among the basic arithmetic operations over \(GF(2^{m})\), the multiplication is the most important, complex, and time consuming. In this paper, we present a low-latency finite field arithmetic algorithm for multiplication which is a core algorithm for division and exponentiation operations. In order to obtain a dedicated pipelined algorithm for finite field multiplication based on all-one polynomial, we split its computation into two parts, design the algorithm to simultaneously compute them, and reduce computation delay. Also, we show the detailed derivation process in order to obtain the proposed algorithm for the pipelined computation. Therefore, the proposed algorithm can lead to a hardware architecture which has a considerably low latency. The multiplier applying the proposed algorithm will be a highly modular architecture and be thus well suited for VLSI implementations.

We propose a novel area/time efficient elliptic curve cryptography (ECC) processor architecture which performs all finite field arithmetic operations in the discrete Fourier domain. The proposed architecture utilizes a class of optimal extension fields (OEF) GF(qm) where the field characteristic is a Mersenne prime q = 2n - 1 and m = n. The main advantage of our architecture is that it achieves extension field modular multiplication in the discrete Fourier domain with only a linear number of base field GF(q) multiplications in addition to a quadratic number of simpler operations such as addition and bitwise rotation. We achieve an area between 25k and 50k equivalent gates for the implementations over OEFs of size 169, 289 and 361 bits. With its low area and high speed, the proposed architecture is well suited for ECC in small device environments such as sensor networks. The work at hand presents the first hardware implementation of a frequency domain multiplier suitable for ECC and the first hardware implementation of ECC in the frequency domain.