Title: Lattice-based message recovery signature schemes

Authors: Miaomiao Tian; Liusheng Huang

Addresses: School of Computer Science and Technology, University of Science and Technology of China, Hefei 230026, China; Suzhou Institute for Advanced Study, University of Science and Technology of China, Suzhou 215123, China ' School of Computer Science and Technology, University of Science and Technology of China, Hefei 230026, China; Suzhou Institute for Advanced Study, University of Science and Technology of China, Suzhou 215123, China

Abstract: The message recovery signature scheme is a very useful signature scheme in which the verification of signature does not require appended message, because the message can be easily recovered from the signature. Although message recovery signatures based on conventional number-theoretic problems have been achieved, it is still unknown whether message recovery signature can be implemented based on lattices, which are receiving considerable attention in cryptographic community since they are resistant to quantum computer's attacks. This paper provides a positive answer to the above question by presenting two concrete lattice-based message recovery signature schemes. The two schemes make use of the efficient lattice-based signature scheme recently created by Lyubashevsky and presented at EUROCRYPT 2012. Our constructions are proved to be secure in the random oracle model under the short integer solution assumption. Compared with Lyubashevsky signature scheme, our schemes are more efficient in terms of communication overhead.

Keywords: cryptography; lattices; message recovery signatures; security; communications overhead.

DOI: 10.1504/IJESDF.2013.058658

International Journal of Electronic Security and Digital Forensics, 2013 Vol.5 No.3/4, pp.257 - 269

Received: 06 Aug 2013
Accepted: 17 Sep 2013
Published online: 26 Jul 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article