Follow blockchain research across journals, conferences, and preprint repositories.
9,005 results · page 351 of 376
Andrew Chi-Chih Yao, Frances Yao, Yunlei Zhao
No abstract is available for this record.
Laicheng Cao
Most of the current trust models in peer-to-peer (P2P) networks are identity based, which means that in order for one peer to trust another, it needs to know the other peer's identity. In addition, the conventional access control mechanism is not suitable because the P2P networks is decentralize and dynamic one. We propose a neighborhood key method, authentication scheme base on zero-knowledge proof without leaking any sensitive information, each peer shares secrets only with authenticated neighbors, which generate verifiable pseudonym instead of their real identity from using a one-way Hash function. Security analysis proves that this method makes authentication can't be impersonated, while achieving better anonymity for peers, malicious peers cannot deduce a real identity. And also shows well defending man-in-middle attacks.
Michael Backes, Cătălin Hriţcu, Matteo Maffei
This paper presents the first type system for statically analyzing security protocols that are based on zero-knowledge proofs. We show how certain properties offered by zero-knowledge proofs can be characterized in terms of authorization policies and statically enforced by a type system. The analysis is modular and compositional, and provides security proofs for an unbounded number of protocol executions. We develop a new type-checker that conducts the analysis in a fully automated manner. We exemplify the applicability of our technique to real-world protocols by verifying the authenticity and secrecy properties of the Direct Anonymous Attestation (DAA) protocol. The analysis of DAA takes less than three seconds.
Benny Applebaum, Boaz Barak, David Xiao
We consider the question of whether P ne NP implies that there exists some concept class that is efficientlyrepresentable but is still hard to learn in the PAC model of Valiant (CACM '84), where the learner is allowed to output any efficient hypothesis approximating the concept, including an "improper" hypothesis that is not itself in the concept class. We show that unless the polynomial hierarchy collapses, such a statement cannot be proven via a large class of reductions including Karp reductions, truth-table reductions, and a restricted form of non-adaptive Turing reductions. Also, a proof that uses a Turing reduction of constant levels of adaptivity would imply an important consequence in cryptography as it yields a transformation from any average-case hard problem in NP to a one-way function. Our results hold even in the stronger model of agnostic learning. These results are obtained by showing that lower bounds for improper learning are intimately related to the complexity of zero-knowledge arguments and to the existence of weak cryptographic primitives. In particular, we prove that if alanguage L reduces to the task of improper learning of circuits, then, depending on the type of the reduction in use, either (1) L has a statistical zero-knowledge argument system, or (2) the worst-case hardness of L implies the existence of a weak variant of one-way functions defined by Ostrovsky-Wigderson (ISTCS '93). Interestingly, we observe that the converse implication also holds. Namely, if (1) or (2) hold then the intractability of L implies that improper learning is hard.
Payman Mohassel, Enav Weinreb
No abstract is available for this record.
Joël Alwen, Abhi Shelat, Ivan Visconti
No abstract is available for this record.
Yevgeniy Dodis, Victor Shoup, Shabsi Walfish
No abstract is available for this record.
Chris Peikert, Vinod Vaikuntanathan
No abstract is available for this record.
Ning Ding, Dawu Gu
No abstract is available for this record.
Jacek Cichoń, Marek Klonowski, Mirosław Kutyłowski
No abstract is available for this record.
Yael Tauman Kalai, Ran Raz
No abstract is available for this record.
Youliang Tian, Changgen Peng, Renping Zhang, Yuling Chen
A practical publicly verifiable secret sharing (PVSS) is constructed based on the bilinear pairing on elliptic curves, which has all advantages of B. Schoenmakerspsila PVSS and its secret is not the form of discrete logarithm, thus this PVSS is extremely practical. Moreover, in the schemepsilas distribution of shares phase, only using bilinearity of bilinear pairing, anybody can verify whether the participants received correct shares without implementing zero-knowledge proofs, without implementing the non-interactive protocol and without construction so called witness of shares applying Fiat-Shamirpsilas technique. Subsequently, in the schemepsilas reconstruction of secret phase, the released shares may be verified by anybody with the same method. Since the PVSS need not to implement non-interactive protocol to prevent malicious players. Therefore this scheme is simpler, more efficient and practical suitable for some especially case.
Guomin Yang, Jing Chen, Duncan S. Wong, Xiaotie Deng · 5 authors
No abstract is available for this record.
Yi Deng
提出了一种从3轮公开掷币的对任何NP语言的诚实验证者零知识证明系统到纯公钥模型下4轮(轮最优)对同一语言的具有并发合理性的并发零知识证明系统.该转化方法有如下优点:1) 它只引起O(1)(常数个)额外的模指数运算,相比Di Crescenzo等人在ICALP 05上提出的需要((n)个额外的模指数运算的转化方法,该系统在效率上有着本质上的提高,而所需的困难性假设不变;2) 在离散对数假设下,该转化方法产生一个完美零知识证明系统.注意到Di Crescenzo等人提出的系统只具有计算零知识性质.该转化方法依赖于一个特殊的对承诺中的离散对数的3轮诚实验证者零知识的证明系统.构造了两个基于不同承诺方案的只需要常数个模指数运算的系统,这种系统可能有着独立价值.;This paper shows how to efficiently transform any 3-round public-coin honest verifier zero knowledge argument system for any language in NP into a 4 round (round-optimal) concurrent zero knowledge argument for the same language in the bare public-key model. The transformation has the following properties: 1) incurs only O(1) (small constant, about 20) additional modular exponentiations. Compared to the concurrent zero knowledge protocol proposed by Di Crescenzo and Visconti in ICALP 2005, in which their transformation requires an overhead of ((n), the protocol is significantly more efficient under the same intractability assumptions; 2) yields a perfect zero knowledge argument under DL assumption. Note that the Di Crescenzo, et al.'s argument system enjoys only computational zero knowledge property. The transformation relies on a specific 3-round honest verifier zero knowledge proof of knowledge for committed discrete log. Such protocols that require only O(1) modular exponentiations based on different kinds of commitment scheme are developed and they may be of independent interest.
Jungha Woo, Abhilasha Bhargav-Spantzel, Anna Squicciarini, Elisa Bertino
A main challenge in mobile commerce is to make it possible for users to manage their transaction histories from both online e-commerce transactions and in-person transactions. Such histories are typically useful to build credit or to establish trust based on past transactions. In this paper we propose an approach to manage electronic receipts on cellular devices by assuring their secure and privacy-preserving usage. We provide a comprehensive notion of transactions history including both on-line transaction and in-person transactions. We apply cryptographic protocols, such as secret sharing and zero knowledge proofs, in a potentially vulnerable and constrained setting. Specifically, our approach supports flexible strategies based on Shamir's secret sharing to cater to different user requirements and architectural constraints. In addition, aggregate zero knowledge proofs are used to efficiently support proofs of various receipt attributes. We have implemented the system on Nokia NFC cellular phones and report in the paper performance evaluation results.
Peter Y. A. Ryan
No abstract is available for this record.
Shafi Goldwasser, Yael Tauman Kalai, Guy N. Rothblum
In this work we study interactive proofs for tractable languages. The (honest) prover should be efficient and run in polynomial time, or in other words a "muggle". The verifier should be super-efficient and run in nearly-linear time. These proof systems can be used for delegating computation: a server can run a computation for a client and interactively prove the correctness of the result. The client can verify the result's correctness in nearly-linear time (instead of running the entire computation itself). Previously, related questions were considered in the Holographic Proof setting by Babai, Fortnow, Levin and Szegedy, in the argument setting under computational assumptions by Kilian, and in the random oracle model by Micali. Our focus, however, is on the original interactive proof model where no assumptions are made on the computational power or adaptiveness of dishonest provers. Our main technical theorem gives a public coin interactive proof for any language computable by a log-space uniform boolean circuit with depth d and input length n. The verifier runs in time (n+d) • polylog(n) and space O(log(n)), the communication complexity is d • polylog(n), and the prover runs in time poly(n). In particular, for languages computable by log-space uniform NC (circuits of polylog(n) depth), the prover is efficient, the verifier runs in time n • polylog(n) and space O(log(n)), and the communication complexity is polylog(n). Using this theorem we make progress on several questions: We show how to construct short (polylog size) computationally sound non-interactive certificates of correctness for any log-space uniform NC computation, in the public-key model. The certificates can be verified in quasi-linear time and are for a designated verifier: each certificate is tailored to the verifier's public key. This result uses a recent transformation of Kalai and Raz from public-coin interactive proofs to one-round arguments. The soundness of the certificates is based on the existence of a PIR scheme with polylog communication. Interactive proofs with public-coin, log-space, poly-time verifiers for all of P. This settles an open question regarding the expressive power of proof systems with such verifiers. Zero-knowledge interactive proofs with communication complexity that is quasi-linear in the witness, length for any NP language verifiable in NC, based on the existence of one-way functions. Probabilistically checkable arguments (a model due to Kalai and Raz) of size polynomial in the witness length (rather than the instance length) for any NP language verifiable in NC, under computational assumptions.
Rafael Pass, Wei-Lung Dustin Tseng, Muthuramakrishnan Venkitasubramaniam
Few techniques for obtaining concurrent zero-knowledge exist; all require a complex and subtle analysis. We provide an arguably simpler and more general analysis of the oblivious simulation technique of Kilian and Petrank (STOC’01) while achieving the same bounds as Prabhakaran, Rosen and Sahai (FOCS’02). Using this analysis, and relying on tools recently developed by Ong and Vadhan (Eurocrypt’07, TCC’08) we are able to establish the following unconditional results: • every language inNP which has a ZK proof (resp. ZK argument, statistical ZK argument) also has a black-box concurrent ZK proof (resp. ZK argument, statistical ZK argument). • every languge which has a statistical ZK proof also has an ω(log n)-round black-box con-current statistical ZK proof.
Michael Backes, Matteo Maffei, Dominique Unruh
We devise an abstraction of zero-knowledge protocols that is accessible to a fully mechanized analysis. The abstraction is formalized within the applied pi-calculus using a novel equational theory that abstractly characterizes the cryptographic semantics of zero-knowledge proofs. We present an encoding from the equational theory into a convergent rewriting system that is suitable for the automated protocol verifier ProVerif. The encoding is sound and fully automated. We successfully used ProVerif to obtain the first mechanized analysis of (a simplified variant of) the Direct Anonymous Attestation (DAA) protocol. This required us to devise novel abstractions of sophisticated cryptographic security definitions based on interactive games. The analysis reported a novel attack on DAA that was overlooked in its existing cryptographic security proof. We propose a revised variant of DAA that we successfully prove secure using ProVerif.
Vipul Goyal, Payman Mohassel, Adam Smith
No abstract is available for this record.
Jens Groth, Amit Sahai
Non-interactive zero-knowledge proofs and non-interactive witness-indistinguishable proofs have played a significant role in the theory of cryptography. However, lack of efficiency has prevented them from being used in practice. One of the roots of this inefficiency is that non-interactive zero-knowledge proofs have been constructed for general NP-complete languages such as Circuit Satisfiability, causing an expensive blowup in the size of the statement when reducing it to a circuit. The contribution of this paper is a general methodology for constructing very simple and efficient non-interactive zero-knowledge proofs and non-interactive witness-indistinguishable proofs that work directly for groups with a bilinear map, without needing a reduction to Circuit Satisfiability. Groups with bilinear maps have enjoyed tremendous success in the field of cryptography in recent years and have been used to construct a plethora of protocols. This paper provides non-interactive witness-indistinguishable proofs and non-interactive zero-knowledge proofs that can be used in connection with these protocols. Our goal is to spread the use of non-interactive cryptographic proofs from mainly theoretical purposes to the large class of practical cryptographic protocols based on bilinear groups.
Jens Groth, Yuval Ishai
No abstract is available for this record.
Dario Catalano, Mario Di Raimondo, Dario Fiore, Mariagrazia Messina
Zero knowledge sets (ZKS), introduced by Micali, Rabin, and Kilian in 2003, allow a prover to commit to a secret set$S$in a way such that it can later prove, non interactively, statements of the form$x\in S$(or$x\notin S$), without revealing any further information (on top of what explicitly revealed by the inclusion/exclusion statements above) on$S$, not even its size. Later, Chaseabstracted away the Micali, Rabin, and Kilian's construction by introducing an elegant new variant of commitments that they called (trapdoor) mercurial commitments. Using this primitive, it was shown how to construct zero knowledge sets from a variety of assumptions (both general and number theoretic). This paper introduces the notion of trapdoor$q$-mercurial commitments (${\ssr qTMC}$s), a notion of mercurial commitment that allows the sender to commit to an ordered sequence of exactly$q$messages, rather than to a single one. Following the previous work, it is shown how to construct ZKS from${\ssr qTMC}$s and collision resistant hash functions. Then, it is presented an efficient realization of${\ssr qTMC}$s that is secure under the so called Strong Diffie Hellman (SDH) assumption, a number theoretic conjecture recently introduced by Boneh and Boyen. Using such scheme as basic building block, it is obtained a construction of ZKS that allows for proofs that are much shorter with respect to the best previously known implementations. In particular, for an appropriate choice of the parameters, our proofs are up to 33% shorter for the case of proofs of membership, and up to 73% shorter for the case of proofs of nonmembership. Experimental tests confirm practical time performances.
Aydin Behnad, Taraneh Eghlidos
A Publicly Veri able Secret Sharing (PVSS) scheme, as introduced by Stadler, has a feature where anyone, besides the participants, can verify the validity of the shares distributed by the dealer. Schoenmakers added a new feature, by providing a proof of correctness of the shares released by the players in the reconstruction process. This protocol is claimed to be an improvement on Stadler's and Fujisaki-Okamoto's, both in eciency and in the type of intractability assumptions. However, Young-Yung improved Schoenmakers' PVSS, using a Discrete-Log instead of a Decision Die-Hellman. In this paper, a new PVSS is presented, having an intrinsic di erence with its predecessors, that is, the participants can prove the validity of their given shares, implicitly, proving their membership by a zero-knowledge protocol. This feature prevents cheaters from participating in the reconstruction process to gain valid shares. Hence, the new proposed PVSS is more secure than previous ones. Besides, the dealer only sends the amount of commitments limited to the threshold value, regardless of the number of shareholders; this leads to a more dynamic protocol.