Blockchain Papers

Dan Boneh, Divya Gupta, Ilya Mironov, Amit Sahai

No abstract is available for this record.

David Derler, Henrich C. Pöhls, Kai Samelin, Daniel Slamanig

Abstract. A redactable signature scheme (RSS) allows removing parts of a signed message by any party without invalidating the respective signa-ture. State-of-the-art constructions thereby focus on messages represented by one specific data-structure, e.g., lists, sets or trees, and adjust the secu-rity model accordingly. To overcome the necessity for this myriad of models, we present a general framework covering arbitrary data-structures and even more sophisticated possibilities. For example, we cover fixed elements which must not be redactable and dependencies between elements. Moreover, we introduce the notion of designated redactors, i.e., the signer can give some extra information to selected entities which become redactors. In practice, this often allows to obtain more efficient schemes. We then present two RSSs; one for sets and one for lists, both constructed from any EUF-CMA secure signature scheme and indistinguishable cryptographic accumulators in a black-box way and show how the concept of designated redactors can be used to increase the efficiency of these schemes. Finally, we present a black-box construction of a designated redactor RSS by combining an RSS for sets with non-interactive zero-knowledge proof systems. All the three constructions presented in this paper provide transparency, which is an im-portant property, but quite hard to achieve, as we also conceal the length of the original message and the positions of the redactions. 1

Essam Ghadafi

No abstract is available for this record.

Philipp Locher, Rolf Haenni

No abstract is available for this record.

Pyrros Chaidos, Jens Groth

No abstract is available for this record.

Adam Everspaugh, Rahul Chatterjee, Samuel Scott, Ari Juels · 5 authors

Conventional cryptographic services such as hardware-security modules and software-based key-management systems offer the ability to apply a pseudorandom function (PRF) such as HMAC to inputs of a client's choosing. These services are used, for example, to harden stored password hashes against offline brute-force attacks. We propose a modern PRF service called PYTHIA designed to offer a level of flexibility, security, and ease-of-deployability lacking in prior approaches. The keystone of PYTHIA is a new cryptographic primitive called a verifiable partially-oblivious PRF that reveals a portion of an input message to the service but hides the rest. We give a construction that additionally supports efficient bulk rotation of previously obtained PRF values to new keys. Performance measurements show that our construction, which relies on bilinear pairings and zero-knowledge proofs, is highly practical. We also give accompanying formal definitions and proofs of security. We implement PYTHIA as a multi-tenant, scalable PRF service that can scale up to hundreds of millions of distinct client applications on commodity systems. In our prototype implementation, query latencies are 15 ms in local-area settings and throughput is within a factor of two of a standard HTTPS server. We further report on implementations of two applications using PYTHIA, showing how to bring its security benefits to a new enterprise password storage system and a new brainwallet system for Bitcoin.

Vinod Vaikuntanathan, Prashant Nalini Vasudevan

We show a general connection between various types of statistical zero-knowledge (SZK) proof systems and (unconditionally secure) secret sharing schemes. Viewed through the SZK lens, we obtain several new results on secret-sharing: Characterizations: We obtain an almost-characterization of access structures for which there are secret-sharing schemes with an ecient sharing algorithm (but not necessarily ecient reconstruction). In particular, we show that for every language L2 SZKL (the class of languages that have statistical zero knowledge proofs with log-space veriers and simulators), a (monotonized) access structure associated with L has such a secretsharing scheme. Conversely, we show that such secret-sharing schemes can only exist for languages in SZK. Constructions: We show new constructions of secret-sharing schemes with ecient sharing and reconstruction for access structures that are in P, but are not known to be in NC, namely Bounded-Degree Graph Isomorphism and constant-dimensional lattice problems. In particular, this gives us the rst combinatorial access structure that is conjectured to be outside NC but has an ecient secret-sharing scheme. Previous such constructions (Beimel and Ishai; CCC 2001) were algebraic and number-theoretic in nature. Limitations: We show that universally-ecie nt secret-sharing schemes, where the complexity of computing the shares is a polynomial independent of the complexity of deciding the access structure, cannot exist for all (monotone languages in) P, unless there is a polynomial q such that P DSPACE(q(n)).

Michael Abramowicz

