MIT IAP 2023 Modern Zero Knowledge Cryptography课程笔记
Lecture 3: Mathematical Building Blocks (Yufei Zhao)
- Fiat Shamir heuristic
- Turn an interactive proof to a non-interactive proof
- P can simulate V
- whenever V picks a random value
- P can simulate V’s randomness by running a cryptographic hash function on the transcript so that P can’t cheat by choosing “favorable random challenges”
- Elliptic Curve
-
y 2 = x 3 + A x + B y^2 = x^3 + Ax + B y2=x3+Ax+B
-
All points in a elliptic curve make a group
-
g in the generator of the group G
-
Difficult problem:
- Discrete Log Problem on Elliptic Curve
- Secret random x generated form Zq
- Share with the public xG
- It is hard to recover x from xG
- Diffie-Hellman Key Exchange (Public key cryptography)
- Alice takes a random a mod q
- Bob takes a random b mod q
- Alice says to the public: aG
- Bob says to the public: bG
- So, Alice and Bob share a secret: abG
- Discrete Log Problem on Elliptic Curve
-
- Pairing based cryptography
- Given cyclic groups G 0 , G 1 , G T G_0, G_1, G_T G0,G1,GT all same prime order q
- a pairing is a nondegenerate bilinear map
- e : G 0 × G 1 → G T e: G_0 \times G_1 \rightarrow G_T e:G0×G1→GT
- Properties
- Bilinear
- e(x+x’, y) = e(x,y) + e(x’,y)
- e(x,y+y’) = e(x,y) + e(x,y’)
- e(ax,y) = ae(x,y) + e(x,ay)
- Nondegenerated
- With generator g 0 ∈ G 0 g_0 \in G_0 g0∈G0 and g 1 ∈ G 1 g_1 \in G_1 g1∈G1
- g T = e ( g 0 , g 1 ) ∈ G T g_T = e(g_0, g_1) \in G_T gT=e(g0,g1)∈GT
- Bilinear
- An application BLS signature scheme (Boneh-Lynn-Shacham)
- Protocol
- Keygen: s k = s sk = s sk=s, p k = s g pk = sg pk=sg
- Sign(sk,m): σ = s H ( m ) \sigma = sH(m) σ=sH(m)
- Verify(pk,m): check e ( p k , H ( m ) ) = e ( g , σ ) e(pk, H(m)) = e(g,\sigma) e(pk,H(m))=e(g,σ)
- It can be extended to allow signature aggregation
- The verifier can collect all the signatures and aggregate them into a single short signature.
- The verifier can just verify the short signature then he knows that everyone signed their messages correctly.
- Protocol
