多线性映射的密码分析及其应用

As an extremely tempting cryptographic primitive, multilinear maps have too numerous new applications and cryptographic services to name. The current mainstream candidate multilinear maps, however, have been broken, including the celebrated GGH map broken by us. The following contents are studied in our project. 1. Continue to investigate the security of current surviving candidates by existing tools or finding out new means of attack. 2. Consider the existance of new candidates, including those “narrow multilnear maps” with partital application functionality. 3. Deal with certain applications of insecure multilinear maps, namely explore what applications of multilinear maps cannot be broken, such as indistinguishiable obufscation and functional encryption. 4. Design reversely, that is, contemplate the possibilities, efficiency and security of the constructions of multilinear maps from indistinguishiable obufscation. Research results will include more diverse attacking methods, a more comprehensive evaluation of multilinear maps, new design and structures, the feasibility in a wide range of application fields, as well as the deep association between multilnear map and program obfuscation. This project will not only take into account both the depth of theory and the breadth of applications, but also pay emphasis on the stability and sustainability of the research. Meanwhile, it is hoped that this project will cohere our research team to be an outstanding one among the international academic communities.

多线性映射是一个诱人的密码原语，有着太多的新型应用和密码服务，然而当前主流的候选多线性映射已被尽数攻破，其中包括我们攻破著名的GGH映射。本项目作如下内容的研究。1.继续研究当前仍存活的那些多线性映射的安全性，或使用我们已有的攻击工具，或寻找新的攻击手段。2.研究新的候选多线性映射的存在性，其中包括具有部分应用功能的“狭义多线性映射”。3.研究不安全的多线性映射的某些安全应用，即探讨多线性映射有哪些应用是不可破的，比如不可区分混淆和功能加密。4.一个反向设计，即由不可区分混淆来构造多线性映射的可能性、效率、安全性。研究成果将包括更加多样的攻击方法，对多线性映射更加全面的评判，多线性映射的新型设计和新型结构，在广泛应用领域中的可行性，以及与程序混淆的深度关联。本项目兼顾理论的深度和应用的广度，并且重视研究工作的稳定性和可持续性。同时也希望借助该项目把课题组凝聚成站在国际学术前沿的研究团队。

多线性映射因其蕴含丰富的密码应用和服务而成为当今密码学领域研究的热点。本项目以多线性映射的构造基础和应用为核心，主要开展了格公钥密码、全同态密码、属性基加密、混淆四方面的研究。经过四年的努力工作，项目组取得了丰富的成果。.首先，在密码原型设计方面，我们基于格上带差错学习、最短向量等困难问题提出了IND-CPA安全的新型公钥加密算法以及服务器辅助可撤销的属性基加密方案；基于格上带差错学习、最小整数解等困难问题，设计了满足不同场景需求的群签名、环签名、聚合签名、基于身份的签名等方案；提出了新型离散高斯抽样算法，且基于此设计了高效的数字签名验证方法。.其次，在密码原型分析方面，我们对Gorbunov等人于STOC’13提出的属性基加密方案给出了共谋陷阱攻击结果；对Boneh等人于EUROCRYPT’14提出的属性基加密方案及其简化变体给出了共谋攻击结果。.再次，在密码协议方面，我们分析了基于格的不经意传输协议在量子环境以及等式安全模型下的安全性；设计了基于格的改进的身份认证协议、不经意传输协议、哈希证明系统。 .最后，在密码应用方面，我们构造了算术电路计算双模函数，以用于全同态自举算法；基于混淆技术，设计了安全的广播多重签名方法、可搜索重加密方法、加密盲签名方法、不经意传输协议。.这些研究成果丰富了多线性映射底层构造工具的多样化设计与运用方法，扩展了多线性映射重要应用方案的安全性分析结果，为多线性映射的密码分析及其应用这一课题提供了坚实而广阔的研究基础。