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

M. Albrecht, Christian Rechberger, Thomas Schneider, Tyge Tiessen · 5 authors

No abstract is available for this record.

Claude Crépeau, Raza Ali Kazmi

In this work we introduce a new hard problem in lattices called Isometric Lattice Problem (ILP) and reduce Linear Code Equivalence over prime fields and Graph Isomorphism to this problem. We also show that this problem has an (efficient prover) perfect zero-knowledge interactive proof; this is the only hard problem in lattices that is known to have this property (with respect to malicious verifiers). Under the assumption that the polynomial hierarchy does not collapse, we also show that ILP cannot be NP-complete. We finally introduce a variant of ILP over the rationals radicands and provide similar results for this new problem.

Tore Kasper Frederiksen, Jesper Buus Nielsen, Claudio Orlandi

No abstract is available for this record.

Thomas Scatko, Nathaniel W. Rowe

Abstract : Authentication is deemed to be a critical function in the operation of tactical wireless ad hoc networks. The dynamic nature and unpredictability of these self - organizing networks requires that new security protocols be deployed that allow users to efficiently gain access to network resources without the burden of a centralized security infrastructure. Authentication protocols based on Zero - Knowledge Proof (ZKP) of identity schemes provide a means for establishing mutual trust between network entities. While many papers have looked at the virtues of ZKP - based authentication protocols from an academic perspective, little work has been carried out to actually deploy and test the protocols in fielded wireless networks. In this paper we present lessons - learned regarding the installation of ZKP - based authentication protocol on processing hardware designed for deployment on AFRL's small unmanned aerial vehicle (UAV) test bed.

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.

Vipul Goyal, Aayush Jain, Dakshita Khurana

Motivated by the goal of removing trusted setup assumptions from cryptography, we introduce the notion of witness signatures. This primitive allows any party with a valid witness to an NP statement to sign a message on behalf of that statement. We also require these signatures to be unforgeable: that is, producing a signature on a new message (even given several message, signature pairs) should be as hard as computing a witness to the NP statement itself. Witness signatures are closely related to previously well-studied notions such as non-malleable non-interactive zero knowledge arguments, and signatures of knowledge. In this work, we formalize this notion and show that most natural definitions are impossible in the plain model without any setup assumptions. While still wanting to avoid a central trusted setup, we turn to the tamper proof hardware token model of Katz (Eurocrypt 2007). Interestingly, we show witness signatures in the hardware token model are closely related to what we call non-malleable multi-prover zero-knowledge proofs in the plain model (i.e. without hardware tokens). We initiate the study of non-malleable multi-prover zero-knowledge proofs, and, provide an unconditional construction of single round non-malleable two-prover zero-knowledge proofs. We then use this primitive to obtain an unconditional

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].

Giuseppe Ateniese, Antonio Faonio, Seny Kamara

We provide a framework for constructing leakage-resilient identification (ID) protocols in the bounded retrieval model (BRM) from proofs of storage (PoS) that hide partial information about the file. More precisely, we describe a generic transformation from any zero-knowledge PoS to a leakage-resilient ID protocol in the BRM. We then describe a ZK-PoS based on RSA which, under our transformation, yields the first ID protocol in the BRM based on RSA (in the ROM). The resulting protocol relies on a different computational assumption and is more efficient than previously-known constructions.

Jun Yan, Jian Weng, Dongdai Lin, Yu-Juan Quan

No abstract is available for this record.

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

Ahmed E. Kosba, Zhichao Zhao, Andrew Miller, Yi Qian · 9 authors

No abstract is available for this record.

Zhichao Zhao, T-H. Hubert Chan

Bitcoin is the first decentralized crypto-currency that is cur-rently by far the most popular one in use. The bitcoin trans-action syntax is expressive enough to setup digital contracts whose fund transfer can be enforced automatically. In this paper, we design protocols for the bitcoin voting problem, in which there are n voters, each of which wishes to fund exactly one of two candidates A and B. The win-ning candidate is determined by majority voting, while the privacy of individual vote is preserved. Moreover, the de-cision is irrevocable in the sense that once the outcome is revealed, the winning candidate is guaranteed to have the funding from all n voters. As in previous works, each voter is incentivized to follow the protocol by being required to put a deposit in the sys-tem, which will be used as compensation if he deviates from the protocol. Our solution is similar to previous protocols used for lottery, but needs an additional phase to distribute secret random numbers via zero-knowledge-proofs. More-over, we have resolved a security issue in previous protocols that could prevent compensation from being paid. 1.

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.

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.

Nesrine Kaaniche

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

Pratibha Kumari, A. Damodaram

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.

Benfano Soewito, Yonathan Marcellinus, Manik Hapsara

A Mobile Ad-hoc Network (MANET) is a group of wireless mobile nodes that dynamically form a network without any pre-established infrastructure or centralized administration, Soewito (2014). Some network hops may be needed to send a packet from one node to another node in the MANET. To do the communication between the nodes, a route has to be selected in the network, therefore it need a routing protocol that manage selection of the route. Selection route in mobile ad-hoc network is not easy because nodes always move so that the topology of network always changed every time. This is a big issue in selection route in mobile ad-hoc network because the route can be broken anytime. Moreover, MANET is more vulnerable than other wireless communication types because every mobile node serves as both the host and the router and forwards packets on behalf of each other. This study presents the analyzing and evaluation several routing algorithms and a novel scheme to build an authentication system by adding the modified zero knowledge proof algorithm to each mobile node in MANET.

Leslie Copley

Our focus in the last chapter was on the construction of an analytic function from a knowledge of its singularities.More often than not, however, we are confronted with the inverse problem: given some knowledge of a function in a restricted region of its domain of holomorphy, determine its singularities.This will be the focus of the present chapter.We have seen repeatedly that one need not know all that much about an analytic function in order to determine its value everywhere in the complex plane or on its Riemann surface.Cauchy's Integral Representation can be viewed as the embodiment of this property and thus far it has provided the key to exploiting it.We are now going to nd out what constitutes a minimal set of information for the determination of an analytic function.The answer is one that is best exploited not by Cauchy's Integral but by one of its consequences, the Taylor series.In so doing, we shall also nd out how to use a representation of a function that is valid in one domain of the complex plane to determine its values at points outside the domain or indeed, at any points where it is holomorphic.Our starting point is the following theorem which, despite its innocuous appearance, is one of the most remarkable results of complex analysis.Theorem: Let f (z) and f (z) be holomorphic in a domain D of the complex plane.If the two functions coincide in any neighbourhood, however small, of a point z in D, or even on a point set with an accumulation point in D, then they coincide throughout D. Proof: The function f (z)f (z) is holomorphic throughout D and has a set of zeros consisting of the points where f (z) and f (z) coincide, with an accumulation point in D. We know that in any domain where it is holomorphic a function either has isolated zeros or it is identically zero.Thus,What this theorem establishes is that a holomorphic function is uniquely determined everywhere within its domain of holomorphy by its behaviour in the neighbourhood of an arbitrary point of that domain.But how can one exploit this remarkable property?Obviously not by means of a Cauchy Integral or dispersion representation or anything else of that ilk as we lack the necessary input information.However, what we do have is precisely the information needed to determine a Taylor series representation.Suppose that we know the value of the function f (z) throughout a neighbourhood of the point z = z which is a point lying within the function's domain of holomorphy, D. This is su cient to permit calculation of the coe cients c = f (z ), c = f (z ), . . ., cm = m! f (m) (z ), . . .

Thomas Groß

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.

Fajiang Yu, Chen Jing, Xiang Yang, Zhu Jiacheng · 5 authors

No abstract is available for this record.