A Lattice-Based Incremental Signature Scheme

A digital signature is a fundamental cryptographic primitive that is used heavily in information society for guaranteeing the authenticity of digital information. Incremental signature, introduced by Bellare, Goldreich, and Goldwasser (CRYPTO'94), is a digital signature that enables a signer to sign messages quickly when these messages are similar. It is extremely useful for authenticating, e.g., big data since there are huge messages in big data and many of them only have small differences. In this paper, we propose an incremental signature scheme from lattices. Our scheme is proven secure against adaptive chosen-message attacks in the standard model, assuming the k -small integer solutions problem on lattices is intractable. We also conduct experiments to evaluate its efficiency. The experimental results demonstrate that our incremental signature scheme is effective for signing a series of messages with many overlaps.