基于格和身份的广播加密方案的研究

摘要

自公钥密码体制思想提出以来，经过不断的发展，已经成为了保障信息安全的主要手段。常用的公钥密码体制构造一般基于两个问题：大整数因子分解问题和离散对数困难问题。但是这些系统的运算复杂性，导致效率问题成为制约公钥密码系统发展的主要因素。随着量子计算的发展进步，基于上述问题的密码体制的安全性亦面临严峻的挑战。1996年Ajtai的开创性工作为基于格的困难问题假设构造新型的公钥密码系统提供了全新的研究方向。针对目前研究结果推测，不存在求解近似因子为多项式的格困难问题的多项式时间量子算法。另外，格是一种线性结构，格上的运算大多是线性运算，因此可以期望基于格的困难问题构造的新密码系统运算效率更高。
　　本文围绕基于格的密码方案展开研究，主要对格的困难问题和基于格的困难问题构造的密码方案进行分析，尤其是基于格的LWE问题构造的方案。另外，着重分析基于身份的加密（IBE）体制的构造思想和安全性证明，并结合广播加密的研究，构造了两个基于格和基于身份的广播加密（IBBE）方案。主要的研究工作如下：
　　一、利用单向陷门函数和强不可伪造一次签名算法构造了基于LWE困难问题的IBBE方案。方案中，利用哈希函数把身份向量映射成矩阵，并构造与身份集合相关联的矩阵。方案在随机预言机模型下证明是能够抵抗适应性选择密文和选择身份攻击（IND-ID-CCA）安全的。证明思想来源于Agrawal的证明思路：通过构造一系列的敌手和挑战者之间的Game来完成安全性的说明。另外，该方案将会话秘钥作为比特串输入，与单比特方案相比，执行效率更高。
　　二、利用单向陷门函数构造一个单比特的基于LWE困难问题的IBBE方案。方案中，利用编码函数将身份向量映射为矩阵，并构造与身份集合相关联的矩阵。另外，方案中对噪声向量进行了特殊处理。该方案的安全性也是通过一系列敌手和挑战者之间的Game完成说明，并在标准模型下证明是能够抵抗选择身份和选择明文攻击（IND-sID-CPA）安全的。