In this thesis, we investigate the notion of privacy for signatures belonging tothe second type, i.e., those which provide privacy with respect to the signed message.
The first part of our work consists of one chapter in which one of the applications of blind signatures in on-line services and games is considered. In this way, we seek an ecient solution for a simple scenario in which a recipient can take a token from an issuer to be paid to an on-line service provider, without revealing anything about the service he intends to use.
The second part of the work considers the problem of formalizing the notion of convertible non-transferable signatures, which is addressed in two chapters. Here the notion of transferability refers to transferring the validity of a signature with respect to a given message by the recipient of the signature to a third party. The basic idea for constructing concrete schemes for such signatures is to build a scheme in which a signature can be valid with regard to any random message unless some piece of information is revealed. Non-transferable (sometimes also called private) signatures enable the signer or the recipient to decide who can verify the issued signature. It is possible to construct such signatures by computing a non-transferable signature using a non-transferable proof (in an interactive or non-interactive way) to prove its validity to the designated veri er. The concept of non-transferable signatures was introduced into cryptography by proposing undeniable signatures, in which after is- suing the signature nobody can verify it with regard to the signed message without the cooperation of the signer. This restriction of veri cation is the point of dierence between traditional signatures that are universally veri able and non-transferable signatures. The best-known examples of non-transferable signatures are undeniable signatures, designated con rmer signatures, directed signatures, universally desig- nated veri er signatures, nominative signatures, etc. In the rst three signatures, it is the signer who is interested in making the signature recognizable only to himself or some pre-chosen party, while in the last two it is the recipient who makes the signature private to himself or some known party chosen by himself. Each of these signatures has its own natural application scenarios. Although these signatures are dierent in both nature and application, almost all of them are built from the same basic primitives: zero-knowledge proofs and commitments.
An attack is mounted on a group signature scheme based on lattice posted in Asia Crypt 2010.It shows the group signature scheme is vulnerable to trap attacks and a dishonest group manager can get all group membersâČ signing keys and then forge all group membersâČ valid signatures.Meanwhile,the scheme canâČt increase or delete group members flexibly and efficiently which is not applicable to dynamic groups.Every time a new member joins,the system has to update the public key and all group membersâČ signing keys which are of huge calculation and low efficiency.Also,the scheme doesnâČt provide an effective method to revoke group members.Using statistical zero-knowledge proofs and time parameters,an improved scheme based on the hardness of the closest vector problem is proposed.The improved scheme is anti-trap attacks and can dynamic increase or deletes group members more efficiently and applicably.
In this paper, we present a solution to the problem of eâcontract validation in a supply chain with chain contracting topology. In chain contracting, there are multiple biâlateral contracts that are related, for example one original contract between two partners is modified by subsequent negotiations to form other biâlateral contracts between other parties in the supply chain. We study how to validate these contracts and ensure appropriate relationship between these contracts. We first identify key technical requirements for such a solution and then present our models that address these requirements. The models are based on the concepts of commitment scheme and zeroâknowledge proof. It can be implemented in a contract engine that supports both the contract formation and contract execution phases of the contract life cycle. Also proposed is a cryptographic scheme to facilitate the electronic transfer of payments.
Harry Kalodner, Miles Carlsten, Paul Ellenbogen, Joseph Bonneau · 5 authors
Secure decentralized namespaces have recently become possible due to cryptocurrency technology. They enable a censorship-resistant domainname system outside the control of any single entity, among other applications. Namecoin, a fork of Bitcoin, is the most prominent example. We initiate the study of decentralized namespaces and the market for names in such systems. Our extensive empirical analysis of Namecoin reveals a system in disrepair. Indeed, our methodology for detecting âsquattedâ and otherwise inactive domains reveals that among Namecoinâs roughly 120,000 registered domain names, a mere 28 are not squatted and have nontrivial content. Further, we develop techniques for detecting transfers of domains in the Namecoin block chain and provide evidence that the market for domains is thin-tononexistent. We argue that the state of the art in mechanism design for decentralized namespace markets is lacking. We propose a model of utility of different names to different participants, and articulate desiderata of a decentralized namespace in terms of this utility function. We use this model to explore the design space of mechanisms and analyze the trade-offs.
AbstractâMany cryptographic primitives, such as pseudorandom generators, encryption schemes, and zero-knowledge proofs, center around the notion of approximability. For instance, a pseudorandom generator is an expanding function which on a random seed, approximates the uniform distribution. In this paper, we classify different notions of computational approximability in the literature, and provide several new types of approximability. More specifically, we identify two hierarchies of computational approximability: The first hierarchy ranges from strong approximabilityâwhich is the most common type in the cryptographyâto the weak approximabilityâas defined by Dwork et al. (FOCS 1999). We define semi-strong, mild, and semi-weak types as well. The second hierarchy, termed K-approximability, is inspired by the Δ-approximability of Dwork et al. (STOC 1998). K-approximability has the same levels as the first hierarchy, ranging from strong K-approximability to weak K-approximability. While both hierarchies are general and can be used to define various cryptographic constructs with different levels of security, they are best illustrated in the context of zero-knowledge protocols. Assuming the existence of (trapdoor) one-way permutations, and exploiting the random oracle model, we present a separation between two definitions of zero knowledge: one based on strong K-approximability, and the other based on semi-strong K-approximability. Especially, we present a protocol which is zero knowledge only in the latter sense. The protocol is interesting in its own right, and can be used for efficient identification. Next, we show that our model for zero knowledge was not closed under sequential composition, and change the model to resolve this issue. After proving a composition theorem, we finally provide a version of the identification protocol which satisfies the requirements of the new model. Some techniques provided in this paper are of independent interest, such as proving a composition theorem in the presence of both simulator and knowledge extractor.
A zero-knowledge protocol allows a prover to convince a verifier of the correctness of a statement without disclosing any other information to the verifier. It is a basic tool and widely used in many other cryptographic applications. However, when stand-alone zero-knowledge protocols are used in complex environments, e.g., the Internet, the basic properties may not be sufficient. This is why researchers considered security of zero-knowledge protocols under concurrent composition and manin-the-middle attacks. Moreover, it is very likely that an adversary might break computers that run the protocol and get internal information of the parties. It is thus necessary to take account of the security of zero-knowledge protocols when adaptive corruptions are allowed. Previous adaptively secure zero-knowledge protocols work either in a stand-alone setting, or in a concurrent setting with trusted setup assumptions. In this paper, we study adaptive security of zero-knowledge protocols under both concurrent self composition and man-in-the-middle attacks in the plain model (i.e., without any set-up assumptions). We provide a construction of adaptively secure concurrent non-malleable zero-knowledge proof/argument for every language in NP.
Abstract. When secure arithmetic is required, computation based on secure multiplication (MULT) is much more efficient than computation based on secure boolean circuits. However, a typical application can also require other building blocks, such as comparison, exponentiation and the modulo (MOD) operation. Secure solutions for these functions proposed in the literature rely on bit-decomposition or other bit-oriented methods, which require O(â) MULTs for â-bit inputs. In the absence of a known bit-length independent solution, the complexity of the whole computation is often dominated by these non-arithmetic functions. To resolve the above problem, we start with a general modular conversion, which converts secret shares over distinct moduli. For this, we proposed a probabilistically correct protocol for this with a complexity that is independent of â. Then, we show that when these non-arithmetic functions are based on secure modular conversions, they can be computed in constant rounds and O(k) MULTs, where k is a parameter for an error rate of 2 ââŠ(k). To promote our protocols to be actively secure, we apply O(k) basic zero-knowledge proofs, which cost at most O(k) exponentiation computation, O(1) rounds and O(k(â + Îș)) communication bits, where Îș is the security parameter used in the commitment scheme.
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 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.
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 .
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.
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.