Blockchain Papers

Thomas Groß

No abstract is available for this record.

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

Tore Kasper Frederiksen, Jesper Buus Nielsen, Claudio Orlandi

No abstract is available for this record.

Alessandro Chiesa, Eran Tromer, Madars Virza

Large computations, when amenable to distributed parallel execution, are often executed on computer clusters, for scalability and cost reasons. Such computations are used in many applications, including, to name but a few, machine learning, webgraph mining, and statistical machine translation. Oftentimes, though, the input data is private and only the result of the computation can be published. Zero-knowledge proofs would allow, in such settings, to verify correctness of the output without leaking (additional) information about the input.

Matthias Tarasiewicz, Andrew Newman

No abstract is available for this record.

Foteini Baldimtsi, Aggelos Kiayias, Thomas Zacharias, Bingsheng Zhang

We introduce a new class of protocols called Proofs of Work or Knowledge (PoWorKs). In a PoWorK, a prover can convince a verifier that she has either performed work or that she possesses knowledge of a witness to a public statement without the verifier being able to distinguish which of the two has taken place. We formalize PoWorK in terms of three basic properties, completeness, f-soundness and indistinguishabil-ity (where f is a function that determines the tightness of the proof of work aspect) and present a construction that transforms 3-move HVZK protocols into 3-move public-coin PoWorKs. To formalize the work aspect in a PoWorK protocol we define cryptographic puzzles that adhere to certain uniformity conditions, which may also be of independent interest. We instantiate our puzzles in the random oracle (RO) model as well as via constructing “dense ” versions of suitably hard one-way functions. We then showcase PoWorK protocols by presenting two applications. We first show how non-interactive PoWorKs can be used to reduce spam email by forcing users sending an e-mail to either prove to the mail server they are approved contacts of the recipient or to perform computational work. As opposed to previous approaches [DN92, DGN03] that applied proofs of work to this problem, our proposal of using PoWorKs is privacy-preserving as it hides the list of the receiver’s approved contacts from the mail server. Our second application for PoWorK relates to zero-knowledge protocols. We show that PoWorK protocols imply straight-line quasi-polynomial simulatable arguments of knowledge; by applying this result to our construction we obtain an efficient straight-line concurrent 3-move statistically quasi-polynomial simulatable argument of knowledge, improving the round complexity of the previously known four-move protocols, [Pas03].

Olivier Blazy, Céline Chevalier, Damien Vergnaud

No abstract is available for this record.

Zhangxiang Hu, Payman Mohassel, Mike Rosulek

We describe a zero-knowledge proof system in which a prover holds a large dataset M and can repeatedly prove NP relations about that dataset. That is, for any (public) relation R and x, the prover can prove that ∃w: R(M,x,w) = 1. After an initial setup phase (which depends only on M), each proof requires only a constant number of rounds and has communication/computation cost proportional to that of a random-access machine (RAM) implementation of R, up to poly-logarithmic factors. In particular, the cost per proof in many applications is sublinear in |M |. Additionally, the storage requirement between proofs for the verifier is constant. 1

Lam Pak Nian, David Lee Kuo Chuen

No abstract is available for this record.

Feroz Ahmad Ahmad, Prashant Kumar, Gulshan Shrivastava, Med Salim Bouhlel

ON 12 JANUARY 2009 a pseudonymous entity signed a transaction that instructed a distributed network to transfer a small amount of digital currency to Hal Finney, one ofthe key figures of the cypherpunk movement. After a few minutes, the transaction was recorded on a distributed public ledger, permanently updating the balance ofbothparties. This transaction— the first Bitcoin transaction—marked the beginning of a new era of decentralized payment systems, ushering in a variety of financial Services that do not depend on any centralized clearinghouse or other financial middleman. Bitcoin is regarded by many as a powerful technological innovation that could disrupt many sectors, in the realm of finance and beyond. But the underlying technology on which the network operates, the Bitcoin blockchain can do much more than that. Just as the internet did in the early-1990s, blockchain technology carries with it a whole new range of promises concerning how decentralization can support and promote individual freedoms and autonomy. Blockchain proponents believe that Bitcoin and other cryptocurrency platforms will revolutionize mechanisms of value exchange in the same way that the internet transformed information sharing, by providing a platform for people to exchange digital resources, in a secure and decentralized manner without the need to rely on any intermediary or trusted authority. But this revolutionary potential also carries with it serious implications for censorship, intellectual property, and the regulated flow of information. A blockchain is a decentralized database of transactions maintained by a distributed network of computers, which all contribute to the verification and the validation of transactions. Once accepted, these transactions are recorded inside a “block” of transactions, which incorporates a reference to previous blocks. This creates a long chain of blocks—a “blockchain”—that stores the history of all transactions in a chronological order. Every block contains information about a particular set of transactions, a reference to the preceding block in the blockchain, and the answer to a complex mathematical puzzle that is used to validate the data associated with that block. A copy of the blockchain is stored on every computer in the network, making it virtually impossible for anyone unilaterally to modify the data stored on this decentralized database: if anyone tries to modify any transaction the fraud will be immediately detected by all other network participants.

Bin Lian, Gongliang Chen, Maode Ma, Jianhua Li

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.

Karim El Defrawy, Joshua Lampkins

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.

Long-Hai Li, Chengqiang Huang, Shao-Feng Fu

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.

Zhi Yi Shao, Bo Yang

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.

Xiaoling Zhu, Donghui Hu, Zhengfeng Hou, Liang Ding

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.

