格公钥密码的新型设计与新型密码分析研究

作为后量子密码的典型代表，格公钥密码的主要缺陷是庞大的空间尺寸。此外，格公钥密码在设计、分析和应用领域远非成熟。本课题针对这些关键问题，拟就以下内容开展工作：（1）基于格的陷门的新型设计和安全性证明，目的是在可证明安全的前提下显著降低陷门的空间尺寸。（2）基于格的加密算法的新型设计，主要目的之一是试图避开脆弱的LWE。（3）应用领域的新发现，比如基于格的特殊签名、不经意传输、签密等。（4）格上各种难题的新型数学分析以及现有格公钥密码的新型密码分析，其中包括对LWE脆弱性的更系统的讨论，SVP王小云算法的更深入分析和变形，NTRU的安全性缺陷的进一步发掘等。综上所述，本课题预期将拓展和深化格公钥密码理论，为未来的后量子信息安全提供更加充分的理论储备。本课题可行的理由有两条：其特点和内容符合我们的专业方向和长期科研积累；我们已经获得了课题的一些初步的但比较重要的预研成果。

格公钥密码是当今密码学领域研究的热点。本项目力图在格上高斯抽样算法、公钥加密算法、数字签名算法及已有密码原型的分析方面取得一批创新成果。经过四年的努力工作，项目组在各个方面都取得了重要进展，基本达到了申请书上的研究目标，具体如下：.在格上高斯抽样算法方面：通过使用Hash函数和一个叫做“接受率”的技术，对Gentry等人提出的高斯抽样算法进行改进。该算法得到高斯分布的尺寸为原有算法的0.64倍。同时，该算法没有以时间开销作为代价。.在公钥加密算法方面：利用盆景树模型和Gentry的抗选择明文攻击的公钥加密方案，构造了一个格上高效的选择密文安全的公钥加密方案；在标准模型下，利用混合加密的概念提出了一个构造KDM安全的非对称加密方案的新方法；利用原像抽样技术，构造了格上第一个允许多次使用的选择明文安全的单向代理重加密方案，该方案可以抵抗合谋攻击，同时该方案扩展为基于身份的单向代理重加密方案；将全同态加密的两种批处理技术应用到一个全同态加密方案中，并基于RLWE困难问题提出一个限层全同态加密方案；利用Smart等人所构造同态加密的几个特殊性质构造出一个简单且具有相对短密钥和密文尺寸的分级加密方案；.在数字签名算法方面：利用原像抽样函数设计了一个高效的线性同态签名方案；基于SIS和LWE问题构造了一个满足强指定验证特性的数字签名方案，利用该签名方案还可以构造一个强指定验证者的环签名方案；基于SIS问题构造了一个代理重签名方案，该方案具有双向性、多次使用性、密钥最优性以及透明性，该方案还可以扩展为基于身份的代理重签名方案。基于SIS问题，利用原像抽样技术构造了格上第一个多次使用的单向代理重签名方案；利用原像抽样算法构造了格上第一个多次使用的单向代理重签名方案。.在密码原型的分析方面：通过研究得知，在公开编码工具的情况下，GGH映射的应用不再安全；隐藏编码工具的情况下，至少一个GGH映射的应用不安全。