Follow blockchain research across journals, conferences, and preprint repositories.
370 results · page 13 of 16
Mira Belenkiy, Jan Camenisch, Melissa Chase, Markulf Kohlweiss · 6 authors
No abstract is available for this record.
Aggelos Kiayias, Hong-Sheng Zhou
No abstract is available for this record.
Payman Mohassel, Enav Weinreb
No abstract is available for this record.
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.
Rafael Pass, Muthuramakrishnan Venkitasubramaniam
No abstract is available for this record.
Oleg Verbitsky
We show that the Double Coset Membership problem for permutation groups possesses perfect zero-knowledge proofs.
Oleg Verbitsky
We design a perfect zero-knowledge proof system for recognition if two permutation groups are conjugate.
Dennis Hofheinz
The selective decommitment problem can be described as follows: assume an adversary receives a number of commitments and then may request openings of, say, half of them. Do the unopened commitments remain secure? Although this question arose more than twenty years ago, no satisfactory answer could be presented so far. We answer the question in several ways: 1. If simulation-based security is desired (i.e., if we demand that the adversary's output can be simulated by a machine that does not see the unopened commitments), then security is not achievable for non-interactive or perfectly binding commitment schemes via black-box reductions to standard cryptographic assumptions. However, we show how to achieve security in this sense with interaction and a non-black-box reduction to one-way permutations. 2. If only indistinguishability of the unopened commitments from random commitments is desired, then security is not achievable for (interactive or non-interactive) perfectly binding commitment schemes, via black-box reductions to standard cryptographic assumptions. However, any statistically hiding scheme does achieve security in this sense. Our results give an almost complete picture when and how security under selective openings can be achieved. Applications of our results include: • Essentially, an encryption scheme must be non-committing in order to achieve provable security against an adaptive adversary. • When implemented with our secure commitment scheme, the interactive proof for graph 3-coloring due to Goldreich et al. becomes zero-knowledge under parallel composition. On the technical side, we develop a technique to show very general impossibility results for black-box proofs.
Kaoru Kurosawa, Shigeo Tsujii
No abstract is available for this record.
Mike Burmester, Fred Piper, Yvo Desmedt, Michael J. Walker
No abstract is available for this record.
Gilles Brassard, Claude Crépeau
No abstract is available for this record.
Tatsuaki Okamoto, Kazuo Ohta
No abstract is available for this record.
Moti Yung
No abstract is available for this record.
Joan Boyar, René Peralta
No abstract is available for this record.
Charles Rackoff, Daniel Simón
No abstract is available for this record.
Toshiya Itoh, Yuji Ohta, Hiroki Shizuya
No abstract is available for this record.
Ivan Damgård
No abstract is available for this record.
Ivan Damgård
No abstract is available for this record.
Hoeteck Wee
No abstract is available for this record.
Hirotada Kobayashi
This paper studies the complexity classes QZK and HVQZK of problems having a quantum computational zero-knowledge proof system and an honest-verifier quantum computational zero-knowledge proof system, respectively. The results proved in this paper include: (a) HVQZK = QZK, (b) any problem in QZK has a public-coin quantum computational zero-knowledge proof system, (c) any problem in QZK has a quantum computational zero-knowledge proof system of perfect completeness, and (d) any problem in QZK has a three-message public-coin quantum computational zero-knowledge proof system of perfect completeness with arbitrarily small constant error in soundness. All the results above are unconditional and do not rely any computational assumptions. For the classes QPZK, HVQPZK, and QSZK of problems having a quantum perfect zero-knowledge proof system, an honest-verifier quantum perfect zero-knowledge proof system, and a quantum statistical zero-knowledge proof system, respectively, the following new properties are proved: (e) HVQPZK = QPZK, (f) any problem in QPZK has a public-coin quantum perfect zero-knowledge proof system, (g) any problem in QSZK has a quantum statistical zero-knowledge proof system of perfect completeness, and (h) any problem in QSZK has a three-message public-coin quantum statistical zero-knowledge proof system of perfect completeness with arbitrarily small constant error in soundness. It is stressed that our proofs are direct and do not use complete promise problems or those equivalents. This gives a unified framework that works well for all of quantum perfect, statistical, and computational zero-knowledge proofs, and enables us to prove properties even on the computational and perfect zero-knowledge proofs for which no complete promise problems are known.
Gilles Brassard, Claude Crépeau
A zero-knowledge interactive proof is a protocol by which Alice can convince a polynomially-bounded Bob of the truth of some theorem without giving him any hint as to how the proof might proceed. Under cryptographic assumptions, we give a general technique for achieving this goal for every problem in NP. This extends to a presumably larger class, which combines the powers of non-determinism and randomness. Our protocol is powerful enough to allow Alice to convince Bob of theorems for which she does not even have a proof: it is enough for Alice to convince herself probabilistically of a theorem, perhaps thanks to her knowledge of some trap-door information, in order for her to be able to convince Bob as well, without compromising the trap-door in any way. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
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
Masayuki Abe, Serge Fehr
Abstract The notion of non-interactive zero-knowledge (NIZK) is of fundamental importance incryptography. Despite the vast attention the concept of NIZK has attracted since its introduction, one question has remained very resistant: Is it possible to construct NIZK schemesfor any NP-language with statistical or even perfect ZK? Groth, Ostrovsky and Sahai recently positively answers to the question by presenting a couple of elegant constructions. However,their schemes pose a limitation on the length of the proof statement to achieve adaptive soundness against dishonest provers who may choose the target statement depending on thecommon reference string (CRS). In this work, we first present a very simple and efficient adaptively-sound perfect NIZKargument system for any NP-language. Besides being the first adaptively-sound statistical NIZK argument for all NP that does not pose any restriction on the statements to be proven,it enjoys a number of additional desirable properties: it allows to re-use the CRS, it can handle arithmetic circuits, and the CRS can be set-up very efficiently without the need foran honest party. We then show an application of our techniques in constructing efficient NIZK schemes for proving arithmetic relations among committed secrets, whereas previousmethods required expensive generic NP-reductions. The security of the proposed schemes is based on a strong non-standard assumption,an extended version of the so-called Knowledge-of-Exponent Assumption (KEA) over bilinear groups. We give some justification for using such an assumption by showing that thecommonly-used approach for proving NIZK arguments sound does not allow for adaptivelysound statistical NIZK arguments (unless NP ae P/poly). Furthermore, we show that theassumption used in our construction holds with respect to generic adversaries that do not exploit the specific representation of the group elements. We also discuss how to avoid thenon-standard assumption in a pre-processing model.