原文为Dario Catalano与Dario Fiore于2013年发表的论文$[1]$

Abstract

本文提出了一种新的原语，称为向量承诺（Vector Commitment，VC），向量承诺可以对一个长度为$q$的有序序列$(m_1,\dots,m_q)$进行承诺，之后在特定的位置揭示承诺值（比如揭示第$i$个位置的值为$m_i$）

向量承诺的一个核心安全性需求称为位置绑定性，也即敌手无法在同一位置将承诺值揭示为不同的两个值

此外，本文还希望向量承诺实现简洁性，也即承诺及其揭示的大小与向量长度无关

这里的简洁性原文用了concise这个单词，感觉很少见到用这个单词，描述简洁性更多见到的是用succinct

本文介绍了基于标准假设和既定假设（established assumptions）的向量承诺的实现（比如RSA假设和基于双线性群的计算DDH假设）

向量承诺是一种紧凑且高效的原语，在许多地方都有用，包括但不限于：可高效更新的可验证数据库、可更新的ZKP数据库、通用动态累加器

1 Introduction

承诺是一种广泛使用的密码学原语，可以视为秘密信封的密码学等价物

利用承诺方案，当承诺者需要承诺一条消息$m$时，可以将该消息放入信封中，并在稍后打开信封，公开其承诺的信息

承诺方案具备两个性质

  • 隐藏性：承诺方案不会揭示被承诺的消息
  • 绑定性：承诺者无法将被承诺的消息揭示为两个不同的值，也即揭示阶段无法改变被承诺的值

承诺方案在密码学中非常有用，且被用于实现大量的复杂密码学协议和密码学原语，但是仅凭上述两个性质难以满足复杂原语中多样化的安全需求，因此密码学的大佬们开始研究一些承诺方案的附加属性和更为复杂的概念，以满足对进阶密码协议的安全性需求，之前研究过一些，比如陷门承诺方案$[5]$（变色龙承诺，Chameleon Comm.）

2 Preliminaries

  • $k\in \N$：安全参数
  • $\mathcal A$：PPT敌手，受安全参数$k$限制
  • $x\larr S$：表示从集合$S$中随机选择一个元素$x$
  • $[n]$：表示正整数集合$\{1,2,\dots,n\}$
  • $(\mathbb G,\mathbb G_T,e,p,g)$：双线性群，两个群的阶均为素数$p$，群$\mathbb G$的生成元为$g$，映射$e:\mathbb G\times\mathbb G\rarr \mathbb G_T$

本文采用两个计算假设：RSA假设和Square-CDH假设

  • RSA Assumption：记$N$为RSA的模数，满足$|N|=k$，记$z\in \Z_N$为随机元素，$e$为由参数$l$确定的素数，长度为$|e|=l+1$，RSA假设要求，对于任意PPT敌手$\mathcal A$，有下列等式成立

$$ Pr[y\larr \mathcal A(N,e,z):y^e=z\mod N]\leq negl(k) $$

  • Square-CDH Assumption：记$\mathbb G$为某一群，阶为素数$p$，生成元为$g\in\mathbb G$，对于随机元素$a\larr \Z_p$，群$\mathbb G$的Square-CDH假设要求任意PPT敌手$\mathcal A$，有下列等式成立

$$ Pr[\mathcal A(g,g^a)=g^{a^2}]\leq negl(k) $$

部分文献研究表明，Square-CDH假设等价于标准CDH假设

3 Vector Commitments

