Blockchain Papers

Craig Gentry, Jens Groth, Yuval Ishai, Chris Peikert · 6 authors

No abstract is available for this record.

Sankita Patel, Mitali Sonar, Devesh C. Jinwala

In this article, the authors propose an approach for privacy preserving distributed clustering that assumes malicious model. In the literature, there do exist, numerous approaches that assume a semi honest model. However, such an assumption is, at best, reasonable in experimentations; rarely true in real world. Hence, it is essential to investigate approaches for privacy preservation using a malicious model. The authors use the Pederson's Verifiable Secret Sharing scheme ensuring the privacy using additively homomorphic secret sharing scheme. The trustworthiness of the data is assured using homomorphic commitments in Pederson's scheme. In addition, the authors propose two variants of the proposed approach - one for horizontally partitioned dataset and the other for vertically partitioned dataset. The experimental results show that the proposed approach is scalable in terms of dataset size. The authors also carry out experimentations to highlight the effectiveness of Verifiable Secret Sharing scheme against Zero Knowledge Proof scheme.

Shinsuke Tamura, Shuji Taniguchi

A scheme for anonymous tag based anonymous credentials is enhanced. Different from existing zero knowledge proof based anonymous credential schemes that require numbers of challenges and responses between verifiers and credential holders, the anonymous tag based scheme requires only small number of challenges and responses between verifiers and credential holders. This is because the scheme in this paper can be easily made sound even in environments where verifiers also may behave dishonestly. However, the original scheme has probabilistic features, i.e. verifiers must generate dummy fake challenges; therefore overheads for managing anonymous systems cannot be reduced to the minimum. The enhanced anonymous tag based scheme excludes these probabilistic features from interactions between verifiers and credential holders. The scheme also corrects several design errors included in the original scheme.

Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti

In [AGP14] Ananth et al. showed that continual leakage-resilient non-transferable interactive proofs exist when a leak-free input-encoding phase is allowed and a common reference string is available. They left open the problem of removing the need of a common reference string. In [BGJK12] Boyle et al. showed that for some interesting functionalities continual leakage-resilient secure computation is possible when leak-free interactive preprocessing and input-encoding phases are allowed. They left open the problem of removing the interactive pre-processing. In this work we study the above questions. Our main contribution shows that leakage-resilient black-box zero-knowledge is impossible when relying on a leak-free input-encoding phase only (i.e., without CRS/preprocessing). Additionally, we also show that leakage-resilient multi-party computation for all functionalities is impossible (regardless of the number of players assuming just one corrupted player) when relying only on a leak-free input-encoding phase (i.e., without CRS/preprocessing). Our results are achieved by extending a technique of [NVZ13] to prove lower bounds for leakage-resilient security. Indeed as in [NVZ13] we use leakage queries to run an execution of a communication-efficient protocol in the head of the adversary. Moreover, to defeat the black-box simulator we connect the above technique for leakage resilience to security against reset attacks.

Nir Bitansky, Omer Paneth

We present new constructions of two-message and one-message witness-indistinguishable proofs (ZAPs and NIWIs). This includes: • ZAPs (or, equivalently, non-interactive zero-knowledge in the common random string model) from indistinguishability obfuscation and one-way functions. • NIWIs from indistinguishability obfuscation and one-way permutations. The previous construction of ZAPs [Dwork and Naor, FOCS 00] was based on trapdoor permutations. The two previous NIWI constructions were based either on ZAPs and a derandomization-type complexity assumption [Barak, Ong, and Vadhan CRYPTO 03], or on a specific number theoretic assumption in bilinear groups [Groth, Sahai, and Ostrovsky, CRYPTO 06]. ∗MIT. Email: nirbitan@csail.mit.edu. Part of this work was done while at Tel Aviv University. †Boston University. Email: omer@bu.edu. Supported by the Simons award for graduate students in theoretical computer science and an NSF Algorithmic foundations grant 1218461.

Sebastian Feld, Mirco Schönfeld, Martin Werner

Bitcoin has become increasingly important in recent years. The exchange rate raised from $14 in January 2013 up to $240 in April 2013 and even $900 in early 2014. In this paper, we present novel insights about Bitcoin's peer-to-peer (P2P) network with a special focus on its distribution among distinct autonomous systems. We traversed Bitcoin's P2P network in a protocol-compliant manner and collected information about the network size, the number of clients, and the network distribution among autonomous systems. Our findings lead to conclusions about the resilience of the Bitcoin ecosystem, the unambiguousness of the blockchain in use, and the propagation and verification of transaction blocks.

