Research On Lattice-based Incremental Signature Schemes

Digital signature is a fundamental cryptographic primitive that is used heavily in information society to guarantee the authenticity of digital information.Incremental signature,introduced by Bellare et al.in CRYPTO'94,is a special kind of digital signature,which can generate signatures of similar messages much faster than standard digital signatures,and thus it can be widely used in certain big data systems such as cloud computing,Internet of Things,as well as blockchain systems.Most of the existing incremental signature schemes are based on the non-quantum computing security assumptions,which will be difficult to remain unforgeable in the age of quantum computers,and it is urgent to design incremental signature schemes that can satisfy quantum security.Lattice-based cryptography,as one of the post quantum cryptosystems that has attracted much attention,not only has high security,but also has high computational efficiency.To address the above issues,this thesis has done the following researches based on incremental signature schemes,lattice-based cryptographic schemes and proof techniques:1.This thesis applies lattice-based cryptography technology to incremental signatures,and proposes a lattice-based incremental signature scheme.It is proved that the scheme can achieve adaptive security in the standard model,assuming the k-small integer solutions problem is intractable.In addition,due to the incremental property of the proposed scheme,compared with the standard signature scheme,this scheme has better performance in terms of the time cost of generating signatures.2.This thesis proposes the concept of identity-based incremental signature by drawing on ideas of identity-based cryptography,and an identity-based incremental signature scheme from lattices.It is proved that the scheme can achieve adaptive security in the standard model,assuming the standard small integer solution problem is intractable.In addition,theoretical analysis and experimental results show that the computational overhead of the incremental signature algorithm is less than that of the standard signature algorithm.