多变量公钥密码的新型设计及在云外包计算中的应用

As a typical kind of post-quantum public key cryptography, multivariate public key cryptosystems have some challenging issues to be addressed, including the fully nonlinear trapdoor design theory and the mutivariate fully homomorphic encryption algorithms. Therefore, this project performs the following researches. Firstly, to avoid the linearity of the trapdoor design and the security flaws of the partial nonlinearity imposed by the padding algorithms in multivariate public key cryptography, study the fully nonlinear trapdoor embedding techniques and the security against the existing attacks. Secondly, study the multivariate fully homomorphic encryption theory, develop new ciphertext updating and ciphertext compression techniques, and prove the security of the newly-designed multivariate fully homomorphic encryption scheme. Thirdly, based on the intractability assumption for solving system of multivariate equations, design more secure and efficient cloud computations outsourcing protocols and the private information retrieval protocols which are applicable to the cases of big fields or rings. The contributions of the project will provide systematic fully nonlinear trapdoor embedding techiques in multivariate public key cryptography, novel multivariate fully homomorpihc encryption theory, and couples of secure and efficient cloud computations outsourcing protocols. The research focuses on both the theoretic depth and the application width, and meanwhile the project also emphasizes particularly on the long-term steadiness and the persistence of the research. We also hope that the project can help us to agglomerate into a research team standing on the international research frontier.

多变量公钥密码作为后量子公钥密码的典型代表之一仍存在诸多值得研究的“硬”课题，其中就包括多变量公钥密码的全局非线性陷门设计理论与多变量全同态加密算法。为此，本项目作如下内容的研究。1.针对多变量公钥密码的陷门嵌入的线性性和现有补丁算法只能实现局部非线性性的安全缺陷，研究多变量公钥密码全局非线性陷门嵌入技术及其抗已有攻击的安全性。2.研究多变量全同态加密理论，探索新的密文更新和密文压缩技术，证明多变量全同态加密的安全性。3.基于多变量多项式组的求解问题的困难假设，设计针对大域或环的、高效、安全的云外包计算协议和隐私信息恢复协议。研究成果将包括多变量公钥密码系统的全局非线性陷门嵌入技术、新颖的多变量全同态加密理论以及一系列高效、安全的云外包计算协议。本项目兼顾理论的深度和应用的广度，同时也侧重研究工作的稳定性和可持续性。同时也希望借助该项目把课题组凝聚成站在国际学术前沿的研究团队。

多变量公钥密码作为后量子公钥密码的典型代表之一仍存在诸多值得研究的“硬”课题，其中就包括多变量公钥密码的全局非线性陷门设计理论与多变量全同态加密算法。为此，本项目基于多变量公钥作如下内容的研究。1.全局非线性陷门嵌入技术；2.全同态加密理论；3.高效安全的云外包计算协议和隐私信息恢复协议。主要结果包括：通过建立子集和问题和联立丢番图逼近问题之间的联系，提出一种新的子集和问题启发式求解算法；基于一些无碰撞性质的研究，提出首个从背包密码到SVP问题上的确定性归约；提出一个基于NTRU 的可证明安全的公钥加密算法的构造，D-NTRU，这一构造比起目前的NTRU变体具有更快的加解密速度、更低的密文扩展、可证明安全；通过将已有的球面采样扩展到非球面，提出一种新型的离散高斯采样算法；构建第一个加密云上达到隐私保护的常规语言搜索机制，并且没有增加额外的通信和计算消耗；对Li等人在2016年提出的可抵抗已知明文攻击的对称全同态加密方案，提出可以利用连分式算法和欧几里得算法来恢复出该方案的私钥信息；之后，改进该密码分析方法，提出了一种新的唯密文攻击；构建第一个同时实现可追踪性，用户撤销，以及密文更新三种功能的属性基加密方案；现有数据安全去重方案普遍面临计算和通信消耗大且无法抵抗共谋攻击，对此提出一个基于密钥共享的云存储数据安全去重方案；降低首个支持多项式尺寸电路的属性基加密方案GVW13的密钥尺寸,并指出该改进方案在密钥矩阵符合某些特性时不能抵抗共谋攻击；构造高效的适用于移动设备的属性加密方案的安全解密外包；提出一种面向商场交易记录的实用隐私保护频繁项集挖掘方法；给出基于理想格的UC安全的不经意传输协议；构造云环境下利用备份数据在用户撤销时重签名的算法；对属性加密的两个主流方案之一，即BGG+14ABE方案给出了弱点分析；提出Kumer的基于欧拉定理的对称全同态加密方案的改进算法，使得方案可以抵抗私钥恢复攻击；构造一系列公钥密码应用方案，包括基于属性的加密、基于身份的加密、去重、审计、环签名、盲签名、无证书签名、群签名等。研究成果丰富了公钥密码的设计理论，为实用的多变量公钥密码体制提供了系统的设计理论和分析技术。