Research On Miller Algorithm Of Optimal Ate Pairing On KSS Curve With Embedding Degree 16

Bilinear pairings were first used to reduce the discrete logarithm problem on elliptic curves to the discrete logarithm problem in a finite field,thereby attacking supersingular elliptic curves and superelliptic curves and their corresponding cryptosystem,for example,FR attack for Tate pairing.Since then,bilinear pairings have also been used to design cryptographic protocols or schemes,such as IBE scheme,BLS short signature,and one round of three-party key agreement.In particular,pairing-based cryptography has been shown to solve some problems that are impossible,difficult,or ineffective with traditional public-key cryptography or symmetric encrytion.For example,the IBE scheme overcomed the public-key management problem in public-key cryptography.However,forced by FFS,NFS and their variants such as TNFS,exTNFS and SexTNFS,which is used to solve the discrete logarithm problem,the parameters of the pairing-friendly curves have been updating to reach a higher security level,and the KSS curves have gradually attracted attention which are faster than BN curves at the same safety level.Therefore,it's still an important research topic in pairing-based cryptography to improve the Miller algorithm so that bilinear pairings on KSS curves can be more efficient.In this paper,the Miller algorithm based on pseudo 8-sparse multiplication for O-Ate pairing on the KSS curve with degree 16 is studied in detail.The first is to summarize the influence factors on the Miller algorithm such as the selection of the elliptic curve,the number of Miller cycles,the calculation of the line evaluation,the operations in the expansion domain(mainly multiplication and inversion),and the caculation of the final exponentiation.And then the thesis modifies and improves the Miller algorithm based on pseudo 8-sparse multiplication.Finally the calculation formula of a kind of line evaluation is simplified.The main work of the thesis is summarized as follows.Firstly,the Miller algorithm based on pseudo 8-sparse multiplication is modified.A detailed analysis of pseudo 8-sparse multiplication is carried out,and the defect that the original algorithm takes the isomorphic point of a point P as input is corrected.By re-deriving the line equation,the corresponding point on the twisted curve is found,and then the line evaluation of the KSS 16 curve is completely transferred to the twisted curve of the curve.Secondly,this thesis reduces the computational complexity of Miller algorithm.A new method of pre-calculation that computational complexity of Miller algorithm is reduced in literature is given.Compared with the method of Barbulescu et al,the improved algorithm complexity in this article is reduced by 615 multiplications in the basic field.Compared with the method of Khandaker et al,the new method's complexity is reduced by multiplications in the basic field.Thirdly,the calculation formula of the line evaluation is simplified.This thesis divides the line evaluation involved in Miller algorithm into two categories,and uses the point(x_2^s-1(?)',y_2^s-1(?)')to calculate the non-zero coefficient of (?)_2^s(?)',(?)'((?)').Although the additional calculation complexity of the formula than that of the original one is 1M_p⁴,the formula can use pre-storage and parallel calculation to improve the calculation speed.