Skip to main content

Questions tagged [interactive-proofs]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
5 votes
1 answer
74 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 ...
Niko Wolf's user avatar
2 votes
1 answer
59 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 ...
Tom_tomato's user avatar
2 votes
1 answer
81 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 ...
itstwelvehere's user avatar
0 votes
2 answers
206 views

What hash algorithm/construction to use to prove Data Availability?

I'm looking for a keyed hash function to use as part of an interactive proof where the Prover proves that they have the entirety of a data block that the Verifier also has. In my application I'm able ...
AJMansfield's user avatar
0 votes
0 answers
38 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 ...
user109993's user avatar
0 votes
1 answer
35 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 = ...
user93353's user avatar
  • 2,150
1 vote
1 answer
126 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,150
1 vote
1 answer
82 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
45 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
21 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
105 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
130 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 ...
CLox's user avatar
  • 151
2 votes
1 answer
238 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,150
0 votes
1 answer
67 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,150
1 vote
1 answer
102 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
  • 477
3 votes
2 answers
108 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
155 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,150
4 votes
1 answer
128 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
8 votes
0 answers
331 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
122 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
  • 752
2 votes
2 answers
436 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
61 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
191 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
3 votes
1 answer
408 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,150
2 votes
1 answer
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)...
user93353's user avatar
  • 2,150
1 vote
0 answers
195 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
  • 468
1 vote
1 answer
230 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