Paper 2017/969

Fast and Adaptively Secure Signatures in the Random Oracle Model from Indistinguishability Obfuscation

Bei Liang and Aikaterini Mitrokotsa

Abstract

Indistinguishability obfuscation (iO) is a powerful cryptographic tool often employed to construct a variety of core cryptographic primitives such as public key encryption and signatures. In this paper, we focus on the employment of iO in order to construct short signatures with strong security guarantees (i.e., adaptive security) that provide a very efficient signing process for resource constrained devices. Sahai and Waters (SW) (STOC 2014) initially explored the construction of iO-based short signature schemes but their proposal provides selective security. Ramchen and Waters (RW) (CCS 2014) attempted to provide stronger security guarantees (i.e., adaptive security) but their proposal is much more computationally expensive than the SW proposal. In this work, we propose an iO-based short signature scheme that provides adaptive security, fast signing for resource-constrained devices and is much more cost-efficient than the RW signature scheme. More precisely, we employ a puncturable PRF with a fixed length input to get a fast and adaptively secure signature scheme without any additional hardness assumption as in the SW signature scheme. To achieve this goal, we employ the technique of Hofheinz et al. called "delayed backdoor programming" using a random oracle, which allows to embed an execution thread that will only be invoked by special inputs generated using secret key information. Furthermore, we compare the cost of our signature scheme in terms of the cost of the underlying PRG used by the puncturable PRF. Our scheme has a much lower cost than the RW scheme, while providing strong security guarantees (i.e., adaptive security).