Besides attracting a billion dollar economy, Bitcoin revolutionized the field of digital currencies and influenced many adjacent areas. This also induced significant scientific interest. In this survey, we unroll and structure the manyfold results and research directions. We start by introducing the Bitcoin protocol and its building blocks. From there we continue to explore the design space by discussing existing contributions and results. In the process, we deduce the fundamental structures and insights at the core of the Bitcoin protocol and its applications. As we show and discuss, many key ideas are likewise applicable in various other fields, so that their impact reaches far beyond Bitcoin itself.
Ahmed E. Kosba, Andrew Miller, Elaine Shi, Zikai Alex Wen · 5 authors
Emerging smart contract systems over decentralized cryptocurrencies allow mutually distrustful parties to transact safely without trusted third parties. In the event of contractual breaches or aborts, the decentralized blockchain ensures that honest parties obtain commensurate compensation. Existing systems, however, lack transactional privacy. All transactions, including flow of money between pseudonyms and amount transacted, are exposed on the blockchain. We present Hawk, a decentralized smart contract system that does not store financial transactions in the clear on the blockchain, thus retaining transactional privacy from the public's view. A Hawk programmer can write a private smart contract in an intuitive manner without having to implement cryptography, and our compiler automatically generates an efficient cryptographic protocol where contractual parties interact with the blockchain, using cryptographic primitives such as zero-knowledge proofs. To formally define and reason about the security of our protocols, we are the first to formalize the blockchain model of cryptography. The formal modeling is of independent interest. We advocate the community to adopt such a formal model when designing applications atop decentralized blockchains.
In a periodic K-times anonymous authentication system, user can anonymously show credential at most K times in one time period. In the next time period, user can automatically get another K-times authentication permission. If a user tries to show credential beyond K times in one time period, anyone can identify the dishonest user (the violator). But identifying violators is not enough for some systems, where it is also desirable to revoke violators' credentials for preventing them from abusing the anonymous property again. However, the problem of revoking credential without trusted third party has not been solved efficiently and practically. To solve it, we present an efficient scheme with efficient revocation of violator's credential. In fact, our method also solves an interesting problem-leaking information in a statistic zero-knowledge way, so our solution to the revocation problem outperforms all prior solutions. For achieving it, we use the special zero-knowledge proof with special information leak for revoking the violator's credential, but it can still be proven to be perfect statistic zero knowledge for guaranteeing the honest user's anonymity. Comparing with existing schemes, our scheme is efficient, and moreover, our method of revoking violator's credential is more practical with the least additional costs.
Christian Decker, Jochen Seidel, Roger Wattenhofer
The Bitcoin system only provides eventual consistency. For everyday life, the time to confirm a Bitcoin transaction is prohibitively slow. In this paper we propose a new system, built on the Bitcoin blockchain, which enables strong consistency. Our system, PeerCensus, acts as a certification authority, manages peer identities in a peer-to-peer network, and ultimately enhances Bitcoin and similar systems with strong consistency. Our extensive analysis shows that PeerCensus is in a secure state with high probability. We also show how Discoin, a Bitcoin variant that decouples block creation and transaction confirmation, can be built on top of PeerCensus, enabling real-time payments. Unlike Bitcoin, once transactions in Discoin are committed, they stay committed.
Recent technological advances have given rise to the popularity and success of cloud. This new paradigm is gaining an expanding interest, since it provides cost efficient architectures that support the transmission, storage, and intensive computing of data. However, these promising storage services bring many challenging design issues, considerably due to the loss of data control. These challenges, namely data confidentiality and data integrity, have significant influence on the security and performances of the cloud system. This thesis aims at overcoming this trade-off, while considering two data security concerns. On one hand, we focus on data confidentiality preservation which becomes more complex with flexible data sharing among a dynamic group of users. It requires the secrecy of outsourced data and an efficient sharing of decrypting keys between different authorized users. For this purpose, we, first, proposed a new method relying on the use of ID-Based Cryptography (IBC), where each client acts as a Private Key Generator (PKG). That is, he generates his own public elements and derives his corresponding private key using a secret. Thanks to IBC properties, this contribution is shown to support data privacy and confidentiality, and to be resistant to unauthorized access to data during the sharing process, while considering two realistic threat models, namely an honest but curious server and a malicious user adversary. Second, we define CloudaSec, a public key based solution, which proposes the separation of subscription-based key management and confidentiality-oriented asymmetric encryption policies. That is, CloudaSec enables flexible and scalable deployment of the solution as well as strong security guarantees for outsourced data in cloud servers. Experimental results, under OpenStack Swift, have proven the efficiency of CloudaSec in scalable data sharing, while considering the impact of the cryptographic operations at the client side. On the other hand, we address the Proof of Data Possession (PDP) concern. In fact, the cloud customer should have an efficient way to perform periodical remote integrity verifications, without keeping the data locally, following three substantial aspects : security level, public verifiability, and performance. This concern is magnified by the client’s constrained storage and computation capabilities and the large size of outsourced data. In order to fulfill this security requirement, we first define a new zero-knowledge PDP proto- col that provides deterministic integrity verification guarantees, relying on the uniqueness of the Euclidean Division. These guarantees are considered as interesting, compared to several proposed schemes, presenting probabilistic approaches. Then, we propose SHoPS, a Set-Homomorphic Proof of Data Possession scheme, supporting the 3 levels of data verification. SHoPS enables the cloud client not only to obtain a proof of possession from the remote server, but also to verify that a given data file is distributed across multiple storage devices to achieve a certain desired level of fault tolerance. Indeed, we present the set homomorphism property, which extends malleability to set operations properties, such as union, intersection and inclusion. SHoPS presents high security level and low processing complexity. For instance, SHoPS saves energy within the cloud provider by distributing the computation over multiple nodes. Each node provides proofs of local data block sets. This is to make applicable, a resulting proof over sets of data blocks, satisfying several needs, such as, proofs aggregation
Iddo Bentov, Charles Lee, Alex Mizrahi, Meni Rosenfeld
We propose a new protocol for a cryptocurrency, that builds upon the Bitcoin protocol by combining its Proof of Work component with a Proof of Stake type of system. Our Proof of Activity protocol offers good security against possibly practical attacks on Bitcoin, and has a relatively low penalty in terms of network communication and storage space.
This paper presents a concept for a new method to provide the authentication and confidentiality using zero knowledge protocol and key exchange. Zero knowledge proof protocol is a essential component of cryptography, which in recent years has increasingly popular amongst scholars. Its applications have widened and it has made inroads in several areas including mathematics and network safety and so on. This simple protocol based on zero knowledge proof by which user can prove to the authentication server that he has the password without having to send the password to the server either clear text or in encrypted format. This is a protocol in which the data learned by one party (i.e., The inspector) allow him/her to verify that a statement is true but does not reveal any additional information. In this paper we first discuss about zero-knowledge protocol proof system of knowledge and also key exchange between users and which then is modified into an authentication scheme with secret key exchange for confidentiality. The whole protocol involves mutual identification of two users, exchange of a random common secret key or session key for the verification of public keys.
Digital signature schemes are a foundational cryptographic building block in certification and the projection of trust. Based on a signature scheme on committed graphs, we propose a framework of certification and proof methods to sign topology graphs and to prove properties of their certificates in zero-knowledge. This framework allows an issuer, such as an auditing system, to sign the topology representation of an infrastructure. The prover, such as an infrastructure provider, can then convince a verifier of topology properties including connectivity and isolation without disclosing the blueprint of the topology itself. By that, we can certify the structure of critical systems while still maintaining confidentiality. We offer zero-knowledge proofs of knowledge for a general specification language of security goals for virtualized infrastructures such that high-level security goals can be proven over topology certificates. We offer an efficient and practical construction, built upon the Camenisch-Lysyanskaya signature scheme, honest-verifier proofs and the strong RSA assumption.
Jelle van den Hooff, M. Frans Kaashoek, Nickolai Zeldovich
VerSum allows lightweight clients to outsource expensive computations over large and frequently changing data structures, such as the Bitcoin or Namecoin blockchains, or a Certificate Transparency log. VerSum clients ensure that the output is correct by comparing the outputs from multiple servers. VerSum assumes that at least one server is honest, and crucially, when servers disagree, VerSum uses an efficient conflict resolution protocol to determine which server(s) made a mistake and thus obtain the correct output.
Most current digital currency schemes and associated ledgers are either centralized or completely distributed similar to the design adopted by Bitcoin. Centralized schemes enable accountability, but leave the privacy of users' identities and transactions in the hands of one organization. Distributed schemes can ensure better privacy but provide little accountability. In this paper we design a privacy-preserving proactively-secure distributed ledger and associated transaction protocols that can be used to implement an accountable digital currency that inherits the ledger's privacy and security features. One of the main technical challenges that we address is dealing with the increase in ledger size over time, an unavoidable aspect as the currency spreads and the ledger is required to be maintained for a long time in the future. We accomplish this by reducing the distributed (secret-shared) storage footprint and the required bandwidth and computation for proactively refreshing the ledger to ensure long-term confidentiality and security. In the full version, we provide performance analysis of some of the subprotocols to estimate the time required to perform transactions and the proactive refreshing of the ledger.
We study a model of incentivizing correct computations in a variety of cryptographic tasks. For each of these tasks we propose a formal model and design protocols satisfying our model's constraints in a hybrid model where parties have access to special ideal functionalities that enable monetary transactions. We summarize our results:
Fine-grained energy usage data made available by recent advancement of smart grid technologies benefit not only electricity utility companies but also customers. Nowadays customers can utilize various services by sharing their own energy usage data. At the same time, such utilization and sharing of electricity usage data with a variety of third party service providers may cause privacy concerns. In this paper, we discuss a privacy preserving mechanism for customers' sharing of energy usage data with third parties using non-interactive zero-knowledge proof systems. Under our scheme, a customer can, for each data sharing and disclosure, add noise to her electricity usage data without entirely losing verifiability of data authenticity, thereby retaining utility of data at third parties even for billing or accounting purposes.
Danushka Jayasinghe, Konstantinos Markantonakis, Keith Mayes
Fair-exchange and anonymity are two important attributes in e-commerce. It is much more difficult to expect fairness in e-commerce transactions using Bit coin due to anonymity and transaction irreversibility. Genuine consumers and merchants who would like to make and receive payments using Bit coin may be reluctant to do so due to this uncertainty. The proposed protocol guarantees strong-fairness while preserving anonymity of the consumer and the merchant, using Bit coin as a payment method which addresses the aforementioned concern. The involvement of the trusted third party (TTP) is kept to a minimum, which makes the protocol optimistic and the exchanged product is not revealed to TTP. It achieves dispute resolution within the protocol run without any intervention of an external judge. Finally we show how the protocol can be easily adapted to use other digital cash systems designed using public ledgers such as Zerocoin/Zerocash.
The increasing demand in promoting cloud computing in either business or other areas requires more security of a cloud storage system. Traditional cloud storage systems fail to protect data integrity information (DII), when the interactive messages between the client and the data storage server are sniffed. To protect DII and support public verifiability, we propose a data integrity verification scheme by deploying a designated confirmer signature DCS as a building block. The DCS scheme strikes the balance between public verifiable signatures and zero-knowledge proofs which can address disputes between the cloud storage server and any user, whoever acting as a malicious player during the two-round verification. In addition, our verification scheme remains blockless and stateless, which is important in conducting a secure and efficient cryptosystem. We perform security analysis and performance evaluation on our scheme, and compared with the existing schemes, the results show that our scheme is more secure and efficient.
In this paper, we devise a novel anonymous voting protocol based on bilinear pairings. This protocol can be used by a group of participants to vote for one or more resolutions under the decentralized condition (boardroom voting), at the meantime preserving the privacy of participants. More specifically, in the session key set-up phase, every participant just need to broadcast a single message containing an ephemeral public key and a zero-knowledge proof. In the commitment phase, participants should broadcast the commitment of their votes although the actual votes are not revealed. After that, in the voting phase, every participant should encrypts his or her vote by combining these public keys and his secret session key, and then broadcast it to others. Finally, the voting result can be recovered by multiplying all the votes together. The advantage of our protocol over others lies in the fact that once the session keys have been established, they can be used repeatedly over multiple commitment and voting phases. So it requires just two rounds of broadcasting in every voting process after the first one, rendering it pretty good in terms of round efficiency. More precisely, if a group need to vote for several resolutions in one meeting, our protocol would involve less computational load and bandwidth usage in every vote. In fact, it is better than all the other techniques known. Our protocol is provably secure under the Decision Bilinear Diffie-Hellman assumption and random oracle assumption.
Shao et al. proposed a novel method for computing private set intersection based on searchable encryption. Compared with the traditional protocols, their technique requires much less computation for the client to obtain the intersection. Concretely, the client only computes m (the cardinality of the client’s input set) multiplications, m hashes, and one modular exponentiation. However, their protocol only satisfies security against semi-honest behaviors. In this paper, we aim to promote the security of Shao et al.’s protocol. Our solution woks in the CRS model, and is based on the non-interactive zero knowledge proof and the succinct non-interactive argument. The proposed protocol satisfies security against malicious adversaries and needs only one round interaction.
The problem of secure multi-party computation(SMPC) is one of the most fundamental problems in information security. First, we introduce the basic concept of SMPC and four SMPC basic agreement: key distribution,oblivious transfer, bit commitment and zero knowledge proof. Secondly, we separately illustrate commitment schemes  commitment transfer protocol, commitment sharing protocol and commitment multiplication protocol. Finally, we present unconditionally secure multi-party computation with a passive adversary, an active adversary, general adversary structures.
Provable data possession (PDP) is one of the techniques to ensure the integrity of data in storage outsourcing. Here in this paper, we speak to the creation of an efficient PDP method for distributed cloud storage to maintain the scalability of service and data migration. On the basis on homomorphic verifiable response and hash index hierarchy we projected a cooperative PDP (CPDP) method. We confirm the security of our method based on multi-prover zeroknowledge proof scheme, which can satisfy knowledge soundness, fullness , and zero-knowledge properties. As well, we expressive performance optimization mechanisms for our method, and in particular present an capable method for selecting finest parameter values to reduce the addition expenses of storage service providers and client. Our experiment shows that our solution introduces lower addition and communication overheads in evaluation with noncooperative approaches.
In this paper, we propose a secure yoking proof protocol for RFID passive tags based on Zero Knowledge. The protocols that have been proposed earlier are either found to be vulnerable to certain attacks or do not comply with EPC standard for passive tags because they use complex encryption schemes. Also, the unique design requirements of yoking/grouping proofs have not been fully addressed by many. Our protocol addresses these important security and design gaps in yoking proofs. The proposed protocol uses pseudo random squares and quadratic residuosity to realize the zero knowledge property. Tag operations are limited to functions such as modulo (MOD), exclusive-or (XOR) and 128-bit Pseudo Random Number Generators (PRNG). Passive tags are capable of these operations and hence the protocol achieves EPC compliance and also meets the necessary security requirements.
Existing location privacy-preserving methods, without a trusted third party, cannot resist conspiracy attacks and active attacks. This paper proposes a novel solution for location based service (LBS) in vehicular ad hoc network (VANET). Firstly, the relationship among anonymity degree, expected company area and vehicle density is discussed. Then, a companion set V is set up by k neighbor vehicles. Based on secure multi-party computation, each vehicle in V can compute the centroid, not revealing its location to each other. The centroid as a cloaking location is sent to LBS provider (P) and P returns a point of interest (POI). Due to a distributed secret sharing structure, P cannot obtain the positions of non-complicity vehicles by colluding with multiple internal vehicles. To detect fake data from dishonest vehicles, zero knowledge proof is adopted. Comparing with other related methods, our solution can resist passive and active attacks from internal and external nodes. It provides strong privacy protection for LBS in VANET.
Zero-knowledge proofs provide a means for a prover to convince a verifier that some claim is true and nothing more. The ability to prove statements while conveying zero information beyond their veracity has profound implications for cryptography and, especially, for its applicability to privacy-enhancing technologies. Unfortunately, the most common zero-knowledge techniques in the literature suffer from poor scalability, which limits their usefulness in many otherwise promising applications. This dissertation addresses the problem of designing communication- and computation-efficient protocols for zero-knowledge proofs and arguments of propositions that comprise many "simple" predicates. In particular, we propose a new formal model in which to analyze batch zero-knowledge protocols and perform the first systematic study of systems for batch zero-knowledge proofs and arguments of knowledge. In the course of this study, we suggest a general construction for batch zero-knowledge proof systems and use it to realize several new protocols suitable for proving knowledge of and relationships among large batches of discrete logarithm (DL) representations in prime-order groups. Our new protocols improve on existing protocols in several ways; for example, among the new protocols is one with lower asymptotic computation cost than any other such system in the literature. We also tackle the problem of constructing batch proofs of partial knowledge, proposing new protocols to prove knowledge of a DL that is equal to at least k-out-of-n other DLs, at most k-out-of-n other DLs, or exactly k-out-of-n other DLs. These constructions are particularly interesting as they prove some propositions that appear difficult to prove using existing techniques, even when efficiency is not a primary consideration. We illustrate the applicability of our new techniques by using them to construct efficient protocols for anonymous blacklisting and reputation systems.