Modular exponentiation, or scalar multiplication, is core to today's main stream public key cryptographic systems. In this article we generalize the classical fractional wNAF method for modular exponentiation - the classical method uses a digit set of the form {1, 3, . . . , m} which is extended here to any set of odd integers of the form {1, d2, . . . , dn}. We propose a general modular exponentiation algorithm based on a generalization of the frac-wNAF recoding and a new precomputation scheme. We also give general formula for the average density of non-zero therms in these representations, prove that there are infinitely many optimal sets for a given number of digits and show that the asymptotic behavior, when those digits are randomly chosen, is very close to the optimal case.

Security and privacy are growing concerns in modern embedded software, given the increasing level of connectivity as well as complexity and features in embedded devices. Use of cryptographic techniques is often a requirement on which the security of the device relies. However, important challenges arise when potential attackers have physical access to the device. Side-channel analysis, including simple power analysis (SPA), is a class of powerful non-intrusive attacks that are suitable for adversaries with physical access to the device. Countermeasures exist, but they typically involve a considerable performance penalty, and some of them in turn introduce a vulnerability to induced fault attacks. In this work, we present several new efficient cryptographic exponentiation algorithms that work by splitting the exponent in two halves for simultaneous processing while using special representations derived from signed-digit encoding that improve computational efficiency. A key detail in the design of these algorithms is that they are compatible with the idea of buffering the operations to provide resistance to SPA. Experimental results are presented, including implementations of the proposed methods with both modular integer exponentiation and elliptic curve (ECC) scalar multiplication. We also performed statistical analysis of the traces, showing that trace segments for different exponent bits are statistically indistinguishable. Our proposed techniques also exhibit better resistance against fault attacks and combined fault and side-channel attacks, compared to previous SPA-resistant techniques.

In this paper we present efficient algorithms to take advantage of the double-base number system in the context of elliptic curve scalar multiplication. We propose a generalized version of Yao's exponentiation algorithm allowing the use of general double-base expansions instead of the popular double base chains. We introduce a class of constrained double base expansions and prove that the average density of non-zero terms in such expansions is O( log k/ log log k) for any large integer k. We also propose an efficient algorithm for computing constrained expansions and finally provide a comprehensive comparison to double-base chain expansions, including a large variety of curve shapes and various key sizes.

Increasingly more and more organizations are opting for outsourcing data to remote cloud service providers (CSPs). Customers can rent the CSPs storage infrastructure to store and retrieve almost unlimited amount of data by paying fees metered in gigabyte/month. For an increased level of scalability, availability, and durability, some customers may want their data to be replicated on multiple servers across multiple data centers. The more copies the CSP is asked to store, the more fees the customers are charged. Therefore, customers need to have a strong guarantee that the CSP is storing all data copies that are agreed upon in the service contract, and all these copies are consistent with the most recent modifications issued by the customers. In this paper, we propose a map-based provable multicopy dynamic data possession (MB-PMDDP) scheme that has the following features: 1) it provides an evidence to the customers that the CSP is not cheating by storing fewer copies; 2) it supports outsourcing of dynamic data, i.e., it supports block-level operations, such as block modification, insertion, deletion, and append; and 3) it allows authorized users to seamlessly access the file copies stored by the CSP. We give a comparative analysis of the proposed MB-PMDDP scheme with a reference model obtained by extending existing provable possession of dynamic single-copy schemes. The theoretical analysis is validated through experimental results on a commercial cloud platform. In addition, we show the security against colluding servers, and discuss how to identify corrupted copies by slightly modifying the proposed scheme.

Some applications like cryptography involve a large number of multiplications of binary polynomial. In this paper, we consider two-, three-, and four-way methods for parallel implementation of binary polynomial multiplication. We propose optimized three- and four-way split formulas which reduce the space and time complexity of the best known methods. Moreover, we present a block recombination method which provides some further reduction in the space complexity of the considered two-, three-, and four-way split multipliers.

One of the hardest aspects of embedded software development is that of debugging, especially when faulty behavior is observed at the production or deployment stage. Non-intrusive observation of the system's behavior is often insufficient to infer the cause of the problem and identify and fix the bug. In this work, we present a novel approach for non-intrusive program tracing aimed at assisting developers in the task of debugging embedded systems at deployment or production stage, where standard debugging tools are usually no longer available. The technique is rooted in cryptography, in particular the area of side-channel attacks. Our proposed technique expands the scope of these cryptographic techniques so that we recover the sequence of operations from power consumption observations (power traces). To this end, we use digital signal processing techniques (in particular, spectral analysis) combined with pattern recognition techniques to determine blocks of source code being executed given the observed power trace. One of the important highlights of our contribution is the fact that the system works on a standard PC, capturing the power traces through the recording input of the sound card. Experimental results are presented and confirm that the approach is viable.

