ZKP Algorithms for Efficient Cryptographic Operations 1 (MSM & Pippenger)

2023-12-24 14:59:58

MIT IAP 2023 Modern Zero Knowledge Cryptography课程笔记

Lecture 6: Algorithms for Efficient Cryptographic Operations (Jason Morton)

  • Multi-scalar Multiplication(MSM)

    • Naive: nP = (((P + P) + P) + P)… = (2(2P))…
    • Binary expand
      • $n = e_0+e_1\alpha+e_2\alpha2+\dots+\e_{\lambda-1}{\lambda-1}
      • Accumulator
        • Q = P;
        • R = 0 if e_0 = 0
        • R = P if e_0 = 1
        • For i = 1 to t
          • Q = 2Q
          • If e_i = 1
            • R = R+Q
        • Return R
      • Overhead: \log_2 n doubling + \log_2 n add
  • Pippenger [Reference:drouyang.eth, https://hackmd.io/@drouyang/SyYwhWIso]
    在这里插入图片描述

    • P = ∑ i = 0 n k i P i P=\sum_{i=0}^n k_i P_i P=i=0n?ki?Pi?
    • Step 1: partition scalars into windows
      • Let’s first partition each scalar into m m m windows each has w w w bits, then
        • k i = k i , 0 + k i , 1 2 w + . . . + k i , ( m ? 1 ) 2 ( m ? 1 ) w k_i = k_{i,0} + k_{i,1} 2^{w} + ... + k_{i,(m-1)} 2^{(m-1)w} ki?=ki,0?+ki,1?2w+...+ki,(m?1)?2(m?1)w
      • You can think of each scalar k i k_i ki? as a bignum and representing it as a multi-precision integer with limb size w w w. Then we have,
        • ∑ i k i P i = ∑ i ∑ j = 0 m ? 1 k i , j 2 j w P i \sum_i k_i P_i = \sum_i \sum_{j=0}^{m-1} k_{i,j} 2^{jw} P_i i?ki?Pi?=i?j=0m?1?ki,j?2jwPi?
      • By reordering the sums, we get
        • ∑ i k i P i = ∑ j 2 j w ( ∑ i k i , j P i ) = ∑ j 2 j w W j \sum_i k_i P_i= \sum_j 2^{jw} \left( \sum_i k_{i,j} P_i \right) = \sum_j 2^{jw} W_j i?ki?Pi?=j?2jw(i?ki,j?Pi?)=j?2jwWj?
        • It means we can calculte the MSM for each window W j W_j Wj? first, then aggregate the results
      • Then, let’s examine W j = ∑ i = 0 n k i , j P i W_j = \sum_{i=0}^n k_{i,j} P_i Wj?=i=0n?ki,j?Pi?
    • Step 2: for each window, add points by bucket
      • Because each window has w w w bits, k i , j k_{i,j} ki,j? has a value range of [ 0 , 2 w ? 1 ] [0, 2^w-1] [0,2w?1].Therefore, we can put n n n points into 2 w 2^w 2w buckets according to the value of k i , j k_{i,j} ki,j?. We can first calculate W j W_j Wj? by,
        • for bucket t t t, t ∈ { 0 , 2 w ? 1 } t \in \{0, 2^w-1\} t{0,2w?1}, calculate the sum of points in this bucket and get B t B_t Bt?.
        • W j = ∑ t = 0 2 w ? 1 t B t W_j = \sum_{t=0}^{2^w-1} t B_t Wj?=t=02w?1?tBt?
    • Step 3: reduce window results
      • P = ∑ i = 0 n k i P i = ∑ j 2 j w W j P=\sum_{i=0}^n k_i P_i = \sum_j 2^{jw} W_j P=i=0n?ki?Pi?=j?2jwWj?

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