Functional Commitment Schemes: From Polynomial Commitments to Pairing-Based Accumulators学习笔记

1. 背景知识

Benoˆıt Libert, Somindu C. Ramanna 和 Moti Yung 2016年论文 《Functional Commitment Schemes: From Polynomial Commitments to Pairing-Based Accumulators from Simple Assumptions》 中提出：

1）Functional Commitment (FC) primitive：用于概括所有的vector commitment、polynomial commitment和其它类型的commitment scheme。

• Committer： commit to vectors of n n n elements over domain D D D (e.g., m ⃗ = ( m 1 , ⋯   , m n ) ∈ D n \vec{m}=(m_1,\cdots,m_n)\in D^n m =(m1​,⋯,mn​)∈Dn)
• Committer：open for a function F ： D n → R F：D^n\rightarrow R F：Dn→R （如 ∑ i = 1 n m i x i = y ∈ R \sum_{i=1}^{n}m_ix_i=y\in R ∑i=1n​mi​xi​=y∈R【 其中 { x i } i = 1 n \{x_i\}_{i=1}^n {xi​}i=1n​ 为public coefficients，此时整个过程包含了vector commitment、polynomial commitment和cryptographic accumulator。】），生成a witness for the fact that F ( m ⃗ ) F(\vec{m}) F(m ) indeed evalutes to y y y。
• Functional Commitment (FC) 应具有function binding属性：即不可能基于同一function F F F 将一个commitment open为2个不同的evaluation y , y ′ y,y^{'} y,y′。
• Functional Commitment (FC) 的commitment 和 opening 应具有constant size （i.e., independent of n n n or function description）。
• Functional Commitment (FC) 应具有hiding属性，被commit的messages 为 information theoretically hidden。
• 本文构建了 Functional Commitment (FC) for a linear functions based on constant-size assumptions in composite order groups endowed with a bilinear map。
• 本文的security proof 基于：the D´ej`a Q framework of Chase and Meiklejohn (Eurocrypt 2014) and its extension by Wee (TCC 2016) to encryption primitives, thus relying on constant-size subgroup decisional assumptions.
• 本文的FC 可实现：polynomial commitment 和 accumulator for large universe。
• 基于的assumption为：

2）vector commitment：messages are v e c t o r s vectors vectors and commitment is only opened with respect to specific positions。

3）polynomial commitment：commit to a polynomial and only reveal evaluations of this polynomial on certain inputs。

Functional commitment 借鉴了Functional encryption的思想。

1.1 Functional encryption

Functional encryption 由2011年Boneh等人论文《Functional Encryption: Definitions and Challenges》中提出： Functional encryption 可 restrict what the receiver learns about encrypted data，当使用 function F F F 的 secret key S K F SK_F SKF​ 进行解密操作时，decryptor learns F ( x ) F(x) F(x) and nothing else。

与此类似的，Functional commitment 允许 committer accurately control what the opening phase can reveal about the committed message。

Functional commitment (FC) 的概念首次由Gorbunov等人在2015年论文《Leveled Fully Homomorphic Signatures from Standard Lattices》中含蓄提出，在该论文中描述了：a statistically-hiding commitment scheme for which the sender is able to only reveal a circuit evaluation C ( x ) C(x) C(x) when x x x is the committed input. 该方案基于well-studied lattice assumption，可支持任意circuit，其输入 x x x 必须被committed to in a bit-by-bit manner (或者说至少应将 x x x split into small blocks)。

若借助common reference string，ordinary statistically-hiding commitment + NIZK proof 可实现 non-interactive FC for general functionalities。

1.2 Verifiable random function

1999年，Micali，Rabin和Vadhan等人在论文《Verifiable Random Functions》 提出了Verifiable random function概念，可实现 a perfectly binding commitment to a pseudo-random function key for which the committer can convince a verifier about the correct function evaluation for the committed key on a given input。

1.3 Selective-opening security

Bellare, Hofheinz和Yilek在2009年论文《 Possibility and Impossibility Results for Encryption and Commitment Secure under Selective Opening》，Dwork等人1999年论文《Magic Functions》中均提出了Selective-opening security问题，即：根据已open的信息，adversary是能根据关联性获得un-open的信息。（the security of un-opened commitments when an adversary gets to see the opening of other commitments to possibly correlated messages.）

1.4 Zero-knowledge set

Zero-knowledge set，由Micali, Rabin和Kilian在2003年论文《Zero-Knowledge Sets》中提出：commit to a set S S S or an elementary database，然后可提供membership proof或non-membership proof of an element without revealing any further information (not even the cardinality of the committed set S S S)。 Ostrovsky, Rackoff和Smith等人在2004年论文《Efficient Consistency Proofs for Generalized Queries on a Committed Database》中将committed database 概念扩展为了更general statement，而不仅仅是membership和non-membership proof。

2. Vector commitment

Vector commitment的概念首次由Libert和Yung在2010年论文《 Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs》中提出，由Catalano和Fiore在2013年论文《Vector Commitments and their Applications》中进一步完善。

主要借助Pedersen-like commitment to vector ( m 1 , ⋯   , m n ) (m_1,\cdots,m_n) (m1​,⋯,mn​)，实现constant-size open (所谓constant是指independent of n n n) for m i m_i mi​ without revealing anything else。

Vector commitment的设计初衷是为了通过mercurial commitment来支持short coordinate-wise opening 从而实现支持short proof的zero-knowledge databse。Vector commitment也可用于verifiable database。

参见博客 Vector Commitments and their Applications学习笔记 和博客 Vector Commitments with Efficient Proofs学习笔记 中指出，构建vector commitment可有以下四种方式：

• 基于accumulator或RSA构建的vector commitment：要求所使用的group应具有unknown order（hidden order）。
• 基于SDH assumption的vector commitment：CRS size为 O ( 2 n ) O(2n) O(2n)，使用了bilinear pairing。
• 基于CDH assumption的vector commitment：CRS size为 O ( n 2 ) O(n^2) O(n2)，使用了bilinear pairing。
• 基于DHE assumption的vector commitment：CRS size为 O ( 2 n ) O(2n) O(2n)，使用了bilinear pairing。

3. Polynomial commitment

Polynomial commitment 由Kate, Zaverucha和Goldberg在2010年论文《 Constant-Size Commitments to Polynomials and their Applications》中提出：生成a constant-size commitment to a polynomial P [ Z ] P[Z] P[Z] (constant指independent of the degree)，然后存在a constant-size witness to convince a verifier that the committed P [ Z ] P[Z] P[Z] indeed evaluates to P ( i ) P(i) P(i) for a given i i i。

Polynomial commitment 可用于：

• verifiable secret sharing；
• anonymous credentials with attributes；
• 不需要隐藏committed set size的zero-knowledge database；
• 利用Lagrange插值，可构建vector commitment。

4. Accumulator

密码学累加器也可理解为是commitment，especially when the hashing algorithm is randomized。累加器与zero-knowledge set类似，可提供inclusion证明（比zero-knowledge set更短的membership证明），但是不同的是，累加器通常无法隐藏the cardinality of the set。

参见博客 密码学累加器cryptographic accumulator。

累加器的构建方式主要分为三大类：

• strong RSA assumption in groups of unknown order：如RSA group或者class group。[6,3,36,11,34]。通常CRS size更short，且可提供non-membership proof从而扩展为通用累加器或动态累加器。但是需要set内的元素为co-prime。
• bilinear maps：如[41,14]。不要求set内元素为prime，但是CRS的size与累加的元素数量一样。可用于e-cash、authenticated data structure等场景，用于证明子集、交集等场景。
• Merkle hash trees：如[44, 11]。基于Merkle tree而不是number theoretic assumption。主要的缺点是使用hash tree，假设hashed set的cardinality为 N N N，则proof size 为 O ( log ⁡ N ) O(\log N) O(logN)，而基于number theoretic 的累加器，其proof size 为 O ( 1 ) O(1) O(1)。

Deler等人2015年论文《 Solving Revocation with Efficient Update of Anonymous Credentials》对the security property of accumulator进行了re-formalize，为accumulator与其它primitive建立了关联：如，拥有indistinguishability属性后，accumulator可用于non-interactive commitment scheme以及zero-knowledge set。

5. Functional commitment (FC)

本论文主要关注Functional commitment (FC) for linear function family { F x ⃗ : D n × D n → D } x ⃗ ∈ D n \{F_{\vec{x}}:D^n\times D^n\rightarrow D\}_{\vec{x}\in D^n} {Fx ​:Dn×Dn→D}x ∈Dn​ 定义为： F x ⃗ = < x ⃗ , m ⃗ > = ∑ i = 1 n x i m i F_{\vec{x}}==\sum_{i=1}^{n}x_im_i Fx ​==∑i=1n​xi​mi​，其中 m ⃗ ∈ D n \vec{m}\in D^n m ∈Dn。【其实即为Inner product？】

基本流程为：

• 用 { F x ⃗ : D n → D } x ⃗ ∈ D n \{F_{\vec{x}}:D^n\rightarrow D\}_{\vec{x}\in D^n} {Fx ​:Dn→D}x ∈Dn​ 来produce commitment to messages of the form m ⃗ = ( m 1 , ⋯   , m n ) ∈ D n \vec{m}=(m_1,\cdots,m_n)\in D^n m =(m1​,⋯,mn​)∈Dn over the domain D D D。
• 对于特定的 x ⃗ ∈ D \vec{x}\in D x ∈D，有 F x ⃗ ( m ⃗ ) = ∑ i = 1 n x i m i = y ∈ D F_{\vec{x}}(\vec{m})=\sum_{i=1}^{n}x_im_i=y\in D Fx ​(m )=∑i=1n​xi​mi​=y∈D，open for F x ⃗ F_{\vec{x}} Fx ​ that F x ⃗ ( m ⃗ ) F_{\vec{x}}(\vec{m}) Fx ​(m ) indeed evaluates to y y y。
• 要求：commitment和witness均应为简洁的，其size应independent of the length of the messages or function description。

本文的FC scheme基于composite order bilinear group内的subgroup decision assumption建立，具有perfect hiding和computationally binding属性。

M. Izabachene, B. Libert, D. Vergnaud 2011年论文《Blockwise P-Signatures and Non-Interactive Anonymous Credentials with Efficient Attributes》中所构建的vector commitment 的secure 是 under non-standard variable-size assumption。 本文借助 M. Chase, S. Meiklejohn. 2014年论文《D´ej`a Q:Using Dual Systems to Revisit q-Type Assumptions》的 Deja Q framework 来obtain security from constant size assumption。

2010年，Benoît Libert和Moti Yung 的论文《Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs》中的思路为：【参看博客 Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs 学习笔记 第2节内容。】

• commit to ( m 1 , ⋯   , m q ) (m_1,\cdots,m_q) (m1​,⋯,mq​)表示为 V = g γ ⋅ ∏ j = 1 q g q + 1 − j m j V=g^{\gamma}\cdot\prod_{j=1}^{q}g_{q+1-j}^{m_j} V=gγ⋅∏j=1q​gq+1−jmj​​ 【该commitment在q-DHE assumption下具有binding属性，若q-DHE assumption不成立，则adversary可produce two distinct openings of V V V at position i i i。同时，也可将该commitment看成是trapdoor commitment，其trapdoor key为 g q + 1 = g α q + 1 g_{q+1}=g^{\alpha^{q+1}} gq+1​=gαq+1，拥有该trapdoor key 的人可open 该commitment为任意值。】
• 为证明 m i m_i mi​为 the i i i-th committed message，Prover提供： W i = g i γ ⋅ ∏ j = 1 , j ≠ i q g q + 1 − j + i m j W_i=g_i^{\gamma}\cdot \prod_{j=1,j\neq i}^{q}g_{q+1-j+i}^{m_j} Wi​=giγ​⋅∏j=1,j​=iq​gq+1−j+imj​​
• Verifier验证： e ( g i , V ) = e ( g , W i ) ⋅ e ( g 1 , g q ) m i e(g_i,V)=e(g,W_i)\cdot e(g_1,g_q)^{m_i} e(gi​,V)=e(g,Wi​)⋅e(g1​,gq​)mi​即可。
• 为实现mercurial commitment 具有更灵活的binding属性，若调整Verifier的验证公式为 e ( g i , V ) = e ( g 1 , W i ) ⋅ e ( g 1 , g q ) m i e(g_i,V)=e(g_1,W_i)\cdot e(g_1,g_q)^{m_i} e(gi​,V)=e(g1​,Wi​)⋅e(g1​,gq​)mi​则相应的binding属性将消失。基本思路为，Prover 的commitment不再只是 V V V，而是 ( C , V ) (C,V) (C,V)，其中 θ ∈ Z p \theta \in\mathbb{Z}_p θ∈Zp​，当 C = g θ C=g^{\theta} C=gθ时，为hard commitment；当 C = g 1 θ C=g_1^{\theta} C=g1θ​时，为soft commitment。Verifier验证的公式为： e ( g i , V ) = e ( C , W i ) ⋅ e ( g 1 , g q ) m i e(g_i,V)=e(C,W_i)\cdot e(g_1,g_q)^{m_i} e(gi​,V)=e(C,Wi​)⋅e(g1​,gq​)mi​

本文在Benoît Libert和Moti Yung 2010年的论文《Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs》的基础上，选择的是composite order bilinear group G \mathbb{G} G of order N = p 1 p 2 p 3 N=p_1p_2p_3 N=p1​p2​p3​， G q G_q Gq​ 代表the subgroup of G \mathbb{G} G of order q q q （ q q q可表示为 p 1 e 1 p 2 e 2 p 3 e 3 p_1^{e_1}p_2^{e_2}p_3^{e_3} p1e1​​p2e2​​p3e3​​，其中 e 1 , e 2 , e 3 ∈ { 0 , 1 } e_1,e_2,e_3\in\{0,1\} e1​,e2​,e3​∈{0,1}）。总的思路为：

• Public key: for g , u ∈ G p 1 g,u\in\mathbb{G}_{p_1} g,u∈Gp1​​， 构建commitment key { g α j } j = 1 n \{g^{\alpha^j}\}_{j=1}^n {gαj}j=1n​和 { U j = u α j } j ∈ [ 1 , 2 n ] ∖ { n + 1 } \{U_j=u^{\alpha^j}\}_{j\in[1,2n]\setminus\{n+1\}} {Uj​=uαj}j∈[1,2n]∖{n+1}​。Trapdoor key 为 U n + 1 U_{n+1} Un+1​
• 待commit messages：vector m ⃗ = m 1 , ⋯   , m n \vec{m}={m_1,\cdots,m_n} m =m1​,⋯,mn​。
• Commit算法：引入随机值 γ \gamma γ实现hiding属性， C = g γ ⋅ ∏ j = 1 n g α j m j C=g^{\gamma}\cdot\prod_{j=1}^{n}g^{\alpha^jm_j} C=gγ⋅∏j=1n​gαjmj​
• 待证明： < x ⃗ , m ⃗ > = y =y =y 【其实即为Inner product proof？其中 m ⃗ \vec{m} m 为witness， x ⃗ \vec{x} x 和 y y y为public info？？】
• Prover计算： W i = u α n − i + 1 γ ⋅ ∏ j = 1 , j ≠ i n u α n + 1 + j − i m j W_i=u^{\alpha^{n-i+1}\gamma}\cdot \prod_{j=1,j\neq i}^{n}u^{\alpha^{n+1+j-i}m_j} Wi​=uαn−i+1γ⋅∏j=1,j​=in​uαn+1+j−imj​，根据收到的challenge x ⃗ = ( x 1 , ⋯   , x n ) \vec{x}=(x_1,\cdots,x_n) x =(x1​,⋯,xn​) 后，计算 W y = ∏ j = 1 n W i x i W_y=\prod_{j=1}^{n}W_i^{x_i} Wy​=∏j=1n​Wixi​​，将 W y W_y Wy​发送给Verifier。【建立的基本思路为： ( γ + α m 1 + α 2 m 2 + ⋯ + α n m n ) ⋅ ( α n x 1 + α n − 1 x 2 + ⋯ + α x n ) = α n + 1 y + F ( x ) (\gamma+\alpha m_1+\alpha^2 m_2+\cdots+\alpha^n m_n)\cdot (\alpha^nx_1+\alpha^{n-1}x_2+\cdots+\alpha x_n)=\alpha^{n+1}y+F(x) (γ+αm1​+α2m2​+⋯+αnmn​)⋅(αnx1​+αn−1x2​+⋯+αxn​)=αn+1y+F(x)】
• Verifier验证： e ( C , ∏ i = 1 n u α n − i + 1 x i ) = e ( g α , u α n ) y ⋅ e ( g , W y ) e(C,\prod_{i=1}^{n}u^{\alpha^{n-i+1}x_i})=e(g^{\alpha},u^{\alpha^n})^y\cdot e(g,W_y) e(C,∏i=1n​uαn−i+1xi​)=e(gα,uαn)y⋅e(g,Wy​) 成立。

可以借鉴2010年，Benoît Libert和Moti Yung 的论文《Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs》中的非对称pairing思路，将上述 u u u选取在 G 3 \mathbb{G}_3 G3​ group。

Functional commitment的基本流程为：

D´ej`a Q framework [23] 可认为是基于subgroup decision assumption的Functional commitment：

5.1 Functional commitment as Polynomial commitment

Polynomial commitment 目标：commit to polynomial P [ Z ] = a 0 + a 1 Z + ⋯ + a n − 1 Z n − 1 P[Z]=a_0+a_1Z+\cdots+a_{n-1}Z^{n-1} P[Z]=a0​+a1​Z+⋯+an−1​Zn−1 of degree n − 1 n-1 n−1 over D D D and reveal an opening for P ( x ) P(x) P(x) for x ∈ D x\in D x∈D。

采用Functional commitment来实现Polynomial commitment：先commit to 系数 ( a 0 , ⋯   , a n − 1 ) ∈ D n (a_0,\cdots,a_{n-1})\in D^n (a0​,⋯,an−1​)∈Dn，构建challenge x ⃗ = ( 1 , x , ⋯   , x n − 1 ) \vec{x}=(1,x,\cdots,x^{n-1}) x =(1,x,⋯,xn−1) 即可。

其实将 x ⃗ \vec{x} x 设置为特定位置 x i = 1 x_i=1 xi​=1，其它位置均为 0 0 0 的情况，对应的即为open 位置 i i i 的vector commitment。

5.2 Functional commitment as Accumulator for large universe

参见博客 Vector Commitments and their Applications学习笔记 中的“2.2 基于RSA的Vector Commitment实现” 可知，基于accumulator可构建vector commitment。

Accumulator for large universe目标：对于集合 S = { y 1 , ⋯   , y n − 1 } S=\{y_1,\cdots,y_{n-1}\} S={y1​,⋯,yn−1​}，提供 membership 或 non-membership proof，证明 x ∈ S 或 者 x ∉ S x\in S 或者x\notin S x∈S或者x∈/​S。

采用Functional commitment来实现Accumulator for large universe：借助5.1节的思路，构建polynomial P [ Z ] = ∏ i = 1 n − 1 ( Z − y i ) = ∑ j = 0 n − 2 a j Z j + Z n − 1 P[Z]=\prod_{i=1}^{n-1}(Z-y_i)=\sum_{j=0}^{n-2}a_jZ^j+Z^{n-1} P[Z]=∏i=1n−1​(Z−yi​)=∑j=0n−2​aj​Zj+Zn−1【可先commit to 系数vector ( a 0 , a 1 , ⋯   , a n − 2 , 1 ) (a_0,a_1,\cdots,a_{n-2},1) (a0​,a1​,⋯,an−2​,1) 】，当且仅当 x ∈ S x\in S x∈S时， P [ x ] = 0 P[x]=0 P[x]=0。

密码学累加器基本流程为：

5.3 Functional commitment构建支持subset query的accumulator

假设 n n n为支持待累加集合的最大元素数， d d d为支持subset证明的subset内的最大元素数。

由博客 Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs 学习笔记 第2节内容可知，若只是vector commitment的某单一位置 m i m_i mi​的open的话，仅需要构建CRS public key： g 1 , ⋯   , g n , g n + 2 , ⋯   , g 2 n g_1,\cdots,g_n,g_{n+2},\cdots,g_{2n} g1​,⋯,gn​,gn+2​,⋯,g2n​，可表述为 [ 1 , 2 n ] [1,2n] [1,2n]，相应的trapdoor key为 g n + 1 g_{n+1} gn+1​，即hole at position n + 1 n+1 n+1。为证明第 i i i个位置为Prover计算： W i = u α n − i + 1 γ ⋅ ∏ j = 1 , j ≠ i n u α n + 1 + j − i m j W_i=u^{\alpha^{n-i+1}\gamma}\cdot \prod_{j=1,j\neq i}^{n}u^{\alpha^{n+1+j-i}m_j} Wi​=uαn−i+1γ⋅∏j=1,j​=in​uαn+1+j−imj​。

为了实现 d d d个位置元素subset的open，可扩展为具有 d d d个hole的CRS [ 1 , ( d + 1 ) n ] [1,(d+1)n] [1,(d+1)n]，对应的trapdoor key 位置为 n + 1 , 2 n + 1 , ⋯   , d n + 1 n+1, 2n+1,\cdots, dn+1 n+1,2n+1,⋯,dn+1。需要将 d d d个元素的open proof combine为constant size，方法为，将单个位置的 W i W_i Wi​表示为 W l , i W_{l,i} Wl,i​——the i i i-th position of the l l l-th element as a “shift” of W i W_i Wi​ by a factor l l l in the exponent： W l , i = u α l n − i + 1 γ ⋅ ∏ j = 1 , j ≠ i n u α l n + 1 + j − i m j W_{l,i}=u^{\alpha^{ln-i+1}\gamma}\cdot \prod_{j=1,j\neq i}^{n}u^{\alpha^{ln+1+j-i}m_j} Wl,i​=uαln−i+1γ⋅∏j=1,j​=in​uαln+1+j−imj​

支持subset query 的accumulator的基本流程为： 支持subset query 的accumulator的具体算法可为：