Alessandro Chiesa, Michael A. Forbes, Tom Gur, Nicholas Spooner
Zero knowledge plays a central role in cryptography and complexity. The seminal work of Ben-Or et al. (STOC 1988) shows that zero knowledge can be achieved unconditionally for any language in NEXP , as long as one is willing to make a suitable physical assumption : if the provers are spatially isolated, then they can be assumed to be playing independent strategies. Quantum mechanics, however, tells us that this assumption is unrealistic, because spatially-isolated provers could share a quantum entangled state and realize a non-local correlated strategy. The MIP * model captures this setting. In this work, we study the following question: Does spatial isolation still suffice to unconditionally achieve zero knowledge even in the presence of quantum entanglement? We answer this question in the affirmative: we prove that every language in NEXP has a 2-prover zero knowledge interactive proof that is sound against entangled provers; that is, NEXP ⊆ ZK-MIP * . Our proof consists of constructing a zero knowledge interactive probabilistically checkable proof with a strong algebraic structure, and then lifting it to the MIP * model. This lifting relies on a new framework that builds on recent advances in low-degree testing against entangled strategies, and clearly separates classical and quantum tools. Our main technical contribution is the development of new algebraic techniques for obtaining unconditional zero knowledge; this includes a zero knowledge variant of the celebrated sumcheck protocol, a key building block in many probabilistic proof systems. A core component of our sumcheck protocol is a new algebraic commitment scheme, whose analysis relies on algebraic complexity theory.
In this work, we propose a novel approach, called Conflicts Check Protocol (CCP), which enables preventing potential attacks on bitcoin system. Based on the observation and discovery of a common symptom that many attacks may generate, an arbitration mechanism is proposed to determine the approval or abandon of certain transactions involved in confliction. Experimental results verified our statistical assumption and proved that the CCP is robust in handling many transactions in confliction scenarios and can significantly enhance the security of the current bitcoin systems. Unlike many of the existing efforts, this work examines the security issue of bitcoin from a new perspective, which can be extended further to a much larger scope of attack analysis and prevention.
Blockchain-based distributed computing platforms enable the trusted execution\nof computation - defined in the form of smart contracts - without trusted\nagents. Smart contracts are envisioned to have a variety of applications,\nranging from financial to IoT asset tracking. Unfortunately, the development of\nsmart contracts has proven to be extremely error prone. In practice, contracts\nare riddled with security vulnerabilities comprising a critical issue since\nbugs are by design non-fixable and contracts may handle financial assets of\nsignificant value. To facilitate the development of secure smart contracts, we\nhave created the FSolidM framework, which allows developers to define contracts\nas finite state machines (FSMs) with rigorous and clear semantics. FSolidM\nprovides an easy-to-use graphical editor for specifying FSMs, a code generator\nfor creating Ethereum smart contracts, and a set of plugins that developers may\nadd to their FSMs to enhance security and functionality.\n
Since 2004, different research was handling the challenges in the centralized voting systems, e-voting protocols and recently the decentralized voting. So electronic voting puts forward some difficulties regarding the voter anonymity, the secure casting of the votes and to prevent the voting process from frauding. The Decentralized property of the technology called "blockchain" could have the solution for many of the challenges in voting research area and brings a new secure mechanism of safe and transparent voting. In this paper, a broad comparison between ongoing voting systems has studied by analyzing their structure and the drawbacks that should consider in future to improve the whole election process from keeping the privacy of the voter, casting a vote with the possibility to check if it was counted correctly to publishing the results. The result of the paper will give a new approach to extend the target of the election from small scale to large scale despite the fact of Ethereum limitation which can cast on the blockchain just five votes per minute. The primary challenge is to find an answer for this question: "How to balance between voter privacy and transparency without breaking the important rule where the voter can proof for a specific candidate that he voted for him in a bribe situation?".
Alberto Sonnino, Mustafa Al-Bassam, Shehar Bano, Sarah Meiklejohn · 5 authors
Coconut is a novel selective disclosure credential scheme supporting distributed threshold issuance, public and private attributes, re-randomization, and multiple unlinkable selective attribute revelations. Coconut integrates with blockchains to ensure confidentiality, authenticity and availability even when a subset of credential issuing authorities are malicious or offline. We implement and evaluate a generic Coconut smart contract library for Chainspace and Ethereum; and present three applications related to anonymous payments, electronic petitions, and distribution of proxies for censorship resistance. Coconut uses short and computationally efficient credentials, and our evaluation shows that most Coconut cryptographic primitives take just a few milliseconds on average, with verification taking the longest time (10 milliseconds).
Abstract A functional credential allows a user to anonymously prove possession of a set of attributes that fulfills a certain policy. The policies are arbitrary polynomially computable predicates that are evaluated over arbitrary attributes. The key feature of this primitive is the delegation of verification to third parties, called designated verifiers. The delegation protects the privacy of the policy : A designated verifier can verify that a user satisfies a certain policy without learning anything about the policy itself. We illustrate the usefulness of this property in different applications, including outsourced databases with access control. We present a new framework to construct functional credentials that does not require (non-interactive) zero-knowledge proofs. This is important in settings where the statements are complex and thus the resulting zero-knowledge proofs are not efficient. Our construction is based on any predicate encryption scheme and the security relies on standard assumptions. A complexity analysis and an experimental evaluation confirm the practicality of our approach.
This paper investigates a critical access control issue in the Internet of Things (IoT). In particular, we propose a smart contract-based framework, which consists of multiple access control contracts (ACCs), one judge contract (JC), and one register contract (RC), to achieve distributed and trustworthy access control for IoT systems. Each ACC provides one access control method for a subject-object pair, and implements both static access right validation based on predefined policies and dynamic access right validation by checking the behavior of the subject. The JC implements a misbehavior-judging method to facilitate the dynamic validation of the ACCs by receiving misbehavior reports from the ACCs, judging the misbehavior and returning the corresponding penalty. The RC registers the information of the access control and misbehavior-judging methods as well as their smart contracts, and also provides functions (e.g., register, update, and delete) to manage these methods. To demonstrate the application of the framework, we provide a case study in an IoT system with one desktop computer, one laptop and two Raspberry Pi single-board computers, where the ACCs, JC, and RC are implemented based on the Ethereum smart contract platform to achieve the access control.
The Internet pervades many aspects of modern life offering up seemingly boundless opportunities to connect, inform and be informed. As the range and number of sources for information online explode, how people go about selecting and interpreting information has become a pertinent area for study, not least in the recent light of the prevalence of fake-news—as people are well known to act upon information they believe to be trustworthy. Where the decision to act incurs risk, an inability to accurately select and assess the credibility of information presents a challenge. <br/><br/>This extended abstract summarizes findings from a study of 57 Bitcoin users. Our analysis shows that this self-identifying technical and expert community was not significantly influenced by confirmation bias (a facet of fake-news). However, the same users also failed to demonstrate a true reliance upon the facts contained in news articles, often deferring trust to the source of the news which could still render them susceptible to fake-news, and, in turn, place their speculation of the crypto-currency at risk.
Existing Byzantine fault tolerance (BFT) protocols face significant challenges in the consortium blockchain scenario. On the one hand, we can make little assumptions about the reliability and security of the underlying Internet. On the other hand, the applications on consortium blockchains demand a system as scalable as the Bit-coin but providing much higher performance, as well as provable safety. We present a new BFT protocol, Gosig, that combines crypto-based secret leader selection and multi-round voting in the protocol layer with implementation layer optimizations such as gossip-based message propagation. In particular, Gosig guarantees safety even in a network fully controlled by adversaries, while providing provable liveness with easy-to-achieve network connectivity assumption. On a wide area testbed consisting of 140 Amazon EC2 servers spanning 14 cities on five continents, we show that Gosig can achieve over 4,000 transactions per second with less than 1 minute transaction confirmation time.
Jia Liu, Tibor Jager, Saqib A. Kakvi, Bogdan Warinschi
Time-lock encryption is a method to encrypt a message such that it can only be decrypted after a certain deadline has passed. We propose a novel time-lock encryption scheme, whose main advantage over prior constructions is that even receivers with relatively weak computational resources should immediately be able to decrypt after the deadline, without any interaction with the sender, other receivers, or a trusted third party. We build our time-lock encryption on top of the new concept of computational reference clocks and an extractable witness encryption scheme. We explain how to construct a computational reference clock based on Bitcoin. We show how to achieve constant level of multilinearity for witness encryption by using SNARKs. We propose a new construction of a witness encryption scheme which is of independent interest: our scheme, based on Subset-Sum , achieves extractable security without relying on obfuscation. The scheme employs multilinear maps of arbitrary order and is independent of the implementations of multilinear maps.
Elli Androulaki, Artem Barger, Vita Bortnikov, Christian Cachin · 21 authors
Fabric is a modular and extensible open-source system for deploying and operating permissioned blockchains and one of the Hyperledger projects hosted by the Linux Foundation (www.hyperledger.org). Fabric is the first truly extensible blockchain system for running distributed applications. It supports modular consensus protocols, which allows the system to be tailored to particular use cases and trust models. Fabric is also the first blockchain system that runs distributed applications written in standard, general-purpose programming languages, without systemic dependency on a native cryptocurrency. This stands in sharp contrast to existing blockchain platforms that require "smart-contracts" to be written in domain-specific languages or rely on a cryptocurrency. Fabric realizes the permissioned model using a portable notion of membership, which may be integrated with industry-standard identity management. To support such flexibility, Fabric introduces an entirely novel blockchain design and revamps the way blockchains cope with non-determinism, resource exhaustion, and performance attacks. This paper describes Fabric, its architecture, the rationale behind various design decisions, its most prominent implementation aspects, as well as its distributed application programming model. We further evaluate Fabric by implementing and benchmarking a Bitcoin-inspired digital currency. We show that Fabric achieves end-to-end throughput of more than 3500 transactions per second in certain popular deployment configurations, with sub-second latency, scaling well to over 100 peers.
This paper investigates the power of quantum statistical zero knowledge interactive proof systems in the relativized setting. We prove the existence of an oracle relative to which quantum statistical zero-knowledge does not contain UP intersect coUP, and we prove that quantum statistical zero knowledge does not contain UP relative to a random oracle with probability 1. Our proofs of these statements rely on a bound on output state discrimination for relativized quantum circuits based on the quantum adversary method of Ambainis, following a technique similar to one used by Ben-David and Kothari to prove limitations on a query complexity variant of quantum statistical zero-knowledge.
As we observe a trend towards the recentralisation of the Internet, this paper raises the question of guaranteeing an everlasting decentralisation. We introduce the properties of strong and soft uncentralisability in order to describe systems in which all authorities can be untrusted at any time without affecting the system. We link the soft uncentralisability to another property called perfect forkability. Using that knowledge, we introduce a new cryptographic primitive called uncentralisable ledger and study its properties. We use those properties to analyse what an uncentralisable ledger may offer to classic electronic voting systems and how it opens up the realm of possibilities for completely new voting mechanisms. We review a list of selected projects that implement voting systems using blockchain technol- ogy. We then conclude that the true revolutionary feature enabled by uncentralisable ledgers is a self-sovereign and distributed identity provider.
In multi-prover interactive proofs (MIPs), the verifier can provide non-local resources for the provers intrinsically. In most cases, this is undesirable. Existing proofs of soundness do not account for the verifier's non-local potential. We show that this may be a problem for many MIPs. We provide a solution by constructing a generalization of the MIP model, of which standard MIPs are a special case. This new model accounts for both the prover and the verifier's non-local correlations. A new property of multi-prover zero-knowledge naturally emerges as a result.
LEO constellation has received intensive research attention in the field of satellite communication. The existing centralized authentication protocols traditionally used for MEO/GEO satellite networks cannot accommodate LEO satellites with frequent user connection switching. This paper proposes a fast and efficient access verification protocol named BAVP by combining identity-based encryption and blockchain technology. Two different key management schemes with IBE and blockchain, respectively, are investigated, which further enhance the authentication reliability and efficiency in LEO constellation. Experiments on OPNET simulation platform evaluate and demonstrate the effectiveness, reliability, and fast-switching efficiency of the proposed protocol. For LEO networks, BAVP surpasses the well-known existing solutions with significant advantages in both performance and scalability which are supported by theoretical analysis and simulation results.
A proof system is a protocol between a prover and a verifier over a common input in which an honest prover convinces the verifier of the validity of true statements. Motivated by the success of decentralized cryptocurrencies, exemplified by Bitcoin, the focus of this thesis will be on proof systems which found applications in some sustainable alternatives to Bitcoin, such as the Spacemint and Chia cryptocurrencies. In particular, we focus on proofs of space and proofs of sequential work. Proofs of space (PoSpace) were suggested as more ecological, economical, and egalitarian alternative to the energy-wasteful proof-of-work mining of Bitcoin. However, the state-of-the-art constructions of PoSpace are based on sophisticated graph pebbling lower bounds, and are therefore complex. Moreover, when these PoSpace are used in cryptocur- rencies like Spacemint, miners can only start mining after ensuring that a commitment to their space is already added in a special transaction to the blockchain. Proofs of sequential work (PoSW) are proof systems in which a prover, upon receiving a statement χ and a time parameter T, computes a proof which convinces the verifier that T time units had passed since χ was received. Whereas Spacemint assumes synchrony to retain some interesting Bitcoin dynamics, Chia requires PoSW with unique proofs, i.e., PoSW in which it is hard to come up with more than one accepting proof for any true statement. In this thesis we construct simple and practically-efficient PoSpace and PoSW. When using our PoSpace in cryptocurrencies, miners can start mining on the fly, like in Bitcoin, and unlike current constructions of PoSW, which either achieve efficient verification of sequential work, or faster-than-recomputing verification of correctness of proofs, but not both at the same time, ours achieve the best of these two worlds.
Virtual machine (VM) measurements data in IaaS cloud play a crucial role in integrity evaluation and decision making. Hence, the secure storage for these data has attracted more attention recently. This paper proposes a novel approach, named Mchain, to enhance the integrity and controllability of the secure storage. Especially, to enhance the integrity, a two-layer blockchain network is introduced. In the first layer, after the production, the data packages are first verified by leveraging a correspondence between a package and a policy, and a one-to-one relation among a VM, a user, and a node. After that, we propose a consensus achievement algorithm to construct a semi-finished block on a candidate block arranged by data packages. Meanwhile, the semi-finished block is distributed to all nodes, which can provide a certain integrity. In the second-layer, tamper-resistant metadata is generated by performing PoW tasks on the semi-finished block, resulting in strong integrity. Further, to enhance the controllability, a revisable user-defined policy-based encryption method with KP-ABE is proposed. It helps to flexibly control the scope of authorized verifiers. The experimental results on six scenarios with simulated data set show that the proposed approach is appealing in integrity and controllability, and the time overhead of data storage.
Digital identities and credentials are gradually replacing physical documents, as they can be verified with more accuracy and efficiency. Since online privacy is becoming more crucial than ever, it is essential to preserve the privacy of individuals whenever possible. Therefore, anonymous attestation of digital credentials should be feasible, where provers can selectively disclose attributes and create abstractions over attributes in their credential, in order to solely disclose the minimum amount of information required to complete the goal of verification.<br/><br/>Many schemes in the field of attribute-based credentials consider a single root authority issuing credentials to provers. This is coherent to the traditional way of the issuance of credentials since the process of producing physical documents is costly to distribute to multiple issuers. Digital identities provide the opportunity for authorities to distribute credential issuance rights (consecutively) to smaller entrusted entities.<br/><br/>To the best of our knowledge, we propose the first protocol which combines both anonymous attestation with attribute-based credentials and the delegation of selective signing rights for the issuance of these credentials. Root authorities could delegate signing rights for selective attributes consecutively to trustees, which are able to create anonymous attribute-based credentials with the acquired attributes for provers. Verifiers are able to verify presentation tokens with solely the public key of the root authority, without gaining knowledge about the identities of the prover and intermediate delegators. We introduce three adapted signature schemes based on existing work in order to realize a concrete instantiation of the protocol. Anonymity is achieved by incorporating Schnorr's zero-knowledge proof of knowledge with bilinear pairings to efficiently prove the correctness of presentation tokens.<br/><br/>We realized a prototype of our concrete instantiation and optimized the verification algorithm in order to achieve optimal pairing performance. Complexity analysis of the protocol shows improvement in efficiency by aggregating attribute signatures throughout signing right delegation. Experimental results demonstrate a degree of practical feasibility for the verification of presentation tokens on commodity hardware within the challenging public transportation access control time bound of 300 ms.<br/>
Recently we presented a single-party cryptographic timestamping mechanism based on proof-of-sequential-work, which we proved secure in the universal composability framework [16]. This paper describes this construction and its security claims and uses it to construct a multi-party permissioned blockchain protocol and show that it achieves an immutability notion. Finally we discuss applications of this protocol, including unpermissioned blockchains, and how these may benefit.