Conner Fromknecht, D. Velicanu, Sophia Yakoubov

Public key infrastructures (PKIs) enable users to look up and verify one another’s public keys based on identities. Current approaches to PKIs are vulnerable because they do not offer sufficiently strong guarantees of identity retention; that is, they do not effectively prevent one user from registering a public key under another’s already-registered identity. In this paper, we leverage the consistency guarantees provided by cryptocurrencies such as Bitcoin and Namecoin to build a PKI that ensures identity retention. Our system, called Certcoin, has no central authority and thus requires the use of secure distributed dictionary data structures to provide efficient support for key lookup. 1

Shashank Agrawal, Shweta Agrawal, Shweta Agrawal, Shweta Agrawal · 5 authors

We provide a new framework of cryptographic agents that unifies various modern “cryp- tographic objects” — identity-based encryption, fully-homomorphic encryption, functional encryption, and various forms of obfuscation – similar to how the Universal Composition framework unifies various multi-party computation tasks like commitment, coin-tossing and zero-knowledge proofs. These cryptographic objects can all be cleanly modeled as “schemata” in our framework. Highlights of our framework include the following: • We use a new indistinguishability preserving (IND-PRE) definition of security that in- terpolates indistinguishability and simulation style definitions, which (often) sidesteps the known impossibilities for the latter. IND-PRE-security is parameterized by the choice of the “test” family, such that by choosing different test families, one can obtain different levels of security for the same primitive (including various standard definitions in the literature). • We present a notion of reduction from one schema to another and a powerful composition theorem with respect to IND-PRE security. We show that obfuscation is a “complete” schema under this notion, under standard cryptographic assumptions. We also provide a stricter notion of reduction (∆-reduction) that composes even when security is only with respect to certain restricted test families of importance. • Last but not the least, our framework can be used to model abstractions like the generic group model and the random oracle model, letting one translate a general class of constructions in these heuristic models to constructions based on standard model assumptions. We also illustrate how our framework can be applied to specific primitives like obfus- cation and functional encryption. We relate our definitions to existing definitions and also give new constructions and reductions between different primitives. ∗University of Illinois, Urbana-Champaign. Email: sagrawl2@illinois.edu. †Indian Institute of Technology, Delhi. Email: shweta.a@gmail.com. ‡University of Illinois, Urbana-Champaign. Email: mmp@illinois.edu.

Handan Kılınç, Alptekın Küpçü

Secure two-party computation cannot be fair against malicious adversaries, unless a trusted third party (TTP) or a gradual-release type super-constant round protocol is employed. Existing optimistic fair two-party computation protocols with constant rounds are either too costly to arbitrate (e.g., the TTP may need to re-do almost the whole computation), or require the use of electronic payments. Furthermore, most of the existing solutions were proven secure and fair via a partial simulation, which, we show, may lead to insecurity overall. We propose a new framework for fair and secure two-party computation that can be applied on top of any secure two party computation protocol based on Yao’s garbled circuits and zero-knowledge proofs. We show that our fairness overhead is minimal, compared to all known existing work. Furthermore, our protocol is fair even in terms of the work performed by Alice and Bob. We also prove our protocol is fair and secure simultaneously, through one simulator, which guarantees that our fairness extensions do not leak any private information. Lastly, we ensure that the TTP never learns the inputs or outputs of the computation. Therefore, even if the TTP becomes malicious and causes unfairness by colluding with one party, the security of the underlying protocol is still preserved.

Arnau Vives-Guasch, M. Magdalena Payeras–Capellà, Macià Mut–Puigserver, Jordi Castellà‐Roca · 5 authors

No abstract is available for this record.

Toru Nakanishi, Nomura Tomoya, Nobuo Funabiki

In anonymous reputation systems, where after an interaction between anonymous users, one of the users evaluates the peer by giving a rating. Ratings for a user are accumulated, which becomes the reputation of the user. By using the reputation, we can know the reliability of an anonymous user. Previously, anonymous reputation systems have been proposed, using an anonymous e-cash scheme. However, in the e-cash-based systems, the bank grasps the accumulated reputations for all users, and the fluctuation of reputations. These are private information for users. Furthermore, the timing attack using the deposit times is possible, which makes the anonymity weak. In this paper, we propose an anonymous reputation system, where the reputations of users are secret for even the reputation manager such as the bank. Our approach is to adopt an anonymous credential certifying the accumulated reputation of a user. Initially a user registers with the reputation manager, and is issued an initial certificate. After each interaction with a rater, the user as the ratee obtains an updated certificate certifying the previous reputation summed up by the current rating. The update protocol is based on the zero-knowledge proofs, and thus the reputations are secret for the reputation manager. On the other hand, due to the certificate, the user cannot maliciously alter his reputation.

