Some new generalized cyclotomic sequences defined by C. Ding and T. Helleseth are proven to exhibit a number of good randomness properties. In this paper, we determine the defining pairs of these sequences of length pm (p prime, m ≥ 2) with order two, then from which we obtain their trace representation. Thus their linear complexity can be derived using Key's method.

Pairing-based cryptography provides us many novel cryptographic applications such as ID-based cryptosystems and efficient broadcast encryptions. The security problems in ubiquitous sensor networks have been discussed in many papers, and pairing-based cryptography is a crucial technique to solve them. Due to the limited resources in the current sensor node, it is challenged to optimize the implementation of pairings on sensor nodes. In this paper we present an efficient implementation of pairing over MICAz, which is widely used as a sensor node for ubiquitous sensor network. We improved the speed of ηT pairing by using a new efficient multiplication specialized for ATmega128L, called the block comb method and several optimization techniques to save the number of data load/store operations. The timing of ηT pairing over GF(2239) achieves about 1.93 sec, which is the fastest implementation of pairing over MICAz to the best of our knowledge. From our dramatic improvement, we now have much high possibility to make pairing-based cryptography for ubiquitous sensor networks practical.

XTR is one of the most efficient public-key cryptosystems that allow us to compress the communication bandwidth of their ciphertext. The compact representation can be achieved by deploying a subgroup Fq2 of extension field Fq6, so that the compression ratio of XTR cryptosystem is 1/3. On the other hand, Dijk et al. proposed an efficient public-key cryptosystem using a torus over Fq30 whose compression ratio is 4/15. It is an open problem to construct an efficient public-key cryptosystem whose compression ratio is smaller than 4/15. In this paper we propose a new variant of XTR cryptosystem over finite fields with characteristic three whose compression ratio is 1/6. The key observation is that there exists a trace map from Fq6 to Fq in the case of characteristic three. Moreover, the cost of compression and decompression algorithm requires only about 1% overhead compared with the original XTR cryptosystem. Therefore, the proposed variant of XTR cryptosystem is one of the fastest public-key cryptosystems with the smallest compression ratio.

The ηT pairing for supersingular elliptic curves over GF(3m) has been paid attention because of its computational efficiency. Since most computation parts of the ηT pairing are GF(3m) multiplications, it is important to improve the speed of the multiplication when implementing the ηT pairing. In this paper we investigate software implementation of GF(3m) multiplication and propose using irreducible trinomials xm+axk+b over GF(3) such that k is a multiple of w, where w is the bit length of the word of targeted CPU. We call the trinomials "reduction optimal trinomials (ROTs)." ROTs actually exist for several m's and for typical values of w = 16 and 32. We list them for extension degrees m = 97, 167, 193, 239, 317, and 487. These m's are derived from security considerations. Using ROTs, we are able to implement efficient modulo operations (reductions) for GF(3m) multiplication compared with cases in which other types of irreducible trinomials are used (e.g., trinomials with a minimum k for each m). The reason for this is that for cases using ROTs, the number of shift operations on multiple precision data is reduced to less than half compared with cases using other trinomials. Our implementation results show that programs of reduction specialized for ROTs are 20-30% faster on 32-bit CPU and approximately 40% faster on 16-bit CPU compared with programs using irreducible trinomials with general k.

The key weakness of Low-Density Parity Check codes is the complexity of the encoding scheme. The generator matrices can be made by Gaussian elimination of parity check matrices for normal block codes. Richardson succeeded in making parity bits from parity check matrices by the low density computation. In this letter, we focus on the execution of numerical experiments which show that even if the matrix D, which is the part of the Richardson's LDPC matrix, is restricted, proposed LDPC codes is lower complexity than Richardson's LDPC codes. The constraint of D results in reducing complexity from O(n + g2) to O(n) due to the omission of computing inverse matrices of φ and T in Richardson's encoding scheme. All the sub-matrices in parity check matrix are composed of Circulant Permutation Matrices based on Galois Fields.

