Questions tagged [zero-knowledge]
The zero-knowledge tag has no usage guidance.
10
questions with no upvoted or accepted answers
18
votes
0
answers
360
views
Does Factoring have a Statistical Zero Knowledge Proof?
The title should be pretty self-explanatory, but to be more precise, consider the decision version of factoring, which is given input $(x,k)$, where $x$ and $k$ are binary encodings of integers, to ...
- 3,718
11
votes
0
answers
190
views
generalizing Ben-Or et al's two-prover bit commitment scheme beyond bits
In "Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions" by Ben-Or, Goldwasser, Kilian, and Wigderson, the authors introduce a bit commitment protocol as a subroutine to their ...
- 4,381
4
votes
0
answers
104
views
Is perfect zero knowledge sequentially composable without auxiliary input?
It is known that plain and computational zero knowledge proof systems are not sequentially composable without auxiliary input (see for example http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1....
- 41
3
votes
0
answers
24
views
(Classical) Zero Knowledge protocol with quantum poly time simulator
We have lower bounds for classical zero-knowledge protocols (eg we cannot have 3-round zero-knowledge protocols for NP, with negligible soundness and black-box simulation). However, some of these ...
- 31
2
votes
0
answers
91
views
Non-interactive proof showing the multiplication of an encrypted matrix with a public vector is as claimed
Consider a "fantasy sports" setting where $m$ contestants each pick $k$ players from a set of $n$ players before a game. The state can be represented by a Boolean matrix $\mathbf{A}$ of size ...
- 393
2
votes
0
answers
119
views
concurrent non-malleable *statistical* zero knowledge
According to Huijia Lin and
Rafael Pass's "Concurrent Non-Malleable Zero Knowledge with
Adaptive Inputs" paper:
if collision-resistant hash functions exist, then
"there exists a $\omega\left(\log^...
user6973
2
votes
0
answers
193
views
Are there efficient black-box constructions of sigma-protocols for SAT?
Is there a known black-box construction for the following implication?
non-interactive string commitment that stretches additively by an
amount which does not depend on the string being ...
user6973
0
votes
0
answers
34
views
Is SZK dependent on the verifier’s model of computation?
What if instead of a probabilistic TM, the verifier in the definition of SZK was a quantum TM?
How would this affect its relation to other classes? Would Statistical Difference still be a complete ...
0
votes
0
answers
144
views
Is it possible to create an arbitrary $\textsf{NP}$-complete statement of chosen size $n$ and witness in polynomial time?
This questions came in my mind as I was reading the concept of hidden-bits of Feige, Lapidot and Shamir in "Multiple non-interactive zero knowledge proofs based on a single random string". There is ...
- 161
-3
votes
0
answers
53
views
Why isn’t BQP in SZK?
It has been proven that $BQP \not\subset SZK$ (see p7 of this paper).
On the other hand, Vadhan’s thesis on complete problems for SZK presents an easy reduction for why $BPP \subset SZK$ (Proposition ...