Questions tagged [interactive-proofs]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
63 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}(...
user93353's user avatar
  • 2,211
1 vote
1 answer
63 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 ...
Lewis Hammond's user avatar
1 vote
0 answers
29 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 ...
884d88baaa's user avatar
0 votes
0 answers
17 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 ...
s0me0ne's user avatar
  • 101
3 votes
1 answer
91 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 ...
Chris's user avatar
  • 236
4 votes
1 answer
105 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 ...
Reggad's user avatar
  • 141
1 vote
1 answer
106 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 ...
user93353's user avatar
  • 2,211
0 votes
1 answer
52 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, ...
user93353's user avatar
  • 2,211
1 vote
1 answer
77 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:...
vxek's user avatar
  • 467
3 votes
2 answers
88 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 ...
Abced Decba's user avatar
0 votes
1 answer
120 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 \...
user93353's user avatar
  • 2,211
4 votes
1 answer
113 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 ...
MERTON's user avatar
  • 181
7 votes
0 answers
300 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 ...
George Herbert's user avatar
1 vote
1 answer
98 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$ ...
Bean Guy's user avatar
  • 742
2 votes
2 answers
369 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?
George Herbert's user avatar
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 ...
Junghee Kim's user avatar
2 votes
0 answers
53 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 ...
wick's user avatar
  • 141
2 votes
1 answer
148 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 ...
geust213's user avatar
2 votes
1 answer
346 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, ...
user93353's user avatar
  • 2,211
2 votes
1 answer
72 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)...
user93353's user avatar
  • 2,211
1 vote
0 answers
173 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. ...
Lev's user avatar
  • 443
1 vote
1 answer
205 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 ...
tur11ng's user avatar
  • 962