In this paper, we present a new low-cost concurrent error detection (CED) S-Box architecture for the Advanced Encryption Standard (AES). Because the complexity and the nonlinearity, it is difficult to develop error detection algorithms for the S-Box. Conventionally, a parity checked S-Box is implemented with ROM (read only memory). In some applications, for example, smart cards, both chip size and fault detection are demanded seriously. ROM-based parity checking cannot meet the demands. We propose our CED S-Box (CEDSB) architecture for two reasons. The first is to design a S-Box without ROM. The second is to obtain a compact S-Box with real time error detection. Based on the composite field, we develop the CEDSB architecture to implement the fault detection for the S-Box. The overhead of the CED for the S-Boxes in GF((24)2) and in GF(((22)2)2) are 152 and 132 NAND gates respectively. The amount of extra gates used for the CEDSB is nearly equal to that of the ROM-based CED S-Box (131 NAND gates). The chip area of the ROM-based CED S-Box, the CEDSBs in GF((24)2), and in GF(((22)2)2) are 2996, 558, and 492 NAND gates separately. The chip area of the CEDSB is more compact than a ROM-based CED S-Box.

We present a bit-parallel squarer for GF(2n) defined by an irreducible trinomial xn +xk +1 using a shifted polynomial basis. The proposed squarer requires TX delay and at most n/2 XOR gates, where TX is the delay of one XOR gate. As a result, the squarer using the shifted polynomial basis is more efficient than one using the polynomial basis except for k=1 or n/2.

In this paper we study relationships between the linear complexities of a sequence when treated as a sequence over two distinct fields. We obtain bounds for one linear complexity in the form of a constant multiple of the other, where the constant depends only on the fields, not on the particular sequence.

Montgomery algorithm has demonstrated its effectiveness in applications like cryptosystems. Most of the existing works on finding the Montgomery inverse of an element over the Galois field are based on the software implementation, which is then extended to derive the scalable hardware architecture. In this work, we consider a fundamental change at the algorithmic level and eliminate the potential problems in hardware implementation which makes the resulting modified Montgomery inverse algorithm over GF(2m) very suitable for hardware realization. Due to its structural simplicity, the modified algorithm can be easily mapped onto a high-speed and possibly low-complexity circuit. Experimental results show that our development can achieve both the area and speed advantages over the previous work when the inversion operation over GF(2m) is under consideration and the improvement becomes more significant when we increase the value of m as in the applications of cryptosystems. The salient property of our development sustains the high-speed operation as well as low hardware complexity over a wide range of m for commercial cryptographic applications and makes it suitable for both the scalable architecture and direct hardware implementation.

Because fault-based attacks on cryptosystems have been proven effective, fault diagnosis and tolerance in cryptography have started a new surge of research and development activity in the field of applied cryptography. Without magnitude comparisons, the Montgomery multiplication algorithm is very attractive and popular for Elliptic Curve Cryptosystems. This paper will design a Montgomery multiplier array with a bit-parallel architecture in GF(2m) with concurrent error detection capability to protect it against fault-based attacks. The robust Montgomery multiplier array with concurrent error detection requires only about 0.2% extra space overhead (if m=512 is as an example) and requires four extra clock cycles compared to the original Montgomery multiplier array without concurrent error detection.

Normal and dual bases are two popular representation bases for elements in GF(2m). In general, each distinct representation basis has its associated different hardware architecture. In this paper, we will present a unified systolic array multiplication architecture for both normal and dual bases, such a unified multiplication architecture is termed a Hankel multiplier. The Hankel multiplier has lower space complexity while compared with other existing normal basis multipliers and dual basis multipliers.

This paper focuses on developing a square root (SQRT) algorithm in finite fields GF(p2d) (d 0). Examining the Smart algorithm, a well-known SQRT algorithm, we can see that there is some computation overlap between the Smart algorithm and the quadratic residue (QR) test, which must be implemented before a SQRT computation. It makes the Smart algorithm inefficient. In this paper, we propose a new QR test and a new SQRT algorithm in GF(p2d), in which not only there is no computation overlap, but also most of computations required for the proposed SQRT algorithm in GF(p2d) can be implemented in the corresponding subfields GF(p2d-i) for 1 i d, which yields many reductions in the computational time and complexity. The computer simulation also shows that the proposed SQRT algorithm is much faster than the Smart algorithm.

We show that a problem of deciding whether a formula for a multivariate polynomial of n variables over a finite field of characteristic 2 has degree n when reduced modulo a certain Boolean ideal belongs to P. When the formula is allowed to have succinct representations as sums of monomials, the problem becomes P-complete.

