Efficient multi-party concurrent signature from lattices

• A novel lattice-based concurrent signature in multi-user setting is proposed.
• Its security is proven in the random oracle model under the small integer solution assumption.
• It can be immune to quantum analysis.

Concurrent signature is a novel paradigm, which can achieve fair exchange of signatures between users. Since its appearance, the topic has been widely concerned, while the study of concurrent signature in multi-user setting suffers from some criticism. Almost all known multi-user concurrent signature schemes rely on the hardness assumptions that is insecure against quantum analysis. Furthermore, most of multi-party concurrent signature (MCS) schemes are lacking of formal security models. In the paper, in the random oracle model, we propose a construction of lattice-based MCS scheme and prove its security under the hardness of the small integer solution (SIS) problem. Since our proposed scheme is based on the lattice assumptions, which is believed to be quantum-resistant, the mathematical properties make our scheme simpler and more flexible.