本文将向量承诺定义为一种非交互式原语，并将其形式化为下列六个算法

  • $KeyGen(1^k,q)$：密钥生成算法，其中$k$表示安全参数，$q$表示承诺向量的长度（$q=poly(k)$），密钥生成算法输出方案需要的公共参数$pp$（并隐式定义消息空间$\mathcal M$）
  • $Com_{pp}(m_1,\dots,m_q)$：对于向量$(m_1,\dots,m_q)\in \mathcal M$，算法输出承诺值$C$和辅助信息$\mathrm {aux}$
  • $Open_{pp}(m,i,\mathrm{aux})$：算法输出一个证明$\Lambda_i$，用于证明第$i$个位置的值
  • $Ver_{pp}(C,m,i,\Lambda_i)$：用于验证证明$\Lambda_i$是否满足$m=m_i$
  • $Update_{pp}(C,m,m',i)$：对于承诺值$C$，算法用于将第$i$个位置的值由$m$更新至$m'$，算法输出新的承诺值$C'$和更新信息$U$
  • $ProofUpdate_{pp}(C,\Lambda_j,m',i,U)$：任意拥有关于承诺值在位置$j$处的证明$\Lambda_j$的用户可以执行该算法，用于将承诺和证明分别更新至$C'$和$\Lambda_j'$，使得$\Lambda_j'$是关于新的承诺值$C'$的合法证明，并且位置$i$的值为更新后的值$m'$（$U$为计算这些值需要的相关信息）

上述方案需要满足位置绑定性（Position Binding），也即对于任意PPT敌手$\mathcal A$，对于诚实生成的相关参数，$\mathcal A$在同一个位置揭示两个不相同的值$m_i\neq m_i'$的概率可忽略

部分承诺方案还需要满足隐藏性，也即敌手在获取到一部分揭示值之后，仍然无法区分两个承诺序列$(m_1,\dots,m_q),(m'_1,\dots,m'_q)$，不过对于向量承诺而言，隐藏性并不是基本安全属性，后续主要关注其绑定性

不过不满足隐藏性的向量承诺可以与标准承诺方案进行组合，以实现隐藏性，首先使用标准承诺方案对消息进行承诺，然后再利用向量承诺对消息序列进行承诺，即可获得隐藏性

3.1 A Vector Commitment based on CDH

介绍一下基于双线性群中CDH假设的向量承诺的实现，安全性可归约为Square-CDH

  • $KeyGen(1^k,q)$：对于双线性群$\mathbb G,\mathbb G_T$，随机选择$(z_1,\dots,z_q)\larr \Z_p$，对于$i\in [q]$，计算$h_i=g^{z_i}$，对于$i,j\in[q],i\neq j$，计算$h_{i,j}=g^{z_iz_j}$，输出公共参数$\mathrm {pp}$如下

$$ \mathrm {pp}=(g,\{h_i\}_{i\in[q]},\{h_{i,j}\}_{i,j\in[q],i\neq j}) $$

记消息空间$\mathcal M=\Z_p$

  • $Com_{pp}(m_1,\dots,m_q)$：承诺值的计算方式如下

$$ C=h_1^{m_1}h_2^{m_2}\cdots h_q^{m_q} $$

算法同时输出辅助信息$\mathrm{aux}=(m_1,\dots,m_q)$

  • $Open_{pp}(m_i,i,\mathrm{aux})$：证明$\Lambda_i$的计算方式如下

$$ \Lambda_i=\prod^q_{j=1,j\neq i}h^{m_j}_{i,j}=\Big( \prod^q_{j=1,j\neq i}h^{m_j}_j \Big)^{z_i} $$

  • $Ver_{pp}(C,m_i,i,\Lambda_i)$：验证等式$e(C/h^{m_i}_i,h_i)=e(\Lambda_i,g)$，当且仅当等式成立时输出1，否则输出0
  • $Update_{pp}(C,m,m',i)$：计算更新承诺值$C'=C\cdot h_i^{m'-m}$，输出$C'$和$U=(m,m',i)$

  • $ProofUpdate_{pp}(C,\Lambda_j,m',U)$：对于承诺值$C$的位置$j$的合法证明$\Lambda_j$，利用更新信息$U=(m,m',i)$，更新方式如下

    • $i\neq j$的情况：计算$C'=C\cdot h_i^{m'-m}$，更新的证明值为$\Lambda_j'=\Lambda_j\cdot (h_i^{m'-m})^{z_j}=\Lambda_j\cdot h_{j,i}^{m'-m}$
    • $i=j$的情况：计算$C'=C\cdot h_i^{m'-m}$，更新的证明值仍为$\Lambda_i$（无需更新证明值）

‍
这里有个定理：若CDH假设成立，则上述方案为一个简洁的向量承诺方案

可以看一下证明，主要是证明上述方案满足位置绑定性，

用反证法，假设存在一个敌手$\mathcal A$，其可以在同一个位置将承诺揭示为两个不同的值$m_i\neq m_i'$，然后尝试构建一个算法$\mathcal B$来攻破CDH假设

首先$\mathcal B$输入$(g,g^a)$，根据前面提到的CDH假设，算法$\mathcal B$的目标是计算$g^{a^2}$，这里$\mathcal B$首先猜测$\mathcal A$揭示的位置（通过随机选择$i\larr [q]$的方式来猜）

然后$\mathcal B$对于$\forall j\in[q],j\neq i$，选择一些随机元素$z_j\larr \Z_p$，基于这些元素计算下列两组元素

$$ \begin{aligned} &\forall j\in [q]\backslash\{i\}:h_j=(g^{z_j}),h_{i,j}=(g^a)^{z_j},h_i=g^a\\ &\forall k,j\in[q]\backslash\{i\},k\neq j:h_{k,j}=g^{z_kz_j} \end{aligned} $$

然后$\mathcal B$令公共参数$\mathrm {pp}=(g,\{h_i\}_{i\in[q]},\{h_{i,j}\}_{i,j\in[q],i\neq j})$​

这里的公共参数$\mathrm{pp}$和真实协议执行中的公共参数具有相同的分布

根据假设，敌手$\mathcal A$可以攻破位置绑定性，这意味着敌手$\mathcal A$可以输出$(C,m,m',j,\Lambda_j,\Lambda_j')$，满足$\Lambda_j,\Lambda_j'$均为合法的证明，且$m\neq m'$

此时若有$i\neq j$，则$\mathcal B$终止模拟过程，否则$\mathcal B$输出$g^{a^2}$，如下

$$ g^{a^2}=(\Lambda_i/\Lambda_i')^{(m_i-m_i')^{-1}} $$

注意到由于$\Lambda_j,\Lambda_j'$均为合法的证明，因此有下列等式成立

$$ e(C,h_i)=e(h^m_i,h_i)\cdot e(\Lambda_i,g)=e(h_i^{m'},h_i)\cdot e(\Lambda_i',g ) $$

因此有$e(h_i,h_i)^{m-m'}=e(\Lambda_i'/\Lambda_i,g)$，由于$h_i=g^a$，不难验证$\mathcal B$的输出符合要求

若$\mathcal A$攻破位置隐藏性的概率为$\epsilon$，则$\mathcal B$可以以$\epsilon/q$的概率攻破Square-CDH假设，证毕

然后简单看一下上述方案的效率，不难看出方案有一个非常明显的缺点，就是公共参数$\mathrm{pp}$非常大，复杂度为$O(q^2)$，导致这个方案不适合与大数据集一起使用

不过回看一下方案，Verifier不需要元素$h_{i,j}$，此时可以优化一下$\mathrm{pp}$，使得Verifier不需要存储$\mathrm{pp}$中的所有的$h_i$，优化方式如下

  • 运行Setup算法的参与方首先对每一对$(i,h_i)$进行签名，并将签名值$\sigma_i$包含至$\mathrm{pp}$中，同时公开签名的验证密钥
  • 承诺放将$\sigma_i,h_i$包含至证明$\Lambda_i$中，此时Verifier只需要保存$g$和签名的验证密钥即可

注意到上述优化方式中第二步需要验证签名值$\sigma_i$，因此需要在验证证明值$\Lambda_i$的算法$Open$中加入验证签名值的步骤

3.2 A Vector Commitment based on RSA

  • $KeyGen(1^K,l,q)$：随机选择两个长度为$k/2$的素数$p_1,p_2$，计算$N=p_1p_2$，选择$q$个长度为$(l+1)$的素数$e_1,\dots,e_q$，满足$\forall i,e_i\nmid \phi(N)$，之后对于$i\in[q]$，计算$S_i$如下

$$ S_i=a^{\prod^q_{j=1,j\neq i}e_j} $$

公共参数$\mathrm{pp}=(N,a,S_1,\dots,S_q,e_1,\dots,e_q)$，消息空间$\mathcal M=\{0,1\}^l$

  • $Com_{pp}(m_1,\dots,m_q)$：计算$C\larr S_1^{m_1}\cdots S_q^{m_q}$，辅助信息$\mathrm{aux}=(m_1,\dots,m_q)$
  • $Open_{pp}(m,i,\mathrm{aux})$：揭示算法计算如下

$$ \Lambda_i\larr \sqrt[e_i]{\prod^q_{j=1,j\neq i}s_j^{m_j}} \mod N $$

  • $Ver_{pp}(C,m,i,\Lambda_i)$：验证算法当且仅当$m\in \mathcal M$，且有等式$C=S_i^m\cdot \Lambda_i^{e_i}\mod N$成立时输出1，否则输出0
  • $Update_{pp}(C,m,m',i)$：计算更新承诺$C'=C\cdot S_i^{m'-m}$，算法同时输出更新信息$U=(m,m',i)$

  • $ProofUpdate_{pp}(C,\Lambda_j,m',i,U)$：和上一个方案一样，分两种情况处理

    • $i\neq j$的情况：计算$C'=C\cdot S_i^{m'-m}$，然后更新证明$\Lambda_j'=\Lambda_j\cdot \sqrt[e_j]{S_i^{m'-m}}$
    • $i=j$的情况：计算$C'=C\cdot S_i^{m'-m}$，无需更新证明

