ZKP学习笔记
ZK-Learning MOOC课程笔记
Lecture 7: Polynomial Commitments Based on Error-correcting Codes (Yupeng Zhang)
- Recall: common paradigm for efficient SNARK
- A polynomial commitment scheme + A polynomial interactive oracle proof (IOP) = SNARK for general circuits
- Poly-commit based on error-correcting codes
- Motivations:
- Plausibly post-quantum secure
- No group exponentiations (prover only uses hashes, additions and multiplications)
- Small global parameters
- Drawbacks:
- Large proof size
- Not homomorphic and hard to aggregate
- Motivations:
7.1 Background on error-correcting codes
- Error-correcting code
-
[
n
,
k
,
Δ
]
[n,k,\Delta]
[n,k,Δ] code
-
Enc(m): Encode a message of size k to a codeword of size n
-
Rate: k n \frac{k}{n} nk: [0,1], as close to 1 as possible文章来源:https://www.toymoban.com/news/detail-715272.html
-
Relative distance: Δ n \frac{\Delta}{n} nΔ [0,1], as close to 1 as possible文章来源地址https://www.toymoban.com/news/detail-715272.html
- Trade-off between the rate and the distance of a code
-
- Linear code
- Any linear combination of codewords is also a codeword
- Encoding can always be represented as vector-matrix multiplication between 𝑚 and the generator matrix
- Minimum distance is the same as the codeword with the least number of non-zeros (weight)
- Example: Reed-Solomon Code
- Any linear combination of codewords is also a codeword
-
[
n
,
k
,
Δ
]
[n,k,\Delta]
[n,k,Δ] code
到了这里,关于ZKP7.1 Polynomial Commitments Based on Error-correcting Codes (Background)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!