As of May 31, 2023, we have updated our Code of Conduct.

Questions tagged [zero-knowledge]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
18 votes
0 answers

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 ...
Henry Yuen's user avatar
  • 3,718
16 votes
1 answer

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 ...
Scott Aaronson's user avatar
12 votes
1 answer

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 ...
Fixee's user avatar
  • 1,003
11 votes
4 answers

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 ...
Geoffrey Irving's user avatar
11 votes
0 answers

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 ...
Noam Zeilberger's user avatar
10 votes
1 answer

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 ...
Shaun Harker's user avatar
8 votes
1 answer

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 (...
user avatar
7 votes
2 answers

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-...
Clion's user avatar
  • 71
6 votes
1 answer

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 ...
this.josh's user avatar
  • 173
5 votes
2 answers

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 ...
Maverickgugu's user avatar
4 votes
3 answers

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: ...
Johannes's user avatar
  • 143
4 votes
1 answer

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,...
Itai Bar-Natan's user avatar
4 votes
0 answers

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
amm's user avatar
  • 41
3 votes
2 answers

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$ ...
Cyker's user avatar
  • 779
3 votes
3 answers

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 ...
Suresh Venkat's user avatar
3 votes
2 answers

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 ...
Subhayan's user avatar
  • 831
3 votes
1 answer

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')
Vinay's user avatar
  • 33
3 votes
1 answer

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 ...
Marcos Villagra's user avatar
3 votes
0 answers

(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 ...
vk19's user avatar
  • 31
3 votes
1 answer

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 ...
Mark S's user avatar
  • 956
2 votes
1 answer

"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 ...
user avatar
2 votes
0 answers

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 ...
Madhav Jha's user avatar
2 votes
0 answers

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^...
user avatar
2 votes
0 answers

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 ...
user avatar
1 vote
1 answer

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, ...
Emilio Ferrucci's user avatar
0 votes
1 answer

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 ...
picolo's user avatar
  • 101
0 votes
1 answer

3-coloring graph zero-knowledge proof [closed]

I was researching about zero-knowledge proofs and in this link I've seen the exercise question: Currently, you can only select adjacent pairs of nodes ...
EralpB's user avatar
  • 119
0 votes
1 answer

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 ...
user avatar
0 votes
0 answers

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 ...
Irna Mosa's user avatar
0 votes
0 answers

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 ...
Burak's user avatar
  • 161
-3 votes
0 answers

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 ...
Irna Mosa's user avatar