Tagged Questions

The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
64 views

Is there a stand-alone statistical ZK argument with concurrent knowledge extraction?

Is any known construction for an interactive argument of knowledge that is stand-alone statistical zero-knowledge, and allows concurrent knowledge extraction? This is a weakening of my previous ...
2
votes
2answers
108 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
157 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 ...
3
votes
1answer
139 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
258 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
89 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
72 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
588 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
182 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
164 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
70 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
161 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 ...
6
votes
1answer
437 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
243 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
701 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
263 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
523 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
403 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 ...