NTRU is a public key cryptosystem based on hard problems over lattices. In this paper, we present efficient methods for convolution product computation which is a dominant operation of NTRU. The new methods are based on the observation that repeating patterns in coefficients of an NTRU polynomial can be used for the construction of look-up tables, which is a similar approach to the sliding window methods for exponentiation. We provide efficient convolution algorithms to implement this idea, and we make a comprehensive analysis of the complexity of the new algorithms. We also give software implementations over a Pentium IV CPU, a MICAz mote, and a CUDA-based GPGPU platform. According to our analyses and experimental results, the new algorithms speed up the NTRU encryption and decryption operations by up to 41%.

This paper proposes a new side channel attack to RSA cryptography. Our target is an implementation with a combination of countermeasures. These are an SPA countermeasure by m-ary method and a DPA countermeasure by randomizing exponent techniques. Here, randomizing exponent techniques shows two DPA countermeasures to randomize the secret exponent d. One is an exponent randomizing technique using d'i = d+ riφ(N) to calculate cd'i (mod N), and another is a technique using di,1 = d/ri and di,2 =(d (mod ri)) to calculate (cdi,1)ri cdi,2 (mod N). Using the combination of countermeasures, it was supposed that the implementation is secure against power attack. However, we firstly show the result to successfully attack the implementation of the combination of these countermeasures. We performed the experiment of this search on a PC, and complete d has been successfully revealed less than 10 hours for both attacks.

Image Registration can be seen as an optimization problem to find a cost function and then use an optimization method to get its minimum. Normalized mutual information is a widely-used robust method to design a cost function in medical image registration. Its calculation is based on the joint histogram of the fixed and transformed moving images. Usually, only a discrete joint histogram is considered in the calculation of normalized mutual information. The discrete joint histogram does not allow the cost function to be explicitly differentiated, so it can only use non-gradient based optimization methods, such as Powell's method, to seek the minimum. In this paper, a parzen-window based method is proposed to estimate the continuous joint histogram in order to make it possible to derive the close form solution for the derivative of the cost function. With this help, we successfully apply the gradient-based optimization method in registration. We also design a new kernel for the parzen-window based method. Our designed kernel is a second order polynomial kernel with the width of two. Because of good theoretical characteristics, this kernel works better than other kernels, such as a cubic B-spline kernel and a first order B-spline kernel, which are widely used in the parzen-window based estimation. Both rigid and non-rigid registration experiments are done to show improved behavior of our designed kernel. Additionally, the proposed method is successfully applied to a clinical CT-MR non-rigid registration which is able to assist a magnetic resonance (MR) guided microwave thermocoagulation of liver tumors.

In this paper, we will report practical modifications of the side-channel analysis to (EC)DSA [1],[2],[5],[34] that Leadbitter et al. have proposed in [16]. To apply the analyses, we assume that the window method is used in the exponentiation or elliptic curve (EC) scalar multiplication and the side-channel information described in Sect. 3.2 can be collected. So far, the method in [16] hasn't been effective when the size q of a cyclic group used in (EC)DSA is 160 bit long and the window size w < 9. We show that the modified method we propose in this paper is effective even when q is 160 bit long and w=4. This shows that our method is effective for various practical implementations, e.g., that in resource restricted environment like IC card devises. First, we estimate the window size w necessary for the proposed analyses (attacks) to succeed. Then by experiment of the new method, we show that private keys of (EC)DSA can be obtained under the above assumptions, in practical time and with sufficient success rate. The result raises the necessity of countermeasures against the analyses (attacks) in the window method based implementation of (EC)DSA.

This paper focuses on algorithms for an efficient scalar multiplication. It proposes two algorithms for computing points of the form 2kP in affine coordinates. One works for k=2, and the other works for an arbitrary natural number k. The efficiency of these algorithms is based on a trade-off between a field inversion and several field multiplications. Montgomery trick is used to implement this trade-off. Since a field inversion is usually more expensive than 10 field multiplications, the proposed algorithms are efficient in comparison with existing ones.

It has recently been reported that the performance of hyperelliptic curve cryptosystems (HECC) is competitive to that of elliptic curve cryptosystems (ECC). Concerning the security of HECC, the theta divisors play an important role. The scalar multiplication using a random base point is vulnerable to an exceptional procedure attack, which is a kind of side-channel attacks, using theta divisors. In the case of cryptographic protocols of the scalar multiplication using fixed base point, however, the exceptional procedure attack is not applicable. First, we present novel efficient scalar multiplication using theta divisors, which is the positive application of theta divisors on HECC. Second, we develop a window-based method using theta divisors that is secure against side-channel attacks. It is not obvious how to construct a base point D such that all pre-computed points are theta divisors. We present an explicit algorithm for generating such divisors.

