International Association for Cryptologic Research

International Association
for Cryptologic Research


Alexander Rostovtsev


Imaginary quadratic orders with given prime factor of class number
Alexander Rostovtsev
Abelian class group Cl(D) of imaginary quadratic order with odd squarefree discriminant D is used in public key cryptosystems, based on discrete logarithm problem in class group and in cryptosystems, based on isogenies of elliptic curves. Discrete logarithm problem in Cl(D) is hard if #Cl(D) is prime or has large prime divisor. But no algorithms for generating such D are known. We propose probabilistic algorithm that gives discriminant of imaginary quadratic order O_D with subgroup of given prime order l. Algorithm is based on properties of Hilbert class field polynomial H_D for elliptic curve over field of p^l elements. Let trace of Frobenius endomorphism is T, discriminant of Frobenius endomorphism D = T^2-4p^l and j is not in prime field. Then deg(H_D) = #Cl(O_D) and #Cl(D)=0 (mod l). If Diophantine equation D = T^2-4p^l with variables l<O(|D|^(1/4)), prime p and T has solution only for l=1, then class number is prime.
Fast exponentiation via prime finite field isomorphism
Alexander Rostovtsev
Raising of the fixed element of prime order group to arbitrary degree is the main operation specified by digital signature algorithms DSA, ECDSA. Fast exponentiation algorithms are proposed. Algorithms use number system with algebraic integer base (-2)^(1/4), 2^(1/4). Prime group order r can be factored as r = pi*pi1 in Euclidean ring Z[Sqrt[-2]], Z[Sqrt[2]] by Pollard and Schnorr algorithm. Farther factorization of prime quadratic divisor as pi = rho*rho1 in the ring Z[(-2)^(1/4)], Z[2^(1/4)] can be done similarly. Finite field of r elements is represented as quotient ring Z[(-2)^(1/4)]/(rho), Z[2^(1/4)]/(rho). Integer exponent k is reduced in corresponding quotient ring by minimization of its absolute norm. Algorithms can be used for fast exponentiation in arbitrary cyclic group if its order can be factored in corresponding number rings. If window size is 4 bits, this approach allows speeding-up 2.5 times elliptic curve digital signature verification comparatively to known methods with the same window size.
Alexander Rostovtsev Anton Stolbunov
A new general mathematical problem, suitable for public-key cryptosystems, is proposed: morphism computation in a category of Abelian groups. In connection with elliptic curves over finite fields, the problem becomes the following: compute an isogeny (an algebraic homomorphism) between the elliptic curves given. The problem seems to be hard for solving with a quantum computer. ElGamal public-key encryption and Diffie-Hellman key agreement are proposed for an isogeny cryptosystem. The paper describes theoretical background and a public-key encryption technique, followed by security analysis and consideration of cryptosystem parameters selection. A demonstrative example of encryption is included as well.
AES side channel attack protection using random isomorphisms
Rostovtsev A.G. Shemyakina O.V.
General method of side-channel attacks protection, based on random cipher isomorphisms is presented. Isomorphic ciphers produce common outputs for common inputs. Cipher isomorphisms can be changed independently on transmitting and receiving sides. Two methods of RIJNDAEL protection are considered. The first one is based on random commutative isomorphisms of underlying structure. The set of field F256 isomorphisms consists of 30 subsets; each of them has 8 commutative elements presented as Galois group elements. This allows increasing the strength with respect to side channel attacks about 32 times, the encryption ratio decreases slightly. This method has relatively small efficiency. The second method is based on cipher byte affine isomorphisms s(x)= Lx+a, and allows in practice eliminate side-channel attacks. The rate of this method is approximately the same as in previous case. The most convenient affine isomorphisms are involutions. Method of such affine isomorphisms generation is presented.
Elliptic Curve Point Multiplication
A.G.Rostovtsev E.B.Makhovenko
A method for elliptic curve point multiplication is proposed with complex multiplication by Sqrt[-2] or by (1+Sqrt[-7])/2 instead of point duplication, speeding up multiplication about 1.34 times. Higher radix makes it possible to use one point duplication instead of two and to speed up computation about 1.6 times. We employ prime group order factorization in corresponding quadratic order and integer exponent reduction modulo quadratic prime in the Euclidean imaginary quadratic ring.