Incremental Digital Signature Scheme Over Ideal Lattice

With the rapid development of quantum computer research and quantum algorithm research,the classical cryptography system whose security depends on the difficult assumption of traditional number theory is facing a huge security threat in the post quantum era.Lattice cryptography,as the most promising cryptography system against quantum attacks,has become the focus of attention.As one of the most important cryptography primitives,digital signature on lattice is naturally favored by researchers.Incremental digital signature is a research branch of digital signature,which is specially designed for the fast updating and small difference between large data.Compared with the standard digital signature,the time-consuming of signing new data is related to the amount of data changes,but not to the complete size of the data.Incremental digital signature has high efficiency in the scenarios of constantly updated big data and fast iterative software authorization.However,the existing incremental digital signature schemes are either traditional cryptography schemes,facing huge security challenges,or based on the general lattice construction,facing the problem of low computing and storage efficiency.In order to enhance the security and efficiency of the incremental digital signature,we creatively introduce the ideal lattice and propose an idea of constructing the incremental digital signature scheme based on the difficult problem on the ideal lattice.This thesis studies the incremental digital signature scheme on the ideal lattice.The main work includes:(1)The two main technical routes of digital signature construction on lattice are sorted out;the formal definition and security model of incremental digital signature on ideal lattice are proposed.Our security model satisfies the existence of unforgeability under adaptive selection message attack,and is explained in detail through the given game model.(2)An incremental signature scheme on ideal lattices that can be proved safe under the standard model constructed by using the G-trapdoor function with pre-image sampling algorithm on the ideal lattice is proposed.Compared with the traditional incremental signature scheme,this scheme has the characteristics of anti-quantum attack;compared with the incremental signature scheme on the general lattice,it achieves higher calculation and storage efficiency.In the standard model,the security satisfies the adaptive selection Unforgeability of existence under message attack.(3)Aiming at the problem of high computational complexity due to the use of complex lattice trap gate generation and pre-image sampling algorithms in the first scheme,an ideal lattice-free algorithm using rejection sampling is proposed.Incremental signature scheme for doors.Compared with the first solution,this solution has theoretically lower computational complexity and simpler construction and use.