A New Post-Quantum Blind Signature From Lattice Assumptions

At present, several post-quantum cryptosystems have been proposed, and lattice-based cryptography is the main candidate. Especially in the direction of digital signatures, there are now many practical lattice-based signature schemes. However, there exist few lattice-based signatures with special property such as blind signature. Blind signature was introduced by Chaum for creating untraceable payment system. Then, it is widely used in e-cash and voting, especially in the revolutionary digital cash system based on blockchain. In our paper, we present a method to construct a post-quantum blind signature based on lattice assumptions, and we proved that any existential forger against the security of the resulting scheme can solve the SISq,n,m,beta problem for beta = (O) over tilde (d ). Our main technique is the rejection sampling theory. The expected number of times needed to output a blind signature is at most e(2) under aborting, and our new scheme has much smaller signature size than those of all the previously proposed blind signature schemes over lattices.