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?
- 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?1?tBt?
- 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=0n?ki?Pi?=∑j?2jwWj?
文章来源:https://blog.csdn.net/weixin_45347752/article/details/135181337
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!