C. Baek, Matt Elbeck

We use Bitcoin and S&P 500 Index daily return data to examine relative volatility using detrended ratios. We then model Bitcoin market returns with selected economic variables to study the drivers of Bitcoin market returns. We report strong evidence to suggest that Bitcoin volatility is internally (buyer and seller) driven leading to the conclusion that the Bitcoin market is highly speculative at present.

Ryan Henry

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.

Yi Qing Lu

Bitcoin is a pure electronic money based on cryptographic proof instead of trust. The principle of Bitcoin can allow any two willing parties to transact directly with each other without the need for a trusted third party. Bitcoin can represent a totally new anarchy virtual currency and an innovation of digital currency. But its development also needs to face to the security of national policy risk, technology risk and trading risks.

Nan Guo, Yuanting Jin, Kangbin Yim

During the execution of a business process users need to be authenticated by multiple component service providers, while their identities need to be shared and propagated across multi-domain in a privacy-preserving fashion. An anonymous credential-based identity verification scheme is proposed to address privacy issue. Users establish trust relationship with the federation by running the enrollment protocol, which is based on zero-knowledge proof of a set of committed attributes. The IdP cannot learn identity-related information about the user. Anonymous credentials issued by the IdP allow users to selectively disclose attributes as required and prove them in an untraceable and unlinkable way, where the IdP cannot trace the showing of credential and component service providers cannot address multiple transactions to the same user even if they collude either. With the proposed attributes proof protocols, users can prove AND and OR relation over multiple attributes, and interval and inequality relation over a single attribute as well.

Dinesh, Erlich, Gilfoyle, Jared · 6 authors

On February 2014, $650.000.000 worth of Bitcoins disappeared. Currently it is unclear whether hackers or MtGox, the largest Bitcoin exchange, are to be blamed. In either case, the anonymous and unregulated nature of the Bitcoin system makes it practically impossible for innocent victims to get their money back. We have investigated the technical possibilities, solutions and implications of introducing a regulatory framework based on redlisting Bitcoin accounts. Despite numerous proposals, the Bitcoin community has voiced a strong opinion against any form of regulation. However, most of the discussions were based on speculations rather than facts. We strive to contribute a scientific foundation to these discussions and illuminate the path to crypto-justice.

Fucai Zhou, Yuxi Li, Qingshi Zhou, Jingwei Miao · 5 authors

Electronic cash is an electronic form of currency, which allows the cash transactions over communication networks under privacy protections. However, it still has some aspects that have not been well studied. Known constructions suffer from at least one of the following limitations: (1) relying on a random oracle, (2) not supporting multiple bank setting and users dynamically joining or (3) prohibitively expensive. In this paper, we propose a new electronic cash system that avoids all these limitations. In other words, our system is anonymous against chosen-ciphertext attack (CCA) in the standard model, and supports multiple banks enrolling and users dynamically joining, which is achieved by the utilization of non-interactive zero-knowledge proof and dynamic group signature. Finally, in the standard model, a formal security proof is given to claim that our system has CCA anonymity, unforgeability, traceability and no double-spending. Compared with the existing systems, ours has advantages of both the efficiency and security.

Fuchun Guo, Yi Mu, Willy Susilo

In this paper, we propose a novel cryptographic notion called subset membership encryption (SME), and provide a very efficient SME scheme. Given a system parameter generated by an encryptor (Alice), a decryptor (Bob) generates a randomized privacy-preserved attribute token P(G) from a set of attributes G. A message is encrypted using an attribute set A chosen by Alice and P(G) provided by Bob. It requires that A is a subset of G for Bob to decrypt the message. We propose a very efficient SME scheme, where both the size of P(G) and ciphertext are short and independent of G and A. In particular, it has three useful and practical applications to oblivious transfer as follows. 1) k-Out-of-n Oblivious Transfer (OT): SME can be naturally applied to a two-round OT, which features a great communication efficiency especially for the receiver, where the receiver only sends two group elements to the message sender. 2) Priced Oblivious Transfer (POT): Our POT protocol allows a buyer to purchase any number of items in each transaction and hide selected items, price and balance from the vendor. In comparison with previous POT protocols, our protocol is more flexible and eliminates the restriction that a buyer can only purchase one item in a transaction. Our POT scheme is very efficient since it does not require any zero-knowledge proof or homomorphic encryption. 3) Restricted Priced Oblivious Transfer (RPOT): We introduce a novel POT named RPOT where a vendor can set restrictions on items or prices in POT. For example, a seller could offer a discounted price to those buyers who have purchased some specific items previously from the same seller.

Florian Kerschbaum, Martín Beck, Dagmar Schönfeld

Privacy is of the utmost importance in genomic matching. Therefore a number of privacy-preserving protocols have been presented using secure computation. Nevertheless, none of these protocols prevents inferences from the result. Goodrich has shown that this resulting information is sufficient for an effective attack on genome databases. In this paper we present an approach that can detect and mitigate such an attack on encrypted messages while still preserving the privacy of both parties. Note that randomization, e.g.~using differential privacy, will almost certainly destroy the utility of the matching result. We combine two known cryptographic primitives -- secure computation of the edit distance and fuzzy commitments -- in order to prevent submission of similar genome sequences. Particularly, we contribute an efficient zero-knowledge proof that the same input has been used in both primitives. We show that using our approach it is feasible to preserve privacy in genome matching and also detect and mitigate Goodrich's attack.