配对计算装置、配对计算方法

摘要

本发明涉及能够实现高速配对计算的配对计算装置、配对计算方法、以及记录配对计算程序的记录媒体。在如同[式1]对Ate配对e(Q，P)进行定义并且k为偶数、3的倍数、4的倍数和6的倍数之一的情形下，在扭曲曲线所规定的真子域上，采用在取fs，Q(P)的(qk-1)/r次幂的情形下变为1的平方和立方非剩余v来进行导出米勒函数fs，Q(P)时所需要的有理函数的运算。

主权项

一种配对计算装置，其连接于网络，作为客户端或服务器，通过进行Ate配对e(Q，P)的配对运算而进行认证，其使用米勒函数fs，Q(·)，利用[式1] e ( Q , P ) = f s , Q ( P ) ( q 2 h - 1 ) / r 计算所述Ate配对e(Q，P)，在此，给定椭圆曲线方程y2＝x3+ax+b，a∈Fq，b∈Fq，q为大于3的素数的幂，使嵌入级数为2h，h为自然数，使E为由Fq2h定义的可配对的椭圆曲线上的有理点构成的加法群，使E[r]为素数阶为r的有理点集合，并且使Φq为弗罗贝尼乌斯自同态，使用G1＝E[r]∩Ker(Φq‑[1])G2＝E[r]∩Ker(Φq‑[q])将Ate配对e定义为非退化双线性映射e：G2×G1→F*q2h/(F*q2h)r，使P∈G1，Q∈G2，并且采用弗罗贝尼乌斯自同态Φq的迹t使s＝t‑1，所述配对计算装置的特征在于，具有：处理部，其进行所述Ate配对e(Q，P)的配对计算；存储部，其存储所述s＝t‑1或所述t、满足P∈E(Fq)的P、满足Q’∈E’(Fqh)的Q’、v‑1的值和v‑3/2的值，以及所述处理部输出的Ate配对e(Q，P)的计算结果；和通信接口，其进行客户端和服务器之间的认证通信，所述处理部包括：运算部，其在基于E(Fq2h)的扭曲曲线E’(Fqh)：y2＝x3+av‑2x+bv‑3的真子域上，采用通过取fs，Q(P)的(q2h‑1)/r次幂而变为1的平方非剩余v∈Fqh来进行导出fs，Q(P)时所需要的有理函数的运算，得到Ate配对e(Q，P)的运算结果；和认证部，其根据所述Ate配对e(Q，P)的运算结果，生成所述客户端的签名数据，或验证所述服务器的签名数据，所述运算部包括：输入单元，其从所述存储部读取并输入所述s＝t‑1或所述t、P、Q’；代入单元，其从所述存储部读取所述v‑1的值和v‑3/2的值，对有理点P的坐标(xp，yp)进行代入运算n←xpv‑1、m←ypv‑3/2，并进行代入运算f←1、T’←Q’作为初始值设定；第一运算单元，其不计算将有理点P的坐标(xp，yp)代入经过有理点T的切线方程lT，T(x，y)＝0的左侧而得到的值lT，T(xp，yp)，而是以lT’，T’(n，m)计算lT，T(xp，yp)v‑3/2，并进行代入运算f←f2·lT’，T’(n，m)；第二运算单元，其进行代入运算T’←2T’；第三运算单元，其在二进制表示的s的规定位的值为1的情形下，不计算将有理点P的坐标(xp，yp)代入经过有理点T和Q的直线方程lT，Q(x，y)＝0的左侧而得到得值lT，Q(xp，yp)，而是以lT’，Q’(n，m)计算lT，Q(xp，yp)v‑3/2，并进行代入运算f←f·lT’，Q’(n，m)；第四运算单元，其在二进制表示的s的规定位的值为1的情形下，进行代入运算T’←T’+Q’；在每次从所述第一运算单元到所述第二运算单元进行运算时，对二进制表示的s的规定位的值减1，并将从所述第一运算单元到所述第四运算单元的运算结果的f存储于所述存储部的单元，以及第五运算单元，其使用存储在所述存储部中的f进行取(q2h‑1)/r次幂的取幂运算，作为配对运算的结果，所述第五运算单元的运算结果被存储于所述存储部。