Identity-based Signatures from Lattices: Simpler, Faster, Shorter^*

Article type: Research Article

Authors: Tian, Miaomiao^† | Huang, Liusheng

Affiliations: School of Computer Science and Technology & Suzhou Institute for Advanced Study, University of Science and Technology of China, China. [email protected], [email protected]

Correspondence: [†] Address for correspondence: School of Computer Science and Technology, University of Science and Technology of China, Hefei 230026, Anhui, China.

Note: [*] This is an extended full version of the paper [25], appeared in the proceedings of IFIP SEC 2014.

Abstract: Identity-based signature is an important technique for light-weight authentication. Recently, many efforts have been made to construct identity-based signatures over lattice assumptions since they would remain secure in future quantum age. In this paper we present a new identity-based signature scheme from lattice problems. This scheme is more efficient than other lattice-based identity-based signature schemes in terms of both computation and communication complexities. We prove its security in the random oracle model under short integer solution assumption that is as hard as approximating several worst-case lattice problems. We also extend the scheme to an identity-based message recovery signature scheme that has better performance.

Keywords: identity-based signature, lattice, performance, message recovery

DOI: 10.3233/FI-2016-1353

Journal: Fundamenta Informaticae, vol. 145, no. 2, pp. 171-187, 2016