The zero-knowledge tag has no wiki summary.
2
votes
0answers
51 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 ...
2
votes
0answers
41 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
196 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
154 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 ...
1
vote
0answers
69 views
Zero-Knowledge from a semi-trusted random beacon and weak timestamping
For this question, assume that one-way functions exist.
The standard zero-knowledge proof system for NP can easily be implemented with a
random beacon and trusted timestamping service instead ...
10
votes
0answers
140 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 ...
1
vote
1answer
56 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
150 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 ...
4
votes
1answer
300 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 ...
5
votes
2answers
230 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
361 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
240 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
279 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
337 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 ...
