A non-interactive zero-knowledge proof can be used to demonstrate the truth of a statement without revealing anything else. It has been shown under standard cryptographic assumptions that non-interactive zero-knowledge proofs of membership exist for all languages in NP. However, known non-interactive zero-knowledge proofs of membership of NP-languages yield proofs that are larger than the corresponding membership witnesses. We investigate the question of minimizing the communication overhead involved in making non-interactive zero-knowledge proofs and show that if fully homomorphic encryption exists then it is possible to minimize the size of non-interactive zero-knowledge proofs and get proofs that are of the same size as the witnesses. Our technique is applicable to many types of non-interactive zero-knowledge proofs. We apply it to both standard non-interactive zero-knowledge proofs and to universally composable non-interactive zero-knowledge proofs. The technique can also be applied outside the realm of non-interactive zero-knowledge proofs, for instance to get witness-size interactive zero-knowledge proofs in the plain model without any setup. Keywords: Non-interactive zero-knowledge proofs, fully homomorphic encryption. 1
A coin-tossing protocol lets two parties decide on a string that should be a random (or at least pseudorandom) string. In this paper, we focus on taking advantage of the perfectly hiding commitment scheme, constant-round perfect zero-knowledge arguments and arguments of knowledge to construct a two-party constant-round perfect protocol for secure coin-tossing, where both of two parties can obtain the common resulting coins and the resulting coins are guaranteed to be statistically close to uniform. The security of our protocol is obtained against malicious non-uniform adversaries that may arbitrarily deviate from the protocol specification. Comparing with the Barak's protocol, we utilize the black-box reduction in the process of security proof and the rounds of our protocol decrease obviously.
Ein E- Voting System muss einerseits sicher sein andererseits muss es gewährleisten dass jede Wahl berücksichtigt und anonym ausgewertet wird. \nDieses Projekt befasst sich mit der Aufgabe, ein solch sicheres, stabiles und transparentes Wahlsystem anzubieten. Das Ziel der Arbeit ist es, einen Web Client zu entwickeln, der mit Hilfe einer Big- Integer Library und JavaScript Funktionen das für E- Voting geeignete Damgård- Jurik Kryptosystem zu implementiert. Weiter galt es, die Verfügbarkeit von echten Zufallszahlen in JavaScript abzuklären. Die generierten Datensätze sind in der JavaScript Object Notation (JSON) an den Server weiterzuleiten. In einem optionalen Teil der Arbeit sollte die Wohlgeformtheit der verschlüsselten Stimmzettel mittels eines Zero-Knowledge Proofs Protokoll nachgewiesen werden können. \nDer verwendete asymmetrische Damgård- Jurik Verschlüsselungsalgorithmus, hat die homomorphe Eigenschaft, dass die Multiplikation chiffrierter Werte gleich der verschlüsselten Summe der entsprechenden Klartexte entspricht. Da nur das aufkumulierte Schlussresultat der Abstimmung entschlüsselt wird, ist dadurch die Anonymität der einzelnen Stimmen gewährleistet. Um die Gültigkeit eines verschlüsselten Wahlzettels zu überprüfen, wird ein Zero-Knowledge Proofs Protokoll verwendet. Da JavaScript nur mit Zahlen bis 53 Bit rechnen kann, ist für die Berechnungen eine JavaScript Big- Integer Library notwendig. Es wurden verschiedene Bibliotheken getestet und im Detail ausgewertet. Ebenfalls wurde die Möglichkeit echte Zufallszahlen plattformunabhängig zu generieren abgeklärt. \nDie Wahl der Big-Integer Library ist auf jsbn.js der Stanford University gefallen und für die Generierung von Zufallszahlen auf jscrypto.js, welche durch die Auswertung von Mausbewegungen Entropie gewinnt. Der implementierte JavaScript Client verschlüsselt erfolgreich Stimmzettel mittels Damgård- Jurik Verschlüsselungsalgorithmus und leitet das Chiffrat mit zusätzlichen, für den Zero-Knowledge Proofs Protokoll notwendigen Parametern im JSON Format an den Server weiter, der die empfangenen Daten auf ihre Wohlgeformtheit prüft. Die Messungen haben ergeben, dass der Google Chrome Browser am optimalsten mit den angewendeten Libraries läuft. Bei der Verwendung eines 1024 Bit RSA Modulus benötigt der Google Chrome Browser 1.7 Sekunden für die Damgård- Jurik Verschlüsselung und zusätzlich 8.8 Sekunden für die Generierung der Zero-Knowledge Proofs Protokoll notwendigen Parametern.
In this paper, based on the verifiable pair and identity-based threshold cryptography, a novel identity-based (ID-based) threshold decryption scheme (IDTDS) is proposed, which is provably secure against adaptive chosen ciphertext attack under the computational bilinear Diffie-Hellman (CBDH) problem assumption in the random oracle. The pubic checkability of ciphertext in the IDTDS is given by simply creating a signed ElGamal encryption instead of a noninteractive zero-knowledge proof. Furthermore, we introduce a modified verifiable pairing to ensure all decryption shares are consistent. Our scheme is more efficient in verification than the schemes considered previously.
Markus Rückert, Michael Schneider, Dominique Schröder
Verifiably encrypted signature schemes (VES) allow a signer to encrypt his or her signature under the public key of a trusted third party, while maintaining public signature verifiability. With our work, we propose two generic constructions based on Merkle authentication trees that do not require non-interactive zero-knowledge proofs (NIZKs) for maintaining verifiability. Both are stateful and secure in the standard model. Furthermore, we extend the specification for VES, bringing it closer to real-world needs. We also argue that statefulness can be a feature in common business scenarios.
Our constructions rely on the assumption that CPA (even slightly weaker) secure encryption, maskable CMA secure signatures, and collision resistant hash functions exist. Maskable means that a signature can be hidden in a verifiable way using a secret masking value. Unmasking the signature is hard without knowing the secret masking value. We show that our constructions can be instantiated with a broad range of efficient signature and encryption schemes, including two lattice-based primitives. Thus, VES schemes can be based on the hardness of worstcase lattice problems, making them secure against subexponential and quantum-computer attacks. Among others, we provide the first efficient pairing-free instantiation in the standard model.
Abstract. The concept of zero-knowledge proofs has been around for about 25 years. It has been redefined over and over to suit the special security requirements of protocols and systems. Common among all definitions is the requirement of the existence of some efficient “device ” simulating the view of the verifier (or the transcript of the protocol), such that the simulation is indistinguishable from the reality. The definitions differ in many respects, including the type and power of the devices, the order of quantifiers, the type of indistinguishability, and so on. In this paper, we will scrutinize the definition of “black-box computational ” zero-knowledge, in which there exists one simulator for all verifiers, the simulator has black-box access to the verifier, and the quality of simulation is such that the real and simulated views cannot be distinguished by polynomial tests (computational indistinguisha-bility). Working in a theoretical model (the Random-Oracle Model), we show that the indistinguishability requirement is stated in a conceptually inappropriate way: Present definitions allow the knowledge of the verifier and distin-guisher to be independent, while the two entities are essentially coupled. Therefore, our main take on the problem will be conceptual and semantic, rather than literal. We formalize the concept by introducing a “knowledge ex-tractor ” into the model, which tries to extract the extra knowledge hard-coded into the distinguisher (if any), and then helps the simulator to construct the view of the verifier. The new paradigm is termed Simulation-Extraction
Vipul Goyal, Yuval Ishai, Mohammad Mahmoody, Amit Sahai
Motivated by the question of basing cryptographic protocols on stateless tamper-proof hardware tokens, we revisit the question of unconditional two-prover zero-knowledge proofs for NP. We show that such protocols exist in the interactive PCP model of Kalai and Raz (ICALP ’08), where one of the provers is replaced by a PCP oracle. This strengthens the feasibility result of Ben-Or, Goldwasser, Kilian, and Wigderson (STOC ’88) which requires two stateful provers. In contrast to previous zero-knowledge PCPs of Kilian, Petrank, and Tardos (STOC ’97), in our protocol both the prover and the PCP oracle are efficient given an NP witness. Our main technical tool is a new primitive that we call interactive locking, an efficient realization of an unconditionally secure commitment scheme in the interactive PCP model. We implement interactive locking by adapting previous constructions of interactive hashing protocols to our setting, and also provide a direct construction which uses a minimal amount of interaction and improves over our interactive hashing based constructions. Finally, we apply the above results towards showing the feasibility of basing unconditional cryptography on stateless tamper-proof hardware tokens, and obtain the following results:
Sarah Meiklejohn, C. Chris Erway, Alptekın Küpçü, Theodora Hinkle · 5 authors
In recent years, many advances have been made in cryptography, as well as in the performance of communication networks and processors. As a result, many advanced cryptographic protocols are now efficient enough to be considered practical, yet research in the area remains largely theoretical and little work has been done to use these protocols in practice, despite a wealth of potential applications. This paper introduces a simple description language, ZKPDL, and an interpreter for this language. ZKPDL implements non-interactive zero-knowledge proofs of knowledge, a primitive which has received much attention in recent years. Using our language, a single program may specify the computation required by both the prover and verifier of a zero-knowledge protocol, while our interpreter performs a number of optimizations to lower both computational and space overhead. Our motivating application for ZKPDL has been the efficient implementation of electronic cash. As such, we have used our language to develop a cryptographic library, Cashlib, that provides an interface for using e-cash and fair exchange protocols without requiring expert knowledge from the programmer. 1
Identification protocols have a very important role in the world of electronic communication. In an identification protocol, the prover (user) proves to the verifier (center) that it is truly the authorized user who is communicating with the center. In one round of batch identification scheme a user with several secret keys (identities) can prove itself to the verifier instead of several proofs. In this paper, the first Weil pairing will be introduced. In addition, we propose a new batch zero-knowledge identification scheme based on the Weil pairing hereafter considered the security analysis of our proposed scheme.