Questions tagged [interactive-proofs]
The interactive-proofs tag has no usage guidance.
15
questions
1
vote
1
answer
37
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:...
- 445
3
votes
1
answer
56
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
0
votes
1
answer
68
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,167
4
votes
1
answer
97
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 ...
- 181
7
votes
0
answers
234
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 ...
1
vote
1
answer
64
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$ ...
- 722
2
votes
2
answers
249
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
0
answers
46
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
42
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
85
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
0
votes
0
answers
84
views
How does parallel repetition preserve Honest Verifier Zero Knowledge?
I do not understand how to formally argue using the simulator of the original Honest Verifier Zero Knowledge Proof?
2
votes
1
answer
224
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,167
2
votes
1
answer
66
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,167
1
vote
0
answers
132
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. ...
- 413
1
vote
1
answer
148
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 ...
- 848