一个新的基于MOF从左到右编码的多标量乘算法

很多基于椭圆曲线的密码协议都需要计算多标量乘法kP lQ。目前常见的多标量乘算法的效率主要取决于标量的(联合)海明权值。JSF表示的平均联合海明权密度为1/2,是所有带符号二进制表示中最优的,但JSF编码只能从右到左实现。提出一个新的从左到右的基于MOF的编码方法,该方法的平均联合海明权密度与基于JSF表示的相同,并提出一个新的多标量乘算法,该算法对标量从左到右进行编码,并将编码合并到多标量乘的主计算中,从而节省了存储标量的新编码的内存空间,提高了实现效率。

A New Mutual Opposite Form Based Left-to-Right Multi-Scalar Multiplication Algorithm

Many elliptic curve based cryptographic protocols require computation of multiple scalar multiplications such as kP lQ.Common methods to compute it are the Shamir method and the interleaving method whereas their speed mainly depends on the(joint) Hamming weight of the scalars.The joint sparse form of two L-bit integers has an average joint Hamming weight of L/2,which is an optimal-weight signed-binary representation,but it can be implemented only from right to left.In this paper,a new recoding method based on the mutual opposite form is proposed.This form has the same average Joint Hamming weight as the JSF.And a new MOF representation based multiple scalar multiplication algorithm is given.This method examines the integers from left to right.This results in the merging of recoding and evaluation stages.So the proposed algorithm can improve the performance and reduce the memory consumption of scalar multiplication operation.