This leaves us with the following interesting possibility: perhaps there exists a hash function that securely instantiates the Fiat-Shamir heuristic for all 3-message public-coin statistically sound proofs, even if it can fail for some computationally sound arguments. Indeed, the existence of such hash functions has been conjectured by Barak, Lindell and Vadhan (FOCS '03), who also gave a seemingly reasonable and sufficient condition under which such hash functions exist. However, we do not have any provably secure construction of such hash functions, under any standard assumption such as the hardness of DDH, RSA, QR, LWE, etc.
In this work we give a broad black-box separation result, showing that the security of such hash functions cannot be proved under virtually any standard cryptographic assumption via a black-box reduction.
Category / Keywords: foundations / interactive proofs, zero-knowledge Publication Info: A merged version of this work and that of [Dachman-Soled, Jain, Kalai, Lopez-Alt] will appear at TCC 2013. Date: received 16 Dec 2012, last revised 19 Dec 2012 Contact author: danwichs at gmail com Available format(s): PDF | BibTeX Citation Version: 20121219:214235 (All versions of this report) Discussion forum: Show discussion | Start new discussion