ZKP Mathematical Building Blocks (2)

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+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
• Pairing based cryptography
  • Given cyclic groups $G_0,G_1,G_T$ all same prime order q
  • a pairing is a nondegenerate bilinear map
    • $e:G_0\times G_1\to G_T$
  • 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\in G_0$ and $g_1\in G_1$
      • $g_T=e(g_0,g_1)\in G_T$
  • An application BLS signature scheme (Boneh-Lynn-Shacham)
    • Protocol
      • Keygen: $sk=s$, $pk=sg$
      • Sign(sk,m): $\sigma =sH(m)$
      • Verify(pk,m): check $e(pk,H(m))=e(g,\sigma )$
    • 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.