Digital Multi-signature Scheme Based on Lattice

The traditional digital multi-signature scheme mostly based on large integer factorization and the discrete logarithm problems, which has not been secure in quantum environment. The paper presents a new lattice-based multi-signature scheme that can resist the quantum attack using the hardness of average-case short integer solution problem (SIS). Multi-signature includes two types: simultaneous signature and sequential signature. The paper describes respectively the key generation, multi-signature generation and multi-signature verification of the two multi-signature schemes, and then has proved the digital multi-signature scheme based on lattice is especially efficient and secure to multi-signature generation.