Eli Ben‐Sasson, Alessandro Chiesa, Christina Garman, Matthew Green · 7 authors
Bit coin is the first digital currency to see widespread adoption. While payments are conducted between pseudonyms, Bit coin cannot offer strong privacy guarantees: payment transactions are recorded in a public decentralized ledger, from which much information can be deduced. Zero coin (Miers et al., IEEE S&P 2013) tackles some of these privacy issues by unlinking transactions from the payment's origin. Yet, it still reveals payments' destinations and amounts, and is limited in functionality. In this paper, we construct a full-fledged ledger-based digital currency with strong privacy guarantees. Our results leverage recent advances in zero-knowledge Succinct Non-interactive Arguments of Knowledge (zk-SNARKs). First, we formulate and construct decentralized anonymous payment schemes (DAP schemes). A DAP scheme enables users to directly pay each other privately: the corresponding transaction hides the payment's origin, destination, and transferred amount. We provide formal definitions and proofs of the construction's security. Second, we build Zero cash, a practical instantiation of our DAP scheme construction. In Zero cash, transactions are less than 1 kB and take under 6 ms to verify - orders of magnitude more efficient than the less-anonymous Zero coin and competitive with plain Bit coin.
The Bitcoin cryptocurrency records its transactions in a public log called the blockchain. Its security rests critically on the distributed protocol that maintains the blockchain, run by participants called miners. Conventional wisdom asserts that the protocol is incentive-compatible and secure against colluding minority groups, i.e., it incentivizes miners to follow the protocol as prescribed. We show that the Bitcoin protocol is not incentive-compatible. We present an attack with which colluding miners obtain a revenue larger than their fair share. This attack can have significant consequences for Bitcoin: Rational miners will prefer to join the selfish miners, and the colluding group will increase in size until it becomes a majority. At this point, the Bitcoin system ceases to be a decentralized currency. Selfish mining is feasible for any group size of colluding miners. We propose a practical modification to the Bitcoin protocol that protects against selfish mining pools that command less than 1/4 of the resources. This threshold is lower than the wrongly assumed 1/2 bound, but better than the current reality where a group of any size can compromise the system.
A collection of questions about Bitcoin and its hypothetical relatives Bitguilder and Bitpenny is formulated. These questions concern technical issues about protocols, security issues, issues about the formalizations of informational monies in various contexts, and issues about forms of use and misuse. Some questions are formulated in the more general setting of informational monies and near-monies. We also formulate questions about legal, psychological, and ethical aspects of informational money. Finally we formulate a number of questions concerning the economical merits of and outlooks for Bitcoin.
The Bitcoin network of decentralized payment transactions has attracted a lot of attention from both Internet users and researchers in recent years. Bitcoin utilizes a peer-to-peer network to issue anonymous payment transactions between different users. In the currently used Bitcoin clients, the full transaction history is available at each node of the network to prevent double spending without the need for a central authority, forming a valuable source for empirical research on network structure, network dynamics, and the implied anonymity challenges, as well as guidance on the future evolution of complex payment systems. We found dynamical effects of which some increase anonymity while others decrease it. Most importantly, several parameters of the Bitcoin transaction graph seem to have become stationary over the last 12–18 months. We discuss the implications.
In this article, we discuss a possible exploit in Bitcoin that arises from the simultaneous adoption of client versions 0.8.1 and 0.8.2 (or 0.8.3) in the network. In version 0.8.2, Bitcoin clients no longer accept transactions with non-strict signature encoding. As we show, this incompatibility with prior client versions can potentially lead to a double-spending attack in a fast payment setting in Bitcoin. The attack can only work when merchants operate on any client version prior to 0.8.2. Our aim is therefore to raise the awareness of merchants to adopt version 0.8.2 (or 0.8.3) if they are willing to accept fast payments [1].
Online advertising is at the core of today’s Web: it is the main business model, generating large annual revenues expressed in tens of billions of dollars that sponsor most of the online content and services. Online advertising consists of delivering marketing messages, embedded into Web content, to a targeted audience. In this model, entities attract Web traffic by offering the content and services for free and charge advertisers for including advertisements in this traffic (i.e., advertisers pay for users’ attention and interests). Online advertising is a very successful form of advertising as it allows for advertisements (ads) to be targeted to individual users’ interests; especially when advertisements are served on users’ mobile devices, as ads can be targeted to users’ locations and the corresponding context. However, online advertising also introduces a number of problems. Given the high ad revenue at stake, fraudsters have economic incentives to exploit the ad system and generate profit from it. Unfortunately, to achieve this goal, they often compromise users’ online security (e.g., via malware, phishing, etc.). For the purpose of maximizing the revenue by matching ads to users’ interests, a number of techniques are deployed, aimed at tracking and profiling users’ digital footprints, i.e., their behavior in the digital world. These techniques introduce new threats to users’ privacy. Consequently, some users adopt ad-avoidance tools that prevent the download of advertisements and partially thwart user profiling. Such user behavior, as well as exploits of ad systems, have economic implications as they undermine the online advertising business model. Meddling with advertising revenue disrupts the current economic model of the Web, the consequences of which are unclear. Given that today’s Web model relies on online advertising revenue in order for users to have access and consume content and services for “free”, coupled with the fact that there are many threats that could jeopardize this model, in this thesis we address the security, privacy and economic issues stemming from this fundamental element of the Web. In the first part of the thesis, we investigate the vulnerabilities of online advertising systems. We identify how an adversary can exploit the ad system to generate profit for itself, notably by performing inflight modification of ad traffic. We provide a proof-of-concept implementation of the identified threat on Wi-Fi routers. We propose a collaborative approach for securing online advertising and Web browsing against such threats. By investigating how a certificate-based authentication is deployed in practice, we assess the potential of relying on certificate-based authentication as a building block of a solution to protect the ad revenue. We propose a multidisciplinary approach for improving the current state of certificate-based authentication on the Web. In the second part of the thesis, we study the economics of ad systems’ exploits and certain potential countermeasures. We evaluate the potential of different solutions aimed at protecting ad revenue being implemented by the stakeholders (e.g., Internet Service Providers or ad networks) and the conditions under which this is likely to happen. We also study the economic ramifications of ad-avoidance technologies on the monetization of online content. We use game-theory to model the strategic behavior of involved entities and their interactions. In the third part of the thesis, we focus on privacy implications of online advertising. We identify a novel threat to users’ location privacy that enables service providers to geolocate users with high accuracy, which is needed to serve location-targeted ads for local businesses. We draw attention to the large scale of the threat and the potential impact on users’ location privacy.
Man Ho Au, Willy Susilo, Yi Mu, Sherman S. M. Chow
Dynamick-times anonymous authentication (k-TAA) schemes allow members of a group to be authenticated anonymously by application providers for a bounded number of times, where application providers can independently and dynamically grant or revoke access right to members in their own group. In this paper, we construct a dynamick-TAA scheme with space and time complexities ofO(log(k)) and a variant, in which the authentication protocol only requires constant time and space complexities at the cost ofO(k) -sized public key. We also describe some tradeoff issues between different system characteristics. We detail all the zero-knowledge proof-of-knowledge protocols involved and show that our construction is secure in the random oracle model under theq-strong Diffie-Hellman assumption andq-decisional Diffie-Hellman inversion assumption. We provide a proof-of-concept implementation, experiment on its performance, and show that our scheme is practical.
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.
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
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.
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\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
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
Traditional electricity meters are replaced by Smart Meters in customers' households. Smart Meters collects fine-grained utility consumption profiles from customers, which in turn enables the introduction of dynamic, time-of-use tariffs. However, the fine-grained usage data that is compiled in this process also allows to infer the inhabitant's personal schedules and habits. We propose a privacy-preserving protocol that enables billing with time-of-use tariffs without disclosing the actual consumption profile to the supplier. Our approach relies on a zero-knowledge proof based on Pedersen Commitments performed by a plug-in privacy component that is put into the communication link between Smart Meter and supplier's back-end system. We require no changes to the Smart Meter hardware and only small changes to the software of Smart Meter and back-end system. In this paper we describe the functional and privacy requirements, the specification and security proof of our solution and give a performance evaluation of a prototypical implementation.
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.
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.