Blockchain Papers

Akihiro Yamamura, Kurokawa Takashi, Junji Nakazato

No abstract is available for this record.

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai

We present a general construction of a zero-knowledge proof for an NP relation R(x,w) which only makes a black-box use of a secure protocol for a related multi-partyfunctionality f. The latter protocol is only required to be secure against a small number of "honest but curious" players. As an application, we can translate previous results on the efficiency of secure multiparty computation to the domain of zero-knowledge, improving over previous constructions of efficient zero-knowledge proofs. In particular, if verifying R on a witness of length m can be done by a circuit C of size s, and assuming one-way functions exist, we get the following types of zero-knowledge proof protocols.

Sae-Ran Kwon, Sangho Lee

No abstract is available for this record.

Hoeteck Wee

No abstract is available for this record.

Bernard Chazelle

No abstract is available for this record.

Gerald V. Post

The current political climate has almost ruled out the use of Internet voting.Many politicians, led by vocal computer scientists, are pushing for voter verified paper receipts; which is likely to push us even further away from even electronic voting systems.On the other hand, cryptographers have created homomorphic encryption and non-interactive zero-knowledge proofs with features that can support Internet voting.Adding a few more protocols, including an extended voting period and repeat voting can solve the remaining problems need to make Internet voting at least as secure as existing systems.

Huafei Zhu, Ying Qiu, Feng Bao

Ad-hoc networks formed by peers without relying on any preexisting infrastructure, have been a very attractive field of academic and industrial research in recent years due to their potential applications. An ad-hoc network allows a peer node further to form a task-driven sub-network such that each node in the generated sub-network may exchange data with each other but any other non-member node is prohibited to access the subnetwork. As a result, a task-driven subnetwork generated by a peer node definitely requires membership proof mechanism (in the scenario of anonymous communications, anonymous membership proof systems are required). In this paper, we provide a novel mechanism for anonymous access control (anonymous membership proof systems) in ad- hoc networks based on a new notion which we call or-protocols in the common reference string model. An or-protocol in essence is a three move zero-knowledge proof system that allows a peer node to prove its membership of a given set which is publicly verifiable. Our protocol is of constant size, i.e., the length of a proof is independent with number of users in a given set, and thus is suitable for practice. Furthermore we show that our protocol is provably secure assuming that the discrete logarithm problem defined over prime field is hard.

Amitabh Saxena

In this paper, we study the opacity property of verifiably encrypted signatures (VES) of Boneh et al. (proposed in Eurocrypt 2003). Informally, opacity implies that although some given aggregate signatures can verified, no useful information about the individual signatures is leaked. However, the very fact that an aggregate signature can be verified leaks certain information- that the individual signature is indeed well-formed. Apart from this, is there any other information leaked? In this paper, we show that there is absolutely no other information leaked about the individual signatures when the aggregation contains only two signatures. In more formal terms, we show that VES are Zero-Knowledge (ZK). We then extend the ZK property of VES to propose efficient Additive Non-Interactive Witness-Indistinguishable (A-NIWI) proofs. Intuitively an A-NIWI proof can be considered as a Proof of Knowledge (PoK) of another A-NIWI proof. 1

Yitao Duan

Privacy is becoming an increasingly important issue in electronic commerce and other online activities that are growing in popularity. This work introduces a framework, called Peers for Privacy (P4P), for implementing many useful algorithms with provable privacy and adequate efficiency in a realistic adversary model at a reasonably large scale. The basic idea is to decompose an algorithm into a series of addition-only steps, which have very efficient private implementation using cryptographic tools. This simple model is surprisingly general and supports many algorithms prevalent in distributed data mining. Examples include linear algorithms like voting and summation, as well as nonlinear algorithms such as regression, classification, SVD, PCA, <i>k</i>-means, ID3, machine learning algorithms based on Expectation Maximization (EM), etc. In fact all algorithms in the statistical query model are supported. <p> The computation of the sums is based on a highly efficient verifiable secret sharing (VSS) scheme that allows secret-shared arithmetic operations to be done over small fields (e.g. 32 or 64 bits) where private arithmetic operations have the same cost as normal arithmetic. This thesis shows that this paradigm admits efficient zero-knowledge tools that can be used to verify the properties of user data such as equality and boundedness. These tools provide practical mechanisms to deal with cheating users. One such tool is an extremely efficient zero-knowledge proof that verifies the L2-norm of the user data is bounded by a constant. This is to prevent a malicious user from exerting too much influence on the computation. The verification uses a linear number of inexpensive small field operations, and only a logarithmic number of large-field (1024 bits or more) cryptographic operations, and can achieve orders of magnitude reduction in running time over standard techniques (from hours to seconds) for large-scale problems. Concrete examples are given to demonstrate how the framework supports private computation of popular algorithms such as SVD, link analysis and association rule mining. The thesis also includes schemes for scalable multicast encryption and bidirectional group communication. They provide secure data transmission support for the type of communication pattern required by the P4P framework and many other group-oriented applications