This paper proposes a self-governing cryptocurrency, dubbed Autonocoin. Cryptocurrency owners play formal tacit coordination games by making investments recorded on the blockchain. Such investments represent bets about the focal point resolution of normative issues, such as whether a proposed change to Autonocoin should occur. The game produces a result that resolves the issue. With a typical cryptocurrency, the client software establishes conventions that ultimately lead to the identification of the authoritative blockchain. Autonocoin completes a circle by making transactions on the blockchain that in turn define those conventions and the expected software behavior. The distributed consensus mechanism embodied by formal tacit coordination games, meanwhile, can make other types of decisions, including which of competing blockchains is authoritative and whether new Autonocoins should be rewarded to benefit those who have taken actions to benefit Autonocoin. This establishes a unique funding model for a cryptocurrency, and it addresses objections to cryptocurrencies issued predominantly to the initial founders, as well as to those that encourage wasteful mining activities.

Rong Hu, Kirill Morozov, Tsuyoshi Takagi

Code-based public-key encryption schemes (PKE) are the candidates for post-quantum cryptography, since they are believed to resist the attacks using quantum algorithms. The most famous such schemes are the McEliece encryption and the Niederreiter encryption. In this paper, we present the zero-knowledge (ZK) proof systems for proving statements about data encrypted using these schemes. Specifically, we present a proof of plaintext knowledge for both PKE's, and also a verifiable McEliece PKE. The main ingredients of our constructions are the ZK identification schemes by Stern from Crypto'93 and by Jain, Krenn, Pietrzak, and Tentes from Asiacrypt'12.

Matteo Maffei, Giulio Malavolta, Manuel Reinert, Dominique Schröder

Cloud storage has rapidly become a cornerstone of many IT infrastructures, constituting a seamless solution for the backup, synchronization, and sharing of large amounts of data. Putting user data in the direct control of cloud service providers, however, raises security and privacy concerns related to the integrity of outsourced data, the accidental or intentional leakage of sensitive information, the profiling of user activities and so on. Furthermore, even if the cloud provider is trusted, users having access to outsourced files might be malicious and misbehave. These concerns are particularly serious in sensitive applications like personal health records and credit score systems. To tackle this problem, we present GORAM, a cryptographic system that protects the secrecy and integrity of outsourced data with respect to both an untrusted server and malicious clients, guarantees the anonymity and unlink ability of accesses to such data, and allows the data owner to share outsourced data with other clients, selectively granting them read and write permissions. GORAM is the first system to achieve such a wide range of security and privacy properties for outsourced storage. In the process of designing an efficient construction, we developed two new, generally applicable cryptographic schemes, namely, batched zero-knowledge proofs of shuffle and an accountability technique based on chameleon signatures, which we consider of independent interest. We implemented GORAM in Amazon Elastic Compute Cloud (EC2) and ran a performance evaluation demonstrating the scalability and efficiency of our construction.

Berry Schoenmakers, Meilof Veeningen

Abstract. Multiparty computation can be used for privacy-friendly out-sourcing of computations on private inputs of multiple parties. A com-putation is outsourced to several computation parties; if not too many are corrupted (e.g., no more than half), then they cannot determine the inputs or produce an incorrect output. However, in many cases, these guarantees are not enough: we need correctness even if all computation parties may be corrupted; and we need that correctness can be verified even by parties that did not participate in the computation. Protocols satisfying these additional properties are called “universally verifiable”. In this paper, we propose a new security model for universally verifi-able multiparty computation, and we present a practical construction, based on a threshold homomorphic cryptosystem. We also develop a multiparty protocol for jointly producing non-interactive zero-knowledge proofs, which may be of independent interest.

Loi Luu, Viswesh Narayanan, Kunal Baweja, Chaodong Zheng · 6 authors

Abstract—In this paper, we design a new blockchain Byzantine consensus protocol SCP where the throughput scales nearly lin-early with the computation: the more computing power available, the more blocks selected per unit time. SCP is also efficient that the number of messages it requires is nearly linear in the network size. The computational scalability property offers the flexibility to tune bandwidth consumption by adjusting computational param-eters (e.g., proof-of-work difficulty). The key ideas lie in securely establishing identities for network participants, randomly placing them in several committees and running a classical consensus protocol within each committee to propose blocks in parallel. We further design a mechanism to allow reaching consensus on blocks without broadcasting actual block data, while still enabling efficient block verification. We prove that our protocol is secure, efficient and applicable to several case studies. We conduct scalability experiments on Amazon EC2 with upto 80 cores, and confirm that SCP matches its theoretical scaling properties. I.

