谭子欣,邓 燚 ,马 丽

1中国科学院信息工程研究所 信息安全国家重点实验室 北京 中国 100093

2密码科学技术国家重点实验室 北京 中国 100878

3中国科学院大学 网络空间安全学院 北京 中国101408

1 引言

在过去,当用户需要访问数据,通常需要向数据管理者发送访问请求,然后管理者通过查表检查该用户是否具有访问权限。在这样的权限管理过程中,查表操作带来的开销往往会随着列表的大小呈线性增长,这样低效的管理方法显然将无法适应未来高速的大数据时代,为了解决这样的问题,1994年Benaloh和de Mare[1]提出了累加器的概念。累加器是指将某个集合中的所有元素压缩成一个较短输出,并能够为所有被累加值生成其对应的成员关系证据,通过成员关系证据可以向他人证明被累加值的成员身份,故而用户可直接将其身份和成员关系证据发送给数据管理者,数据管理者再通过一个确定的检验算法来判定该用户的合法性,这样的过程大大缩减了权限管理中的验证时间。除此之外,累加器在数字签名、匿名凭证、范围证明、集合成员关系证明等领域也有相当多的应用场景。

近二十年来,累加器的发展日新月异,功能性及安全性也在不断的更新和完善。1997年Barić和Pfitzmann[2]提出了无碰撞累加器的概念,并且首次给出了累加器的安全性定义。2002年Camenisch和 Lysyanskaya[3]提出了动态累加器的概念,即累加器增删元素的更新操作的时间复杂度独立于集合大小。2005年 Nguyen[4]提出了基于强Diffie-Hellman假设的动态累加器,2008年Damgård[5]和Triandopoulos又在此基础上设计出了能够支持非成员关系证明的双线性映射累加器。……