Towards Tightly Secure Lattice Short Signature and Id-Based Encryption
Constructing short signatures with tight security from standard assumptions is a long-standing open problem. We present an adaptively secure, short (and stateless) signature scheme, featuring a constant security loss relative to a conservative hardness as
- PDF / 531,498 Bytes
- 31 Pages / 439.37 x 666.142 pts Page_size
- 98 Downloads / 231 Views
Abstract. Constructing short signatures with tight security from standard assumptions is a long-standing open problem. We present an adaptively secure, short (and stateless) signature scheme, featuring a constant security loss relative to a conservative hardness assumption, Short Integer Solution (SIS), and the security of a concretely instantiated pseudorandom function (PRF). This gives a class of tightly secure short lattice signature schemes whose security is based on SIS and the underlying assumption of the instantiated PRF. Our signature construction further extends to give a class of tightly and adaptively secure “compact” Identity-Based Encryption (IBE) schemes, reducible with constant security loss from Regev’s vanilla Learning With Errors (LWE) hardness assumption and the security of a concretely instantiated PRF. Our approach is a novel combination of a number of techniques, including Katz and Wang signature, Agrawal et al. lattice-based secure IBE, and Boneh et al. key-homomorphic encryption. Our results, at the first time, eliminate the dependency between the number of adversary’s queries and the security of short signature/IBE schemes in the context of lattice-based cryptography. They also indicate that tightly secure PRFs (with constant security loss) would imply tightly, adaptively secure short signature and IBE schemes (with constant security loss).
1
Introduction
Short signatures are useful and desirable for providing data authenticity in lowbandwidth and/or high-throughput applications where many signatures have to be processed very quickly. Most digital signature schemes are based on computationally hard problems on specific algebraic groups, e.g., finite fields, curves, and lattices. A signature is “short” if the signature consists in a (small) constant number of group elements (e.g., field elements or lattice points). Although bare-bones signatures can be obtained from very weak assumptions (e.g., collision-resistant hash functions), constructing efficient short signatures satisfying standard security requirements (e.g., existential unforgeability under adaptively chosen-message attacks), from reasonable assumptions, appears to be Xavier Boyen—Research conducted with generous support from the Australian Research Council under Discovery Project grant ARC DP-140103885. c International Association for Cryptologic Research 2016 J.H. Cheon and T. Takagi (Eds.): ASIACRYPT 2016, Part II, LNCS 10032, pp. 404–434, 2016. DOI: 10.1007/978-3-662-53890-6 14
Towards Tightly Secure Lattice Short Signature and Id-Based Encryption
405
a challenging task. Some of the existing short signature schemes use random oracles, e.g., [10,19,36,48,50], or rely on non-standard computational assumptions (strong, interactive assumptions, and/or q-type parametric assumptions), e.g., [16,26,30,33,34], or require signers to maintain state across signatures, e.g., [45]. The first short signature scheme from a reasonable and non-parametric assumption without random oracles was proposed by Waters [56]. Hohenberger and Waters late
Data Loading...
