Questions tagged [zero-knowledge]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
0 answers
89 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 ...
1 vote
1 answer
163 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, ...
3 votes
1 answer
179 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')
  • 33
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 ...
  • 852
0 votes
1 answer
138 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 ...
  • 101
0 votes
1 answer
367 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 ...
  • 119
18 votes
0 answers
355 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 ...
  • 3,718
16 votes
1 answer
482 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
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
260 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 votes
2 answers
337 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 ...
  • 831
4 votes
1 answer
322 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
1 answer
213 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
3 answers
697 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
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^...
user avatar
2 votes
0 answers
179 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 ...
user avatar
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: ...
  • 143
8 votes
1 answer
215 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 (...
user avatar
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 ...
0 votes
1 answer
84 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 ...
user avatar
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 ...
user avatar
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-...
  • 71
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 ...
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 ...
  • 1,003
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$ ...
  • 779
6 votes
1 answer
628 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 ...
  • 173
10 votes
1 answer
561 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 ...