Questions tagged [zero-knowledge]
The zero-knowledge tag has no usage guidance.
31
questions
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 ...
-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 ...
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
1
vote
1
answer
168
views
Graph associated to a mathematical statement (for the purpose of zero-knowledge proofs)
I'll preface this question by saying I have very little (zero!) knowledge of theoretical computer science, and this post is a genuine attempt to understand something, even if at an intuitive level, ...
- 5,290
3
votes
1
answer
181
views
Zero Knowledge proofs of knowledge
Is there Zero Knowledge Proof of Knowledge protocol for Hash function? (If h(v)=w) without revealing v to the anyone can we prove that we know 'v')
- 256
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
1
answer
89
views
Reference Request: soundness in a ZKP achieved by walking along a doubly-stochastic Markov chain?
Consider the following variant of a zero-knowledge proof that two graphs, $G_1$ and $G_2$, given by adjacency matrices $M_1$ and $M_2$, respectively, are not isomorphic.
Here Peggy the prover wants ...
CommunityBot
- 1
0
votes
1
answer
139
views
is Zero knowledge Proof same as commitment schemes? [closed]
I am studying about the zero knowledge proofs and I am looking for a practical (example based) approach to undrestand its process. I have studied the theory a little bit and I find it interesting yet ...
CommunityBot
- 1
0
votes
1
answer
372
views
3-coloring graph zero-knowledge proof [closed]
I was researching about zero-knowledge proofs and in this link http://web.mit.edu/~ezyang/Public/graph/svg.html I've seen the exercise question:
Currently, you can only select adjacent pairs of nodes ...
- 46
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 ...
CommunityBot
- 1
16
votes
1
answer
484
views
Complexity classes for proofs of knowledge
Prompted by a question Greg Kuperberg asked me, I'm wondering if there are any papers that define and study complexity classes of languages admitting various kinds of proofs of knowledge. Classes ...
- 16.3k
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
11
votes
4
answers
263
views
Minimum communication cost for zero knowledge proofs of three colorability
Goldreich et al.'s proof that three colorability has zero knowledge proofs uses bit commitment for an entire coloring of the graph in each round [1]. If a graph has $n$ vertices and $e$ edges, a ...
- 3,243
7
votes
2
answers
2k
views
Zero knowledge proof for value of a hash function
Is there a zero knowledge proof which demonstrates that Peggy knows a value v whose hash-function is w?
In my understanding of the general theorems on zero-k there EXISTS such a function if the has-...
- 2,799
8
votes
1
answer
216
views
question about concurrent ZK paper by Prabhakaran & Sahai
Concurrent Zero Knowledge Proofs with Logarithmic
Round-Complexity
Page numbers are from the paper itself, and not the pdf.
From page 3,
"An interactive proof system is said to be black-box (...
- 11.9k
3
votes
2
answers
363
views
How are PCPs and ZKPs related?
I only have a (very) introductory knowledge about the Hardness of Approximation and PCP theorem, and I am wondering if it has any specific implications (or can somehow be studied) with Zero Knowledge ...
- 1,897
4
votes
1
answer
325
views
Are there any implementations for zero-knowledge proofs of NP-complete problems?
It's been known for a long time that any claim in NP has a zero-knowledge proof for it. Has anybody actually implemented a zero-knowledge proof system for a NP-complete language? Using a search engine,...
- 401
3
votes
1
answer
214
views
How to properly define a zero-knowledge proof system with oracle access
An $IP$ system $(P,V)$ is zero-knowledge (ZK) for some language $L$ if for every probabilistic polynomial-time verifer $V^*$ there exists a probabilistic polynomial-time algorithm $S$ for every $x\in ...
- 16.3k
3
votes
3
answers
698
views
Zero knowledge verification of an encryption protocol
This seems like a straightforward application of zero knowledge techniques, but an answer eludes me.
Alice and Bob claim to have devised an encryption scheme: specifically, they claim to possess ...
- 16.3k
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^...
- 21.4k
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 ...
CommunityBot
- 1
4
votes
3
answers
1k
views
NIZK proofs: Why is the prove function necessary?
In NIZK proofs, the prover can generate its proof for statement $y$ and witness $w$ using
$$\pi \gets \mathrm{Prove}(\sigma,y,w)\text{,}$$
where $\sigma$ is the common reference string. Source: ...
- 401
5
votes
2
answers
273
views
Instances of Noninteractive Zero knowlege Proofs
I am working on Cryptographic protocols. While I was doing a survey, I required some "Non-Interactive Zero Knowledge Proofs" (NIZK) which I can use.
I can only find transformations between different ...
- 401
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
2
votes
1
answer
170
views
"forward-secure" zero knowledge protocols
Has anything been done on the modification of the zero knowledge condition
where the distinguisher has access to the witness used by the prover and
the random bits used by the algorithm that ...
- 1,242
0
votes
1
answer
86
views
Jointly Establishing a Shared Random String for NIZK proofs of knowledge
If OWFs exist, then a Shared Random String for
NIZK proofs (of membership) can be established by:
verifier commits a random string of the same length using statistically hiding commitment
prover ...
- 1,242
12
votes
1
answer
2k
views
Why is Feige-Fiat-Shamir not Zero Knowledge without sign bits?
In chapter 10 of HAC (10.4.2), we see the well-known Feige-Fiat-Shamir identification protocol based on a zero-knowledge proof using the (presumed) difficulty of extracting square roots modulo a ...
- 16.3k
3
votes
2
answers
335
views
Zero knowledgeness of a simple protocol
Say there's a public encryption scheme whose public key is $p_k$ and secret key is $s_k$. Prover $P$ wants to convince verifier $V$ that he knows $s_k$. The protocol is:
$V$ uniformly generates $m$ ...
- 11
6
votes
1
answer
629
views
Existence of zero-knowledge proof for location
N items have been placed at specific points on a map. A prize is awarded to the first person who turns in a list with the location of all N items. The location of each item must fall with a distance ...
- 21.4k
10
votes
1
answer
564
views
Interactive Proof for HORN-SAT?
Is there a way that a prover can convince a verifier that some HORN-SAT expression is satisfiable?
Of course this might seem silly, since there are linear time algorithms for HORN-SAT. On the other ...
- 575