In this paper, we propose new schemes for subquadratic arithmetic complexity multiplication in binary fields using optimal normal bases. The schemes are based on a recently proposed method known as block recombination, which efficiently computes the sum of two products of Toeplitz matrices and vectors. Specifically, here we take advantage of some structural properties of the matrices and vectors involved in the formulation of field multiplication using optimal normal bases. This yields new space and time complexity results for corresponding bit parallel multipliers.

In this paper, we consider three-way split formulas for binary polynomial multiplication and Toeplitz matrix vector product (TMVP). We first recall the best known three-way split formulas for polynomial multiplication: the formulas with six recursive multiplications given by Sunar in a 2006 IEEE Transactions on Computers paper and the formula with five recursive multiplications proposed by Bernstein at CRYPTO 2009. Second, we propose a new set of three-way split formulas for polynomial multiplication that are an optimization of Sunar's formulas. Then, we present formulas with five recursive multiplications based on field extension. In addition, we extend the latter formulas to TMVP. We evaluate the space and delay complexities when computations are performed in parallel and provide a comparison with best known methods.

Computing the product of a Toeplitz matrix and a vector arises in various applications including cryptography. In this paper, we consider Toeplitz matrices and vectors with entries in $({\hbox{\rlap{I}\kern 2.0pt{\hbox{F}}}}_2)$. For improved efficiency in such computations, large Toeplitz matrices and vectors are recursively split and special formulas with subquadratic arithmetic complexity are applied. To this end, we first present a formula for the five-way splitting and then provide a generalization for the $(k)$-way splitting, where $(k)$ is an arbitrary integer. These formulas can be used to compute a Toeplitz matrix-vector product (TMVP) of size $(n)$ with an arithmetic complexity of $(O(n^{\log_k(k(k+1)/2)}))$.

Outsourcing data to the cloud are beneficial for reasons of economy, scalability, and accessibility, but significant technical challenges remain. Sensitive data stored in the cloud must be protected from being read in the clear by a cloud provider that is honest-but-curious. Additionally, cloud-based data are increasingly being accessed by resource-constrained mobile devices for which the processing and communication cost must be minimized. Novel modifications to attribute-based encryption are proposed to allow authorized users access to cloud data based on the satisfaction of required attributes such that the higher computational load from cryptographic operations is assigned to the cloud provider and the total communication cost is lowered for the mobile user. Furthermore, data re-encryption may be optionally performed by the cloud provider to reduce the expense of user revocation in a mobile user environment while preserving the privacy of user data stored in the cloud. The proposed protocol has been realized on commercially popular mobile and cloud platforms to demonstrate real-world benchmarks that show the efficacy of the scheme. A simulation calibrated with the benchmark results shows the scalability potential of the scheme in the context of a realistic workload in a mobile cloud computing system.