Recently, the radix-3 representation of integers is used for the efficient implementation of pairing based cryptosystems. In this paper, we propose non-adjacent form of radix-r representation (rNAF) and efficient algorithms for generating rNAF. The number of non-trivial digits is (r-2)(r+1)/2 and its average density of non-zero digit is asymptotically (r-1)/(2r-1). For r=3, the non-trivial digits are {2, 4} and the non-zero density is 0.4. We then investigate the width-w version of rNAF for the general radix-r representation, which is a natural extension of the width-w NAF. Finally we compare the proposed algorithms with the generalized NAF (gNAF) discussed by Joye and Yen. The proposed scheme requires a larger table but its non-zero density is smaller even for large radix. We explain that gNAF is a simple degeneration of rNAF--we can consider that rNAF is a canonical form for the radix-r representation. Therefore, rNAF is a good alternative to gNAF.

The Single Instruction, Multiple Data (SIMD) architecture enables computation in parallel on a single processor. The SIMD operations are implemented on some processors such as Pentium 3/4, Athlon, SPARC, or even on smart cards. This paper proposes efficient algorithms for assembling an elliptic curve addition (ECADD), doubling (ECDBL), and k-iterated ECDBL (k-ECDBL) with SIMD operations. We optimize the number of auxiliary variables and the order of basic field operations used for these addition formulas. If an addition chain has k-bit zero run, we can replace k-time ECDBLs to the proposed faster k-ECDBL and the total efficiency of the scalar multiplication can be improved. Using the singed binary chain, we can compute a scalar multiplication about 10% faster than the previously fastest algorithm proposed by Aoki et al. Combined with the sliding window method or the width-w NAF window method, we also achieve about 10% faster parallelized scalar multiplication algorithms with SIMD operations. For the implementation on smart cards, we establish two fast parallelized scalar multiplication algorithms with SIMD resistant against side channel attacks.

We introduce efficient algorithms for the τ-adic sliding window method, which is a scalar multiplication algorithm on Koblitz curves over F2m. The τ-adic sliding window method is divided into two parts: the precomputation part and the main computation part. Until now, there has been no efficient way to deal with the precomputation part; the required points of the elliptic curves were calculated one by one. We propose two fast algorithms for the precomputation part. One of the proposed methods decreases the cost of the precomputation part by approximately 30%. Since more points are calculated, the total cost of scalar multiplication is decreased by approximately 7.5%.

This paper describes our vehicle classification system, which is based on local-feature configuration. We have already demonstrated that our system works very well for vehicle recognition in outdoor environments. The algorithm is based on our previous work, which is a generalization of the eigen-window method. This method has the following three advantages: (1) It can detect even if parts of the vehicles are occluded. (2) It can detect even if vehicles are translated due to veering out of the lanes. (3) It does not require segmentation of vehicle areas from input images. However, this method does have a problem. Because it is view-based, our system requires model images of the target vehicles. Collecting real images of the target vehicles is generally a time consuming and difficult task. To ease the task of collecting images of all target vehicles, we apply our system to computer graphics (CG) models to recognize vehicles in real images. Through outdoor experiments, we have confirmed that using CG models is effective than collecting real images of vehicles for our system. Experimental results show that CG models can recognize vehicles in real images, and confirm that our system can classify vehicles.

We introduce efficient algorithms for scalar multiplication on elliptic curves defined over FP. The algorithms compute 2k P directly from P, where P is a random point on an elliptic curve, without computing the intermediate points, which is faster than k repeated doublings. Moreover, we apply the algorithms to scalar multiplication on elliptic curves, and analyze their computational complexity. As a result of their implementation with respect to affine (resp. weighted projective) coordinates, we achieved an increased performance factor of 1.45 (45%) (resp. 1.15 (15%)) in the scalar multiplication of the elliptic curve of size 160-bit.

Power exponentiation is an important operation in modern cryptography. This operation can be efficiently calculated using the concept of the addition chain. In this paper, two new systematic methods, a Run-length method and a Hybrid method, are proposed to generate a short addition chain. The performance of these two methods are theoretically analyzed and it is shown that the Hybrid method is more efficient and practical than known methods. The proposed methods can reduce the addition chain length by 8%, in the best case, compared to the Window method.

The addition chain (A-chain) and addition-subtraction chain (AS-chain) are efficient tools to calculate power Me (or multiplication eM), where integere is fixed andM is variable. Since the optimization problem to find the shortest A (or AS)-chain is NP-hard, many algorithms to get a sub-optimal A (or AS)-chain in polynomial time are proposed. In this paper, a window method for the AS-chain and an extended window method for the A-chain and AS-chain are proposed and their performances are theoretically evaluated by applying the theory of the optimal variable-to-fixed length code, i. e. , Tunstall code, in data compression. It is shown by theory and simulation that the proposed algorithms are more efficient than other algorithms in practical cases in addition to the asymptotic case.