适于双线性对计算的椭圆曲线构造和高效双线性对设计

高效实现基于双线性对的密码系统或协议由两部分决定：1）适于双线性对计算的椭圆曲线；2）可有效计算的双线性对。本项目拟利用分解分圆多项式的技巧和复乘方法构造更多适于双线性对计算的椭圆曲线。这部分研究结果一方面可为不同安全级别的密码系统实现提供更丰富的曲线选择；另一方面可从根本上提高密码系统的实现效率。此外，本项目拟设计可高效计算的双线性对和优化已有的双线性对计算方法，以达到更高安全级别(主要考虑AES 128比特安全级别)的性能要求。特别地，将重点考虑具体的密码协议中所需要的双线性对计算问题，如ZSS短签名中的反身双线性对,这将满足双线性对在存储资源或传输带宽受限制的环境(如智能卡或传感器)下工作的应用需求。该项目的完成可为实现下一代更高安全级别的密码系统提供可靠的理论支撑。

基于双线性对的密码学是公钥密码学中的一个重要研究领域。真正能够在密码协议或者方案中安全使用的双线性对只有利用有限域上的超椭圆曲线或者椭圆曲线来构造。而实现这些基于双线性对的密码协议或者方案，其效率瓶颈在于能否高效计算密码协议中所需要的双线性对赋值运算。目前大多数提高双线性对效率的算法并没有结合具体的密码协议，因而不具有针对性。如果根据不同协议中所使用双线性对的特殊性质，那么可以产生更高效率的算法。椭圆曲线上有理点群中的基本运算，即点加和多倍点运算，在基于双线性对的密码协议或者是椭圆曲线密码体制中的实现都必须用到，如果能够提高该基础运算的效率，那么对推动椭圆曲线密码应用具有重要现实意义。本课题主要贡献在于双线性对密码学的基础算法理论方面。因为在线离线签名和指定验证者签名都需要反身双线性对e(P,P), 利用反身双线性对中的第一个分量和第二个分量有内在关系的情况， 在适于双线性对计算的曲线上，我们构造了新的反身双线性对，这些双线性对比以前的双线性对计算效率都要高。从而满足了应用需求。 这些成果分别发表在信息科学领域期刊IEEE trans. Information Theory 和 Journal of Mathematical Cryptology上. 由于小特征上的椭圆曲线特别适合在存储资源或者计算资源受限的硬件环境下使用，针对特征3上的椭圆曲线，我们提出了新的点加和多倍点算法，从而在根本上提高了相关密码协议的实现效率。该成果发表密码学学术会议The Conference on Selected Areas in Cryptography 2012上。 对于构造适于双线性对计算的椭圆曲线方面，我们起初拟构造小特征（即特征为2和3）的适于双线性对计算的非超奇异椭圆曲线，但因为近年Joux等人提出的快速函数域筛法，使得这类曲线的安全度大大降低，所以导致我们放弃该问题的研究。另外，代数曲线不仅在密码学中取得了广泛应用，也在编码领域有很多重要用途。所以我们针对能译RS码的GS算法，也和别的研究者合作提出了改进算法。在本项目的资助下，项目组不仅做出了在密码和编码方面具有学术价值的成果，而且主持人独立主持科研项目的能力得到了进一步提高。