Huan Meng

Bitcoin is a digital currency which is based on P2P network and open source software. It is avirtual currency without any control by any centralized organization. New Bitcoins are issuedby lots of specified algorithms. The whole Bitcoin network utilizes the distributed database toverify and record all the transactions through the nodes in the P2P network in which thedouble spending is prevented. No person or organization is able to control Bitcoin based on adecentralized P2P network and algorithm. The cryptographic functions of Bitcoin are designedto allow only the real Bitcoin owner to pay and transfer, and ensure the anonymity andmarketability.The purpose of this thesis is to analyze the security architecture and services for the Bitcoin system and describe of all the features and infrastructures of the whole Bitcoin network. A whole establishment demo including wallet client, mining server with GUI and mining client is implemented. Further improvement will be suggested and recommended for the system

Georg Neugebauer, Lucas Brutschy, Ulrike Meyer, Susanne Wetzel

No abstract is available for this record.

Emmanuelle Anceaume, Gilles Guette, Paul Lajoie-Mazenc, Thomas Sirvent · 5 authors

No abstract is available for this record.

Rafail Ostrovsky, Alessandra Scafuro, Muthuramakrishnan Venkitasubramaniam

We show how to construct a O(1)-round resettably-sound zero-knowledge argument of knowledge based on one-way functions where additionally the construction and proof of se-curity is black-box. Zero-knowledge proofs (ZK) are fundamental cryptographic constructs used in numerous applications. Formalized using a “simulation ” paradigm, ZK requires that for every malicious verifier there exists a “simulator ” that can indistinguishably reproduce the view of the verifier in an interaction with the honest prover. Resettable-soundness introduced by Barak, Goldreich, Goldwasser and Lindell (FOCS 01) additionally demands the soundness property to hold even if the malicious prover is allowed to “reset ” and “restart ” the verifier. Using the breakthrough non-black-box technique of Barak (FOCS 01) they also provided a constant-round construction of a resettably-sound ZK argument relying on the existence of collision-resistance hash-functions. This construction and subsequent constructions all rely on the underlying cryptographic primitive in a non black-box way. Recently, Goyal, Ostro-vsky, Scafuro and Visconti (STOC 14) showed how to extend the Barak’s technique to obtain a construction and proof of security that relies on the collision-resistant hash-function in a black-box manner while still having a non black-box simulator. Such a construction is referred to as semi black-box. From the work of Chung, Pass and Seth (STOC 13) we know that the minimal assumption required to construct resettably-sound ZK argument is the existence of one-way functions. In this work we close the gap between (semi) black-box and non black-box constructions by showing a black-box (round-efficient) resettably-sound argument relying on one-way functions only. 1

Benoît Libert, Marc Jóye, Moti Yung, Thomas Peters

To gain strong confidence in the security of a public-key scheme, it is most desirable for the security proof to feature a tight reduction between the adversary and the algorithm solving the underlying hard problem. Recently, Chen and Wee (Crypto’13) described the first Identity-Based Encryption scheme with almost tight security under a standard assumption. Here, “almost tight” means that the security reduction only loses a factor O(λ) —where λ is the security parameter— instead of a factor proportional to the number of adversarial queries. Chen and Wee also gave the shortest signatures whose security almost tightly relates to a simple assumption in the standard model. Also recently, Hofheinz and Jager (Crypto ’12) constructed the first CCA-secure public-key encryption scheme in the multi-user setting with tight security. These constructions give schemes that are significantly less efficient in length (and thus, processing) when compared with the earlier schemes with loose reductions in their proof of security. Hofheinz and Jager’s scheme has a ciphertext of a few hundreds of group elements, and they left open the problem of finding truly efficient constructions. Likewise, Chen and Wee’s signatures and IBE schemes are somewhat less efficient than previous constructions with loose reductions from the same assumptions. In this paper, we consider space-efficient schemes with security almost tightly related to standard assumptions. We construct an efficient CCA-secure public-key encryption scheme whose chosen-ciphertext security in the multi-challenge, multi-user setting almost tightly relates to the DLIN assumption (in the standard model). Quite remarkably, the ciphertext size decreases to 69 group elements under the DLIN assumption whereas the best previous solution required about 400 group elements. Our scheme is obtained by taking advantage of a new almost tightly secure signature scheme (in the standard model) which is based on the recent concise proofs of linear subspace membership in the quasi-adaptive non-interactive zero-knowledge setting (QA-NIZK) defined by Jutla and Roy (Asiacrypt’13). Our signature scheme reduces the length of the previous such signatures (by Chen and Wee) by 37% under the Decision Linear assumption, by almost 50% under the K-LIN assumption, and it becomes only 3 group elements long under the Symmetric eXternal Diffie-Hellman assumption. Our signatures are obtained by carefully combining the proof technique of Chen and Wee and the above mentioned QA-NIZK proofs.

