The Experts below are selected from a list of 53823 Experts worldwide ranked by ideXlab platform
John Watrous - One of the best experts on this subject based on the ideXlab platform.
-
Zero-Knowledge Proof Systems for QMA
SIAM Journal on Computing, 2020Co-Authors: Anne Broadbent, Fang Song, John WatrousAbstract:Prior work has established that all problems in NP admit classical zero-Knowledge Proof systems, and under reasonable hardness assumptions for quantum computations, these Proof systems can be made ...
-
zero Knowledge Proof systems for qma
Foundations of Computer Science, 2016Co-Authors: Anne Broadbent, Fang Song, John WatrousAbstract:Prior work has established that all problems in NP admit classical zero-Knowledge Proof systems, and under reasonable hardness assumptions for quantum computations, these Proof systems can be made secure against quantum attacks. We prove a result representing a further quantum generalization of this fact, which is that every problem in the complexity class QMA has a quantum zero-Knowledge Proof system. More specifically, assuming the existence of an unconditionally binding and quantum computationally concealing commitment scheme, we prove that every problem in the complexity class QMA has a quantum interactive Proof system that is zero-Knowledge with respect to efficient quantum computations. Our QMA Proof system is sound against arbitrary quantum provers, but only requires an honest prover to perform polynomial-time quantum computations, provided that it holds a quantum witness for a given instance of the QMA problem under consideration.
-
Zero-Knowledge Proof systems for QMA
2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), 2016Co-Authors: Anne Broadbent, Fang Song, John WatrousAbstract:Prior work has established that all problems in NP admit classical zero-Knowledge Proof systems, and under reasonable hardness assumptions for quantum computations, these Proof systems can be made secure against quantum attacks. We prove a result representing a further quantum generalization of this fact, which is that every problem in the complexity class QMA has a quantum zero-Knowledge Proof system. More specifically, assuming the existence of an unconditionally binding and quantum computationally concealing commitment scheme, we prove that every problem in the complexity class QMA has a quantum interactive Proof system that is zero-Knowledge with respect to efficient quantum computations. Our QMA Proof system is sound against arbitrary quantum provers, but only requires an honest prover to perform polynomial-time quantum computations, provided that it holds a quantum witness for a given instance of the QMA problem under consideration. The Proof system relies on a new variant of the QMA-complete local Hamiltonian problem in which the local terms are described by Clifford operations and standard basis measurements. We believe that the QMA-completeness of this problem may have other uses in quantum complexity.
Oded Goldreich - One of the best experts on this subject based on the ideXlab platform.
-
how to construct constant round zero Knowledge Proof systems for np
Journal of Cryptology, 1996Co-Authors: Oded Goldreich, Ariel KahanAbstract:Constant-round zero-Knowledge Proof systems for every language in $$\mathcal{N}\mathcal{P}$$ are presented, assuming the existence of a collection of claw-free functions. In particular, it follows that such Proof systems exist assuming the intractability of either the Discrete Logarithm Problem or the Factoring Problem for Blum integers.
-
On the Composition of Zero-Knowledge Proof Systems
SIAM Journal on Computing, 1996Co-Authors: Oded Goldreich, Hugo KrawczykAbstract:The wide applicability of zero-Knowledge interactive Proofs comes from the possibility of using these Proofs as subroutines in cryptographic protocols. A basic question concerning this use is whether the (sequential and/or parallel) composition of zero-Knowledge protocols is zero-Knowledge too. We demonstrate the limitations of the composition of zero-Knowledge protocols by proving that the original definition of zero-Knowledge is not closed under sequential composition; and that even the strong formulations of zero-Knowledge (e.g., black-box simulation) are not closed under parallel execution. We present lower bounds on the round complexity of zero-Knowledge Proofs, with significant implications for the parallelization of zero-Knowledge protocols. We prove that three-round interactive Proofs and constant-round Arthur--Merlin Proofs that are black-box simulation zero-Knowledge exist only for languages in BPP. In particular, it follows that the "parallel versions" of the first interactive Proofs systems presented for quadratic residuosity, graph isomorphism, and any language in NP, are not black-box simulation zero-Knowledge, unless the corresponding languages are in BPP. Whether these parallel versions constitute zero-Knowledge Proofs was an intriguing open questions arising from the early works on zero-Knowledge. Other consequences are a Proof of optimality for the round complexity of various known zero-Knowledge protocols and the necessity of using secret coins in the design of "parallelizable" constant-round zero-Knowledge Proofs.
-
Definitions and properties of zero-Knowledge Proof systems
Journal of Cryptology, 1994Co-Authors: Oded Goldreich, Yair OrenAbstract:In this paper we investigate some properties of zero-Knowledge Proofs, a notion introduced by Goldwasser, Micali, and Rackoff. We introduce and classify two definitions of zero-Knowledge: auxiliary-input zero-Knowledge and blackbox-simulation zero-Knowledge. We explain why auxiliary-input zero-Knowledge is a definition more suitable for cryptographic applications than the original [GMR1] definition. In particular, we show that any protocol solely composed of subprotocols which are auxiliary-input zero-Knowledge is itself auxiliary-input zero-Knowledge. We show that blackbox-simulation zero-Knowledge implies auxiliary-input zero-Knowledge (which in turn implies the [GMR1] definition). We argue that all known zero-Knowledge Proofs are in fact blackbox-simulation zero-Knowledge (i.e., we proved zero-Knowledge using blackbox-simulation of the verifier). As a result, all known zero-Knowledge Proof systems are shown to be auxiliary-input zero-Knowledge and can be used for cryptographic applications such as those in [GMW2]. We demonstrate the triviality of certain classes of zero-Knowledge Proof systems, in the sense that only languages in BPP have zero-Knowledge Proofs of these classes. In particular, we show that any language having a Las Vegas zero-Knowledge Proof system necessarily belongs to RP . We show that randomness of both the verifier and the prover, and nontriviality of the interaction are essential properties of (nontrivial) auxiliary-input zero-Knowledge Proofs.
-
A perfect zero-Knowledge Proof system for a problem equivalent to the discrete logarithm
Journal of Cryptology, 1993Co-Authors: Oded Goldreich, Eyal KushilevitzAbstract:An interactive Proof system is called perfect zero-Knowledge if the probability distribution generated by any probabilistic polynomial-time verifier interacting with the prover on input theorem ϕ , can be generated by another probabilistic polynomial-time machine which only gets ϕ as input (and interacts with nobody!). In this paper we present a perfect zero-Knowledge Proof system for a decision problem which is computationally equivalent to the Discrete Logarithm Problem. Doing so we provide additional evidence to the belief that perfect zero-Knowledge Proof systems exist in a nontrivial manner (i.e., for languages not in BPP ). Our results extend to the logarithm problem in any finite Abelian group.
-
ICALP - On the Composition of Zero-Knowledge Proof Systems
Automata Languages and Programming, 1Co-Authors: Oded Goldreich, Hugo KrawczykAbstract:A basic question concerning zero-Knowledge Proof systems is whether their (sequential and/or parallel) composition is zero-Knowledge too. This question is not only of natural theoretical interest, but is also of great practical importance as it concerns the use of zero-Knowledge Proofs as subroutines in cryptographic protocols.
Anne Broadbent - One of the best experts on this subject based on the ideXlab platform.
-
QMA-Hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge
2020Co-Authors: Anne Broadbent, Alex Bredariol GriloAbstract:We provide several advances to the understanding of the class of Quantum Merlin-Arthur Proof systems (QMA), the quantum analogue of NP. First, we answer a longstanding open question by showing that the Consistency of Local Density Matrices problem is QMA-complete under Karp reductions. We also show for the first time a commit-and-open computational zero-Knowledge Proof system for all of QMA as a quantum analogue of a "sigma" protocol. We then define a Proof of Quantum Knowledge, which guarantees that a prover is effectively in possession of a quantum witness in an interactive Proof, and show that our zero-Knowledge Proof system satisfies this definition. Finally, we show that our Proof system can be used to establish that QMA has a quantum non-interactive zero-Knowledge Proof system in the secret parameters setting. Our main technique consists in developing locally simulatable Proofs for all of QMA: this is an encoding of a QMA witness such that it can be efficiently verified by probing only five qubits and, furthermore, the reduced density matrix of any five-qubit subsystem can be computed in polynomial time and is independent of the witness. This construction follows the techniques of Grilo, Slofstra, and Yuen [FOCS 2019].
-
Zero-Knowledge Proof Systems for QMA
SIAM Journal on Computing, 2020Co-Authors: Anne Broadbent, Fang Song, John WatrousAbstract:Prior work has established that all problems in NP admit classical zero-Knowledge Proof systems, and under reasonable hardness assumptions for quantum computations, these Proof systems can be made ...
-
zero Knowledge Proof systems for qma
Foundations of Computer Science, 2016Co-Authors: Anne Broadbent, Fang Song, John WatrousAbstract:Prior work has established that all problems in NP admit classical zero-Knowledge Proof systems, and under reasonable hardness assumptions for quantum computations, these Proof systems can be made secure against quantum attacks. We prove a result representing a further quantum generalization of this fact, which is that every problem in the complexity class QMA has a quantum zero-Knowledge Proof system. More specifically, assuming the existence of an unconditionally binding and quantum computationally concealing commitment scheme, we prove that every problem in the complexity class QMA has a quantum interactive Proof system that is zero-Knowledge with respect to efficient quantum computations. Our QMA Proof system is sound against arbitrary quantum provers, but only requires an honest prover to perform polynomial-time quantum computations, provided that it holds a quantum witness for a given instance of the QMA problem under consideration.
-
Zero-Knowledge Proof systems for QMA
2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), 2016Co-Authors: Anne Broadbent, Fang Song, John WatrousAbstract:Prior work has established that all problems in NP admit classical zero-Knowledge Proof systems, and under reasonable hardness assumptions for quantum computations, these Proof systems can be made secure against quantum attacks. We prove a result representing a further quantum generalization of this fact, which is that every problem in the complexity class QMA has a quantum zero-Knowledge Proof system. More specifically, assuming the existence of an unconditionally binding and quantum computationally concealing commitment scheme, we prove that every problem in the complexity class QMA has a quantum interactive Proof system that is zero-Knowledge with respect to efficient quantum computations. Our QMA Proof system is sound against arbitrary quantum provers, but only requires an honest prover to perform polynomial-time quantum computations, provided that it holds a quantum witness for a given instance of the QMA problem under consideration. The Proof system relies on a new variant of the QMA-complete local Hamiltonian problem in which the local terms are described by Clifford operations and standard basis measurements. We believe that the QMA-completeness of this problem may have other uses in quantum complexity.
Hideaki Sone - One of the best experts on this subject based on the ideXlab platform.
-
Efficient card-based zero-Knowledge Proof for Sudoku
Theoretical Computer Science, 2020Co-Authors: Tatsuya Sasaki, Takaaki Mizuki, Daiki Miyahara, Hideaki SoneAbstract:Abstract In 2009, Gradwohl, Naor, Pinkas, and Rothblum proposed physical zero-Knowledge Proof protocols for Sudoku. That is, for a puzzle instance of Sudoku, their excellent protocols allow a prover to convince a verifier that there is a solution to the Sudoku puzzle and the prover knows it, without revealing any information about the solution. The possible drawback is that the existing protocols have an extractability error with a non-zero probability, or need special cards (such as scratch-off cards). Thus, in this study, we propose new protocols to perform zero-Knowledge Proof of Knowledge for Sudoku using a normal deck of playing cards with no extractability error. Our protocols can be easily implemented by humans with a reasonable number of playing cards.
-
Interactive Physical Zero-Knowledge Proof for Norinori
2019Co-Authors: Jean-guillaume Dumas, Tatsuya Sasaki, Takaaki Mizuki, Daiki Miyahara, Pascal Lafourcade, Hideaki SoneAbstract:Norinori is a logic game similar to Sudoku. In Norinori, a grid of cells has to be filled with either black or white cells so that the given areas contain exactly two black cells, and every black cell shares an edge with exactly one other black cell. We propose a secure interactive physical algorithm, relying only on cards, to realize a zero-Knowledge Proof of Knowledge for Norinori. It allows a player to show that he or she knows a solution without revealing it. For this, we show in particular that it is possible to physically prove that a particular element is present in a list, without revealing any other value in the list, and without revealing the actual position of that element in the list.
-
Physical Zero-Knowledge Proof for Makaro
2018Co-Authors: Xavier Bultel, Tatsuya Sasaki, Takaaki Mizuki, Daiki Miyahara, Jannik Dreier, Jean-guillaume Dumas, Pascal Lafourcade, Atsuki Nagao, Kazumasa Shinagawa, Hideaki SoneAbstract:Makaro is a logic game similar to Sudoku. In Makaro, a grid has to be filled with numbers such that: given areas contain all the numbers up to the number of cells in the area, no adjacent numbers are equal and some cells provide restrictions on the largest adjacent number. We propose a proven secure physical algorithm, only relying on cards, to realize a zero-Knowledge Proof of Knowledge for Makaro. It allows a player to show that he knows a solution without revealing it.
-
card based zero Knowledge Proof for sudoku
Fun with Algorithms, 2018Co-Authors: Tatsuya Sasaki, Takaaki Mizuki, Hideaki SoneAbstract:In 2009, Gradwohl, Naor, Pinkas, and Rothblum proposed physical zero-Knowledge Proof protocols for Sudoku. That is, for a puzzle instance of Sudoku, their excellent protocols allow a prover to convince a verifier that there is a solution to the Sudoku puzzle and that he/she knows it, without revealing any information about the solution. The possible drawback is that the existing protocols have a soundness error with a non-zero probability or need special cards (such as scratch-off cards). Thus, in this study, we propose new protocols to perform zero-Knowledge Proof for Sudoku that use a normal deck of playing cards and have no soundness error. Our protocols can be easily implemented by humans with a reasonable number of playing cards.
-
FUN - Card-Based Zero-Knowledge Proof for Sudoku
2018Co-Authors: Tatsuya Sasaki, Takaaki Mizuki, Hideaki SoneAbstract:In 2009, Gradwohl, Naor, Pinkas, and Rothblum proposed physical zero-Knowledge Proof protocols for Sudoku. That is, for a puzzle instance of Sudoku, their excellent protocols allow a prover to convince a verifier that there is a solution to the Sudoku puzzle and that he/she knows it, without revealing any information about the solution. The possible drawback is that the existing protocols have a soundness error with a non-zero probability or need special cards (such as scratch-off cards). Thus, in this study, we propose new protocols to perform zero-Knowledge Proof for Sudoku that use a normal deck of playing cards and have no soundness error. Our protocols can be easily implemented by humans with a reasonable number of playing cards.
Eyal Kushilevitz - One of the best experts on this subject based on the ideXlab platform.
-
Zero-Knowledge Proofs from Secure Multiparty Computation
SIAM Journal on Computing, 2009Co-Authors: Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit SahaiAbstract:A zero-Knowledge Proof allows a prover to convince a verifier of an assertion without revealing any further information beyond the fact that the assertion is true. Secure multiparty computation allows $n$ mutually suspicious players to jointly compute a function of their local inputs without revealing to any $t$ corrupted players additional information beyond the output of the function. We present a new general connection between these two fundamental notions. Specifically, we present a general construction of a zero-Knowledge Proof for an NP relation $R(x,w)$, which makes only a black-box use of any secure protocol for a related multiparty functionality $f$. The latter protocol is required only to be secure against a small number of “honest but curious” players. We also present a variant of the basic construction that can leverage security against a large number of malicious players to obtain better efficiency. As an application, one 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 that one-way functions exist, we get the following types of zero-Knowledge Proof protocols: (1) Approaching the witness length. If $C$ has constant depth over $\wedge,\vee,\oplus,\neg$ gates of unbounded fan-in, we get a zero-Knowledge Proof protocol with communication complexity $m\cdot{poly}(k)\cdot{polylog}(s)$, where $k$ is a security parameter. (2) “Constant-rate” zero-Knowledge. For an arbitrary circuit $C$ of size $s$ and a bounded fan-in, we get a zero-Knowledge protocol with communication complexity $O(s)+{poly}(k,\log s)$. Thus, for large circuits, the ratio between the communication complexity and the circuit size approaches a constant. This improves over the $O(ks)$ complexity of the best previous protocols.
-
A perfect zero-Knowledge Proof system for a problem equivalent to the discrete logarithm
Journal of Cryptology, 1993Co-Authors: Oded Goldreich, Eyal KushilevitzAbstract:An interactive Proof system is called perfect zero-Knowledge if the probability distribution generated by any probabilistic polynomial-time verifier interacting with the prover on input theorem ϕ , can be generated by another probabilistic polynomial-time machine which only gets ϕ as input (and interacts with nobody!). In this paper we present a perfect zero-Knowledge Proof system for a decision problem which is computationally equivalent to the Discrete Logarithm Problem. Doing so we provide additional evidence to the belief that perfect zero-Knowledge Proof systems exist in a nontrivial manner (i.e., for languages not in BPP ). Our results extend to the logarithm problem in any finite Abelian group.
