从有限域到椭圆曲线上的编码映射构造与应用综述

作者：何晓阳; 于伟; 王鲲鹏

来源：密码学报, 2018, 5(03): 301-314.

DOI：10.13868/j.cnki.jcr.000241

• 椭圆曲线
• 确定性编码
• 散列函数
• 随机谕言
• Elligator算法

本文总结了从有限域Fq到椭圆曲线E(Fq)的,花费确定性多项式时间的编码映射.该类编码映射的用途大致可分为两种:1.从它们出发,构造从比特串到椭圆曲线上有理点的,与随机谕言不可区分的散列函数.这样的散列函数在多种密码学协议中都有应用,如基于身份的密码体制可以利用这些散列函数,高效地生成公钥.2.对编码映射的定义域加以限制,可以实现从Fq的一个较大的子集到椭圆曲线上有理点的单射编码.此单射编码是可以高效求逆的,因而该椭圆曲线上的有理点可以用比特串表示,并且当有理点在曲线上均匀分布时,用来表示它们的比特串是与均匀分布不可区分的.利用这一表示,可以将一批需要在不同用户间交换椭圆曲线上点的密码协议改进为通过交换随机比特串实现通信的协议,从而成功地规避网络监测.编码映射的实现,有多种方式:当q≡3(mod 4)时,SWU算法及其变体可用来构造编码映射;当q≡2(mod 3)时,通过Icart算法及其变体亦可构造相应的编码映射.这些映射的时间复杂度都是O(log3q).此外,我们总结了从有限域到超椭圆曲线的编码映射.

• 单位
  中国科学院大学; 中国科学院信息工程研究所; 信息安全国家重点实验室