close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
Asymptotically Optimal
Communication for Torus-Based
Cryptography
David Woodruff
MIT
Joint work with Marten van Dijk
Philips/MIT
Contents
1. Background – XTR, torus-based crypto
2. Our Contributions
1. Relax a problem concerning tori
2. Solve the relaxation
3. Applications
1. Generalized ElGamal Signatures
2. Hybrid ElGamal Encryption
3. Conclusions
Diffie-Hellman Key Exchange
q = 2p + 1, g generates Gp 2 GF(q)* ,
Gp cyclic group of order p
a 2 Zp
ga
b 2 Zp
gb
Agree on key gab
ElGamal: work in extension field GF(qd)*
Schnorr: work in small prime subgroup of GF(q)*
The XTR Public-Key System


[BPV99] Combine ideas: use prime subgroup G of GF(q6)* of
w/order(G) = p | (q^2 – q + 1).
 “Field representation” of elts in G uses 6 log q bits
 [BPV99] More efficient representation of G
 2log q bits/elt
 Known attacks ~ size of minimal field containing G =>
Can show this is GF(q6)
6 *
 So 1/3 bits exchanged, yet full security of GF(q ) !
6 *
 DL, CDH in p-subgroup of GF(q ) believed as hard as DL,
CDH in p-subgroup of GF(P) where prime P ~ q6
[LV00] XTR = this idea + efficient arithmetic
Why does it work?
 Recall: |G| | (q2 – q + 1)
 Best attack number field sieve, uses field structure,
so time ~ minimal field containing G

Background: N-th cyclotomic polynomial
n(x) = 0< k<n : gcd(k, n) = 1 (x- e2 i k/n)
deg(n (x)) = (n)
|GF(qn)*| = qn – 1 = d | n d(q)
But 6(q) = q2 –q + 1 as in [BPV99]

So 6(q) | GF(q6)*, can show GF(q6) smallest such field.


Representation problem


Save even more? Use G ½ GF(qn)* for n > 6 with
|G| = n(q)?
Savings: log |G| = (n) log q bits Vs. n log q





Ratio approaches 1 / log log n for n prod. distinct primes
But how to represent elts of G?
Want < n log q bits, ideally (n) log q bits
[BPV99] represent G, |G| | 6(q), with 2log q bits.
[BHV02, RS03] show no straightforward way to
extend [BPV99] to n prod. ¸ 3 distinct primes
Torus-Based Cryptography


[RS03]: group Tn ½ GF(qn)* of order n(q) is just GF(q)
points of algebraic torus
 => Extending [BPV99] = rational parameterization of
algebraic torus
 Only known how if n product · 2 prime powers.
 [RS03] give another cryptosystem for n = 6.
But need n product ¸ 3 distinct primes for savings (n)/n
to get better.
Our Relaxation


Assume n(q) = |Tn| prime , o.w. let G ½ Tn have
large prime order
Relax rqmt of representing individual elts of Tn and
observe for some applications:
It suffices to represent a sequence of m elts of Tn
with m (n) log q + C bits, C independent of m
1. Don’t need to rationally parameterize torus
2. Get optimal communication for signatures, + PK encryption
3. Get Asymptotically optimal communication for key exchange
Solving the Relaxed Problem




n product of first k primes
Mobius function (n) = (-1)k
Construct efficiently computable bijections , -1
: Tn x (Xd | n, (n/d) = -1 GF(qd)*)
Xd | n, (n/d) = +1 GF(qd)*
Developing the Bijections

n = 2*3*5 = 30
: T30 x GF(q)* x GF(q6)* x GF(q10)* x GF(q15)*
! GF(q2)* x GF(q3)* x GF(q5)* x GF(q30)*

Strategy:






For e = 1, 6, 10, 15, map GF(qe)* into Xd | e Td
Collect tuple C = £{e=1, 6, 10, 15} £d | e Td
Use T30 and permute C to get C’ = £e = 2, 3, 5, 30 £d | e Td
For e=2, 3, 5, 30, decompose C’ to map Xd | e Td into GF(qe)*
Map -1 is similar.
The Bijections





