论文部分内容阅读
多线性映射是一个新奇的密码原语,有着太多的密码应用和新型服务。GGH(该名字源于三位作者Garg,Gentry和Halevi名字的首字母)映射是第一个也是最主要的多线性映射候选方案,它的出现拉开了多线性映射研究热潮的序幕,各种高级密码应用和新的候选方案等一大批优秀成果相继涌现。尽管Garg等人通过对GGH映射进行大量的密码分析来说明其安全性,并指出GGH映射能够抵抗几乎所有与格相关的密码攻击,但由于他们无法对GGH映射进行安全性证明,人们对GGH映射以及基于GGH映射的各种密码应用到底是否安全持一定的怀疑态度。本文致力于GGH映射及其各种密码应用(分为公开/隐藏编码工具两种情况)的安全性方面的研究。通过引入变形的编码/零测试、对特定NPC问题的弱化以及构建替代的编码工具等新技术,我们对GGH映射及其各种密码应用进行了有效的攻击,取得如下主要成果。1.攻破了基于GGH映射的非交互多方密钥交换协议(Eurocrypt 2013):首先,通过弱离散对数攻击,可由公开信息求出用户秘密的“等价秘密”;然后,通过我们提出的第一个新技术――变形的编码/零测试工具,可以将“等价秘密”中的噪声降低至足够小,进而得到用户间所共享的秘密。由于该协议的安全基础是基于GGH映射的分级编码判定Diffie-Hellman假设,因此,我们的攻击也表明该困难假设不成立。2.攻破了基于GGH映射的分级编码计算Diffie-Hellman假设(Eurocrypt 2013)以及基于GGH映射的两个代表性应用――身份基聚合签名方案(Crypto 2013)和属性基加密方案(Crypto 2013):通过对第一个新技术的改进,我们可以将一个高阶编码降为其相应的1阶编码,这意味着对分级编码系统进行了“除法”运算,破坏了其“可乘不可除”的代数结构。这种“除法”运算可以直接用来攻破基于GGH映射的分级编码计算Diffie-Hellman假设。此外,对基于GGH映射的身份基聚合签名方案,我们在只得到系统公钥的情况下,可以有效地计算出任意用户的私钥,进而可以伪造该用户对任意消息的签名;对基于GGH映射的属性基加密方案,任意合法用户可以在只得到公开参数的情况下,解密任意密文,包括那些他/她没有解密权限的密文,这完全破坏了属性基加密方案中的访问控制特性。3.攻破了基于GGH映射和3-精确覆盖问题的证据加密方案(STOC 2013):在上述变形的编码/零测试的基础上,通过引入第二个新技术――将3-精确覆盖这一NPC问题弱化为易解的组合3-精确覆盖问题,我们可以在编码工具公开的情况下,攻破该证据加密方案;进一步,在上述两个新技术的基础上,通过引入第三个新技术――构建替代的的编码工具,我们同样可以在编码工具隐藏的情况下,攻破该证据加密方案。4.攻破了GGH映射的两种简单修改方案:这两种类型的修改方案由我们自己提出,基本涵盖了GGH映射的所有简单变形。通过对第一个新技术的扩展和进一步的分析,在“2κ是多项式大”的假设下,攻破了这两种修改方案。我们的工作是对GGH映射及其应用的否定。可以断言:在编码工具公开的情况下,任何基于GGH映射的密码应用都是不安全的;在编码工具隐藏的情况下,至少有一个基于GGH映射的密码应用是不安全的;GGH映射很难通过简单修改来避开我们的攻击。