Search

Multiplications in G F ( 2 N ) can be securely optimized for cryptographic applications when the integer N is small and does not match machine words (i.e., N < 32 ). In this paper, we present a set of optimizations applied to DAGS, a code-based post-quantum cryptographic algorithm and one of the submissions to the National Institute of Standards and Technology’s (NIST) Post-Quantum Cryptography (PQC) standardization call.

Intel and AMD support the carry-less multiplication (CLMUL) instruction set in their x64 processors. We use CLMUL to implement an almost universal 64-bit hash family ( CLHASH). We compare this new family with what might be the fastest almost universal family on x64 processors ( VHASH). We find that CLHASH is at least 60 % faster. We also compare CLHASH with a popular hash function designed for speed (Google's CityHash). We find that CLHASH is 40 % faster than CityHash on inputs larger than 64 bytes and just as fast otherwise. [ABSTRACT FROM AUTHOR]

The architecture and the implementation of a high-performance scalable elliptic curve cryptography processor (ECP) are presented. The proposed ECP is able to support all five prime field elliptic curves recommended by the National Institute of Standards and Technology (NIST). The design takes advantage of the high-performance capabilities of the DSP48E slices available in Xilinx field-programmable gate arrays (FPGAs) to achieve high speed and low hardware resource utilization. The proposed design parallelizes the underlying prime field operations to reduce the latency of the elliptic curve point multiplication (ECPM) operation. Prime field inversion is performed efficiently using the same arithmetic blocks as the ones used for prime field multiplication and addition/subtraction. To the best of the authors' knowledge, the proposed scalable ECP is the fastest and smallest ECP that can support all five NIST recommended prime curves without the need to reconfigure the hardware. It can compute the ECPM between 1.709 and 28.04 ms using a Xilinx Virtex-5 FPGA. [ABSTRACT FROM PUBLISHER]

Elliptic curve cryptosystems (ECC) are becoming more and more popular and are included in many standards, as they offer high security strength when compared with other conventional public-key cryptosystems, for the same key length. But the security strength of hardware implementations of ECC is challenged by side channel attacks (SCA) such as power analysis. Reversible logic circuits ideally consume zero energy, which serves as the motivation to implement cryptographic algorithms against power analysis attacks. This paper proposes two new hardware architectures for performing montgomery multiplication in GF(p) and GF(2m), as they are the power consuming operations in ECC. The two architectures are optimized to reduce the hardware cost and they are then implemented in reversible logic with reduced number of quantum cost. In this work, the reversible logic synthesis is performed with Toffoli family of reversible gates. The performance metrics of all the multipliers are analyzed and properly tabulated. Scalar multiplication on elliptic curve points, which is the core operation used in every elliptic curve cryptosystem, has been implemented in reversible logic by using the proposed reversible montgomery multipliers. [ABSTRACT FROM AUTHOR]

One of the most cost-critical operations when applying Shor's algorithm to binary elliptic curves is the underlying field arithmetic. Here, we consider binary fields $${\mathbb {F}}_{2^n}$$ in polynomial basis representation, targeting especially field sizes as used in elliptic curve cryptography. Building on Karatsuba's algorithm, our software implementation automatically synthesizes a multiplication circuit with the number of $$T$$ -gates being bounded by $$7\cdot n^{\log _2(3)}$$ for any given reduction polynomial of degree $$n=2^N$$ . If an irreducible trinomial of degree $$n$$ exists, then a multiplication circuit with a total gate count of $${\mathcal {O}}(n^{\log _2(3)})$$ is available. [ABSTRACT FROM AUTHOR]

This paper presents a comprehensive study of the computation of square roots over finite extension fields. We propose two novel algorithms for computing square roots over even field extensions of the form \BBF{q^2}, with q = p^n, p an odd prime and n \geq 1. Both algorithms have an associate computational cost roughly equivalent to one exponentiation in \BBF{q^2}. The first algorithm is devoted to the case when q \equiv 1\, mod\, 4, whereas the second one handles the case when q \equiv 3\, mod\,4. Numerical comparisons show that the two algorithms presented in this paper are competitive and in some cases more efficient than the square root methods previously known. [ABSTRACT FROM AUTHOR]

In this work, we present new arithmetic formulas for a projective version of the affine point representation $$(x,x+y/x),$$ for $$x\ne 0,$$ which leads to an efficient computation of the scalar multiplication operation over binary elliptic curves. A software implementation of our formulas applied to a binary Galbraith-Lin-Scott elliptic curve defined over the field $$\mathbb {F}_{2^{254}}$$ allows us to achieve speed records for protected/unprotected single/multi-core random-point elliptic curve scalar multiplication at the 127-bit security level. When executed on a Sandy Bridge 3.4 GHz Intel Xeon processor, our software is able to compute a single/multi-core unprotected scalar multiplication in 69,500 and 47,900 clock cycles, respectively, and a protected single-core scalar multiplication in 114,800 cycles. These numbers are improved by around 2 and 46 % on the newer Ivy Bridge and Haswell platforms, respectively, achieving in the latter a protected random-point scalar multiplication in 60,000 clock cycles. [ABSTRACT FROM AUTHOR]

We present a new algorithm for computing m-th roots over the finite field Fq, where q = pn, with p a prime, and m any positive integer. In the particular case m = 2, the cost of the new algorithm is an expected O(M(n) log(p) + C(n) log(n)) operations in Fp, where M(n) and C(n) are bounds for the cost of polynomial multiplication and modular polynomial composition. Known results give M(n) = O(n log(n) log log(n)) and C(n) = O(n1.67), so our algorithm is subquadratic in n. [ABSTRACT FROM AUTHOR]

Abstract: We present a bit-parallel polynomial basis multiplier based on a new divide-and-conquer approach using squaring. In particular, we apply the proposed approach to special types of irreducible pentanomials called as types I and II pentanomials, and induce explicit formulae and complexities of the proposed multiplier for these types of pentanomials. As a result, the proposed multiplier for type I pentanomials has almost the same time complexity, but about 25% reduced space complexity compared with the best known results in the literature. For type II pentanomials, we obtain the multiplier which has the lowest time complexity and about 25% reduced space complexity than the best known polynomial basis multipliers. [Copyright &y& Elsevier]

Copyright of Visión Electrónica is the property of Fondo de Universidad Distrital Francisco Jose de Caldas and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Abstract: A scalable elliptic curve cryptography (ECC) processor is presented in this paper. The proposed ECC processor supports all five Koblitz curves recommended by the National Institute of Standards and Technology (NIST) without the need to reconfigure the FPGA. The paper proposes a finite field arithmetic unit (FFAU) that reduces the number of clock cycles required to compute the elliptic curve point multiplication (ECPM) operation for ECC. The paper also presents an improved point addition (PADD) algorithm to take advantage of the novel FFAU architecture. A scalable ECC processor (ECP) that is completely implemented in hardware that makes use of the novel PADD algorithm and FFAU is also presented in this paper. The design is synthesized and implemented for a target Virtex-4 XC4VFX12 FPGA. It uses 2431 slices, 1219 slice registers, 3815 four-input look-up tables (LUT) and can run at a maximum frequency of 155.376MHz. The proposed design is the fastest scalable ECP that supports all five Koblitz curves known to the authors as it evaluates the ECPM for K-163 in 0.273ms, K-233 in 0.604ms, K-283 in 0.735ms, K-409 in 1.926ms and K-571 in 4.335ms. The proposed design is suitable for server-side security applications where both high-speed and scalability are important design factors. [Copyright &y& Elsevier]

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(2n) with the type 4 GNB can be embedded into fields with an ONB. [ABSTRACT FROM AUTHOR]

Abstract: Finite field arithmetic is becoming increasingly important for a variety of different applications including cryptography, error coding theory and computer algebra. Among finite field arithmetic operations, multiplication is of special interest because it is considered the most important building block. multipliers present reduced space and time complexities when the field is generated by some special irreducible polynomials. Among these, irreducible pentanomials of degree m are specially important because they are abundant and there are several eligible candidates for a given m. In this paper, we consider bit-parallel polynomial basis multipliers over the finite field generated using type 2 irreducible pentanomials, for which explicit formulas and algorithms for the computation of the products are given. In this contribution, two new subclasses of type 2 irreducible pentanomials are also introduced. The theoretical complexity analysis proves that the bit-parallel multipliers here presented have the lowest number of XOR gates known to date for similar polynomial basis multipliers based on this type of irreducible pentanomials, while the number of AND gates and the time complexity match the best known results found in the literature. [Copyright &y& Elsevier]

The increasing importance of security in computers and communication systems introduces the need for several public-key cryptosystems. The modular division and multiplication arithmetic operations in GF (p) and GF (2") are extensively used in many public key cryptosystems, such as E1-Gamal cryptosystem, Elliptic Curve Cryptography (ECC), and the Elliptic Curve Digital Signature Algorithm (ECDSA). Processing these cryptosystems involves complicated computations, therefore, it is recommended to develop specialized hardware to speed up these computations. In this work, we propose efficient hardware design to compute both operations (division and multiplication) in the binary extension finite filed (GF (2"). The common points in both operations are utilized in our design to reduce the design area and delay, making the proposed architecture faster than other previously proposed designs. The FPGA implementation of the proposed design shows better results compared with other designs in this field. [ABSTRACT FROM AUTHOR]

Abstract: I present a new method to compute a bit-parallel polynomial basis squarer for generated by an arbitrary irreducible polynomial using weakly dual basis. I apply the proposed method to irreducible pentanomial and derive the explicit formulae for squarer. It is the first time that gives the explicit formulae and an upper complexity bound of squarer for irreducible pentanomials. Moreover, such formulae permit one to choose pentanomial for any odd whose multiplier, as well as squarer, can be performed more efficiently. [Copyright &y& Elsevier]

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(232) to GF(2128). 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(264), HAIL improves its performance by a factor of two, while simultaneously providing a higher level of security. [ABSTRACT FROM AUTHOR]

In this paper, we present a new method to compute the Mastrovito matrix for GF(2^m) 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 x^m+x^k3+x^{k2}+x^{k1}+1 with k1 < k2 \leq (k1+k3)/2 < k3 < \min (2k1,m/2). As a result, the time complexity of the proposed multiplier matches or outperforms the previously known results. On the other hand, the number of XOR gates of the proposed multiplier is slightly greater than the best known results. [ABSTRACT FROM AUTHOR]

Abstract: Since their introduction in constructive cryptographic applications, pairings over (hyper)elliptic curves are at the heart of an ever increasing number of protocols. As they rely critically on efficient implementations of pairing primitives, the study of hardware accelerators has become an active research area. In this paper, we propose two coprocessors for the reduced pairing introduced by Barreto et al. as an alternative means of computing the Tate pairing on supersingular elliptic curves. We prototyped our architectures on FPGAs. According to our place-and-route results, our coprocessors compare favorably with other solutions described in the open literature. We eventually present the first ASIC implementation of the reduced pairing. [Copyright &y& Elsevier]

In this paper, a high-speed word level finite field multiplier in F2m 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-μm complimentary metal-oxide-semiconductor (CMOS) process is also presented. [ABSTRACT FROM AUTHOR]

Abstract: Systolic arrays for multiplication in of Yeh et al. with LSB (least significant bit) first algorithm have the unfavorable properties such as increased area complexity and bidirectional data flows compared with the arrays of Wang and Lin with MSB (most significant bit) first algorithm. In this paper, by using a polynomial basis with LSB first algorithm, we present new bit parallel and bit serial systolic arrays over . Our bit parallel systolic multiplier has unidirectional data flows with seven latches in each basic cell. Also our bit serial systolic array has only one control signal with eight latches in each basic cell. Thus our new arrays with LSB first algorithm have shorter critical path delay, comparable hardware complexity, and have the same unidirectional data flows compared with the arrays using MSB first algorithm. We also present new linear systolic arrays for multiplication in using irreducible trinomial . It is shown that our linear arrays with trinomial basis have reduced hardware complexity since they require two fewer latches than the linear systolic arrays using general irreducible polynomials. [Copyright &y& Elsevier]

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. [ABSTRACT FROM PUBLISHER]

Since their introduction in constructive cryptographic applications, pairings over (hyper)elliptic curves are at the heart of an ever increasing number of protocols. With software implementations being rather slow, the study of hardware architectures became an active research area. In this paper, we discuss several algorithms to compute the ηT pairing in characteristic three and suggest further improvements. These algorithms involve addition, multiplication, cubing, inversion, and sometimes cube root extraction over IF3m. We propose a hardware accelerator based on a unified arithmetic operator able to perform the operations required by a given algorithm. We describe the implementation of a compact coprocessor for the field IF397 given by IF3[x]/(x97 + x12 + 2), which compares favorably with other solutions described in the open literature. [ABSTRACT FROM AUTHOR]

A novel serial-in parallel-out finite field multiplier using redundant representation is proposed. It is shown that the proposed architecture has either a significantly lower complexity and comparable critical path delay or a significantly smaller critical path delay and comparable complexity in comparison to the previously proposed architectures using the same representation. For the class of fields where there exists a type I optimal normal basis, the proposed multiplier compares favorably to the normal basis multipliers. A digit-level version for the new multiplier is also presented in this paper. [ABSTRACT FROM AUTHOR]

Elliptic curve cryptography is a very promising cryptographic method offering the same security level as traditional public key cryptosystems (RSA, El Gamal) but with considerably smaller key lengths. However, the computational complexity and hardware resources of an elliptic curve cryptosystem are very high and depend on the efficient design of EC point operations and especially point multiplication. Those operations, using the elliptic curve group law, can be analyzed in operations of the underlined GF(2 k ) Field. Three basic GF(2 k ) Field operations exist, addition–subtraction, multiplication and inversion–division. In this paper, we propose an optimized inversion algorithm that can be applied very well in hardware avoiding well known inversion problems. Additionally, we propose a modified version of this algorithm that apart from inversion can perform multiplication using the architectural structure of inversion. We design two architectures that use those algorithms, a two-dimensional multiplication/inversion systolic architecture and an one-dimensional multiplication/inversion systolic architecture. Based on either one of those proposed architectures a GF(2 k ) arithmetic unit is also designed and used in a EC arithmetic unit that can perform all EC point operations required for EC cryptography. The EC arithmetic unit’s design methodology is proposed and analyzed and the effects of utilizing the one or two-dimensional multiplication/inversion systolic architecture are considered. The performance of the system in all its design steps is analyzed and comparisons are made with other known designs. We manage to design a GF(2 k ) arithmetic unit that has the space and time complexity of an inverter but can perform all GF(2 k ) operations and we show that this architecture can apply very well to an EC arithmetic unit required in elliptic curve cryptography. [Copyright &y& Elsevier]

Abstract: We determine the number of nonzero coefficients (called the Hamming weight) in the polynomial representation of in , where is an irreducible trinomial. [Copyright &y& Elsevier]

In this paper, we present a bit-parallel multiplier for GF(2m) defined by an irreducible pentanomial ixm + xk3 + xk2 + xk1 + 1, where 1 ≤ k1 < k2 < k3 ≤ m/2. In order to design an efficient bit-parallel multiplier, we introduce a shifted polynomial basis and modify a reduction matrix presented by Reyhani-Masoleh and Hasan. As a result, the time complexity of the proposed multiplier is TA + (3 + [log2(m - 1)])Tx, where TA and Tx are the delay of one AND and one XOR gate, respectively. This result matches or outperforms the previously known results. On the other hand, the proposed multiplier has the same space complexity as the previously known multipliers except for special types of irreducible pentanomials. Note that its hardware architecture is similar to that presented by Reyhani-Masoleh and Hasan. [ABSTRACT FROM AUTHOR]

In this paper, we propose a complete set of algorithms for the arithmetic operations in finite fields of prime medium characteristic. The elements of the fields ...pk are represented using the newly defined Lagrange representation, where polynomials are expressed using their values at sufficiently many points. Our multiplication algorithm, which uses a Montgomery approach, can be implemented in O(k) multiplications and O(k² log k) additions in the base field ...p. For the inversion, we propose a variant of the extended Euclidean GCD algorithm, where the inputs are given in the Lagrange representation. The Lagrange representation scheme and the arithmetic algorithms presented in the present work represent an interesting alternative for elliptic curve cryptography. [ABSTRACT FROM AUTHOR]

Partitioning techniques enable identification of fault-embedding scan cells in scan-based BIST. We introduce, in this paper, deterministic partitioning techniques capable of resolving the location of the fault-embedding scan cells. We outline a complete mathematical analysis that identifies the class of deterministic partitioning structures and complement this rigorous mathematical analysis with an exposition of the appropriate cost-effective implementation techniques. We validate the superiority of the deterministic techniques both in an average-case sense by conducting simulation experiments and in a worst-case sense through a thorough mathematical analysis. [ABSTRACT FROM AUTHOR]

Abstract: Using a new reformulation of the extended Euclidean algorithm, we propose new two-dimensional systolic architectures for inversion in . Our new architectures require considerably less hardware in comparison to the architectures we proposed recently, while achieving the same critical path delays, latencies, and throughputs. Our new architectures compare even more favorably to the inversion architectures proposed previously by others. In common with much previous work in this area, one of our new architectures uses a centralized control mechanism. The other new architecture proposed in this paper uses a distributed control mechanism which results in all the cells in our architecture having the same circuitry regardless of the value of m. Hence the latter new architecture has excellent scalability properties. [Copyright &y& Elsevier]

A fast parallel architecture for the implementation of elliptic curve scalar multiplication over binary fields is presented. The proposed architecture is implemented on a single-chip FPGA device using parallel strategies that trades area requirements for timing performance. The results achieved show that our proposed design is able to compute GF(2191) elliptic curve scalar multiplication operations in 63 μs. [Copyright &y& Elsevier]