"Gap groups"
Definition: A gap group is a group where Decisional Diffie Hellman (DDH) is easy but where Computational Diffie Hellman is hard
How do you construct one? Using this notion of a bilinear map.
Suppose we have a main group G1 and a shadow group G2, both multiplicative
groups of order q
G1 is a group of prime order q, has generator g (main group)G2 is a group of prime order q, has generator h (shadow group)We have a pairing function e, or a bilinear map, such that it
takes two elements from G1 and gives you one in G2:
e : G1 x G1 -> G2e(g,g) = hWhat are all the properties of this function?
e : G1 x G1 -> G2e(g,g) = h\forall u, v \in G1, and a,b \in Z, we have e(u^a, v^b) = e(u,v)^abe(g,g) != 1Picture to illustrate this shadowing operation:
G1 g g^a g^b g^b g^ab
| | | | |
\| \| \| \| \|
G2 h h^a h^b h^b h^ab
(except the mapping function takes two args, not one)
\forall (a,b), e(g^a, g^b) = h^ab
The shadowing operations can be implemented as:
e(g, g) = h
e(g^a, g) = h^a
e(g^b, g) = h^b
e(g^a, g^b) = h^ab
Google for "pairing-based crypto lounge", to see applications of bilinear maps.
In practice G1 is an elliptic curve group and G2 is a finite field like
Z_{p^6}. Won't go into a discussion of what the bilinear map actually is
(complicated apparently).
You can compute a pairing function in like 25ms apparently.
Theorem: DDH is easy in G1, if you have G2 and a bilinear map from G1 to G2.
To check if g^a, g^b and g^c (could be g^r or g^ab) are related, we can check if e(g^a, g^b) = e(g, g^c) (i.e., if h^ab = h^c <=> ab = c (mod q))
Properties:
e(g^a,g^b) = e(g^a, g)^b = e(g, g)^ab, = e(g, g^b)^a
Note: If DLP is easy in G2 it is also easy in G1 (can map g^a => h^a, can compute a from h^a => have a for g^a) .
Q: Why do you need a prime order q group?
G1 is an elliptic curve group, a supersingular one (terminology?)
y^2 = x^3 + ax + b (mod p)
To make it supersingular, you need p = 2 (mod 3), p > 5, a = 0, b \in Z_p*
y^2 = x^3 + 1 (mod p)
G2 is a finite field F*_{p^k} for some small k
We need groups of prime order q, so we use subgroups of prime order q, |q| = 160 bits from G1 and G2
The bilinear map can be the "Weil pairing" or "Tate pairing"
We're gonna have a setup sort of like ElGamal. Assume all notation from previous section.
Let H : messages -> G1 be collision-resistant (CR) hash function that maps
messages to our G1 group.
Secret key is some value x, 0 < x < q picked randomly.
Public key is g^x (in G1)
To sign M, output s_x(M) = (H(M))^x
How to verify this signature? If we let m = H(M), signature will be equal to
m^x.
Bilinear maps allow us to "move betwen" these values:
g g^x m m^x
\ \-------/ /
\-----------------/
To verify, we have to check that e(g, m^x) = e(g^x, m)
e(g, m^x) = e(g^x, m) <=> (m = g^t, for some t, since G1 is cyclic)
e(g, g^tx) = e(g^x, g^t) <=>
h^tx = h^tx <=>
tx = tx
Note that since m \in G1 => m = g^t, for some t, we don't need
to find t, we just use it here to show that we should get equality.
A general remark about elliptic curves, is that the DLP problem gets harder faster
relative to the size of the group (compared to Z_p*)
For a point on an elliptic curve, you've got two values, the x and y coords.
|p| = 160 bits
point on curve is (x,y), 320 bits
Claim: we can represent a point with only 160 bits. Given (x, y) can represent
it as x, and for y, I can just compute it (there are only two possible, for
this particular curve) and give you a + or - bit to distinguish which y is
the good one
Isn't taking square roots hard? Depends on what the prime p is congruent to 1
(mod 4) then it's easy, if it's congruent to 3 (mod 4) then it's a little
harder, but still fast using some randomization.
Theorem: BLS signatures are secure against existential forgery under chosen
message attack in the random-oracle model (ROM) and assuming CDH is hard in G1
We saw the original Diffie-Hellman problem where Alice and Bob can agree on a key.
Alice, Bob and Charles want to agree on a key. We can do this with DH but with
a lot of message passing: gotta send g^ab, g^ac, g^bc to each other and compute
g^abc as the shared key.
Faster using bilinear maps
A g^a
B g^b
C g^c
Can take e(g^a, g^b)^c = h^abc
Can take e(g^b, g^c)^a = h^abc
Can take e(g^c, g^a)^b = h^abc
If we want 4-way agreement, maybe a trilinear map could be of use.
Suppose I want to send you a message, and all I have is your email address. Is there a way for me to use that as a public key?
Note: If there's a public key => there needs to be secret key => who computes it? Clearly it can't be you, because if you can simply compute it, then so can anyone else => Seems like we need a trusted third party (TTP) to compute the secret keys.
TTP has a secret s and a public key y = g^s \in G1. Everybody knows the TTP's
public key.
We have:
H1 : names -> G1* (CR hash fn)
H2 : G2 -> {0,1}^* (an element in G2 can be used to generate a keystream)
You want to encrypt a message M to name using y as the public key of the
TTP.
encrypt(M, name, y):
r <--R-- Z_q*
Q_A <-- H1(name), Q_A \in G1
g_A <-- e(Q_A, g^s), g_A \in G2
ctext <- (g^r, M \xor H2(g_A^r))
my secret is sk = d_A = H1(name)^s = Q_A^s
gotta get it from the TTP, because I don't know s
decrypt(d_A = Q_A^s, (u = g^r, v = M \xor H2(g_A^r))):
I have g, g^s, g^r, Q_A^s
v \xor H2(e(d_A, u)) = v \xor H2(e(Q_A^s, g^r))
e(Q_A^s, g^r) = e(Q_A, g)^rs = e(Q_A, g^s)^r = g_A^r
can now do v \xor g_A^r and get the message back
Note: You can encrypt to me, before I even have my secret...
Can be shown to be semantically secure in the Random Oracle Model.