To enhance user privacy, anonymous credential systems allow the user to convince a verifier of the possession of a certificate issued by the issuing authority anonymously. The typical application is the privacy-enhancing electronic ID (eID). Although a previously proposed system achieves the constant complexity in the number of finite-set attributes of the user, it requires the use of RSA. In this paper, we propose a pairing-based anonymous credential system excluding RSA that achieves the constant complexity. The key idea of our proposal is the adoption of a pairing-based accumulator that outputs a constant-size value from a large set of input values. Using zero-knowledge proofs of pairing-based certificates and accumulators, any AND and OR relation can be proved with the constant complexity in the number of finite-set attributes. We implement the proposed system using the fast pairing library, compare the efficiency with the conventional systems, and show the practicality in a mobile eID application.
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.
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
Moshe Babaioff, Shahar Dobzinski, Sigal Oren, Aviv Zohar
Many large decentralized systems rely on information propagation to ensure their proper function. We examine a common scenario in which only participants that are aware of the information can compete for some reward, and thus informed participants have an incentive not to propagate information to others. One recent example in which such tension arises is the 2009 DARPA Network Challenge (finding red balloons). We focus on another prominent example: Bitcoin, a decentralized electronic currency system. Bitcoin represents a radical new approach to monetary systems. It has been getting a large amount of public attention over the last year, both in policy discussions and in the popular press. Its cryptographic fundamentals have largely held up even as its usage has become increasingly widespread. We find, however, that it exhibits a fundamental problem of a different nature, based on how its incentives are structured. We propose a modification to the protocol that can eliminate this problem. Bitcoin relies on a peer-to-peer network to track transactions that are performed with the currency. For this purpose, every transaction a node learns about should be transmitted to its neighbors in the network. The current implemented protocol provides an incentive to nodes to not broadcast transactions they are aware of. Our solution is to augment the protocol with a scheme that rewards information propagation. Since clones are easy to create in the Bitcoin system, an important feature of our scheme is Sybil-proofness. We show that our proposed scheme succeeds in setting the correct incentives, that it is Sybil-proof, and that it requires only a small payment overhead, all this is achieved with iterated elimination of dominated strategies. We complement this result by showing that there are no reward schemes in which information propagation and no self-cloning is a dominant strategy.
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.
Anonymity in Bitcoin, a peer-to-peer electronic currency system, is a complicated issue. Within the system, users are identified by public-keys only. An attacker wishing to de-anonymize its users will attempt to construct the one-to-many mapping between users and public-keys and associate information external to the system with the users. Bitcoin tries to prevent this attack by storing the mapping of a user to his or her public-keys on that user's node only and by allowing each user to generate as many public-keys as required. In this chapter we consider the topological structure of two networks derived from Bitcoin's public transaction history. We show that the two networks have a non-trivial topological structure, provide complementary views of the Bitcoin system and have implications for anonymity. We combine these structures with external information and techniques such as context discovery and flow analysis to investigate an alleged theft of Bitcoins, which, at the time of the theft, had a market value of approximately half a million U.S. dollars.
In this paper, we study methods for improving the utility and privacy of\nreputation scores for online auctions, such as used in eBay, so as to reduce\nthe effectiveness of feedback extortion. The main ideas behind our techniques\nare to use randomization and various schemes to escrow reputations scores until\nappropriate external events occur. Depending on the degree of utility and\nprivacy needed, these external techniques could depend on the number and type\nof reputation scores collected. Moreover, if additional privacy protection is\nneeded, then random sampling can be used with respect reputation scores in such\na way that reputation aggregates remain useful, but individual reputation\nscores are probabilistically hidden from users. Finally, we show that if\nprivacy is also desired with respect to the the reputation aggregator, then we\ncan use zero-knowledge proofs for reputation comparisons.\n
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.
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
Matteo Maffei, Giulio Malavolta, Manuel Reinert, Dominique Schröder
The existing (election) voting systems, e.g., representative democracy, have many limitations and often fail to serve the best interest of the people in collective decision making. To address this issue, the concept of liquid democracy has been emerging as an alternative decision-making model to make better use of "the wisdom of crowds". Very recently, a few liquid democracy implementations, e.g. Google Votes and Decentralized Autonomous Organization (DAO), are released; however, those systems only focus on the functionality aspect, as no privacy/anonymity is considered. In this work, we, for the first time, provide a rigorous study of liquid democracy under the Universal Composability (UC) frame- work. In the literature, liquid democracy was achieved via two separate stages -- delegation and voting. We propose an efficient liquid democracy e-voting scheme that uni es these two stages. At the core of our design is a new voting concept called statement voting, which can be viewed as a natural extension of the conventional voting approaches. We remark that our statement voting can be extended to enable more complex voting and generic ledger-based non-interactive multi-party computation. We believe that the statement voting concept opens a door for constructing a new class of e-voting schemes.
Digital signatures are fundamental cryptographic primitives. They are useful as a stand-alone application and building blocks of complex cryptographic systems. Accumulators are another useful cryptographic primitive which provide a way to combine a set of values into one short value. They are useful in improving efficiency of cryptographic systems. In particular, these two primitives are key components in privacy-preserving cryptographic systems. In this thesis, we study the use of digital signatures and accumulators in cryptographic applications. We design digital signature schemes and accumulators with different features that are suitable for a wide range of applications. We are interested in privacy-preserving cryptographic applications including anonymous electronic cash systems, anonymous authentication schemes and anonymous credential systems. We construct three different digital signature schemes, each with distinctive features. We also propose two novel constructions of accumulators. Based on our signature schemes and accumulators, we design two compact electronic cash schemes and a divisible electronic cash scheme. All our schemes are truly anonymous, meaning that privacy of the users is well-protected. We also explore other applications of our newly proposed signatures and accumulators. Specifically, we give a construction of k-times anonymous authentication schemes and attribute-based anonymous credential systems. During the course of the development of the thesis, we generalise existing techniques of zero-knowledge proof-of-knowledge protocol of double-discrete logarithms into zero-knowledge proof-of-knowledge protocol of representation of a committed value. Our protocol is compatible with existing zero-knowledge proof-of-knowledge protocols that demonstrate relationship amongst discrete logarithms. We believe that this protocol, together with the newly introduced primitives, are of independent interest.
Rafael Pass, Wei-Lung Dustin Tseng, Douglas Wikström
We show that only languages in BPP have public-coin black-box zero-knowledge protocols that are secure under an unbounded (polynomial) number of parallel repetitions. This result holds both in the plain model (without any setup) and in the bare public key model (where the prover and the verifier have registered public keys). We complement this result by constructing a public-coin black-box zero-knowledge proof based on one-way functions that remains secure under any a priori bounded number of concurrent executions. A key step (of independent interest) in the analysis of our lower bound shows that any public-coin protocol, when repeated sufficiently in parallel, satisfies a notion of “resettable soundness” if the verifier picks its random coins using a pseudorandom function.