For more than 20 years, black-box impossibility results have been used to argue the infeasibility of constructing certain cryptographic primitives (e.g., key agreement) from others (e.g., one-way functions). In this dissertation we further extend the frontier of this field by demonstrating several new impossibility results as well as a new framework for studying a more general class of constructions.
Our first two results demonstrate impossibility of black-box constructions of two commonly used cryptographic primitives. In our first result we study the feasibility of black-box constructions of predicate encryption schemes from standard assumptions and demonstrate strong limitations on the types of schemes that can be constructed. In our second result we study black-box constructions of constant-round zero-knowledge proofs from one-way permutations and show that, under commonly believed complexity assumptions, no such constructions exist.
A widely recognized limitation of black-box impossibility results, however, is that they say nothing about the usefulness of (known) non-black-box techniques. This state of affairs is unsatisfying as we would at least like to rule out constructions using the set of techniques we have at our disposal. With this motivation in mind, in the final result of this dissertation we propose a new framework for black-box constructions with a non-black-box flavor, specifically, those that rely on zero-knowledge proofs relative to some oracle. Our framework is powerful enough to capture a large class of known constructions, however we show that the original black-box separation of key agreement from one-way functions still holds even in this non-black-box setting that allows for zero-knowledge proofs.
We define a new notion of relatively-sound non-interactive zeroknowledge (NIZK) proofs, where a private verifier with access to a trapdoor continues to be sound even when the Adversary has access to simulated proofs and common reference strings. It is likely that this weaker notion of relative-soundness suffices in most applications that need simulation-soundness. We show that for certain languages whicharediversegroups,and henceallowsmoothprojectivehashfunctions, one can obtain more efficient single-theorem relatively-sound NIZKsas opposed to simulation-sound NIZKs. We alsoshow that such relatively-sound NIZKs can be used to build rather efficient publiclyverifiable CCA2-encryption schemes. By employing this new publicly-verifiable encryption scheme along withanassociatedsmoothprojective-hash,weshowthatarecentPAKmodel single-round password-basedkey exchange protocol of Katz and
Abstract. We present a generic transformation that allows us to use a large class of pairing-based signatures to construct schemes for signing group elements in a structure preserving way. As a result of our transformation we obtain a new efficient signature scheme for signing a vector of group elements that is based only on the well established decisional linear assumption (DLIN). Moreover, the public keys and signatures of our scheme consist of group elements only, and a signature is verified by evaluating a set of pairing-product equations. In combination with the Groth-Sahai proof system, such a signature scheme is an ideal building block for many privacy-enhancing protocols. To do this, we start by proposing a new stateful signature scheme for signing vectors of exponents that is F-unforgeable under weak chosen message attacks. This signature scheme is of independent interest as it is compatible with Groth-Sahai proofs and secure under a computational assumption implied by DLIN. Then we give a general transformation for signing group elements based on signatures (for signing exponents) with efficient non-interactive zero-knowledge proofs. This transform also removes any dependence on state in the signature used to sign exponents. Finally, we obtain our result by instantiating this transformation with the above signature scheme and Groth-Sahai proofs. 1
Abstract. In resetting attacks against a proof system, a prover or a verifier is reset and enforced to use the same random tape on various inputs as many times as an adversary may want. Recent deployment of cloud computing gives these attacks a new importance. This paper shows that argument systems for any NP language that are both resettably-sound and resettable zero-knowledge are possible by a constant-round protocol in the BPK model. For that sake, we define and construct a resettablyextractable conditional commitment scheme.
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.
Abstract. Smart meters that track fine-grained electricity usage and implement sophisticated usage-based billing policies, e.g., based on timeof-use, are a key component of recent smart grid initiatives that aim to increase the electric grid’s efficiency. A key impediment to widespread smart meter deployment is that fine-grained usage data indirectly reveals detailed information about consumer behavior, such as when occupants are home, when they have guests or their eating and sleeping patterns. Recent research proposes cryptographic solutions that enable sophisticated billing policies without leaking information. However, prior research does not measure the performance constraints of real-world smart meters, which use cheap ultra-low-power microcontrollers to lower deployment costs. In this paper, we explore the feasibility of designing privacy-preserving smart meters using low-cost microcontrollers and provide a general methodology for estimating design costs. We show that it is feasible to produce certified meter readings for use in billing protocols relying on Zero-Knowledge Proofs with microcontrollers such as those inside currently deployed smart meters. Our prototype meter is capable of producing these readings every 10 seconds using a $3.30USD MSP430 microcontroller, while less powerful microcontrollers deployed in today’s smart meters are capable of producing readings every 28 seconds. In addition to our results, our goal is to provide smart meter designers with a general methodology for selecting an appropriate balance between platform performance, power consumption, and monetary cost that accommodates privacy-preserving billing protocols. 1
Cramer, Damgard, and Nielsen [CDN01] show how to construct an efficient secure multiparty computation scheme using a threshold homomorphic encryption scheme that has four properties i) a honest-verifier zero-knowledge proof of knowledge of encrypted values, ii) proving multiplications correct iii) threshold decryption and iv) trusted shared key setup. Naor and Nissim [NN01a] show how to construct secure multi-party protocols for a function f whose communication is proportional to the communication required to evaluate f without security, albeit at the cost of computation that might be exponential in the description of f . Gentry [Gen09a] shows how to combine both ideas with fully homomorphic encryption in order to construct secure multi-party protocol that allows evaluation of a function f using communication that is independent of the circuit description of f and computation that is polynomial in | f |. This paper addresses the major drawback’s of Gentry’s approach: we eliminate the use of non-black box methods that are inherent in Naor and Nissim’s compiler. To do this we show how to modify the fully homomorphic encryption construction of van Dijk et al. [vDGHV10] to be threshold fully homomorphic encryption schemes. We directly construct (information theoretically) secure protocols for sharing the secret key for our threshold scheme (thereby removing the setup assumptions) and for jointly decrypting a bit. All of these constructions are constant round and we thoroughly analyze their complexity; they address requirements (iii) and (iv). The fact that the encryption scheme is fully homomorphic addresses requirement (ii). To address the need for an honest-verifier zero-knowledge proof of knowledge of encrypted values, we instead argue that a weaker solution suffices. We provide a 2-round blackbox protocol that allows us to prove knowledge of encrypted bits. Our protocol is not zeroknowledge, but it provably does not release any information about the bit being discussed, and this is sufficient to prove the correctness of a simulation in a method similar to Cramer et al. Altogether, we construct the first black-box secure multi-party computation protocol that allows evaluation of a function f using communication that is independent of the circuit description of f .
Proof-carrying authorization (PCA) is one of the most popular approaches for the enforcement of access control policies. In a nutshell, the idea is to formalize a policy as a set of logical rules and to let the requester construct a formal proof showing that she has permissions to access the desired resource according to the provider’s policy. This policy may depend on logical formulas that are assumed by other principals in the system. The validity of these formulas is witnessed by digital signatures. The usage of digital signatures, however, has a serious drawback, i.e., sensitive data are leaked to the verifier, which severely limits the applicability of PCA. In this paper, we introduce the notion of privacy-aware proof-carrying authorization, an extension of PCA based on a powerful combination of digital signatures and zero-knowledge proofs of knowledge of such signatures. The former are used to witness the validity of logical formulas, the latter to selectively hide sensitive data. Our framework supports a variety of privacy properties, such as data secrecy and user anonymity. We conducted an experimental evaluation to demonstrate the feasibility of our approach.
The proposed public-key managements of Ad hoc networks must take many nodes as service nodes,which run counter to the characters of Ad hoc networks,such as self-organized and centerless.They also take much traffic to create public-private key pairs and certificates,and they are poor in robustness.This paper proposed a novel fully self-organized public-key management system that took zero knowledge proofs into the process of certification and allowed users to generate their public-private key pairs,to issue certificates,and to perform authentication regardless of the network partitions and without any certralized services.The protocol analysis study and simulations prove that the public-key management system has low traffic,high reliability and robustness.
Based on ELGamal digital signature and zero-knowledge proof with the method of directed signature,a two-way identification scheme was proposed,which enabled two specific users to validate each other's identity without exposing one's own secret information.The scheme has higher security and lower computing complexity.
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
This paper proposes a zero-knowledge proof scheme of possessing a DSA digital signature,in which the prover does not directly give the DSA signature of the message,but gives a zero-knowledge proof of possessing the DSA signature.Preventing the signature from being copied at discretion,the scheme can be used in copyright protection.
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.
The Zero-Knowledge Proof(ZKP)is a powerful tool which can be used and already be used for many cryptographic applications and E-Commerce.But all existing Zero-Knowledge Proofs are iterative in nature,it increases the communication traffic of in interactive bilateral,and makes difficult in practice.This thesis proposes a new ZKP protocol which runs in one-round while ensure the completeness property,and the soundness property,and decreases the communication traffic in the maximum extent.The scheme is based on the Paillier Cryptosystem,and ascribes security to it.
This paper presents a new zero-knowledge protocol for SDH pair(A,a),which is based on Chik How Tan encryption,then we prove that the protocol is an honest verifier zero knowledge proof of knowledge under DBDH assumption.The protocol is suitable for users with higher requirements for data security.Compared with[6],the protocol is of higher efficiency.