Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya, Sarah Meiklejohn
Depending on the application, malleability in cryptography can be viewed as either a flaw or — especially if sufficiently understood and restricted — a feature. In this vein, Chase, Kohlweiss, Lysyanskaya, and Meiklejohn recently defined malleable zero-knowledge proofs, and showed how to control the set of allowable transformations on proofs. As an application, they construct the first compact verifiable shuffle, in which one such controlled-malleable proof suffices to prove the correctness of an entire multi-step shuffle. Despite these initial steps, a number of natural open problems remain: (1) their construction of controlled-malleable proofs relies on the inherent malleability of Groth-Sahai proofs and is thus not based on generic primitives; (2) the classes of allowable transformations they can support are somewhat restrictive; and (3) their construction of a compactly verifiable shuffle has proof size O(N 2 + L) (where N is the number of votes and L is the number of mix authorities), whereas in theory such a proof could be of size O(N + L). In this paper, we address these open problems by providing a generic construction of controlledmalleable proofs using succinct non-interactive arguments of knowledge, or SNARGs for short. Our construction has the advantage that we can support a very general class of transformations (as we no longer rely on the transformations that Groth-Sahai proofs can support), and that we can use it to obtain a proof of size O(N + L) for the compactly verifiable shuffle.
Sebastian Faust, Markulf Kohlweiss, Giorgia Azzurra Marson, Daniele Venturi
The Fiat-Shamir transform is a well studied paradigm for removing interaction from publiccoin protocols. We investigate whether the resulting non-interactive zero-knowledge (NIZK) proof systems also exhibit non-malleability properties that have up to now only been studied for NIZK proof systems in the common reference string model: first, we formally define simulation soundness and a weak form of simulation extraction in the random oracle model (ROM). Second, we show that in the ROM the Fiat-Shamir transform meets these properties under lenient conditions. A consequence of our result is that, in the ROM, we obtain truly efficient non malleable NIZK proof systems essentially for free. Our definitions are sufficient for instantiating the Naor-Yung paradigm for CCA2-secure encryption, as well as a generic construction for signature schemes from hard relations and simulation-extractable NIZK proof systems. These two constructions are interesting as the former preserves both the leakage resilience and key-dependent message security of the underlying CPA-secure encryption scheme, while the latter lifts the leakage resilience of the hard relation to the leakage resilience of the resulting signature scheme.
Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya, Sarah Meiklejohn
Malleability for cryptography is not necessarily an opportunity for attack, but in many cases a potentially useful feature that can be exploited. In this work, we examine notions of malleability for non-interactive zero-knowledge (NIZK) proofs. We start by defining a malleable proof system, and then consider ways to meaningfully control the malleability of the proof system, as in many settings we would like to guarantee that only certain types of transformations can be performed. We also define notions for the cases in which we do not necessarily want a user to know that a proof has been obtained by applying a particular transformation; these are analogous to function/circuit privacy for encryption. As our motivating application, we consider a shorter proof for verifiable shuffles. Our controlled-malleable proofs allow us for the first time to use one compact proof to prove the correctness of an entire multi-step shuffle. Each authority takes as input a set of encrypted votes and a controlled-malleable NIZK proof that these are a shuffle of the original encrypted votes submitted by the voters; it then permutes and re-randomizes these votes and updates the proof by exploiting its controlled malleability. As another application, we generically use controlled-malleable proofs to realize a strong notion of encryption security. Finally, we examine malleability in existing proof systems and observe that Groth-Sahai proofs are malleable. We then go beyond this observation by characterizing all the ways in which they are malleable, and use them to efficiently instantiate our generic constructions from above; this means we can instantiate our proofs and all their applications using only the Decision Linear (DLIN) assumption. Work done as an intern at Microsoft Research Redmond
José Bacelar Almeida, Manuel Barbosa, Endre Bangerter, Gilles Barthe · 6 authors
Developers building cryptography into security-sensitive applications face a daunting task. Not only must they understand the security guarantees delivered by the constructions they choose, they must also implement and combine them correctly and efficiently. Cryptographic compilers free developers from having to implement cryptography on their own by turning high-level specifications of security goals into efficient implementations. Yet, trusting such tools is risky as they rely on complex mathematical machinery and claim security properties that are subtle and difficult to verify. In this paper, we present ZKCrypt, an optimizing cryptographic compiler that achieves an unprecedented level of assurance without sacrificing practicality for a comprehensive class of cryptographic protocols, known as Zero-Knowledge Proofs of Knowledge. The pipeline of ZKCrypt tightly integrates purpose-built verified compilers and verifying compilers producing formal proofs in the CertiCrypt framework. By combining the guarantees delivered by each stage in the pipeline, ZKCrypt provides assurance that the implementation it outputs securely realizes the high-level proof goal given as input. We report on the main characteristics of ZKCrypt, highlight new definitions and concepts at its foundations, and illustrate its applicability through a representative example of an anonymous credential system.
Networks and entity groupings requires entity authentication while preserving the privacy of the entity being authenticated. Zero-Knowledge Proof (ZKP) plays an important role in authentication without revealing secret information. Diffie–Hellman (D-H) key exchange algorithm was developed to exchange secret keys through unprotected channels. This paper discusses zero-knowledge protocols and Diffie– Hellman algorithm and analyzes their vulnerability against known attacks. Also it presents a proposed protocol based on modification of Diffie–Hellman algorithm into an interactive zero-knowledge proof protocol. The proposed protocol is designed and developed to satisfy the zero-knowledge proof properties and resists the known attacks
Rosemberg Silva, Pierre-Louis Cayrel, Richard Lindner
In this paper we propose a new 5-pass zero-knowledge identification scheme with soundness error close to 1/2. We use the hardness of the Inhomogeneous Small Integer Solution problem as security basis. Our protocol achieves lower communication costs compared with previous lattice-based zeroknowledge identification schemes. Besides, our construction allows smaller public and secret keys by applying the use of ideal lattices. We allow the prover to possess several pairs of secret and public keys, and choose randomly which pair is to be used in a given round of execution. We also dealt with nonces in zero-knowledge schemes in a new way, lowering the number of values exchanged between the prover and the verifier. Hence, our scheme has the good features of having a zero-knowledge security proof based on a well known hard problem of lattice theory, with worst to average-case reduction, and small size of secret and public keys.
Ioannis Chatzigiannakis, Apostolos Pyrgelis, Paul G. Spirakis, Yannis C. Stamatiou
Elliptic Curve Cryptography (ECC) is an attractive alternative to\nconventional public key cryptography, such as RSA. ECC is an ideal candidate\nfor implementation on constrained devices where the major computational\nresources i.e. speed, memory are limited and low-power wireless communication\nprotocols are employed. That is because it attains the same security levels\nwith traditional cryptosystems using smaller parameter sizes. Moreover, in\nseveral application areas such as person identification and eVoting, it is\nfrequently required of entities to prove knowledge of some fact without\nrevealing this knowledge. Such proofs of knowledge are called Zero Knowledge\nInteractive Proofs (ZKIP) and involve interactions between two communicating\nparties, the Prover and the Verifier. In a ZKIP, the Prover demonstrates the\npossesion of some information (e.g. authentication information) to the Verifier\nwithout disclosing it. In this paper, we focus on the application of ZKIP\nprotocols on resource constrained devices. We study well-established ZKIP\nprotocols based on the discrete logarithm problem and we transform them under\nthe ECC setting. Then, we implement the proposed protocols on Wiselib, a\ngeneric and open source algorithmic library. Finally, we present a thorough\nevaluation of the protocols on two popular hardware platforms equipped with low\nend microcontrollers (Jennic JN5139, TI MSP430) and 802.15.4 RF transceivers,\nin terms of code size, execution time, message size and energy requirements. To\nthe best of our knowledge, this is the first attempt of implementing and\nevaluating ZKIP protocols with emphasis on low-end devices. This work's results\ncan be used from developers who wish to achieve certain levels of security and\nprivacy in their applications.\n
Ioannis Chatzigiannakis, Apostolos Pyrgelis, Paul G. Spirakis, Yannis C. Stamatiou
Elliptic Curve Cryptography (ECC) is an attractive alternative to conventional public key cryptography, such as RSA. ECC is an ideal candidate for implementation on constrained devices where the major computational resources i.e. speed, memory are limited and low-power wireless communication protocols are employed. That is because it attains the same security levels with traditional cryptosystems using smaller parameter sizes. Moreover, in several application areas such as person identification and eVoting, it is frequently required of entities to prove knowledge of some fact without revealing this knowledge. Such proofs of knowledge are called Zero Knowledge Interactive Proofs (ZKIP) and involve interactions between two communicating parties, the Prover and the Verifier. In a ZKIP, the Prover demonstrates the possesion of some information (e.g. authentication information) to the Verifier without disclosing it. In this paper, we focus on the application of ZKIP protocols on resource constrained devices. We study well-established ZKIP protocols based on the discrete logarithm problem and we transform them under the ECC setting. Then, we implement the proposed protocols on Wiselib, a generic and open source algorithmic library. Finally, we present a thorough evaluation of the protocols on two popular hardware platforms equipped with low end microcontrollers (Jennic JN5139, TI MSP430) and 802.15.4 RF transceivers, in terms of code size, execution time, message size and energy requirements. To the best of our knowledge, this is the first attempt of implementing and evaluating ZKIP protocols with emphasis on low-end devices. This work's results can be used from developers who wish to achieve certain levels of security and privacy in their applications.
Ivan Damgård, Jakob Funder, Jesper Buus Nielsen, Louis Salvail
Attacks on classical cryptographic protocols are usually modeled by allowing an adversary to ask queries from an oracle. Security is then defined by requiring that as long as the queries satisfy some constraint, there is some problem the adversary cannot solve, such as compute a certain piece of information. In this paper, we introduce a fundamentally new model of quantum attacks on classical cryptographic protocols, where the adversary is allowed to ask several classical queries in quantum superposition. This is a strictly stronger attack than the standard one, and we consider the security of several primitives in this model. We show that a secret-sharing scheme that is secure with threshold $t$ in the standard model is secure against superposition attacks if and only if the threshold is lowered to $t/2$. We use this result to give zero-knowledge proofs for all of NP in the common reference string model. While our protocol is classical, it is sound against a cheating unbounded quantum prover and computational zero-knowledge even if the verifier is allowed a superposition attack. Finally, we consider multiparty computation and show that for the most general type of attack, simulation based security is not possible. However, putting a natural constraint on the adversary, we show a non-trivial example of a protocol that can indeed be simulated.
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.
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
We use an idea of linear representations of the symmetric group to reduce the number of communication rounds in the verification protocol, proposed in Crypto 2005 by Peng et al., of a shuffling. We assume Paillier encryption scheme with which we can apply some known zero-knowledge proofs following the same line of approaches of Peng et al. Incidence matrices of 1-subsets and 2-subsets of a finite set is intensively used for the implementation, and the idea of <TEX>$\lambda$</TEX>-designs is employed for the improvement of the computational complexity.
Nowadays it is widely accepted to formulate the security of a protocol carrying out a given task via the "trusted-party paradigm," where the protocol execution is compared with an ideal process where the outputs are computed by a trusted party that sees all the inputs. A protocol is said to securely carry out a given task if running the protocol with a realistic adversary amounts to "emulating" the ideal process with the appropriate trusted party. In the Universal Composability (UC) framework the program run by the trusted party is called an ideal functionality. While this simulation-based security formulation provides strong security guarantees, its usefulness is contingent on the properties and correct specification of the ideal functionality, which, as demonstrated in recent years by the coexistence of complex, multiple functionalities for the same task as well as by their "unstable" nature, does not seem to be an easy task. In this paper we address this problem, by introducing a general methodology for the sound specification of ideal functionalities. First, we introduce the class of canonical ideal functionalities for a cryptographic task, which unifies the syntactic specification of a large class of cryptographic tasks under the same basic template functionality. Furthermore, this representation enables the isolation of the individual properties of a cryptographic task as separate members of the corresponding class. By endowing the class of canonical functionalities with an algebraic structure we are able to combine basic functionalities to a single final canonical functionality for a given task. Effectively, this puts forth a bottom-up approach for the specification of ideal functionalities: first one defines a set of basic constituent functionalities for the task at hand, and then combines them into a single ideal functionality taking advantage of the algebraic structure. In our framework, the constituent functionalities of a task can be derived either directly or, following a translation strategy we introduce, from existing game-based definitions; such definitions have in many cases captured desired individual properties of cryptographic tasks, albeit in less adversarial settings than universal composition. Our translation methodology entails a sequence of steps that derive a corresponding canonical functionality given a game-based definition. In this way, we obtain a well-defined mapping of game-based security properties to their corresponding UC counterparts. Finally, we demonstrate the power of our approach by applying our methodology to a variety of basic cryptographic tasks, including commitments, digital signatures, zero-knowledge proofs, and oblivious transfer. While in some cases our derived canonical functionalities are equivalent to existing formulations, thus attesting to the validity of our approach, in others they differ, enabling us to "debug" previous definitions and pinpoint their shortcomings.