ZKP Mathematical Building Blocks (2)

2023-12-24 10:31:08

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
  • 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?
    • 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.

文章来源:https://blog.csdn.net/weixin_45347752/article/details/135178744
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。