摘要: 研究的背景和意义。 零知识证明是一种概率交互证明的过程，这个证明过程有效的说明一个语言的成员之所属关系， 同时不暴露除此以外的任何信息。 零知识证明由Goldwasser， Micali， 和Rackoff于上个世纪80年代中期提出。 现在发展成为密码学的一个非常活跃的分支。 有鉴于现代丰富的零知识证明的成果，以及集合这个数学上最为基本的概念， 人们寻找适当的零知识集合的构造。 Micali， Rabin和Kilian 2003 年在FOCS会议上给出了第一个关于零知识集合的概念。 这个概念表达这样的理念: 一个证明者对于一个有限集合给出一个承诺。 随后，当一个验证者询问某个元素的所属关系时，证明者可以给出一个成员或者非成员关系的证明。这个证明不泄露出集合其他的信息。零知识集合是一个非常有应用前景的概念。比如，在现代社会中，隐私保护是一个越来越受到人们重视的问题。医院对于病人的信息有保密的义务，一个具体的例子是：某个医院为了配合某个机构对于患某些疾病者的调查。医院将该院患该疾病的病人进行作为零知识集合进行承诺。然后对于该机构感兴趣的人员进行回答和证明，从而保护所有其他患者的私密信息。类似这样的例子比比皆是。 研究的内容，研究中采取的方法，手段和新的发现。 Micali 等人给出了第一个零知识集合的构造。这个构造采用了Merkle 树的方法进行证明所承诺的值。对于每个节点的值使用了后来称为水银承诺（mercurial commitment）的方案。在这个方案中，使用了Peterson 承诺方案。这个方案被后来者证明，可以用其他具有类似性质的技术实现。纵观Micali等人的构造，可以发现，该构造有一个很大的局限性：即无法有效地对于所承诺的集合进行更新。当我们添加一个值时，该方案会牵涉到许多的内部节点，甚至导致破坏完全零知识性。对于减少一个值也有类似问题。这个问题的产生主要源于该结构的树状构造。另外，正如后来人们证明的那样，水银承诺等价于陷门承诺。就是说，Micali 等人的结构使用了陷门手段。 研究的创新点和主要贡献。 针对上述问题，我们仔细的研究了零知识集合的必要条件，利用积聚器（accumulator）的原理，成功地构造了第一个不使用树结构的零知识集合的方案。我们的结构具有表达简洁，证明简洁，和验证简洁的特点。另外，该结构是一个天然的易于更新的结构。新的结构在承诺、证明中没有使用任何的陷门手段。这也是一个有别于现有构造的新颖之处。但是我们的结构是一个计算零知识集合而不是完全零知识集合。该结构的安全性证明是在随机问答器模型下完成的。一个在标准模型下安全的完全的零知识集合的构造和证明将在另一个文章中给出。