Zero-knowledge proof schemes are one of the main building blocks of modern cryptography. Using the Helios voting protocol as a practical example, we show mistakes in the previous understanding of these proof schemes and the resulting security problems. We proceed to define a hierarchy of security notions that solidifies our understanding of proof schemes: weak proof schemes, strong proof schemes and multi-proofs. We argue that the problems in Helios result from its use of weak proofs and show how these proofs can be made strong. We provide the first proof of ballot privacy for full Helios ballots with strong proofs. In Helios, a proof scheme commonly known as Fiat-Shamir-Schnorr is used to strengthen encryption, a construction also known as Signed E1Gamal or more generally, Encrypt+PoK. We show that in the Encrypt+PoK construction, our hierarchy of proof scheme notions corresponds naturally to a well-known hierarchy of security notions for public-key encryption: weal< proofs yield chosen-plain text secure encryption, strong proofs yield non-malleable encryption and multi-proofs yield chosen-ciphertext secure encryption. Next, we ask whether Signed E1Gamal is chosen-ciphertext secure, a question closely related but not identical to whether Fiat-Shamir-Schnorr proofs are multi-proofs. We answer both these questions negatively: under a reasonable assumption, the failure of which would cast doubt on the security of Schnorr-like proofs, we prove that Signed E1Gamal cannot be shown to be chosen-ciphertext secure by a reduction to the security of plain E1Gamal. This answers an open question, to our knowledge first asked by Shoup and Gennaro in a paper published in 1998.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:649374 |
| Date | January 2014 |
| Creators | Bernhard, David |
| Publisher | University of Bristol |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
Page generated in 0.0018 seconds