Dominique Unruh

We present a new definition of computationally binding commitment schemes in the quantum setting, which we call “collapse-binding”. The definition applies to string commitments, composes in parallel, and works well with rewindingbased proofs. We give simple constructions of collapse-binding commitments in the random oracle model, giving evidence that they can be realized from hash functions like SHA-3. We evidence the usefulness of our definition by constructing three-round statistical zero-knowledge quantum arguments of knowledge for all NP languages.

Eike Kiltz, Hoeteck Wee

Non-interactive zero-knowledge (NIZK) proofs for algebraic relations in a group, such as the GrothSahai proofs, are an extremely powerful tool in pairing-based cryptography. A series of recent works focused on obtaining very efficient NIZK proofs for linear spaces in a weaker quasi-adaptive model. We revisit recent quasiadaptive NIZK constructions, providing clean, simple, and improved constructions via a conceptually different approach inspired by recent developments in identity-based encryption. We then extend our techniques also to linearly homomorphic structure-preserving signatures, an object both of independent interest and with many applications.

Aggelos Kiayias, Thomas Zacharias, Bingsheng Zhang

No abstract is available for this record.

Yuval Ishai, Mor Weiss, Guang Yang

A Probabilistically Checkable Proof (PCP) allows a randomized verifier, with oracle access to a purported proof, to probabilistically verify an input statement of the form “x ∈ L ” by querying only few bits of the proof. A zero-knowledge PCP (ZKPCP) is a PCP with the additional guarantee that the view of any verifier querying a bounded number of proof bits can be efficiently simulated given the input x alone, where the simulated and actual views are statistically close. Originating from the first ZKPCP construction of Kilian et al. (STOC ’97), all previous constructions relied on locking schemes, an unconditionally secure oracle-based commitment primitive. The use of locking schemes makes the verifier inherently adaptive, namely, it needs to make at least two rounds of queries to the proof. Motivated by the goal of constructing non-adaptively verifiable ZKPCPs, we suggest a new technique for compiling standard PCPs into ZKPCPs. Our approach is based on leakage-resilient circuits, which are circuits that withstand certain “side-channel ” attacks, in the sense that these attacks reveal nothing about the (properly encoded) input, other than the output. We observe that the verifier’s oracle queries constitute a side-channel attack on the wire-values of the circuit

Alex Biryukov, Daniel Dinu, Dmitry Khovratovich

Memory-hard functions are becoming an important tool in the design of password hashing schemes, cryptocur-rencies, and more generic proof-of-work primitives that are x86-oriented and can not be computed on dedicated hardware more efficiently. We develop a simple and cryptographically secure approach to the design of such functions and show how to exploit the architecture of modern CPUs and memory chips to make faster and more secure schemes compared to existing alternatives such as scrypt. We also propose cryptographic criteria for the components, that prevent cost reductions using time-memory tradeoffs and side-channel leaks. The concrete proof-of-work instantiation, which we call Argon2, can fill GBytes of RAM within a second, is resilient to various tradeoffs, and is suitable for a wide range of applications, which aim to bind a computation to a certain architecture. Concerning potential DoS attacks, our scheme is lightweight enough to offset the bottleneck from the CPU to the memory bus thus leaving sufficient computing power for other tasks. We also propose parameters for which our scheme is botnet resistant. As an application, we suggest a cryptocurrency design with fast and memory-hard proof-of-work, which allows memoryless verification. 1

Gaby G. Dagher, Benedikt Bünz, Joseph Bonneau, Jeremy Clark · 5 authors

