Vector Commitments with Efficient Proofs学习笔记

admin管理员组

文章数量:1530019

1. 背景知识

Markulf Kohlweiss和Alfredo Rial 2012年文章《Vector Commitments with Efficient Proofs》和相应的ppt《Vector Commitments with Efficient Proofs》
初始motivation为 2010年《Privacy-Preserving Smart Metering》提到的智能计量的隐私保护。在该智能计量场景中，存在：计量meter方 M M M，服务提供provider方 P P P，政府机构government agency A A A，以及用户user U U U。

• M M M 测量 U U U 的消费（如水或电），将测得的值前面后发送给 U U U【基本格式为： a consumption value, a consumption time interval and a signature on both the consumption and the time.】。
  
• P P P 将已签名的收费政策发送给 U U U【含：the price per unit of consumption for each time interval.】。
  
• A A A 将另一份的已签名的收费政策发送给 U U U【该收费政策可对每个用户都不一样，签名时包含了特定用户 U U U的身份信息】。
  
• 在计算费用的时候，用户 U U U会从 A A A和 P P P给的收费政策中选择每个时间段更低的收费标准，从而形成用户 U U U专属的收费中间表：
  
• 目标：
  用户 U U U需要证明其缴纳的费用是正确计算的，但是同时要保护其专属的收费中间表不对外公布。该证明过程包含一个OR statement where U U U proves that, for each interval, the employed rate was signed either by P P P or by A A A。传统的OR argument生成的proof size grows with the number of tariff policies involved。

本文采用vector commitment机制来commit to a vector ( x 1 , ⋯   , x n ) (x_1,\cdots,x_n) (x1​,⋯,xn​) and open it to x i ( i ∈ [ 1 , n ] ) x_i(i\in [1,n]) xi​(i∈[1,n]) with cost independent of n n n。

U U U commit to the vector of其专属的收费中间表，并提供相应的证明，如：for each vector component, U U U proves that it was signed either by P P P or by A A A。
为了证明费用计算的正确性， U U U 需证明其采用的rate was committed in the correct vector component。

2. 基于accumulator构建的vector commitment

---

可参见博客 Vector Commitments and their Applications学习笔记 中第2.2节内容“基于RSA的Vector Commitment实现”。

---

3. 基于SDH assumption的vector commitment

将[kzg10]2010年论文《Polynomial Commitments*》【精简版本为《Constant-Size Commitments to Polynomials and Their Applications*》】中实现的polynomial commitment【基于SDH assumption】扩展为vector commitment。扩展方式为，对于vector ( x 1 , ⋯   , x n ) (x_1,\cdots,x_n) (x1​,⋯,xn​)，基于Lagrange插值 { ( 1 , x 1 ) , ⋯   , ( n , x n ) } \{(1,x_1),\cdots,(n,x_n)\} {(1,x1​),⋯,(n,xn​)}构建polynomial，对position i i i进行polynomial evaluation返回的值即为 x i x_i xi​。
对[kzg10]论文polynomial commitment的代码实现可参见博客：

• Polynomial Commitments代码实现【1】——scipr-lab/poly-commit（含不同曲线性能对比）
• Polynomial Commitments代码实现【2】——lovesh/kzg-poly-commit

polynomial commitment转vector commitment的详细思路可参见2015年论文《Composable & Modular Anonymous Credentials:Definitions and Practical Constructions》中第三节内容：【博客 vector commitment 中有提及。】

4. 基于DHE assumption的vector commitment

2010年Benoît Libert和Moti Yung 的论文《Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs》中基于DHE assumption构建的vector commitment。

详情参见博客 Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs 学习笔记

5. 基于CDH assumption的vector commitment

Catalano和Fiore 2011年论文《Concise vector commitments and their applications to zero-knowledge elementary databases》【又名《Vector Commitments and their Applications》】中提出了基于CDH assumption的vector commitment实现。详情参见博客 Vector Commitments and their Applications学习笔记 中第2.1节内容“基于CDH的Vector Commitment实现”。

本文标签： 学习笔记CommitmentsVectorProofsEfficient