# Questions tagged [zero-knowledge-proofs]

Zero-knowledge proofs are an interactive method for one party to prove to another that a statement is true, without revealing anything other than the veracity of the statement.

753 questions
Filter by
Sorted by
Tagged with
59 views

### Groth16 simulate zero-knowledge proof for invalid statement

The zero-knowledge property of the Groth16 (https://eprint.iacr.org/2016/260, page 8) non-interactive zero-knowledge argument is based on the existence of a simulator $\text{Sim}$ generating "...
69 views

### Prove that $x$ is the sum of digitally signed numbers without revealing the summands

Imagine this: Charlie chooses two integers $x_1$ and $x_2$ and signs each of these integers with the same private key. Charlie sends the following to Alice: $x_1$ and $x_2$, the two signatures, and ...
89 views

### ZKP: Prove that >18 while hiding age

I am relatively new to cryptography, but I've been programming for a while. Here's a story that sets well the problem I'm trying to solve: Alice has a digital passport that's signed with her ...
29 views

### THe operation proof part of paper "Why and How zhSNARK works"

I'm reading the paper "Why and How zk-SNARK works" to learn zkSNARK, and I suffered some problem in section 4.4, when prove the ability of single operation. In this section, it tries to come ...
49 views

### Why Zk-SNARKs are Argument of Knowledge if a Knowledge Extractor exists?

From what I know, proving the existance of a Knowledge Extractor implies perfect soundness. So why in zk-SNARKs (and similar) we talk about Arguments of Knowledge, where the soundness property is only ...
33 views

### Are zk-STARKs a Sigma protocol? Is the communication interactive? And other doubts

I've heard that STARKS are not a non-interactive protocol, if so: What is (briefly) the mechanism they use to operate? Can they be considered a Sigma protocol? Why SNARKs are not interactive, instead?...
129 views

### Is "Witness" and "Proof" the same thing when talking about Zero Knowledge? What about "argument"? And "statement"?

I've seen people making lots of distinctions while reading papers about zero-knowledge. I've seen the term "Argument of Knowledge" that seems to be used as a weaker "Proof of Knowledge&...
21 views

### What are the main attacks that can be done against a ZK Σ-protocol like Schnorr's identification scheme?

I heard about the "Chess Grandmaster Problem", Eavesdropping attacks and Man-in-the-middle. Can they be applied in any way to a ZK protocol? I'm not looking for long examples, just what are ...
58 views

### Why do Lattice-based Proof Systems not use the $\ell_2$ norm and canonical embedding?

I was recently reading the paper A non-PCP Approach to Succinct Quantum-Safe Zero-Knowledge. Among other things, it discusses an adaption of the "folding" technique (from Bulletproofs) to ...
43 views

### Are there batched vector/polynomial commitment proofs with sublinear proof size for Verkle Trees?

High level goal: a Verkle tree (Merkle tree using algebraic vector commitments at each level rather than hashes) with depth d where I can prove the existence of <...
80 views

### Difference between an authentication scheme and a identification scheme in ZK proofs?

EDIT: I want to specify what I know about schemes security: Authentication schemes: P can prove V he is P, and nobody else can prove V that they are P. Identification schemes: P can prove V he is P, ...
80 views

### How to prove that the Fiat-Shamir identification scheme is zero-knowledge?

I'm trying to prove that this protocol https://de.wikipedia.org/wiki/Fiat-Shamir-Protokoll is zero-knowledge (the page is in german but it was the only good and simple image i could find) I'm a ...
52 views

### zkSnark: Converting R1CS to QAP

I am reading through Vitalin Buterin's page on R1CS & QAP - https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649 I understood upto the part where he gets ...
465 views

### What's the main difference between the Schnorr identification scheme and its Smart-Card implementation?

This question arises because I couldn't find any official paper for the Schnorr identification scheme, but only for the Smart-Card implementation of it. Also, it seems that everyone, when talking ...
206 views

### Why Zero-Knowledge protocols are used for NP problems if IP is the class of interactive proof systems where they come from?

As stated in the title, I'm studying ZKPs and I see they are just interactive proof systems that respect the zero-knowledge property. Now, if that's true, why aren't they used for IP problems, the ...
120 views

48 views

### Can interactive zero-knowledge proof systems be implemented using secure two-party computation?

I am defining multi-party computation using the real-ideal paradigm (see A Pragmatic Introduction to Secure Multi-Party Computation). That is, for any successful attack on an MPC protocol in the real ...
39 views

### How does one construct a SNARK circuit for proving the knowledge of a SHA256 pre-image?

Usually one explains how the R1CS/QAPs and SNARKs work using examples of circuits with multiplication and addition nodes, and constructing polynomials from that is relatively straightforward. SHA-2 ...
52 views

### Does the degree of this polynomial matter to achieve zero-knowledge? PlonK question

I was reading the paper PlonK and in the Round 1 of the claim to achieve zero-knowledge by adding random multiples (of degree one) of the polynomial $Z_H = x^n - 1$ to the secret polynomials. Here, $H$...
87 views

### Proof that someone has access to a private key whose public key is part of a known group

I'm a crypto newbie and hoping to get pointed in the right direction. I've seen some related questions like this but none that satisfy my requirements. Let's say Jane's Forum is a large community, and ...
54 views

### Verifiable execution of a program

I would like to know what cryptographic primitives could be used for Alice to prove to Bob that she actually executed a program. The goal is to make a Proof-of-useful work, where Alice proves she ...
47 views

### Zero Knowledge Proof for Merkle Tree Update

I have a Merkle tree that contains the balances of users in each leaf. Periodically, users are paid more, and their corresponding Merkle leaves are updated, which results in a new Merkle root. Is it ...
78 views

### Is the following proof scheme zero-knowledge?

Consider that I wish to prove knowledge of some RSA private key corresponding to a public key $(e,N)$. A naive interactive proof scheme would proceed as follows: $V$ generates some random message $m$ ...
20 views

### Zero-knowledge proof set - one time proof construction and different verifications

Is it possible to construct a zero-knowledge proof set and then change the verification query without reconstructing the proof? For instance, my set could include red, blue and green but while, at ...
92 views

### Proof that a message is signed by a member of a group

I'm a newbie at cryptography. Here is my question: Alice makes a list of people: Bob, Carol and Dan; Alice gives a unique secret key to every member on the list, so they can uniquely sign messages; ...
66 views

### ZKP but the verifier knows all possible secrets

Is there a (preferably simple) implementation of ZKP where the verifier already knows the set of possible secrets? Especially if the set is very small (even as few as 2 or 3 options). The prover must ...
49 views

### Comparing two private values and extracting the ciphertext corresponding to the minimum value

How can I solve this problem: I have a directed graph of nodes that can be malicious and all of them have a private value. Consider a node "B" with private value "BPrivateValue = b&...
29 views

### Efficient proof for Cartesian product

I am trying to find some efficient zero-knowledge arguments that could prove the vector ${\bf v}$ is the Cartesian product of two vectors ${\bf x}$ and ${\bf y}$. I know there are efficient inner ...
171 views

### Zero knowledge RSA public key

Suppose Bob has $k>1$ RSA public keys $(e_i, n_i)$ without any knowledge of their corresponding private keys. Alice also has all the public keys, but also has a private key for only one of them, ...
37 views

### Zero-knowledge composability

Suppose a protocol P is composed of two different zero-knowledge protocols. Can we assume P is also zero-knowledge?
81 views