Questions tagged [zero-knowledge]
The zero-knowledge tag has no usage guidance.
25
questions
0
votes
0answers
142 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 ...
2
votes
1answer
79 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 ...
0
votes
1answer
98 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 ...
-1
votes
1answer
238 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 ...
16
votes
0answers
290 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 ...
16
votes
1answer
415 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 ...
4
votes
0answers
79 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....
11
votes
4answers
220 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 ...
2
votes
2answers
154 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 ...
4
votes
1answer
307 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,...
3
votes
1answer
168 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 ...
3
votes
3answers
559 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 ...
2
votes
0answers
112 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^...
2
votes
0answers
118 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 ...
4
votes
3answers
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: ...
8
votes
1answer
200 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
votes
0answers
181 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 ...
0
votes
1answer
83 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 ...
2
votes
1answer
165 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 ...
7
votes
2answers
1k 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-...
5
votes
2answers
262 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 ...
12
votes
1answer
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 ...
3
votes
2answers
329 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$ ...
6
votes
1answer
608 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 ...
10
votes
1answer
520 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 ...
