Questions tagged [interactive-proofs]
The interactive-proofs tag has no usage guidance.
31 questions
8
votes
0
answers
376
views
Proof of Knowledge & Rewinding Lemma
I'm somewhat confused about how the definition of a proof of knowledge relates to the Theorem 19.1 in Boneh-Shoup (http://toc.cryptobook.us/book.pdf), particularly in relation to Schnorr's protocol ...
5
votes
1
answer
109
views
Why does extractability not contradict zero-knowledge?
I was introduced to the QR-protocol that shows that a number y is a quadratic residue modulo x through an interactive protocol. The protocol is perfect zero-knowledge but it also proves that the ...
- 111
5
votes
1
answer
193
views
In Zero Knowledge Proofs (ZKP) why does the simulator and extractor get the power to rewind "time" and not some other superpower?
Why was the simulator/extractor specifically given the power to rewind "time" instead of a different super power?
Was it defined in the first ZKP paper that the simulator and extractor would ...
- 195
4
votes
1
answer
139
views
Why does the challenge need to be prime in Wesolowski's succinct argument of $y=x^{e}$?
In Wesolowski's VDF (verifiable delay function) a prover produces a pair $(x, y)$ and needs to argue to the verifier that the pair satisfies $y = x^e \pmod N$ for some $e$ computable to both. The ...
- 225
4
votes
2
answers
230
views
Rigorous Proof on Malicious Zero-Knowledge Property of Schnorr Protocol
Let us recall the Schnorr Protocol, following Chris Peikert's excellent Notes on the Theory of Cryptography.
Protocol. Let $G=\langle g \rangle$ be a cyclic group of order $q$. We consider an ...
- 246
3
votes
1
answer
495
views
The significance of rewinding a simulation in an ZK interactive proof
I'm reading Matthew Green's blog post on ZK Interactive Proofs
I don't understand the part where he explains how using a time machine shows that the prover is leaking zero information
Specifically, ...
- 2,316
3
votes
2
answers
123
views
Definition of soundness for interactive proof systems
I am reading the Wikipedia page for Interactive proof systems and am having trouble understand the notation in the definition of soundness, many of which is left unspecified.
Given a formal language ...
- 133
2
votes
2
answers
516
views
How to calculate soundness error of a sigma protocol?
How do I calculate the soundness error of a sigma protocol, such as Schnorr's interactive protocol for knowledge of a discrete logarithm?
2
votes
1
answer
90
views
Interactive Proofs: Why $\delta \lt \frac 13$ for Soundness & Completeness?
From a text on Interactive Proofs
$x \in {0,1}^n$ is input
$V$ is verifier
$P$ is prover
$r$ is $V$'s internal randomness
$P$ provides a value $y$ which is claimed to be equal to $f(x)$
(Completeness)...
- 2,316
2
votes
1
answer
93
views
Deterministic vs probabilistic adversaries in a proof-of-knowledge context
In several security games, it is safe to replace probabilistic polynomial-time adversaries with deterministic ones without reducing the adversarial advantage. The relevant argument can be found here.
...
- 23
2
votes
1
answer
97
views
Languages $L$ that have perfect zero-knowledge that do not have any $AM$ proof system that is perfect or zero-knowledge on $L$
In the GMR[85] paper, a conjecture is made in section 3.7:
There exist languages $L$ that have perfect or statistical zero-knowledge proof systems, but do not have any Arthur-Merlin proof system that ...
2
votes
1
answer
379
views
GKR Protocol - is it one Sum-Check per layer or is it one Sum-Check per gate?
I am reading about GKR protocol from Justin Thaler's book - Proofs, Arguments & Zero Knowledge
On Page 59,
In the first message, $P$ tells $V$ the (claimed) output(s) of the circuit. The protocol ...
- 2,316
2
votes
1
answer
77
views
3-Coloring Zero-Knowledge Proof: rational verifier?
I'm studying the application of Zero-Knowledge Proofs (ZKP) to graph 3-colorability. I haven't fully understood the need for randomness in the verifier's choice of the edge to challenge the prover ...
- 23
2
votes
1
answer
246
views
Knowledge extractors in proofs of knowledge
I'm somewhat new to cryptography and I've been looking at knowledge extractors in proofs of knowledge and I am a little confused by the use of somewhat different definitions.
In textbooks or early ...
- 21
2
votes
0
answers
47
views
Accumulation Updater for Cryptography
I want update in place for sorted element list and proof for accumulator encoding of only element updated. I try to find technique similar to this, but only GCTI pop up and similar methods.
It must ...
- 21
2
votes
0
answers
70
views
Interactive proof of possession of a signed message
Suppose Alice has a verifiable (message, signature) pair from Cedric, who would not cooperate and routinely uses an algo (ecdsa, eddsa, rsa, or insert yours here) to sign messages.
Alice wants to ...
- 141
2
votes
1
answer
288
views
Which hash functions have the mathematical properties required to prove data availability?
I'm looking for a specific keyed hash function with security properties that allow it to be used for a step in an interactive proof, in which a Verifier has some message, and the Prover needs to prove ...
- 136
1
vote
1
answer
275
views
Can we achieve statistical Completeness, Soundness and Zero Knowledge in an Interactive Proof?
The question is mainly stated in the title, sorry for it being a bit small of a question. I was reading about ZK proofs and I was wondering what do we know about their limits only their properties. Do ...
- 992
1
vote
1
answer
187
views
Small proofs for large sums
Suppose we have $n$ public elements $x_1,\ldots,x_n$, say elements of an elliptic curve $E$ (but maybe also $\mathbb{F}_p^*$ or $\mathbb{Z}_N^*$ with multiplication instead of sum), and an element $x$ ...
- 155
1
vote
1
answer
191
views
GKR Protocol - does it matter which gate in each layer the SumCheck Protocol is run on?
I am reading about GKR protocol from Justin Thaler's book - Proofs, Arguments & Zero Knowledge
Page 61, Lemma 4.7
$W_i(z) = \sum_{b,c \in \lbrace 0,1 \rbrace^{k_{i+1}}} add_i (z,b,c)\cdot (W_{i+1}(...
- 2,316
1
vote
1
answer
131
views
Amplifying the completeness and soundness of a proof scheme
A (interactive) proof system for a language $\mathcal{L}$ is defined by two algorithms $\mathcal{P}$, a prover, and $\mathcal{V}$, an efficient verifier, with the following requirements:
Completeness:...
- 509
1
vote
1
answer
150
views
Why I always obtain this soundness bound in parallel repetition of interactive proof systems
Fix an interactive proof system $(P,V)$ and denote by $(P_k,V_k)$ an interactive proof system in which the parties play in parallel $k$ copies of $(P,V)$ and for which $V_k$ accepts if and only if $V$ ...
- 762
1
vote
1
answer
105
views
Why is zero knowledge defined via simulation w.r.t. inputs *in* the language?
In every definition of zero-knowledge (ZK) proof systems that I have seen (see, e.g., this one on Wikipedia, or this primer by Goldreich), a proof system $\langle p, v \rangle$ for a language $L$ is ...
1
vote
0
answers
58
views
On public coin zero knowledge protocols
Goldwasser and Sipser proved that a private coin interactive proof system can be converted into a public coin system. This conversion preserves round complexity (up to an additive factor of 2), but ...
- 83
1
vote
0
answers
225
views
Compiling a ZK-SNARK into a Signature of Knowledge by way of FS/BCS transformations
In a sigma protocol, a well known transformation to a signature is Fiat-Shamir, where message derived randomness is mixed into the randomness of the challenge. A natural example is Schnorr signatures. ...
- 467
0
votes
1
answer
48
views
GKR & Sum-check Protocol - how are the random numbers split across different variables?
I am reading about GKR protocol from Justin Thaler's book - Proofs, Arguments & Zero Knowledge
Section 4.6.5 - Page 64 - Description of GKR Protocol
$S_0$ is the number of gates in layer 0.
$k_0 = ...
- 2,316
0
votes
1
answer
92
views
Sumcheck Protocol: How to represent a matrix as an MLE which takes row & column numbers as parameters?
This is from Justin Thaler's book - Proofs, Arguments & Zero Knowledge
Page 43
For it to make sense to talk about multilinear extensions, we need to view the adjacency matrix $A$ not as a matrix, ...
- 2,316
0
votes
1
answer
182
views
Is this Zero Knowledge interactive proof for Quadratic non-residuosity proper?
This is from Alan Rosen's video on Interactive proofs - https://youtu.be/6uGimDYZPMw?t=1754
Here the proof is that
the Verifier gets a random bit $b$ .
If $b = 0$, then Verifier gets a random $y \...
- 2,316
0
votes
0
answers
54
views
What's the simplest and most instructive polynomial interactive oracle proof?
I'm writing my thesis about Zero-Knowledge Proofs and I'm trying to write a short and instructive introduction to zk-SNARKs at the moment (I have to stay within a certain limit of pages).
I introduced ...
- 111
0
votes
0
answers
45
views
Can ring signatures be considered as non interactive set membership proofs?
Can ring signatures be considered as non interactive set membership proofs?
For example, if the message msg is set to null, can the ring signature scheme proposed by Rivest et al. be regarded as a non ...
- 115
0
votes
0
answers
23
views
Trustless anonymization problem
Imagine a message exchange system where every actor publicly exposes his identity. In such a system, Alice wants to exchange messages with an entity run by Bob, but neither Alice nor Bob wants to ...
- 101