Storage-as-a-service offered by cloud service providers (CSPs) is a paid facility that enables organizations to outsource their sensitive data to be stored on remote servers. In this paper, we propose a cloud-based storage scheme that allows the data owner to benefit from the facilities offered by the CSP and enables indirect mutual trust between them. The proposed scheme has four important features: 1) it allows the owner to outsource sensitive data to a CSP, and perform full block-level dynamic operations on the outsourced data, i.e., block modification, insertion, deletion, and append, 2) it ensures that authorized users (i.e., those who have the right to access the owner's file) receive the latest version of the outsourced data, 3) it enables indirect mutual trust between the owner and the CSP, and 4) it allows the owner to grant or revoke access to the outsourced data. We discuss the security issues of the proposed scheme. Besides, we justify its performance through theoretical analysis and a prototype implementation on Amazon cloud platform to evaluate storage, communication, and computation overheads.

For an increased level of scalability, availability and durability, some customers may want their data to be replicated on multiple cloud servers. The more copies the cloud service provider (CSP) is asked to store, the more fees the customers are charged. In this paper, we propose a pairing-based provable multi-copy data possession (PB-PMDP) scheme, which provides an evidence to the customers that all outsourced copies are actually stored and remain intact. Moreover, it allows authorized users (i.e., those who have the right to access the owner's file) to seamlessly access the file copies stored by the CSP, and supports public verifiability. The proposed scheme is proved to be secure against colluding servers. We illustrate the performance of the PB-PMDP scheme through theoretical analysis, which is validated by experimental results. The verification time of our scheme is practically independent of the number of file copies. Additionally, we discuss how to identify corrupted copies by slightly modifying the proposed PB-PMDP scheme.

In this paper, we present a new method for parallel binary finite field multiplication which results in subquadratic space complexity. The method is based on decomposing the building blocks of the Fan-Hasan subquadratic Toeplitz matrix-vector multiplier. We reduce the space complexity of their architecture by recombining the building blocks. In comparison to other similar schemes available in the literature, our proposal presents a better space complexity while having the same time complexity. We also show that block recombination can be used for efficient implementation of the GHASH function of Galois Counter Mode (GCM).

In the recent past, subquadratic space complexity multipliers have been proposed for binary fields defined by irreducible trinomials and some specific pentanomials. For such multipliers, alternative irreducible polynomials can also be used, in particular, nearly all one polynomials (NAOPs) seem to be better than pentanomials. For improved efficiency, multiplication modulo an NAOP is performed via modulo a quadrinomial whose degree is one more than that of the original NAOP. In this paper, we present a Toeplitz matrix-vector product based approach for multiplication modulo a quadrinomial. We obtain a fully parallel multiplier with a subquadratic space complexity. The Toeplitz matrix-vector product-based approach is also interesting in the design of sequential multipliers. We present two such multipliers that process a two-bit digit every clock cycle. Field-programmable gate-array implementations of the proposed sequential as well as fully parallel multipliers for the field size of 163 are also presented.

We study Dickson bases for binary field representation. Such a representation seems interesting when no optimal normal basis exists for the field. We express the product of two field elements as Toeplitz or Hankel matrix-vector products. This provides a parallel multiplier which is subquadratic in space and logarithmic in time. Using the matrix-vector formulation of the field multiplication, we also present sequential multiplier structures with linear space complexity.

In the recent past, subquadratic space complexity multipliers have been proposed for binary fields defined by irreducible trinomials and some specific pentanomials. For such multipliers, alternative irreducible polynomials can also be used, in particular, nearly all one polynomials (NAOPs) seem to be better than pentanomials (see [7]). For improved efficiency, multiplication modulo an NAOP is performed via modulo a quadrinomial whose degree is one more than that of the original NAOP. In this paper, we present a Toeplitz matrix-vector product based approach for multiplication modulo a quadrinomial. We obtain a fully parallel (nonsequential) multiplier with a subquadratic space complexity, which has the same order of space complexity as that of Fan and Hasan. The Toeplitz matrix-vector product based approach is also interesting in the design of sequential multipliers. In this paper, we present two such multipliers: one with bit serial output and the other bit parallel output.

A new approach to subquadratic space complexity GF(2n) multipliers has been proposed recently. The corresponding algorithm for software implementations is developed. While its recursive implementation is as simple as that of the Karatsuba algorithm, it requires much less memory to store the look-up table. Therefore it is quite suitable for memory-constrained applications, for example smart cards.

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.

For some applications, elliptic curve cryptography (ECC) is an attractive choice because it achieves the same level of security with a much smaller key size in comparison with other schemes such as those that are based on integer factorization or discrete logarithm. For security reasons, especially to provide resistance against fault-based attacks, it is very important to verify the correctness of computations in ECC applications. In this paper, error-detecting and fault-tolerant elliptic curve cryptosystems are considered. Error detection may be a sufficient countermeasure for many security applications; however, fault-tolerant characteristic enables a system to perform its normal operation in spite of faults. For the purpose of detecting errors due to faults, a number of schemes and hardware structures are presented based on recomputation or parallel computation. It is shown that these structures can be used for detecting errors with a very high probability during the computation of the elliptic curve scalar multiplication (ECSM). Additionally, we show that using parallel computation along with either PV or recomputation, it is possible to have fault-tolerant structures for the ECSM. If certain conditions are met, these schemes are more efficient than others such as the well-known triple modular redundancy. Prototypes of the proposed structures for error detection and fault tolerance have been implemented, and experimental results have been presented.

A high performance architecture of elliptic curve scalar multiplication based on the Montgomery ladder method over finite field GF(2m) is proposed. A pseudo-pipelined word serial finite field multiplier with word size w, suitable for the scalar multiplication is also developed. Implemented in hardware, this system performs a scalar multiplication in approximately 6⌈m/w⌉(m−1) clock cycles and the gate delay in the critical path is equal to TAND + ⌈log2(w/k)⌉TXOR, where TAND and TXOR are delays due to two-input AND and XOR gates respectively and 1 ≤ k ≪ w is used to shorten the critical path.

We present efficient squaring formulae based on the Toom-Cook multiplication algorithm. The latter always requires at least one non-trivial constant division in the interpolation step. We show such non-trivial divisions are not needed in the case two operands are equal for three, four and five-way squarings. Our analysis shows that our 3-way squaring algorithms have much less overhead than the best known 3-way Toom-Cook algorithm. Our experimental results show that one of our new 3-way squaring methods performs faster than mpz_mul ( ) in GNU multiple precision library (GMP) for squaring integers of approximately 2400-6700 bits on Pentium IV Prescott 3.2 GHz. For squaring in Z[x], our 3-way squaring algorithms are much superior to other known squaring algorithms for small input size. In addition, we present 4-way and 5-way squaring formulae which do not require any constant divisions by integers other than a power of 2. Under some reasonable assumptions, our 5-way squaring formula is faster than the recently proposed Montgomery's 5-way Karatsuba-like formulae.

In this paper, we extend a recent piece of work on low-weight polynomial form integers (LWPFIs). We present a new coefficient reduction algorithm based on the Montgomery reduction algorithm and provide its detailed analysis results. We give a condition for eliminating the final subtractions at the end of our Montgomery reduction algorithm adapted to perform the coefficient reduction. Our experimental results show that a new coefficient reduction algorithm is indeed more efficient than the one presented in [1].

In this article we consider detection of errors in polynomial basis multipliers, which have applications in channel coding, VLSI testing, and cryptography. Error detection is performed by applying a class of linear codes while the multiplier is in use. In this article, two error detection schemes are presented. Results show that the probability of error detection of our single-input encoding (SIE) scheme using eight redundant bits is approximately 0.996. Additionally, the time and area overheads of the schemes for our bit-serial implementations are in a reasonable range, e.g., for the SIE scheme with eight redundant bits, the area overhead is 39.71% and the time overhead has been observed to be negligible.

This paper investigates the concurrent detection of multiple-bit errors in polynomial basis (PB) multipliers over binary extension fields. To this end, multiple parity bits are considered for both inputs of the multiplier. For the multiplier architecture considered here, the two inputs go through considerably different sets of circuits and this allows us to use different number of parity bits with the inputs. In a bit-parallel implementation of a GF(2163) PB multiplier with eight parity bits for the first input and three parity bits for the second input, the area overhead and the probability of error detection are approximately 55.59% and 0.997, respectively. Additionally, the average time overhead of the scheme implemented in a bit-parallel fashion is approximately 25%.

Based on Toeplitz matrix-vector products and coordinate transformation techniques, we present a new scheme for subquadratic space complexity parallel multiplication in GF(2n) using the shifted polynomial basis. Both the space complexity and the asymptotic gate delay of the proposed multiplier are better than those of the best existing subquadratic space complexity parallel multipliers. For example, with n being a power of 2, the space complexity is about 8 percent better, while the asymptotic gate delay is about 33 percent better, respectively. Another advantage of the proposed matrix-vector product approach is that it can also be used to design subquadratic space complexity polynomial, dual, weakly dual, and triangular basis parallel multipliers. To the best of our knowledge, this is the first time that subquadratic space complexity parallel multipliers are proposed for dual, weakly dual, and triangular bases. A recursive design algorithm is also proposed for efficient construction of the proposed subquadratic space complexity multipliers. This design algorithm can be modified for the construction of most of the subquadratic space complexity multipliers previously reported in the literature

For original paper see P.L. Montgomery, ibid., vol.54, no.3, p.362-369, (2005). We show that multiplication complexities of n-term Karatsuba-Like formulae of GF(2)[x] (7w

Based on a recently proposed Toeplitz matrix-vector product approach, a subquadratic computational complexity scheme is presented for multiplications in binary extended finite fields using type I and II optimal normal bases.

The detection of errors in arithmetic operations is an important issue. This paper discusses the detection of multiple-bit errors due to faults in bit-serial and bit-parallel polynomial basis (PB) multipliers over binary extension fields. Our approach is based on multiple parity bits. Experimental results presented here show that due to an increase in the number of parity bits, the area overhead tends to increase linearly, but the probability of error detection approaches unity fairly quickly, e.g., for eight parity bits. In bit-serial implementation of a GF(2163) PB multiplier using eight parity bits, the area overhead and the probability of error detection are 10.29% and 0.996, respectively. This is achieved without any increase in the computation time of the GF(2163) PB multiplier

Applying the matrix-vector product idea of the Mastrovito multiplier to the GF(2^{m}) Montgomery multiplication algorithm, we present a new parallel multiplier for irreducible trinomials. This multiplier and the corresponding shifted polynomial basis (SPB) multiplier have the same circuit structure for the same set of parameters. Furthermore, by establishing isomorphisms between the Montgomery and the SPB constructions of GF(2^{m}), we show that the Montgomery algorithm can be used to perform the SPB multiplication without any changes and vice versa.

In many cryptographic schemes, the most time consuming basic arithmetic operation is the finite field multiplication and its hardware implementation for bit parallel operation may require millions of logic gates. Some of these gates may become faulty in the field due to natural causes or malicious attacks, which may lead to the generation of erroneous outputs by the multiplier. In this paper, we propose new architectures to detect erroneous outputs caused by certain types of faults in bit-parallel and bit-serial polynomial basis multipliers over finite fields of characteristic two. In particular, parity prediction schemes are developed for detecting errors due to single and certain multiple stuck-at faults. Although the issue of detecting soft errors in registers is not considered, the proposed schemes have the advantage that they can be used with any irreducible binary polynomial chosen to define the finite field

A class of universal unidirectional bit serial systolic architectures for multiplicative inversion and division over Galois field GF(2/sup m/) is presented. The field elements are represented with polynomial (standard) basis. These systolic architectures have no carry propagation structures and are suitable for hardware implementations where the dimension of the field is large and may vary. This is the typical case for cryptographic applications. These architectures are independent of any defining irreducible polynomial of a given degree as well. The time complexity is constant and area complexity is linear (w.r.t. field dimension) and these measures are equivalent to or exceed similar proposed designs.

For efficient hardware implementation of finite field arithmetic units, the use of a normal basis is advantageous. In this paper, two classes of architectures for multipliers over the finite field GF(2/sup m/) are proposed. These multipliers are of sequential type, i.e., after receiving the coordinates of the two input field elements, they go through k, 1 /spl les/ k /spl les/ m, iterations (i.e., clock cycles) to finally yield all the coordinates of the product in parallel. The value of k depends on the word size w = /spl lceil/m/k/spl rceil/. For w > 1, these multipliers are highly area efficient and require fewer number of logic gates even when compared with the most area efficient multipliers available in the open literature. This makes the proposed multipliers suitable for applications where the value of m is large but space is of concern, e.g., resource constrained cryptographic systems. Additionally, if the field dimension m is composite, i.e., m = kn, then the extension of one class of the architectures yields a highly efficient multiplier over composite fields.

Representing the field elements with respect to the polynomial (or standard) basis, we consider bit parallel architectures for multiplication over the finite field GF(2m). In this effect, first we derive a new formulation for polynomial basis multiplication in terms of the reduction matrix Q. The main advantage of this new formulation is that it can be used with any field defining irreducible polynomial. Using this formulation, we then develop a generalized architecture for the multiplier and analyze the time and gate complexities of the proposed multiplier as a function of degree m and the reduction matrix Q. To the best of our knowledge, this is the first time that these complexities are given in terms of Q. Unlike most other articles on bit parallel finite field multipliers, here we also consider the number of signals to be routed in hardware implementation and we show that, compared to the well-known Mastrovito's multiplier, the proposed architecture has fewer routed signals. The proposed generalized architecture is further optimized for three special types of polynomials, namely, equally spaced polynomials, trinomials, and pentanomials. We have obtained explicit formulas and complexities of the multipliers for these three special irreducible polynomials. This makes it very easy for a designer to implement the proposed multipliers using hardware description languages like VHDL and Verilog with minimum knowledge of finite field arithmetic.

In this article, two digit-serial architectures for normal basis multipliers over ( GF (2 m )) are presented. These two structures have the same gate count and gate delay. We also consider two special cases of optimal normal bases for the two digit-serial architectures. A straightforward implementation leaves gate redundancy in both of them. An algorithm that can considerably reduce the redundancy is also developed. The proposed architectures are compared with the existing ones in terms of gate and time complexities.

Cryptographic schemes, such as authentication, confidentiality, and integrity, rely on computations in very large finite fields, whose hardware realization may require millions of logic gates. In a straightforward design, even a single fault in such a complex circuit is likely to yield an incorrect result and may be exploited by an attacker to break the cryptosystem. In this regard, we consider computing over finite fields in presence of certain faults in multiplier circuits. Our work reported here deals with errors caused by such faults in polynomial basis multipliers over finite fields of characteristic two and presents a scheme to correct single errors. Towards this, pertinent theoretical results are derived, and both bit-parallel and bit-serial fault tolerant multipliers are proposed.

A unidirectional bit serial systolic architecture for division over Galois field GF(2/sup m/) is presented which uses both triangular and polynomial basis representations. It is suitable for hardware implementations where the dimension of the field is large and may vary. This is the typical case for cryptographic applications. This architecture is simulated in Verilog-HDL and synthesized for a clock period of 1.4 ns using Synopsys. The time and area complexities are truly linear, since no carry propagation structures are present, and the complexity measures are equivalent or excel the best designs proposed so far.

For efficient hardware implementation of finite field arithmetic units, the use of a normal basis is advantageous. Two architectures for multipliers over the finite field GF(2/sup m/) are proposed. Both of these multipliers are of sequential type - after receiving the coordinates of the two input field elements, they go through m iterations (or clock cycles) to finally yield all the coordinates of the product in parallel. These multipliers are highly area efficient and require fewer number of logic gates even when compared with the most area efficient multiplier available in the open literature. This makes the proposed multipliers suitable for applications where the value of m is large but space is of concern, e.g., resource constrained cryptographic systems. Additionally, the AND gate count for one of the multipliers is /spl lfloor/m/2/spl rfloor/+1 only. This implies that if the multiplication over GF(2/sup m/) is performed using a suitable subfield GF(2/sup n/), where n>1 and n|m, then the corresponding multiplier architecture will yield a highly efficient digit or word serial multiplier.

In cryptographic applications, the use of normal bases to represent elements of the finite field GF(2/sup m/) is quite advantageous, especially for hardware implementation. In this article, we consider an important field operation, namely, multiplication which is used in many cryptographic functions. We present a class of algorithms for normal basis multiplication in GF(2/sup m/). Our proposed multiplication algorithm for composite finite fields requires a significantly lower number of bit level operations and, hence, can reduce the space complexity of cryptographic systems.

For cryptographic applications, normal bases have received considerable attention, especially for hardware implementation. We consider fast software algorithms for normal basis multiplication over the extended binary field GF(2/sup m/). We present a vector-level algorithm, which essentially eliminates the bit-wise inner products needed in the conventional approach to the normal basis multiplication. We then present another algorithm, which significantly reduces the dynamic instruction counts. Both algorithms utilize the full width of the data-path of the general purpose processor on which the software is to be executed. We also consider composite fields and present an algorithm, which can provide further speed-ups and an added flexibility toward hardware-software codesign of processors for very large finite fields.

The Massey-Omura multiplier of GF(2/sup m/) uses a normal basis and its bit parallel version is usually implemented using m identical combinational logic blocks whose inputs are cyclically shifted from one another. In the past, it was shown that, for a class of finite fields defined by irreducible all-one polynomials, the parallel Massey-Omura multiplier had redundancy and a modified architecture of lower circuit complexity was proposed. In this article, it is shown that, not only does this type of multiplier contain redundancy in that special class of finite fields, but it also has redundancy in fields GF(2/sup m/) defined by any irreducible polynomial. By removing the redundancy, we propose a new architecture for the normal basis parallel multiplier, which is applicable to any arbitrary finite field and has significantly lower circuit complexity compared to the original Massey-Omura normal basis parallel multiplier. The proposed multiplier structure is also modular and, hence, suitable for VLSI realization. When applied to fields defined by the irreducible all-one polynomials, the multiplier's circuit complexity matches the best result available in the open literature.

This article presents simple and highly regular architectures for finite field multipliers using a redundant representation. The basic idea is to embed a finite field into a cyclotomic ring which is based on the elegant multiplicative structure of a cyclic group. One important feature of our architectures is that they provide area-time trade-offs which enable us to implement the multipliers in a partial-parallel/hybrid fashion. This hybrid architecture has great significance in its VLSI implementation in very large fields. The squaring operation using the redundant representation is simply a permutation of the coordinates. It is shown that, when there is an optimal normal basis, the proposed bit-serial and hybrid multiplier architectures have very low space complexity. Constant multiplication is also considered and is shown to have an advantage in using the redundant representation.

Among the basic arithmetic operations over finite fields, the computation of a multiplicative inverse is the most time consuming operation. A number of methods are presented to efficiently compute the inverse using the extended Euclidean algorithm. The proposed methods can significantly reduce the computation time over large fields where the field elements are represented using a multi-precision format. A hardware structure for the inverter is also presented. The structure is area efficient and is suitable for resource constrained systems. Additionally, an application of the proposed inversion algorithm is given in the context of elliptic curve cryptography.

Because of their shorter key sizes, cryptosystems based on elliptic curves are being increasingly used in practical applications. A special class of elliptic curves, namely, Koblitz curves, offers an additional, but crucial advantage of considerably reduced processing time. Power analysis attacks are applied to cryptosystems that use scalar multiplication on Koblitz curves. Both the simple and the differential power analysis attacks are considered and a number of countermeasures are suggested. While the proposed countermeasures against the simple power analysis attacks rely on making the power consumption for the elliptic curve scalar multiplication independent of the secret key, those for the differential power analysis attacks depend on randomizing the secret key prior to each execution of the scalar multiplication. These countermeasures are computationally efficient and suitable for hardware implementation.

System-level design of packet switching fabrics focuses on performance metrics and rarely considers the physical requirements that are usually addressed later at the circuit-level. However, low-power dissipation has become a major requirement in such fabrics dictated by the requirements of emerging applications and by the recent advances in fabrication and VLSI technologies. This paper proposes a framework for system-level design of packet switching fabrics that integrates performance specifications along with physical requirements and constraints. Moreover, realistic traffic models are used to derive the transition activity and the packet arrival and departure events needed for power estimation. Physical requirements are defined by an architectural model for power dissipation based on the stochastic traffic model, models for silicon area, chip count, and input-output pins, which provide a complete system-level specification of the fabric. Performance constraints are also derived from the stochastic traffic model. This framework formulates and solves the power optimization problem subject to those physical and performance constraints as an integer nonlinear optimization problem. The results obtained emphasize the importance of traffic-driven system-level optimization and show the efficiency of this framework as a system-level design space exploration tool.

A new architecture for finite field exponentiation using weakly dual bases is presented. An extended bidirectional linear feedback shift register is designed to multiply an arbitrary field element with certain essential multiplicands in weakly dual basis (WDB). Each of these multiplications is done in one single clock cycle. It is shown that a bit parallel implementation of the WDB fourth power has complexities comparable to those of polynomial basis fourth power. The proposed structure can effectively speed up the computation of exponentiation and is expected to reduce the power consumption compared to the conventional square and multiply scheme. Compared to the structure for polynomial basis exponentiation, the new structure is thus advantageous in a system where the WDB is already available.

Many cryptographic systems use multiplication in the finite field GF(2/sup n/) for their underlying computations. In the recent past, a number of look-up table-based algorithms have been proposed for the software implementation of GF(2/sup n/) multiplication. Look-up table-based algorithms can provide speed advantages, but they either require a large memory space or do not fully utilize the resources of the processor on which the software is executed. In this work, an algorithm for GF(2/sup n/) multiplication is proposed which can alleviate this problem. In each iteration of the proposed algorithm, a group of bits of one of the input operands are examined and two look-up tables are accessed. The groupsize determines the table sizes, but does not affect the utilization of the processor resources. It can be used for both software and hardware realizations and is particularly suitable for implementations in memory constrained environment, such as smart cards and embedded cryptosystems.

With the explosive growth of electronic commerce, dedicated cryptographic processors are becoming essential since general-purpose processors cannot provide the performance and functionality directly needed, This paper proposes an architecture for a versatile Galois field GF(2/sup m/) processor for cryptographic applications. This processor uses both canonical and triangular bases for field elements representation and manipulation. The variable dimension datapath of the processor is versatile enough to meet the varying requirements for different applications and environments. To provide flexibility for different cryptographic applications, an instruction set architecture is designed. Finally, a prototype VLSI implementation of the Galois field processor is presented and discussed.

In this paper a VLSI architecture is proposed for an algorithm-agile encryptor for ATM networks. The architecture is based on a circular sorting queue that buffers and switches incoming cells to the appropriate encryption pipelines. It also handles multicast cells that require different encryption algorithms for different destinations. Delay and loss priority are analyzed for multi-class traffic processed through the encryptor. The analysis results are necessary to size the buffer properly and to choose an appropriate priority scheme. An ASIC prototype of the sorting queue that supports an aggregate traffic rate of up to 21.2 Gbps is also presented.

In radix-r number system, the minimal weight signed-digit (SD) representation has minimal number of nonzero signed-digits which belong to the set {/spl plusmn/1, /spl plusmn/2, ..., /spl plusmn/(r-1)}. In this article, we derive closed form expressions for the average number of nonzero digits in the minimal weight SD representation and for the average length of the canonical SD representation, a special case of the minimal weight SD form, of a positive integer whose radix-r form is of length n, n/spl ges/1.

Unlike most research involving finite field multipliers, this work targets a low-power multiplier through the application of various power reduction techniques to different types of multipliers and comparing their power consumption among other factors, rather than comparing complexity measures such as gate count or area. Gate count is used as a starting point to choose potential architectures, namely, polynomial and normal basis architectures. Power reduction techniques employed are mainly concerned with architecture- and logic-level low-power techniques. They include supply voltage reduction, power cost estimations, using low-power logic families and pipelining.

Inversion over Galois fields is much more difficult than the corresponding multiplication. Efficient computation of inverses in GF(2/sup m/) is considered by solving a set of linear equations over the ground field GF(2). The proposed algorithm uses two separate bases for the representation of its input and output elements and has low computational complexity. The algorithm is also suitable for hardware implementation using VLSI technologies.

New implementations of bit-parallel multipliers for a class of finite fields are proposed. The class of finite fields is constructed with irreducible AOPs (all one polynomials) and ESPs (equally spaced polynomials). The size and time complexities of our proposed multipliers are lower than or equal to those of the previously proposed multipliers of the same class.

New structures of bit-parallel weakly dual basis (WDB) multipliers over the binary ground field are proposed. An upper bound on the size complexity of bit-parallel multiplier using an arbitrary generating polynomial is given. When the generating polynomial is an irreducible trinomial x/sup m/+x/sup k/+1, 1/spl les/k/spl les/[m/2], the structure of the proposed bit-parallel multiplier requires only m/sup 2/ two-input AND gates and at most m/sup 2/-1 XOR gates. The time delay is no greater than T/sub A/+([log/sub 2/ m]+2)T/sub x/, where T/sub A/ and T/sub X/ are the time delays of an AND gate and an XOR gate, respectively.

The Galois field division is a complex arithmetic operation. The corresponding division-and-accumulation (DAA) is not only complex but also a time consuming operation. In this article, the DAA over GF(2/sup m/) is considered, and a simple scheme for its sequential operation is presented. A multiple stream DAA structure is developed which supports pipeline operations and yields an increased throughput with only a modest increase in the hardware. As an application, the use of the sequential DAA algorithm is shown for the high speed encoding of Reed-Solomon codes.

In this paper, exponentiation of a primitive root in GF(2/sup m/) is considered. Signed digit (SD) number representation is used to efficiently represent the exponent and the corresponding algorithms and structures for exponentiation are developed. For primitive multiplications required in exponentiations, extended bidirectional linear feedback shift registers are proposed and used for the cases where the exponent is represented as a binary or a radix-4 SD number. Comparisons are made with other methods on the bases of space, time, and possible power consumption. Since the proposed structures can effectively reduce power and area when implemented in VLSI, they are especially suitable for battery powered portable devices.

Multiple error-correcting Reed-Solomon (RS) codes have many practical applications. The complexity of an RS encoder depends on multiplications in the finite field over which the code is defined. We consider a triangular basis for representing the field elements, and present an architecture for a rate-adaptive RS encoder using a triangular basis multiplication algorithm. The architecture supports pipeline and bit-serial operations, and has a low circuit complexity.>

An adaptive interference canceller with an adjustable center weight is proposed to improve the performance of the conventional fixed center-weight canceller for applications in data transmission systems such as normal binary phase shift keying (BPSK) and direct sequence spread spectrum BPSK modems. The performance of the new interference canceller is shown to be better than that of the conventional canceller by analysis.>

A Massey-Omura parallel multiplier of finite fields GF(2/sup m/) contains m identical blocks whose inputs are cyclically shifted versions of one another. It is shown that for fields GF(2/sup m/) generated by irreducible all one polynomials, a portion of the block is independent of the input cyclic shift; hence, the multiplier contains redundancy. By removing the redundancy, a modified parallel multiplier is presented which is modular and has a lower circuit complexity.>

A systolic structure for bit-serial division over the field GF(2/sup m/) is developed. Consideration is given to avoid global data communications and dependency of the time step duration on m. This is important for applications where the value of m is large. The divider requires only three basic processors and one simple control signal and its circuit and time complexities are proportional to m/sup 2/ and m, respectively. It does not depend on the irreducible polynomial and can be expanded easily. Moreover, with m additional simple processors, a bit-serial systolic multiplier is developed which uses part of the divider structure. This is advantageous from the implementation point of view, as both the divider and multiplier can be fabricated on a single chip, resulting in a reduction of area.>

Structures for parallel multipliers of a class of fields GF(2/sup m/) based on irreducible all one polynomials (AOP) and equally spaced polynomials (ESP) are presented. The structures are simple and modular, which is important for hardware realization. Relationships between an irreducible AOP and the corresponding irreducible ESPs have been exploited to construct ESP-based multipliers of large fields by a regular expansion of the basic modules of the AOP-based multiplier of a small field. Some features of the structures also enable a fast implementation of squaring and multiplication algorithms and therefore make fast exponentiation and inversion possible. It is shown that, if for a certain degree, an irreducible AOP as well as an irreducible ESP exist, then from the complexity point of view, it is advantageous to use the ESP-based parallel multiplier.>