ZKP Algorithms for Efficient Cryptographic Operations 1 (MSM Pippenger)

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\alpha^{2+\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={\sum }_{i=0}^n{k}_i{P}_i$
  • Step 1: partition scalars into windows
    • Let’s first partition each scalar into $m$ windows each has $w$ bits, then
      • $k_i=k_{i,0}+k_{i,1}{2}^w+...+k_{i,(m-1)}{2}^{(m-1)w}$
    • You can think of each scalar $k_i$ as a bignum and representing it as a multi-precision integer with limb size $w$. Then we have,
      • ${\sum }_i{k}_i{P}_i={\sum }_i{\sum }_{j=0}^{m-1}{k}_{i,j}{2}^{jw}{P}_i$
    • By reordering the sums, we get
      • ${\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$
      • It means we can calculte the MSM for each window $W_j$ first, then aggregate the results
    • Then, let’s examine $W_j={\sum }_{i=0}^n{k}_{i,j}{P}_i$
  • Step 2: for each window, add points by bucket
    • Because each window has $w$ bits, $k_{i,j}$ has a value range of $[0,2^w-1]$.Therefore, we can put $n$ points into $2^w$ buckets according to the value of $k_{i,j}$. We can first calculate $W_j$ by,
      • for bucket $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$.
      • $W_j={\sum }_{t=0}^{2^w-1}t{B}_t$
  • Step 3: reduce window results
    • $P={\sum }_{i=0}^n{k}_i{P}_i={\sum }_j{2}^{jw}{W}_j$