A Zero-Knowledge PCP (ZK-PCP) is a randomized PCP such that the view of any (perhaps cheating) efficient verifier can be efficiently simulated up to small statistical distance. Kilian, Petrank, and Tardos (STOC '97) constructed ZK-PCPs for all languages in NEXP. Ishai, Mahmoody, and Sahai (TCC '12), motivated by cryptographic applications, revisited the possibility of efficient ZK-PCPs for all of NP where the PCP is encoded as a polynomial-size circuit that given a query i returns the ith symbol of the PCP. Ishai et al showed that there is no efficient ZK-PCP for NP with a non-adaptive verifier, that prepares all of its PCP queries before seeing any answers, unless NP⊆coAM and the polynomial-time hierarchy collapses. The question of whether adaptive verification can lead to efficient ZK-PCPs for NP remained open.
In this work, we resolve this question and show that any language or promise problem with efficient ZK-PCPs must be in SZK (the class of promise problems with a statistical zero-knowledge single prover proof system). Therefore, no NP-complete problem can have an efficient ZK-PCP unless NP⊆SZK (which also implies NP⊆coAM and the polynomial-time hierarchy collapses). We prove our result by reducing any promise problem with an efficient ZK-PCP to two instances of the Conditional Entropy Approximation problem defined and studied by Vadhan (FOCS'04) which is known to be complete for the class SZK.
In this paper we put forward the Bounded Player Model for secure computation. In this new model, the number of players that will ever be involved in secure computations is bounded, but the number of computations has no a priori bound. Indeed, while the number of devices and people on this planet can be realistically estimated and bounded, the number of computations these devices will run can not be realistically bounded. We stress that in the Bounded Player model, in addition to no a priori bound on the number of sessions, there is no synchronization barrier, no trusted party, and simulation must be performed in polynomial time. In this setting, we achieve concurrent Zero Knowledge (cZK) with sub-logarithmic round complexity. Our security proof is (necessarily) non-black-box, our simulator is “straight-line” and works as long as the number of rounds is ω(1). We further show that unlike previously studied relaxations of the standard model (e.g., bounded number of sessions, timing assumptions, super-polynomial simulation), concurrent-secure computation is still impossible to achieve in the Bounded Player model. This gives evidence that our model is “closer” to the standard model than previously studied models, and study of this model might shed light on constructing round efficient concurrent zero-knowledge in the standard model as well.
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.
In this note, we show the existence of constant-round computational zero-knowledge proofs of knowledge for all N P. The existence of constant-round zero-knowledge proofs was proven by Goldreich and Kahan (Journal of Cryptology, 1996), and the existence of constant-round zeroknowledge arguments of knowledge was proven by Feige and Shamir (CRYPTO 1989). Although it is widely believed that there exist constant-round zero-knowledge proofs of knowledge for all N P, to the best of our knowledge, no proof of this fact has been published. 1
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
Simon Barber, Xavier Boyen, Elaine Shi, Ersin Uzun
Abstract. Bitcoin is a distributed digital currency which has attracted a substan-tial number of users. We perform an in-depth investigation to understand what made Bitcoin so successful, while decades of research on cryptographic e-cash has not lead to a large-scale deployment. We ask also how Bitcoin could become a good candidate for a long-lived stable currency. In doing so, we identify several issues and attacks of Bitcoin, and propose suitable techniques to address them. 1
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.
Sebastian Ries, Marc Fischlin, Leonardo A. Martucci, Max Muuhlhauser
The topics of trust and privacy are more relevant to users of online communities than ever before. Trust models provide excellent means for supporting users in their decision making process. However, those models require an exchange of information between users, which can pose a threat to the users' privacy. In this paper, we present a novel approach for a privacy preserving computation of trust. Besides preserving the privacy of the recommenders by exchanging and aggregating recommendations under encryption, the proposed approach is the first that enables the trusting entities to learn about the trustworthiness of their recommenders at the same time. This is achieved by linking the minimum amount of information that is required for the learning process to the actual recommendation and by using zero-knowledge proofs for assuring the correctness of this additional information.
Raluca Ada Popa, Andrew J. Blumberg, Hari Balakrishnan, Frank H. Li
A significant and growing class of location-based mobile applications aggregate position data from individual devices at a server and compute aggregate statistics over these position streams. Because these devices can be linked to the movement of individuals, there is significant danger that the aggregate computation will violate the location privacy of individuals. This paper develops and evaluates PrivStats, a system for computing aggregate statistics over location data that simultaneously achieves two properties: first, provable guarantees on location privacy even in the face of any side information about users known to the server, and second, privacy-preserving accountability (i.e., protection against abusive clients uploading large amounts of spurious data). PrivStats achieves these properties using a new protocol for uploading and aggregating data anonymously as well as an efficient zero-knowledge proof of knowledge protocol we developed from scratch for accountability. We implemented our system on Nexus One smartphones and commodity servers. Our experimental results demonstrate that PrivStats is a practical system: computing a common aggregate (e.g., count) over the data of 10,000 clients takes less than 0.46 s at the server and the protocol has modest latency (0.6 s) to upload data from a Nexus phone. We also validated our protocols on real driver traces from the CarTel project.
Vote validity proof and verification is an efficiency bottleneck and privacy drawback in homomorphic e-voting. The existing vote validity proof technique is inefficient and only achieves honest-verifier zero knowledge. In this paper, an efficient proof and verification technique is proposed to guarantee vote validity in homomorphic e-voting. The new proof technique is mainly based on hash function operations that only need a very small number of costly public key cryptographic operations. It can handle untrusted verifiers and achieve stronger zero knowledge privacy. As a result, the efficiency and privacy of homomorphic e-voting applications will be significantly improved.
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.
A public watermark detection scheme using verifiable secret sharing is proposed. It removes the expensive zero-knowledge interactive proofs and replaces the traditional trusted third party with a group of proxies. Moreover, the scheme is secure against sensitivity attacks and very efficient in terms of computation cost, the number of rounds and bandwidth required in the communications.
Open access
Advanced Steganography and Watermarking Techniques
In this paper, we study methods for improving the utility and privacy of reputation scores for online auctions, such as used in eBay, so as to reduce the effectiveness of feedback extortion. The main ideas behind our techniques are to use randomization and various schemes to escrow reputations scores until appropriate external events occur. Depending on the degree of utility and privacy needed, these external techniques could depend on the number and type of reputation scores collected. Moreover, if additional privacy protection is needed, then random sampling can be used with respect reputation scores in such a way that reputation aggregates remain useful, but individual reputation scores are probabilistically hidden from users. Finally, we show that if privacy is also desired with respect to the the reputation aggregator, then we can use zero-knowledge proofs for reputation comparisons.
In this thesis, we provide contributions to signature schemes and identi cation schemes in four di erent ways.\nFirst, we make contributions to universal designated veri er signatures. We propose the notion of a one-time universal designated veri er signature such that the number of veri ers verifying the signature is controlled by the signer. We also propose the notion of a universal designated veri er signature with threshold-signers such that the privacy and anonymity of the signer can be achieved.\nSecond, we propose a new notion called "policy-controlled signatures". In this notion, a policy-controlled signature can be veri ed by a veri er that satis es a policy assigned by a signer. We provide two extensions to this notion, which are "universal policy-controlled signatures" and "multi-level controlled signatures". Universal policy-controlled signatures allow a party called "a policy signer" to apply a policy on a signature on a particular message such that only a veri er that satis es this policy can verify this policy-controlled signature. In practice, some policies can be simply represented by a level of the security, for example, "POLICY= more than the fth level of security". From the above idea, a de nition of multi-level controlled signatures is introduced. It allows a signer to eliminate the unnecessary chain of attributes in the policy and simply assign the level of security as a policy instead. Hence, the size of the policy remains constant.\nNext, a new notion called "fair multi-signatures" is proposed. A multi-signature allows a group of parties to engage in an interactive protocol in order to generate a joint signature on an agreement. If all the signers follow the protocol honestly, then a multi-signature is generated and distributed fairly. However, if a dishonest signer refuses to complete his part in the protocol, but he has already obtained the other parties' contributions, then the honest signers cannot obtain a multi-signature and yet the dishonest signer can generate a multi-signature. Our notion of fair multisignatures ensures that if the protocol is completed, then every signer involved in the signing protocol can output a multi-signature. Meanwhile, if the protocol is not completed, then none of the signers involved in the signing protocol can output a multi-signature.\nFinally, in modern communications, the public becomes aware of privacy issues. Some identi cation systems provide privacy for users, especially those that are based on zero knowledge proof. However, a malicious user may take advantage of privacy to deny his malicious acts. Hence, we propose a new notion called "escrowed deniable identi cation schemes". In this notion, a trusted party is introduced to act as a transaction opener such that it can generate evidence of the conversation from the deniable transcript generated during the interaction between a prover and a veri er. In an identi cation scheme, the major concern about security is impersonation. The strongest type of attack against identi cation schemes is the reset attack. In this thesis, we provide an identity-based identi cation scheme secure against reset attack. We also provide proof of our scheme which is secure against reset attack in the standard model.
Smartmeters report the current electricity consumption over the internet back to their energy providers. Finely-sampled power consumption enables the energy provider to learn the habits of the customer's household in which the smart meter is installed. This paper presents a protocol which preserves customer privacy but also allows the detection of unregistered smart meters and prevents spamming and replay attacks. A trusted-third-party is not needed. This protocol, whose security proof relies on the strong RSA assumption and the random oracle model, is based on zero-knowledge techniques. The protocol has been implemented on different hardware platforms and benchmark results are given.
Open access
Cryptography and Data Security
Smart Grid Security and Resilience
Physical Unclonable Functions (PUFs) and Hardware Security
We propose a coin-flip protocol which yields a string of strong, random coins and is fully simulatable against poly-sized quantum adversaries on both sides. It can be implemented with quantum-computational security without any set-up assumptions, since our construction only assumes mixed commitment schemes which we show how to construct in the given setting. We then show that the interactive generation of random coins at the beginning or during outer protocols allows for quantum-secure realizations of classical schemes, again without any set-up assumptions. As example applications we discuss quantum zero-knowledge proofs of knowledge and quantum-secure two-party function evaluation. Both applications assume only fully simulatable coin-flipping and mixed commitments. Since our framework allows to construct fully simulatable coin-flipping from mixed commitments, this in particular shows that mixed commitments are complete for quantum-secure two-party function evaluation. This seems to be the first completeness result for quantum-secure two-party function evaluation from a generic assumption.
David Bernhard, Véronique Cortier, Olivier Pereira, Ben Smyth · 5 authors
Abstract. Recent results show that the current implementation of He-lios, a practical e-voting protocol, does not ensure independence of the cast votes, and demonstrate the impact of this lack of independence on vote privacy. Some simple fixes seem to be available and security of the revised scheme has been studied with respect to symbolic models. In this paper we study the security of Helios using computational models. Our first contribution is a model for the property known as ballot privacy that generalizes and extends several existing ones. Using this model, we investigate an abstract voting scheme (of which the revised Helios is an instantiation) built from an arbitrary encryp-tion scheme with certain functional properties. We prove, generically, that whenever this encryption scheme falls in the class of voting-friendly schemes that we define, the resulting voting scheme provably satisfies ballot privacy. We explain how our general result yields cryptographic security guaran-tees for the revised version of Helios (albeit from non-standard assump-tions). Furthermore, we show (by giving two distinct constructions) that it is possible to construct voting-friendly encryption, and therefore voting schemes, using only standard cryptographic tools. We detail an instan-tiation based on ElGamal encryption and Fiat-Shamir non-interactive zero-knowledge proofs that closely resembles Helios and which provably satisfies ballot privacy. 1
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.