Hong Zhong

Secure Multiparty Computation technique plays an important role in the security research of distributed systems.This paper firstly summarizes the advances in theoretical and practical studies on SMC,and then analysis the basic protocols and its related cryptographic algorithms.Secondly,the key tools,secret share,homomorphic public key cryptography,mix network,zero knowledge proof,oblivious transfer and private comparison protocol in implementation SMC are studied deeply.Finally,some research directions in this area are also proposed.

Manoj Prabhakaran, Rui Xue

Zero-knowledge set is a primitive introduced by Micali, Rabin, and Kilian (FOCS 2003) which enables a prover to commit a set to a verifier, without revealing even the size of the set. Later the prover can give zero-knowledge proofs to convince the verifier of membership/nonmembership of elements in/not in the committed set. We present a new primitive called Statistically Hiding Sets (SHS), similar to zero-knowledge sets, but providing an information theoretic hiding guarantee. This is comparable to relaxing zero-knowledge proofs to witness independent proofs. More precisely, we continue to use the simulation paradigm for our definition, but do not require the simulator (nor the distinguisher) to be efficient. We present a new scheme for statistically hiding sets, which does not fit into the “Merkletree/mercurial-commitment” paradigm used for all zero-knowledge set constructions so far. This not only provides some efficiency gains compared to the best possible schemes in that paradigm, but also lets us provide statistical hiding, without the prover having to maintain growing amounts of state with each new proof; this is not known to be possible with the previous approach.

Oluwafemi Ajayi, Richard Sinnott, Anthony Stell

Access control in decentralised collaborative systems present huge challenges especially where many autonomous entities including organizations, humans, software agents from different security domains seek to access and share resources in a secure and controlled way. Automated trust negotiation (ATN) is one approach that has been proposed for trust discovery and realisation, which enables entities viz. strangers to access resources across autonomous boundaries through iterative exchange of credentials. Various negotiation strategies have been proposed to protect credential disclosure during trust negotiations. However in some domains such as e-health, not all entities are willing to negotiate credentials or disclose access policies directly to strangers regardless of negotiation strategies and instead prefer to negotiate and disclose sensitive information only to strangers within what we refer to as a circle of trust. In this paper, we introduce a formal model to describe how locally trusted intermediary parties can provide multiple negotiation and delegations hops to protect credentials and access policies. We propose a dynamic trust negotiations (DTN) model that not only protects sensitive information from disclosure but also reduces semantic issues that exist with credentials in decentralized systems. This work is currently being explored and implemented within the e-health domain: specifically in the MRC-funded Virtual Organisation for Trials of Epidemiological Studies (VOTES) project

Lu Li, Jinsong Han, Lei Hu, Jinpeng Huai · 6 authors

Most of the current trust models in peer-to-peer (P2P) systems are identity based, which means that in order for one peer to trust another, it needs to know the other peer's identity. Hence, there exists an inherent tradeoff between trust and anonymity. To the best of our knowledge, there is currently no P2P protocol that provides complete mutual anonymity as well as authentication and trust management. We propose a zero-knowledge authentication scheme called pseudo trust (PT), where each peer, instead of using its real identity, generates an unforgeable and verifiable pseudonym using a one-way hash function. A novel authentication scheme based on zero-knowledge proof is designed so peers can be authenticated without leaking any sensitive information. With the help of PT, most existing identity-based trust management schemes become applicable in mutual anonymous P2P systems. We analyze the levels of security and anonymity in PT, and evaluate its performance using trace-driven simulations and a prototype implementation. The strengths of pseudo trust include the lack of need for a centralized trusted party or CA, high scalability and security, low traffic and cryptography processing overheads, and man-in-middle attack resistance. We aim for the pseudo trust design to be included in the P2P trust and anonymity context.

Moti Yung, Yunlei Zhao

No abstract is available for this record.

Ivan Damgård, Rune Thorbek

We present two universally composable and practical protocols by which a dealer can, verifiably and non-interactively, secret-share an integer among a set of players. Moreover, at small extra cost and using a distributed verifier proof, it can be shown in zero-knowledge that three shared integers a, b, c satisfy ab = c. This implies by known reductions non-interactive zero-knowledge proofs that a shared integer is in a given interval, or that one secret integer is larger than another. Such primitives are useful, e.g., for supplying inputs to a multiparty computation protocol, such as an auction or an election. The protocols use various set-up assumptions, but do not require the random oracle model.

