Multivariate Cryptography on Smart Cards

Mehdi-Laurent Akkar
Jacques Patarin
CP8,ml.akkar@free.fr
j.patarin@frlv.bull.fr

68 route de Versailles
78431 Louveciennes, FRANCE

Public Key Cryptography• Arithmetic Schemes
Typical operation• Elliptic Curves
Typical operation• Multivariate schemes
Typical operations• Others (Graphs, Lattices …)
often not efficient

a.b mod n
a,b,n 512 to 2048 bitsa + b on the curvea,b 100 to 220 bits
a+b mod n / a.b mod n
a,b,n 1 to 16 bits
speed, size of keys …

Multivariate Cryptography (1)• Multivariate Polynomials Cryptography– Degre 1:– Degre 2:– Degre 3:– Degre 4:

Error correcting codes schemes (Mc Eliece, Niedereiter)
HFEV- (ie. Quartz ...), C*-- (ie. Flash, Sflash)
Dragons of degre 32R-

• Properties:– No proofs of security (indirect results)– Very efficien for authentificatin, signature and encryption.

Multivariate Cryptography (2)• Multivariate Combinatorial Cryptography:– Non NP-Hard:– NP Hard:IP
PKP, SD, PPP, MinRank• Properties:– Good proof of security– Very efficient for authentification– Not efficient for signatures– No encryptionIP (Isomophisms of Polynomials)• Secret of Alice (A) :an isomorphism s between 2 sets of equations (X) and (Y)Public Key :(X) and (Y)• AliceBobAliceBob

Randomly generates (Z) isomorph to (X) by t
Send to Alice 0 or 1
0
Send tto bobto Bob1
Send t o s-10
Check that (X) is t-isomorph to (Z)1
Check that (Y) is (s-1o t)-isomorph to (Z)HFE = Hidden Fields Equation• x : cleartext (or signature), x∈ Fqn, x= (x1, …, xn)
s : secret affine bijection
ab = f(a) = ∑ χ ij a+ ∑ µi a with a,b∈ Fqn,degre(b) < d (< 1000t : secret affine bijection
qi + q jqi

y : cyphertext (or message to sign), y ∈ Fqn, y= (y1, …, yn)• The public key is the composition of the 3 operations.

C*-- = C* scheme withmissing equations & only one branch• x : cleartext (or signature), x∈ Fqn, x= (x1, …, xn)
s : secret affine bijection
ab = f(a) = a1+ qθ

with a Fqn,t : secret affine non bijective fonction
y : message to sign(no encryption) , y ∈ Fqα, y= (y1, …, yα)where α<n and qn-α > 264• The public key is the composition of the 3 operations.

Example: n=8 / K=F2

Efficiency (signature) (1)• RSA 1024
– Best known attack– RAM in secret key computations– RAM in public key computations– Length of the public key– Length of the secret key– ROM Code– Secret key computation (CRT)– Public key computation (e=3)– Length of the Signature

1011 Mips year (281 op.)
264 bytes
400 bytes128+1 bytes
128 bytes
500 bytes
1600 basic operations
8 basic operations
128 bytes

Efficiency (signature) (2)• Quartz (HFEv- variant)– Best known attack– RAM in secret key computations– RAM in public key computations– Length of the public key– Length of the scret key– ROM Code– Secret key computation (CRT)– Public key computation (e=3)– Length of the Signature

1013 Mips year (2100 op)
500 bytes
40 bytes
71000 bytes
3000 bytes
500 bytes
16000 basic operations
0.5 basic operations
16 bytesEfficiency (signature) (3)• Flash (C*-- variant)– Best known attack– RAM in secret key computations– RAM in public key computations– Length of the public key– Length of the scret key– ROM Code– Secret key computation (CRT)– Public key computation (e=3)– Length of the Signature

1013 Mips year (2100 op)
100 bytes
30 bytes
18000 bytes
2750 bytes
500 bytes
10 basic operations
1 basic operations
37 bytes