Nico Döttling, Daniel Kraschewski, Jörn Müller‐Quade, Tobias Nilges

Universally composable secure computation was assumed to require trusted setups, until it was realized that parties exchanging (untrusted) tamper-proof hardware tokens allow an alternative approach (Katz; EUROCRYPT 2007). This discovery initialized a line of research dealing with two different types of tokens. Using only a single stateful token, one can implement general statistically secure two-party computation (Dottling, Kraschewski, Muller-Quade; TCC 2011); though all security is lost if an adversarial token receiver manages to physically reset and rerun the token. Stateless tokens, which are secure by definition against any such resetting-attacks, however, do provably not suffice for statistically secure computation in general (Goyal, Ishai, Mahmoody, Sahai; CRYPTO 2010). We investigate the natural question of what is possible if an adversary can reset a token at most a bounded number of times (e.g., because each resetting attempt imposes a significant risk to trigger a self-destruction mechanism of the token). Somewhat surprisingly, our results come close to the known positive results with respect to non-resettable stateful tokens. In particular, we construct polynomially many instances of statistically secure and universally composable oblivious transfer, using only a constant number of tokens. Our techniques have some abstract similarities to previous solutions, which we grasp by defining a new security property for protocols that use oracle access. Additionally, we apply our techniques to zero-knowledge proofs and obtain a protocol that achieves the same properties as bounded-query zero-knowledge PCPs (Kilian, Petrank, Tardos; STOC 1997), even if a malicious prover may issue stateful PCP oracles.

Ran Canetti, Abhishek Jain, Omer Paneth

The traditional setting for concurrent zero knowledge considers a server that proves a statement in zero-knowledge to multiple clients in multiple concurrent sessions, where the server’s actions in a session are independent of all other sessions. Persiano and Visconti [ICALP 05] show how keeping a limited amount of global state across sessions allows the server to significantly reduce the overall complexity while retaining the ability to interact concurrently with an unbounded number of clients. Specifically, they show a protocol that has only slightly super-constant number of rounds; however the communication complexity in each session of their protocol depends on the number of other sessions and has no a-priori bound. This has the drawback that the client has no way to know in advance the amount of resources required for completing a session of the protocol up to the moment where the session is completed. We show a protocol that does not have this drawback. Specifically, in our protocol the client obtains a bound on the communication complexity of each session at the start of the session. Additionally the protocol is constant-rounds. Our protocol is fully concurrent, and assumes only collision-resistant hash functions. The proof requires considerably different techniques than those of Persiano and Visconti. Our main technical tool is an adaptation of the “committed-simulator ” technique of Deng et. al [FOCS 09]. 1

Ivan Damgård, Bernardo David, Irene Giacomelli, Jesper Buus Nielsen

We present a new compact verifiable secret sharing scheme, based on this we present the first construction of a homomorphic UC commitment scheme that requires only cheap symmetric cryptography, except for a small number of seed OTs. To commit to a k -bit string, the amortized communication cost is O ( k ) bits. Assuming a sufficiently efficient pseudorandom generator, the computational complexity is O ( k ) for the verifier and O ( k 1 + ε ) for the committer (where ε < 1 is a constant). In an alternative variant of the construction, all complexities are O ( k · polylog ( k )). Our commitment scheme extends to vectors over any finite field and is additively homomorphic. By sending one extra message, the prover can allow the verifier to also check multiplicative relations on committed strings, as well as verifying that committed vectors a , b satisfy a = φ ( b ) for a linear function φ . These properties allow us to non-interactively implement any one-sided functionality where only one party has input (this includes UC secure zero-knowledge proofs of knowledge). We also present a perfectly secure implementation of any multiparty functionality, based directly on our VSS. The communication required is proportional to a circuit implementing the functionality, up to a logarithmic factor. For a large natural class of circuits the overhead is even constant. We also improve earlier results by Ranellucci et al. on the amount of correlated randomness required for string commitments with individual opening of bits. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Sherman S. M. Chow, Matthew Franklin, Haibin Zhang

