This paper is concerned with two variants of the transformation that appear but have not been clearly delineated in existing literature. Both variants start with the prover making a commitment. The strong variant then hashes both the commitment and the statement to be proved, whereas the weak variant hashes only the commitment. This minor change yields dramatically different security guarantees: in situations where malicious provers can select their statements adaptively, the weak Fiat-Shamir transformation yields unsound/unextractable proofs. Yet such settings naturally occur in systems when zero-knowledge proofs are used to enforce honest behavior. We illustrate this point by showing that the use of the weak Fiat-Shamir transformation in the Helios cryptographic voting system leads to several possible security breaches: for some standard types of elections, under plausible circumstances, malicious parties can cause the tallying procedure to run indefinitely and even tamper with the result of the election.
On the positive side, we define a form of adaptive security for zero-knowledge proofs in the random oracle model (essentially simulation-sound extractability), and show that a variant which we call strong Fiat-Shamir yields secure non-interactive proofs.
This level of security was assumed in previous works on Helios and our results are then necessary for these analyses to be valid. Additionally, we show that strong proofs in Helios achieve non-malleable encryption and satisfy ballot privacy, improving on previous results that required CCA security.Category / Keywords: foundations / fiat-shamir, zero-knowledge, random oracle model Original Publication (with major differences): IACR-ASIACRYPT-2012 Date: received 10 Aug 2016 Contact author: csxdb at bristol ac uk Available format(s): PDF | BibTeX Citation Version: 20160812:172421 (All versions of this report) Short URL: ia.cr/2016/771 Discussion forum: Show discussion | Start new discussion