Revisiting Lower and Upper Bounds for Selective Decommitments

Опубликовано 27 июля 2016, 19:31

The usual notion of security for commitment schemes says that a commitment scheme is secure if it is both binding and hiding. In [DNRS99, DNRS03], Dwork et al. pointed out an interesting subtlety in the typical formalization of hiding. More specifically, they showed that the typical notion of hiding may not imply security against certain kind of attacks which are natural against commitment schemes. The attack is called selective opening attack (SOA, for short). This fundamental question of existence of commitment schemes that are SOA-secure was answered affirmatively by Bellare, Hofheinz, and Yilek in [BHY09] , and Hofheinz in [Hof11], who presented an SOA-secure scheme which is based solely on the non-blackbox use of a one-way permutation and which has super-constant number of rounds. This result however opened other challenging questions about achieving a better round complexity and obtaining fully black-box schemes using underlying primitives and code of the adversary in a black-box manner. Recently, in TCC 2011, Xiao ([Xia11]) investigated on how to achieve (nearly) optimal SOA-secure commitment schemes where optimality is in the sense of both the round complexity and the black-box use of cryptographic primitives. The work of Xiao focuses on a simulation-based security notion of SOA. Moreover, the various results in [Xia11] focus only on either parallel or concurrent SOA. In this work we first point out various issues in the claims of [Xia11] that actually re-open several of the questions left open in [BHY09, Hof11]. Then, we provide new lower bounds and concrete constructions that produce a very different state-of-the-art compared to the one claimed in [Xia11]. This is a joint work with Rafail Ostrovsky, Alessandra Scafuro, and Ivan Visconti. This work was published at TCC 2013.