Bitcoin exchanges function like banks, securely holding their cus-tomers ’ bitcoins on their behalf. Several exchanges have suffered catastrophic losses with customers permanently losing their sav-ings. A proof of solvency demonstrates that the exchange controls sufficient reserves to settle each customer’s account. We introduce Provisions, a privacy-preserving proof of solvency whereby an ex-change does not have to disclose its Bitcoin addresses; total hold-ings or liabilities; or any information about its customers. We also propose an extension which prevents exchanges from colluding to cover for each other’s losses. We have implemented Provisions and it offers practical computation times and proof sizes even for a large Bitcoin exchange with millions of customers.

Rafail Ostrovsky, Alessandra Scafuro, Muthuramakrishnan Venkitasubramanian

No abstract is available for this record.

Thomas Groß

No abstract is available for this record.

Liam Morris

Cash in the real world allows for parties to exchange currency without the need to go through some sort of central authority. One person, Alice, can simply hand cash over to another person, Bob. In this transaction the only two people that have knowledge of this exchange are Alice and Bob. Until recently there was no electronic equivalent to this exchange. In 1982 David Chaum proposed a system of anonymous electronic cash based on blind signatures, and in 1990 founded DigiCash as an electronic cash company. There were a few banks that implemented electronic cash systems, but these banks and DigiCash ultimately went bankrupt in 1997 and 1998 despite the enthusiasm surrounding anonymous electronic cash. Between 1998 and 2008 there were no successful implementations of electronic cash that offer a decentralized, anonymous, and untraceable system.\nIn 2008 a paper was published by Satoshi Nakamoto on the cryptocurrency known as Bitcoin. A cryptocurrency is a form of electronic cash backed by mathematical and cryptographic constructs, unlike traditional currency which was historically backed by gold or silver. Cryptocurrencies have seen rising popularity in recent years due to their decentralized, distributed, peer-to-peer protocols. Part of this rising popularity is also attributable to the supposed anonymity of these protocols; however, due to the public transaction history required for these protocols and the fact that transactions are pseudonymous and not purely anonymous, this supposed anonymity does not exist. While the systems may achieve the goal of decentralized currency it does not achieve the goal of untraceability. In this thesis we analyze the technical implementations of Bitcoin and other cryptocurrencies to determine the level of anonymity provided by these protocols. We also analyze proposed improvements for their feasibility.

Pasquale Forte, Diego Romano, Giovanni Schmid

After more than six years from the launch of Bitcoin, it has become ev-ident that the decentralized transaction ledger functionality implemented through the blockchain technology can be used not only for cryptocur-rencies, but to register, confirm and transfer any kind of contract and property. In this work we analyze the most relevant functionalities and known issues of this technology, with the intent of pointing out the pos-sible behaviours that are not as efficient as they should when thinking with a broader outlook. Our analysis would be the starting point for the introduction of a new approach to blockchain creation and management, which will be the subject of a forthcoming paper. 1

Esha Ghosh, Olga Ohrimenko, Roberto Tamassia

No abstract is available for this record.

Vinod Vaikuntanathan, Prashant Nalini Vasudevan

We show a general connection between various types of statistical zero-knowledge (SZK) proof systems and (unconditionally secure) secret sharing schemes. Viewed through the SZK lens, we obtain several new results on secret-sharing: • Characterizations: We obtain an almost-characterization of access structures for which there are secret-sharing schemes with an efficient sharing algorithm (but not necessarily efficient reconstruction). In particular, we show that for every language L ∈ SZKL (the class of languages that have statistical zero knowledge proofs with log-space verifiers and simulators), a (monotonized) access structure associated with L has such a secret-sharing scheme. Conversely, we show that such secret-sharing schemes can only exist for languages in SZK. • Constructions: We show new constructions of secret-sharing schemes with both ef-ficient sharing and efficient reconstruction for access structures associated with lan-guages that are in P, but are not known to be in NC, namely Bounded-Degree Graph Isomorphism and constant-dimensional lattice problems. In particular, this gives us the first combinatorial access structure that is conjectured to be outside NC but has an efficient secret-sharing scheme. Previous such constructions (Beimel and Ishai; CCC 2001) were algebraic and number-theoretic in nature. • Limitations: We also show that universally-efficient secret-sharing schemes, where the complexity of computing the shares is a polynomial independent of the complexity of deciding the access structure, cannot exist for all (monotone languages in) P, unless there is a polynomial q such that P ⊆ DSPACE(q(n)). 1