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=0nkiPi
- 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,12w+...+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 ∑ikiPi=∑i∑j=0m−1ki,j2jwPi
- 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 ∑ikiPi=∑j2jw(∑iki,jPi)=∑j2jwWj
- 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=0nki,jPi
- Let’s first partition each scalar into
m
m
m windows each has
w
w
w bits, then
- 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−1tBt
- 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,
- 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=0nkiPi=∑j2jwWj
