# Questions tagged [interactive-proofs]

The tag has no usage guidance.

29 questions
Filter by
Sorted by
Tagged with
335 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 ...
85 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 ...
139 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 ...
• 161
129 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
188 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
426 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,252
109 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
444 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?
79 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,252
71 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. ...
84 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 ...
261 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,252
63 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 ...
202 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
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 ...
64 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
246 views

### What efficient keyed hash algorithm can be used 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 ...
• 129
1 vote
237 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 ...
• 982
1 vote
134 views

• 2,252
70 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,252
156 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,252