To speed up discrete-log based cryptographic schemes, we propose new methods of computing exponentiations {gx1, gx2, , gxs} simultaneously in combination with precomputation. Two proposed methods, VAS-B and VSS-B, are based on an extension of vector addition chains and an extension of vector addition-subtraction chains, respectively. Analysis of these methods clarifies upper bounds for the number of multiplications required. The VAS-B requires less multiplications than previously proposed methods with the same amount of storage. The VSS-B requires less multiplications than previously proposed methods with less amount of storage. The VSS-B can suitably be applied to schemes over elliptic curves.

A fast method for computing a multiple mP for a point P on elliptic curves is proposed. This new method is based on optimal addition sequences and the Frobenius map. The new method can be effectively applied to elliptic curves E(Fqn), where q is a prime power of medium size (e.g., q 128). When we compute mP over curves E(Fqn) with qn of nearly 160-bits and 11 q 128, the new method requires less elliptic curve additions than previously proposed methods. In this case, the average number of elliptic curve additions ranges from 40 to 50.

We propose an RSA-type scheme over the nonsingular part of a singular cubic curve En (0,b) : y2x3+bx2 (mod n), where n is a product of form-free primes p and q. Our new scheme encrypts/decrypts messages of 2 log n bits by operations of the x and y coordinates. The decryption is carried out over Fp or a subgroup of a quadratic extension of Fp, depending on quadratic residuosity of message-dependent parameter b. The decryption speed in our new scheme is about 4.6 and 5.8 times faster than that in the KMOV scheme and the Demytko scheme, respectively. We prove that if b is a quadratic residue in Zn, breaking our new scheme over En(0,b) is not easier than breaking the RSA scheme.

Elliptic curves Em: By2 = x3+Ax2+x are suitable for cryptographic use because fast addition operations can be defined over Em. In elliptic curve cryptosystems, encryption/decryption involves multiplying a point P on Em by a large integer n. In this paper, we propose a fast algorithm for computing such scalar multiplication over Em. The new algorithm requires fewer operations than previously proposed algorithms. As a result, elliptic curve cryptosystems based on Em can be speeded up by using the new algorithm.

The basic operation in elliptic cryptosystems is the computation of a multiple dP of a point P on the elliptic curve modulo n. We propose a fast and systematic method of reducing the number of operations over elliptic curves. The proposed method is based on pre-computation to generate an adequate addition-subtraction chain for multiplier the d. By increasing the average length of zero runs in a signed binary representation of d, we can speed up the window method. Formulating the time complexity of the proposed method makes clear that the proposed method is faster than other methods. For example, for d with length 512 bits, the proposed method requires 602.6 multiplications on average. Finally, we point out that each addition/subtraction over the elliptic curve using homogeneous coordinates can be done in 3 multiplications if parallel processing is allowed.

We propose an architecture for offloading processes in applications to support low-performance devices. Almost all applications based on standardized web technologies are compatible with our architecture. We discuss how interfaces should be used properly to offload processes in JavaScript and argue that an interface for offloading should only be used for defining complex processes. We also propose a method for applying our architecture to web applications that use web workers. Our method automatically offloads some worker processes to the cloud. We also compare the processing times achieved with and without our method. Our architecture exhibits good efficacy with regards to the N-Queen problem, although it is influenced by network latency between a device and the cloud.

Dr. Kenji Koyama, one of the most respected and prominent Japanese researchers in modern cryptography, passed away on March 27, 2000. He left behind him many outstanding academic achievements in cryptography as well as other areas such as emotion transmission theory, learning and mathematical games. In this manuscript, with our deepest sympathy and greatest appreciation for his contribution to our society, we introduce his major works mainly in cryptography, although his papers in other areas are included in the bibliography list.