Question: Which map : GF(qe)* to Xd | e Td to use?
If for all a,b | e, gcd(|Ta|, |Tb|) = 1, then domain &
range of  isomorphic
 follows from structure theorem:
H1, …, Hk are cyclic groups s.t. 8 i  j gcd(|Hi|, |Hj|) =
1, m = |H1|  |Hk|, and Gm cyclic of order m.
Then : Gm -> H1 x … x Hk , and -1 are isomorphisms:


() = (m/|Hi|)i 2 [k]
-1 (1, …, k) = 1e1  kek, where i mei /|Hi| = 1
: The General Case
 GF(qe)*, Xd | e Td not  if gcd(|Ta|, |Tb|) > 1 for a, b | e.
 Idea: divide out common factors U of |Td| and
decompose  into isomorphism + table lookup:

Example: Map GF(q2)* to T1 x T2





|T1| = q-1, |T2| = q+1, so 2 | gcd(|T1|, |T2|)
Suppose 2 | (q-1), 4 | (q+1), gcd(|T1|/2, |T2|/4) = 1
GF(q2)*  G8 x G(q-1)/2 x G(q+1)/4
Bijection from G8 to G2 x G4 using table lookup
G2 x G(q-1)/2  T1 and G4 x G(q+1)/4  T2
+ Isomorphisms are efficient using structure theorem
+ Table efficient since it is small
Parameter Selection

Choose q wisely


Heuristic algorithm for n = 30, 210




Want small table
Choose random q certain size
Check n(q) contains large prime factor by trial division
Check U is small
Theoretical algorithm for general n




Choose random prime r first
Choose q at random subject to r | n(q)
“Test” q to ensure U is small
Density theorems => terminates quickly w.h.p.
Applying the Bijections

: Tn x (Xd | n, (n/d) = -1 GF(qd)*) -> Xd | n, (n/d) = +1 GF(qd)*

Let - = d | n, (n/d) = -1 d, + = d | n, (n/d) = +1 d

Think of  as map: Tn £ Fq- to Fq+

Negligibly few points where  undefined


Handle these points separately
Use randomization to avoid bad points
Applications


To represent x1, …, xm in Tn,
 choose “seed” s1 2 Fq
+
 compute (x1, s1) = t1 2 Fq
- x F (n)
 split t1 into s2 x r1 2 Fq
q
+
 compute (x2, s2) = t2 2 Fq
- x F (n)
 split t2 into s3 x r2 2 Fq
q
 …
 …
Efficient representation for large m
{
Output
r1 … rm,
sm+1
A Signature Scheme
- Generalized ElGamal Signatures
work for any group: use Tn

 ElGamal Box alg outputs h 2 Tn + other stuff I
 Message M in I
 Write I as I1 x I2 2 Fq- x {0,1}*
 Output sig(M) = (h, I1), I2
 Verifier inverts , uses ElGamal verification
 Key idea: Embed message into Fq- so small signature
Hybrid ElGamal Encryption
Let a 2R {1, …, n(q)} be Alice’s private key
Let ga be her public key, g generator of Tn
E = symmetric cipher
Encrypt(m):
(1) choose k 2R {1,…, n(q)}, set e = gk
(2) use gak to get symmetric key k
(4) compute Ek(m) = (c, d) 2 Fq- x {0,1}*
(5) output (e, c), d
Decryption: Use a, -1 to get k, Ek(m) and then m
Key idea: Embed Ek(m) into Fq- so small encryption
Conclusions & Future Work


Results:
 Compact representation of sequences of elts of Tn
 Protocols w/optimal communication
 ElGamal signature / encryption (both hybrid and
almost non-hybrid) schemes
 Diffie-Hellman key exchange (asyptotically optimal)
Future Work:
 Rational parameterization of algebraic torus
 => efficient representation of single elts of Tn
 Our computational costs
 Improvements [vdWS] give ~ 21log q
multiplications per evaluation of 
1/--страниц
Пожаловаться на содержимое документа