Two operations, polynomial multiplication and modular reduction, are newly induced by the properties of the modified Booth's algorithm and irreducible all one polynomials, respectively. A new and effective methodology is hereby proposed for computing multiplication over a class of fields GF(2m) using the two operations. Then a low complexity multiplexer-based multiplier is presented based on the aforementioned methodology. Our multiplier consists of m 2-input AND gates, an (m2 + 3m - 4)/2 2-input XOR gates, and m(m - 1)/2 4 1 multiplexers. For the detailed estimation of the complexity of our multiplier, we will expand this argument into the transistor count, using a standard CMOS VLSI realization. The compared results show that our work is advantageous in terms of circuit complexity and requires less delay time compared to previously reported multipliers. Moreover, our architecture is very regular, modular and therefore, well-suited for VLSI implementation.

This investigation proposes a new multiplication algorithm in the finite field GF(2m) over the polynomial basis, in which the irreducible xm +xn + 1 with gcd(m,n) = 1 generates the field GF(2m). The algorithm involves two steps--the intermediate multiplication and the modulo reduction. In the first step, the intermediate multiplication algorithm permutes a polynomial to construct the full-bit-parallel systolic intermediate multiplier. The circuit is identical of m2 cells, each cell is identical of one 2-input AND gate, one 2-input XOR gate, and four 1-bit latches. In the second step, based on the results of the intermediate multiplication in the first step, the modulo reduction circuit is built using regular and simple reduction operations. The latency of the proposed multiplier requires m + k + 1 clock cycles, where k = + 1. Notably, the latency can be very low if n is in the range 1 n . For the computing multiplication in GF(2m), the novel multiplier exhibits much lower latency than the existing systolic multipliers, and is well suited to VLSI systems due to their regular interconnection pattern, modular structure and fully inherent parallelism.

A new algorithm for efficient arithmetic in an optimal extension field is proposed. The new algorithm improves the speeds of multiplication, squaring, and inversion by performing two subfield multiplications simultaneously within a single integer multiplication instruction of a CPU. Our algorithm is used to improve throughputs of elliptic curve operations.

We propose a new multiple access communication system based on finite field wavelet spread signature (FFWSS). In addition to the function of frequency diversity and multiple access, which are typically provided by traditional spreading codes, the FFWSS spreads data symbols in time, resulting in robustness against frequency selective slow fading. Using the FFWSS to spread a data symbol so that it is overlapped with neighboring symbols, a FFWSS-CDMA system is developed. It is observed that the ratio of the maximum nontrivial value of periodic correlation function to the code length of FFWSS is the same as that of a Sidelnikov sequence. Using RAKE-based receivers, simulation results show that the proposed FFWSS-CDMA system yields lower bit error rate (BER) than conventional DS-CDMA and MT-CDMA systems in multipath fading channels.

2-Factor covering designs, a type of combinatorial designs, have recently received attention since they have industrial applications including software testing. For these applications, even a small reduction on the size of a design is significant, because it directly leads to the reduction of testing cost. In this letter, we report ten new designs that we constructed, which improve on the previously best known results.

To design a high-speed m-bit parallel inversion circuit over GF(2m), we study two variations for the repetition-operation of the numerical formula, AB2, in employing square-first and multiply-first type operations. From the proposed two variations, we propose four inversion architectures, adopting the multiplier and square in [10], as follows: simple duplication semi-systolic architecture for multiply-first inversion circuit (MFIC), m-bit parallel semi-systolic architecture for MFIC, simple duplication semi-systolic architecture for square-first inversion circuit (SFIC), and simplified m-bit parallel semi-systolic architecture for SFIC. Among them, performance of the simplified m-bit parallel semi-systolic architecture for SFIC is recommended for a high-speed applications to get a maximum throughput in the sense of small hardware-complexity, and low latency. When we implement the simplified 8-bit parallel semi-systolic architecture for SFIC over GF(28) by using 0.25 µm CMOS library, necessary are 2495 logic-gates and 1848 latches, and the latency is 56 and the estimated clock-rate is 580 MHz at 100% throughput.

A VLSI algorithm for division in GF(2m) with the canonical basis representation is proposed. It is based on the extended Binary GCD algorithm for GF(2m), and performs division through iteration of simple operations, such as shifts and bitwise exclusive-OR operations. A divider in GF(2m) based on the algorithm has a linear array structure with a bit-slice feature and carries out division in 2m clock cycles. The amount of hardware of the divider is proportional to m and the depth is a constant independent of m.