Yehuda Lindell, Benny Pinkas

Abstract. We show an efficient secure two-party protocol, based on Yao’s construction, which provides security against malicious adversaries. Yao’s original protocol is only secure in the presence of semi-honest adversaries. Security against malicious adversaries can be obtained by applying the compiler of Goldreich, Micali and Wigderson (the “GMW compiler”). However, this approach does not seem to be very practical as it requires using generic zero-knowledge proofs. Our construction is based on applying cut-and-choose techniques to the original circuit and inputs. Security is proved according to the ideal/real simulation paradigm, and the proof is in the standard model (with no random oracle model or common reference string assumptions). The resulting protocol is computationally efficient: the only usage of asymmetric cryptography is for running O(1) oblivious transfers for each input bit (or for each bit of a statistical security parameter, whichever is larger). Our protocol combines techniques from folklore (like cut-and-choose) along with new techniques for efficiently proving consistency of inputs. We remark that a naive implementation of the cut-and-choose technique with Yao’s protocol does not yield a secure protocol. This is the first paper to show how to properly implement these techniques, and to provide a full proof of security. Our protocol can also be interpreted as a constant-round black-box reduction of secure two-party com-putation to oblivious transfer and perfectly-hiding commitments, or a black-box reduction of secure two-party computation to oblivious transfer alone, with a number of rounds which is linear in a sta-tistical security parameter. These two reductions are comparable to Kilian’s reduction, which uses OT alone but incurs a number of rounds which is linear in the depth of the circuit [18]. 1

Richard S. Norville, Kamesh Namuduri, Ravi Pendse

Zero-knowledge proof (ZKP) based authentication protocols provide a smart way to prove an identity of a node without giving away any information about the secret of that identity. There are many advantages as well as disadvantages to using this protocol over other authentication schemes, and challenges to overcome in order to make it practical for general use. This chapter examines the viability of ZKPs for use in authentication protocols in networks. It is concluded that nodes in a network can achieve a desired level of security by trading off key size, interactivity, and other parameters of the authentication protocol. This chapter also provides data analysis that can be useful in determining expected authentication times based on device capabilities. Pseudocode is provided for implementing a graph-based ZKP on small or limited processing devices.Request access from your librarian to read this chapter's full text.

Ivan Damgård, Jesper Buus Nielsen, Daniel Wichs

