椭圆曲线上与密码算法相关的计算问题

This subject focus on the computation problems of discrete logarithm, point multiplication and bilinear pairing which are main parts of elliptic curve and widely applied in cryptography. For some special elliptic curves, we utilize the properties of the mapping between curves and the extention of function fields to find out some proper elliptic curves on which the discrete logarithm problems can be efficiently solved, thereby accelerate the algorithm complexity of discrete logarithm problems. We research on the method of constructing smaller factor basis utilizing the properties of the subset of the point group of elliptic curves, and thereby improve the computation complexity of the elliptic curve discrete logarithm problem. We research on the fault attack on the discrete logarithm problem of hyperelliptic curves utilizing the property that the point multiplication is independent of some parameters. Using the endomorhpism over some special elliptic curves, We try to apply the window method to the computation of point multiplication on these curves. We research on the different addition formulas with different representation of coordinate and the application of these formulas in the pre-computation of window method to improve the efficiency of point adding calculation. We research on the method of constructing the bilinear pairing of elliptic curve utilizing the construction of elliptic curves with smaller norm, and thereby construct the bilinear pairing with Miller iteration's times as less as possible

本课题主要研究在椭圆曲线密码算法中广泛应用的椭圆曲线上的离散对数、点乘和双线性对的计算问题。本课题拟利用椭圆曲线函数域的扩域的性质,研究曲线之间映射的特殊性质,找到合适的曲线提高某些特殊类型椭圆曲线上离散对数问题的计算速度；利用椭圆曲线点群的子集的性质,研究构造较少个数的因子基的方法,提高椭圆曲线上离散对数问题的计算速度；利用曲线上点乘运算与曲线方程的某些参数无关,研究基于超椭圆曲线的离散对数困难问题的密码算法的植入错误攻击；利用特殊类型的椭圆曲线上的自同态映射，将窗口算法应用到特殊类型的椭圆曲线点乘的计算中；利用椭圆曲线上不同坐标表示的点加公式，研究加法公式在窗口算法预计算中的应用,提高一次点加计算的效率；利用构造范数较小的椭圆曲线方法, 研究椭圆曲线上双线性对的构造方法，构造需要Miller迭代次数尽可能少的双线性对。

项目组成员在公钥密码算法困难问题的计算，密码算法的分析设计等密码学基础研究领域取得了一系列有深刻理论意义和应用价值的研究成果。项目组成员在SIAM Journal on Computing, Theoretical Computer Science, Science China Information Sciences 等发表6篇SCI收录的论文，在PKC, SAC, CT-RSA, FSE等重要的国际会议发表11篇EI收录论文。截至目前累计被引55次，其中单篇被引次数最高达16次。具体讲, 项目组成员解决了有限域上的 CDH 问题是否存在困难谓词这一密码研究领域的长期公开问题；解决了 Erich Kaltofen 提出的在关于有限域上的亚线性时间内判定 3 项式是否存在根的公开问题；首次给出了估计一类随机整数格的最短向量长度下界的一般方法；将亏格 2 的曲线上离散对数问题归约到弱的亏格相同的曲线的群上；给出了随机 NTRU 格的最短向量长度的下界估计；给出了具有更小的渐进因子的 GapCVPP 问题的一个多项式时间算法；重新形式化地研究并构造了“双接受者加密”；首次研究了多接收者加密方案在广义多用户环境下的安全性；探讨了可后向恢复公钥加密（PKE-SR）的性质；提出了可将 KEM/DEM 转化为 PKE-SR 的两种有效方法；给出了基于子群成员假设构造损耗陷门函数的一般性构造方法；针对 TrustCom 2013 中提出的一种实用版本的基于整数的全同态加密的用于验证数据完整性的协议，提出一种选择明文攻击；给出了缩减轮数 Camellia 分组密码算法的两类攻击方法；提出了一种改进中间相遇攻击的新方法―基于密钥的中间状态过滤，发明了构造截断差分特征的新方法。