这里有两个点需要注意

  • $Open$算法：利用$\mathrm{pp}$的信息，可以在不需要知道$N$的分解的情况下计算$\Lambda_i$
  • $Ver$算法：不仅需要验证证明正确，还需要验证公钥的正确性，也即验证$S_i$确实是由随机性$a$和指数$e_1,\dots,e_q$计算得到的

上述方案对应的定理如下：若RSA假设成立，则上述算法为简洁的向量承诺方案

下面看一下证明，也是主要关注位置绑定性，同样使用反证法，构造算法$\mathcal B$来完成证明

首先$\mathcal B$输入$(N,e,z)$，其中$e$为长度为$l+1$的素数，同时算法$\mathcal B$利用敌手计算$y$，满足$z=y^e\mod N$

之后$\mathcal B$随机选择索引$j\in [q]$（猜测敌手$\mathcal A$的揭示位置），令$e_j=e,a=z$，公钥的其余部分与$KeyGen$算法中的计算方式相同

对于敌手$\mathcal A$的输出$(C,m,m',j,\Lambda_j,\Lambda_j')$，满足$\Lambda_j,\Lambda_j'$均为合法的证明，且$m\neq m'$，若$i\neq j$，则$\mathcal B$终止，否则$\mathcal B$可以根据等式$S=S_i^m\cdot \Lambda_i^{e_i},S=S^{m'}_i\cdot \Lambda_i'^{e_i}$，计算得到下列等式

$$ S^{m-m'}_i=(\Lambda'_i/\Lambda_i)^{e_i}\tag 1 $$

此时记$\delta=m-m',\Lambda=\Lambda'_i/\Lambda_i$，可将上述等式改写为

$$ a^{\delta\cdot \prod_{j\neq i}e_j}=(\Lambda)^{e_i}\tag 2 $$

若$\Lambda=1$，由于$a$为$\Z_N$中的随机元素，根据$[2]$中的结果，$a$的阶很大，因此此时可以以不可忽略的概率完成分解

因此，若假设$\Lambda\ne 1$，则利用$[3]$中的方案，此时可以得到$a$的$e_i$次根，具体而言，由于$\gcd(m\prod_{j\neq i}e_j,e_i)=1$，此时利用扩展欧几里得算法可以计算出两个系数$\lambda,\mu$，满足

$$ \lambda\cdot m\prod_{j\neq i}e_j+\mu\cdot e_i=1 $$

这里把式2中的$m$视为式1中的$\delta$，然后将式2代入式1，可得

$$ \begin{aligned} &a^{\delta\cdot \prod_{j\neq i}e_j}=(\Lambda)^{e_i}\\ &a^{\lambda\delta\cdot \prod_{j\neq i}e_j}=(\Lambda)^{\lambda e_i}\\ &a^{\lambda\delta\cdot \prod_{j\neq i}e_j+\mu\cdot e_i}=(\Lambda)^{\lambda e_i}\cdot a^{\mu\cdot e_i\\}\\ &a=(\Lambda^\lambda a^\mu)^{e_i} \end{aligned} $$

因此$\Lambda^\lambda a^\mu$是$e_i$次根，从而利用这一点攻破RSA假设，证毕

效率方面，和基于CDH方案的相同，具有$\mathrm{pp}$较大的缺点，不过RSA方案中的$\mathrm{pp}$与向量长度$q$呈线性关系，比基于CDH的方案好一些，但是也没有特别好

不过与CDH相同，基于RSA的方案也可以采用签名的方式进行优化

3.3 A Vector Commitment with constant-size public parameters

上面的两个方案都有一个共同的缺点：公共参数的大小与向量的长度相关，即便是最好的RSA方案也是线性阶的，采用签名的方式进行优化并没有从本质上解决问题，而且验证签名也需要引入额外的计算量，导致了其不适用于一些数据集比较大的场景

本节介绍一下如何使得基于RSA的方案的公共参数与向量长度独立，但是这个优化会导致小路的下降，因此这里只是作为一个独立的研究点，表明具有常数大小的承诺，且公共参数的长度独立于向量长度的向量承诺是可实现的

基于RSA方案的优化主要是针对$KeyGen$算法的优化，其余算法不变

这里需要用到一个伪随机函数$f_s:\{0,1\}^*\rarr \{0,1\}^{l+1}$，优化方案具体如下

首先为伪随机函数选择一个随机种子$s$和一个随机的二进制串$c\larr \{0,1\}^{l+1}$，然后定义一个函数$F_{s,c}$

$$ F_{s,c}(j)=f_s(i,j)\oplus c $$

其中$i\geq 1$，表示使得$f_s(i,j)\oplus c$为奇素数的最小整数

然后选择随机元素$a\in \Z_N$

对于$i\in [q]$，定义$S_i$如下

$$ S_i=a^{\prod^q_{j=1,j\neq i}e_j} $$

其中$e_j=F_{s,c}(j),\forall j\in [q]$，此时公钥为$vpk=(N,a,s,c)$，消息空间$\mathcal M=\{0,1\}^l$

相关内容和安全性证明可以参考$[4]$

4 Others

原文后面几章主要是介绍一下应用场景，感兴趣的可以看原文$[1]$，主要有下列几个应用

  • Verfiable Databases with Efficient Updates from Vector Commitments
  • (Updatable) Zero-Knowledge Elementary Databases from Vector Commitments
  • Universal Dynamic Accumulators from Vector Commitments

这里搬运一下原文第一节中对这三个方案的概述，详细方案可以看原文第4章之后的内容

Verifiable Databases with Efficient Updates

Benabbas，Gennaro和Vahlis三位大佬于2011年提出了可有效验证更新的数据库的概念（Verifiable Database with Efficient Updates，VDB）

该原语考虑了下面这个场景：假设一个资源受限的客户端希望再服务端上存储一个大型数据库，且后续希望对该数据库进行检错，或分配新值来更新数据库

由于客户端资源受限，为了提高效率，客户端需要确保执行此类操作时的计算开销与数据库的大小无关（初始化阶段除外）

此外，为了确保安全性，服务端无法在不被客户端检测到的情况下篡改数据库

首先考虑静态数据库（客户端不执行任何更新操作），可以通过消息身份认证或签名来实现，比如让客户端先对记录进行签名，然后请求服务端将记录和签名值一起输出

但是如果考虑动态的数据库，由于需要执行更新操作，签名不太好处理更新的行为，此时可以让客户端在本地追踪对数据库的修改，但是这一点又与资源受限的前提条件矛盾

解决这个问题的方法有很多，包括但不限于累加器，已验证的数据结构（Authenticated Data Structures，ADS）和可验证计算（VC），还有大佬琢磨出了一个称为已验证身份的远程文件系统（Authenticated Remote File System）来解决

但是$[5]$中的研究结果表明，基于累加器和ADS的方案要么依赖于非恒定大小的假设（比如q-Strong DH），要么开销巨大（比如需要生成素数和重洗牌，re-shuffling），Benabbas等人提出了一个具有高效查询和更新时间还算凑合的解决方案，该方案依赖于复合阶双线性群中的恒定大小假设，但该方案不满足公开可验证性，只有数据库的所有者才能验证服务器提供的证明的正确性

本文介绍了向量承诺可用于构建VDB，解决了上述不满足公开可验证性的问题，更重要的是，如果使用本文基于CDH的方案，还可以获得可验证数据库的实现，该实现依赖于标准的恒定大小的假设，效率比Benabbas等人的方案还要好

Updateable Zero Knowledge Elementary Databases

零知识集（Zero Knowledge Set，ZKS）最早由Micali，Rabin和Kilian三位大佬提出，允许Prover已某种方式承诺一个秘密集合$S$，并在后续阶段证明元素是否在该集合中，也即证明$x\in S$，或者$x\notin S$

该协议具有两个性质

  • Verifier可以在不知道集合$S$的任何信息的条件下（甚至不知道集合的大小），检查接收到的证明的有效性，而不仅仅是检查某个元素的成员或非成员归属
  • 证明应当是可靠的（Reliable），任意恶意的Prover都无法通过虚假的证明说服Verifier

Chase等人以及Catalano、Dodis和Visconti对Micali等人的结构进行了抽象，前者表明ZKS可以由陷门mercurial承诺和抗碰撞Hash函数构建，而且ZKS暗示了具备抗碰撞Hash函数的功能，后者从单向函数的假设出发，表明陷门可变承诺的一般构造

综合上述两个研究结果，抗碰撞Hash函数是在CRS模型中构建ZKS的充要条件，但是从实践角度来看，这两个方案的有效性都不足以确保其用于实际应用中

原因是这些方案需要用深度为$k$的Merkle Tree来对集合$S\sub \{0,1\}^k$进行承诺，树中的中间节点均为该节点两个子节点的mercurial承诺（而不是子结点的Hash值）

由于方案基于Merkle Tree构建，因此证明和揭示成员的归属问题需要展示叶节点至根结点的一个路径，这意味着证明大小与树的深入相关，而树的深度又与集合大小相关，至多只能对大小为$|S|=2^k$的集合构造ZKS，因此不适用于对大集合构建ZKS

而且这里还有一个问题，前面提到了不希望Verifier知道集合$S$的大小，这里需要选择，为了确保选择的$k$足够大，使得$2^k\gg |S|$，来隐藏$|S|$，这么一来又会导致Merkle Tree的深度增加，效率就更低了

Catalano、Fiore和Messina讨论了用较短的证明构建ZKS的问题，这几个大佬的想法是抛弃Merkle Tree这种二叉树，改用$q$元树，并尝试对mercurial承诺进行扩展（大佬们在原文中称为q-Trapdoor mercurial承诺，qTMC）

但是qTMC的缺点在于没有意料之中的高效，尽管软揭示（soft opening）与$q$无关，但是硬揭示（hard opening）与$q$呈线性关系，导致不太实用

后续研究中，Libert和Yung给出了一个q-mercurial承诺，可以实现恒定大小，从而使得zkEBD具有很短的证明（通过增加$q$来得到任意平坦的树），但是该方案依赖于非常数大小的假设：q-Diffie-Hellman Exponent Assumption

本文利用了一个定理：（简洁的）陷门q-mercurial承诺方案可通过向量承诺和陷门mercurial承诺方案构建，从而紧致ZKS可以从mercurial承诺和向量承诺构建，此时将向量承诺与已知的陷门承诺相结合时可以得到满足所需性质的qTMC

紧致（Compact），意思是ZKS的成员和非成员证明很短

此外，利用此类方案实例化Catalano等人的zkEDB的构造是，可以得到一个紧凑的zkEDB方案，且方案在标准假设下是可证明安全的

而且，本文的CDH方案的证明长度和Libert等人的方案相当，但是依赖于更好和更标准的安全假设

更重要的是，本文介绍了具有短证明的可更新zkEDB的构造，这个概念最早由Liskov引入，目的是将zkEDB扩展至动态数据库

在可更新的构造中，Prover可以更新数据库中的某些元素$x$，并输出新的承诺$C'$和更新信息$U$，拥有证明$\pi_y(y\neq x)$和承诺值$C$的用户可以将证明和承诺分别更新至$\pi_y',C'$

本文利用向量承诺实现了紧致的可更新zkEDB，证明和更新的大小的都要比Liskov的方案小得多，且本文还介绍了如何在随机预言机模型中利用VC实现可更新的qTMC和利用可验证随机函数构建可更新的zkEDB

Fully Dynamic Universal Accumulators

密码学累加器的概念最早由Benaloh和Me Mare提出，用于构造一组值的紧致表示，并可以给出成员证明，后续有学者将其扩展到动态的情况，动态表明被累加的集合可以改变，且可以更新之前的证明，累加器的一个扩展是通用累加器，不仅可以给出成员证明，还可以给出非成员证明

目前已知的累加器的构造（包含动态的和通用的）在没有随机预言机的条件下都是安全的，这些构造要么基于复合阶群（Composite Order Group）构建，且需要开销很大的运算来将集合元素映射到素数，要么基于素数阶群构建，但仅依赖于非恒定大小的假设（比如q-Strong DH或者q-DH）

此外，基于素数阶群的方案有一个缺点：仅支持大小为多项式有界的集合，而且此类方案需要群乘法，因此效率也是个头疼的问题

Additional Applications of Vector Commitments

一些可能会用到向量承诺的场景，比如伪匿名证书（Pseudonymous Credentials，不知道是不是这么翻译）

References

$[1]$ Dario Catalano, Dario Fiore:Vector Commitments and Their Applications. Public Key Cryptography 2013: 55-72

$[2]$ J. Hastad, A. Schrift, and A. Shamir. The discrete logarithm modulo a composite hides $o(n)$ bits. In Journal of Computer and System Science, volume 47 (3), pages 376–404, 1993.

$[3]$ Adi Shamir. On the generation of cryptographically strong pseudorandom sequences. ACM Trans. Comput.Syst., 1(1):38–44, 1983.

$[4]$ Susan Hohenberger and Brent Waters. Short and stateless signatures from the RSA assumption. In Shai Halevi,editor, CRYPTO 2009, volume 5677 of LNCS, pages 654–670. Springer, August 2009.

$[5]$ Melissa Chase, Alexander Healy, Anna Lysyanskaya, Tal Malkin, and Leonid Reyzin. Mercurial commitments with applications to zero-knowledge sets. In Ronald Cramer, editor, EUROCRYPT 2005, volume 3494 of LNCS,pages 422–439. Springer, May 2005.

‍