No abstract is available for this record.

Essam Ghadafi

Abstract. In this work, we first formalize the notion of dynamic group signatures with distributed traceability, where the capability to trace signatures is distributed among nmanagers without requiring any interaction. This ensures that only the participation of all tracing managers permits tracing a signature, which reduces the trust placed in a single tracing manager. The threshold variant follows easily from our definitions and constructions. Our model offers strong security requirements. Our second contribution is a generic construction for the notion which has a concurrent join protocol, meets strong security requirements, and offers efficient traceability, i.e. without requiring tracing managers to produce expensive zero-knowledge proofs for tracing correctness. To dispense with the expensive zero-knowledge proofs required in the tracing, we deploy a distributed tag-based encryption with public verifiability. Finally, we provide some concrete instantiations, which, to the best of our knowledge, are the first efficient provably secure realizations in the standard model simultaneously offering all the aforementioned properties. To realize our constructions efficiently, we construct an efficient distributed (and threshold) tag-based encryption scheme that works in the efficient Type-III asymmetric bilinear groups. Our distributed tag-based encryption scheme yields short ciphertexts (only 1280 bits at 128-bit security), and is secure under an existing variant of the standard decisional linear assumption. Our tag-based encryption scheme is of independent interest and is useful for many applications beyond the scope of this paper. As a special case of our distributed tag-based encryption scheme, we get an efficient tag-based encryption scheme in Type-III asymmetric bilinear groups that is secure in the standard model.

Jethro G. Beekman

Bitcoin supports complex transactions where the recipient of a transaction can be programmatically determined. Using these transactions, multi-party computation protocols that aim to ensure fairness among partici-pants have been designed. We present a Denial of Service attack against these protocols that results in a net loss for some or all of the honest parties involved, violating those fairness goals. 1

Esha Ghosh, Olga Ohrimenko, Roberto Tamassia

Given a list L with n elements, an order query on L asks whether a given element x2L precedes or follows another element y2 L. More generally, given a set of m elements from L, an order query asks for the set ordered according to the positions of the elements in L. We introduce two formal models for answering order queries on a list in a verifiable manner and in zero-knowledge. We also present efficient constructions for these models. Our first model, called zero-knowledge list (ZKL), generalizes membership queries on a set to order queries on a list in zero-knowledge. We present a construction of ZKL based on zero-knowledge sets and a homomorphic integer commitment scheme. Our second model, privacy-preserving authenticated list (PPAL), extends authenticated data structures by adding a zero-knowledge privacy requirement. In this model, a list is outsourced by a trusted owner to an untrusted cloud server, which answers order queries issued by clients. The server also returns a proof of the answer, which is verified by the client using a digest of the list obtained from the owner. PPAL supports the security properties of data integrity against a malicious server and privacy protection against a malicious client. Though PPAL can be implemented using our ZKL construction, this construction is not as efficient as desired in cloud applications. To this end, we present an efficient PPAL construction based on blinded bilinear accumulators and bilinear maps, which is provably secure and zero-knowledge (e.g., hiding even the size of the list). Our PPAL construction uses proofs of O(m) size and allows the client to verify a proof in O(m) time. The owner executes the setup in O(n) time and space. The server uses O(n) space to store the list and related authentication information, and takes O(min(m log n; n)) time to answer a query and generate a proof. Both our ZKL and PPAL constructions have one round of communication and are secure in the random oracle model. Finally, we show that our ZKL and PPAL frameworks can be extended to support fundamental statistical queries (including maximum, minimum, median, threshold and top-t elements) efficiently and in zero-knowledge.

Yehuda Lindell

In this short paper, we present a Fiat-Shamir type transform that takes any Sigma protocol for a relation R and outputs a non-interactive zero-knowledge proof (not of knowledge) for the associated language L R , in the common reference string model. As in the Fiat-Shamir transform, we use a hash function H. However, zero-knowledge is achieved under standard assumptions in the common reference string model (without any random oracle), and soundness is achieved in the non-programmable random oracle model. The concrete computational complexity of the transform is only slightly higher than the original Fiat-Shamir transform.