We introduce a new notion called `-isolated proofs of knowledge (`-IPoK). These are proofs of knowledge where a cheating prover is allowed to exchange up to ` bits of communication with some external adversarial environment during the run of the proof. Without any additional setup assumptions, no witness hiding protocol can be an `-IPoK for unbounded values of `. However, for any pre-defined threshold `, and any relation in NP and we construct an `-IPoK protocol for that relation. The resulting protocols are zero knowledge (ZK) in the standard sense, i.e., w.r.t. a verifier that communicates only with the prover during the proof. The cost of having a large threshold ` is a large communication complexity of the constructed protocol. We analyze these costs and present a solution that is asymptotically optimal. If a cheating verifier is allowed to communicate arbitrarily with an external environment, it is not possible to construct an `-IPoK that is also ZK with respect to such a verifier. As another new notion, we define `-isolated zero knowledge (`-IZK) where the verifier is `-isolated. For every relation in NP and every `, we construct an `-IPoK protocol that is also `-IZK. We describe several applications of `-IPoK protocols under the physical assumption that one can `isolate a prover for the duration of the proof phase. Firstly, we can use a witness indistinguishable (WI) `-IPoK to prevent “man-in-the-middle” attacks on identification schemes. Prior results for this scenario required all verifiers to register keys under a PKI, or the ability to fully isolate the prover. Secondly, a partially isolated prover can register a public key and use a WI `-IPoK to prove knowledge of the corresponding secret key to another party acting as a verifier. This allows us to set up a PKI where the key registrant does not need to trust the Certificate Authority. The PKI is not perfect since the proof is only witness indistinguishable and not zero knowledge. In a companion paper, we show how to set up such a PKI and use it to implement arbitrary multiparty computation securely in the UC framework without relying on any trusted third parties.

Jan Camenisch, Thomas Groß, Dieter Sommer

Federated Identity Management (FIM) allows for securely provisioning certified user identities and attributes to relying parties. It establishes higher security and data quality compared to user-asserted attributes and provides for stronger user privacy protection than technologies based upon user-side attribute certificates. Therefore, industry pursues the deployment of FIM solutions as one cornerstone of the WS-Security framework. Current research proposes even more powerful methods for security and privacy protection in identity management with so called anonymous credential systems. Being based on new, yet well-researched, signature schemes and cryptographic zero-knowledge proofs, these systems have the potential to improve the capabilities of FIM by superior privacy protection, user control, and multiple use of single credentials. Unfortunately, anonymous credential systems and their semantics being based upon zero-knowledge proofs are incompatible with the XML Signature Standard which is the basis for the WS-Security and most FIM frameworks. We put forth a general construction for integrating anonymous credential systems with the XML Signature Standard and FIM protocols. We apply this method to the WS-Security protocol framework and thus obtain a very flexible WS-Federation Active Requestor Profile with strong user control and superior privacy protection.

Yael Tauman Kalai, Ran Raz

Let Lambda : {0, 1}ntimes {0,1}mrarr {0,1} be a Boolean formula of size d, or more generally, an arithmetic circuit of degree d, known to both Alice and Bob, and let y isin {0,1}mbe an input known only to Alice. Assume that Alice and Bob interacted in the past in a preamble phase (that is, applied a preamble protocol that depends only on the parameters, and not on Lambday). We show that Alice can (non-interactively) commit to y, by a message of size poly(m, log d), and later on prove to Bob any N statements of the form Lambda (x1, y) = z1,..., Lambda(xN,y) = zNby a (computationally sound) non-interactive zero-knowledge proof of size poly(d, log N). (Note the logarithmic dependence on N). We give many applications and motivations for this result. In particular, assuming that Alice and Bob applied in the past the (poly-logarithmic size) preamble protocol: 1. given a CNF formula Psi(w1,..., wm) of size N, Alice can prove the satisfiability of Psi by a (computationally sound) non-interactive zero-knowledge proof of size poly(m). That is, the size of the proof depends only on the size of the witness and not on the size of the formula. 2. Given a language L in the class LOGSNP and an input x isin {0, 1}n, Alice can prove the membership x isin L by a (computationally sound) non-interactive zero-knowledge proof of size polylog n. 3. Alice can commit to a Boolean formula y of size m, by a message of size poly(m), and later on prove to Bob any N statements of the form y(x1) = z1,..., y(xN) = zNby a (computationally sound) non-interactive zero-knowledge proof of size poly(m, log N). Our cryptographic assumptions include the existence of a poly-logarithmic symmetric-private-information-retrieval (SPIR) scheme, as defined in (C. Cachin et. al, 1999), and the existence of commitment schemes, secure against circuits of size exponential in the security parameter

Justin Brickell, Vitaly Shmatikov

The output of a data mining algorithm is only as good as its inputs, and individuals are often unwilling to provide accurate data about sensitive topics such as medical history and personal finance. Individuals maybe willing to share their data, but only if they are assured that it will be used in an aggregate study and that it cannot be linked back to them. Protocols for anonymity-preserving data collection provide this assurance, in the absence of trusted parties, by allowing a set of mutually distrustful respondents to anonymously contribute data to an untrusted data miner.To effectively provide anonymity, a data collection protocol must be collusion resistant, which means that even if all dishonest respondents collude with a dishonest data miner in an attempt to learn the associations between honest respondents and their responses, they will be unable to do so. To achieve collusion resistance, previously proposed protocols for anonymity-preserving data collection have quadratically many communication rounds in the number of respondents, and employ (sometimes incorrectly) complicated cryptographic techniques such as zero-knowledge proofs.We describe a new protocol for anonymity-preserving, collusion resistant data collection. Our protocol has linearly many communication rounds, and achieves collusion resistance without relying on zero-knowledge proofs. This makes it especially suitable for data mining scenarios with a large number of respondents.

Alejandro Hevia

No abstract is available for this record.

Yan Zhu

Ownership proofs of digital works allow to justify the copyright claim to the buyers without revealing any secret information and prevent the owner from deceiving without the assumption of the trusted individual. This paper proposes an ownership proofs scheme for digital works based on proactive verifiable secret sharing and secure multiparty computation. In the proposed scheme, verifiable secret sharing ensures the correctness of ownership secrets and achieves security against cheating participants. Proactive security provides an automatic recovery feature to maintain the integrity and security of secret throughout the lifetime of the scheme. Furthermore, the ownership verification is implemented by using secure multiparty computation and zero-knowledge proofs with homomorphic commitments. Without the assumption of the existence of a trusted individual, the proposed scheme can provide effective computation and discover the dishonesty if not too many individuals collude.

Susan Hohenberger, Stephen A. Weis

No abstract is available for this record.