# Questions tagged as ['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.
Score: 0
How to prove that paillier encryption is positive (zero-knowledge)?

Is it possible that the plaintext encrypted in a ciphertext using paillier encryption is positive without using a zero knowledge range proof?

Score: 2
Is this a safe zero knowledge proof that two paillier encryptions are equal?

We have encryptions $$c_1$$ and $$c_2$$, the person who knows the plaintext and randomness in both wants to prove that they know it. Let $$r_1$$ and $$r_2$$ be the randomness values in $$c_1$$ and $$c_2$$ respectively. The prover then randomly generates another random number, $$z$$. They then calculate $$a_1 = r_1^n z^n$$, $$a_2 = r_2^n z^n$$. These are the proofs. A verifier would just have to multiply $$a_2$$ with

Score: 0
Zero-knowledge proofs for preventing data abuse

I am looking for a theoretical solution to the following problem: Alice receives a signed statement from her bank with information about her account and credit balance. Alice wants to prove this knowledge of the contents and the bank's valid signature to Bob, but at the same time prevent Carol from determining who signed the proof.

To better illustrate my problem, I took the liberty of making a s ...

Score: 4
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 "fake" proofs for valid statements $$(\phi, w) \in R$$ without knowledge of the witness $$w$$ for statement $$\phi$$.

My question is whether for Groth16 there also exists a simulator $$\text{Sim}'$$ to generate "fake" ...

Score: 3
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
• his public key.
• Alice computes $$x = x_1 + x_2$$ and sends the following to Bob:
• $$x$$ and
• Charlie's public key.

Can Alice prove to Bob (without involving Charlie) that $$x$$ is the sum of two numbers ...

Score: 5
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 government's private key. Each property is signed separately, and it would still be verifiable that, for example, her first name is "Alice", without saying that her last name is "Smith".

From here, knowing that  ...

Score: 1
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 up with a protocol to verify that the prover have the ability of doing multiplication. It gives two number $$b$$ and $$c$$ and tries to verify the result of multiplication. The prover construct to polynomials $$l(x)$$

Score: 1
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 computational (a.k.a, secure only from computationally bounded Provers), if a Knowledge Extractor also exists? Am I missing something? Maybe a Knowledge Extractor can be proven in different "levels" of ...

Score: 0
Are zk-STARKs a Sigma protocol? Is the communication interactive? And other doubts
1. 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?
1. Is it correct to state that STARKS are quantum-secure and they don't need a trusted setup because they are defined in the random oracle model, and they use a hash that is collision resistant and this i ...
Score: 5
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": what I understood is that if you talk about the normal soundness property you talk about "arguments", whilst if you talk about the validity property (from Proofs of Knowledge) then you talk about "proofs". Is it cor ...

Score: 0
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 the main attacks and briefly how they work will do.
Thank you so much!

Score: 5
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 SIS-based proofs.

The paper measures distances in the $$\ell_\infty$$ norm (rather than $$\ell_2$$), and is vague on which choice of embedding it uses (although I imagine it is the coefficient embedding). These choices  ...

Score: 0
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 n key/value pairs in the tree. Assuming the verifier already has the tree root commitment as well as the key/value pairs, I would like the additional proof size to be sublinear in either d or n, or ideally both. Zero-knowledge is not required. ...

Score: 2
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, and V can't prove to anybody else that he is P.
• Signature schemes: P can prove V he is P, and V can't prove even to himself that he is P.

Score: 0
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 student and I've never proven the zero-knowledge property, I know a simulator has to exist in order for a protocol to be zero-knowledge, but I've never actually seen how to do it or how its done, can you help m ...

Score: 1
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

$$A=\begin{pmatrix} 0&1&0&0&0&0 \\ 0&0&0&1&0&0 \\ 0&1&0&0&1&0 \\ 5&0&0&0&0&1 \\ \end{pmatrix}$$

$$B=\begin{pmatrix} ...$$

Score: 4
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 about the SIS links the paper for the Smart-Card implementation. So I'm kinda confused, especially 'cause English isn't my native language and I can't figure it out by myself. I don't understand if they are the ...

Score: 5
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 complexity class of interactive proof systems that was originally introduced for them? I mean, isn't the proof mechanism interactive in ZKPs between Prover and Verifier? Then why are we talking about NP proble ...

Score: 2
Altering a subroutine PPT's output to fit a reduction proof

I have a protocol that operates in the malicious setting which involves parties sending each other group elements $$u\in \mathbb{G}$$ of a specific form (For example, these are messages of the form $$u=g^{\alpha}\cdot h^{\beta}$$ with generators $$h,g\in \mathbb{G}$$ and $$\alpha, \beta \in \mathbb{Z}_q$$ for some prime $$q$$).

Additionally, these parties attach non-interactive zero-knowledge proofs of kn ...

Score: 0
zkSnark Intro by Maksym Petkus: Is the polynomial defined over $Z$ or is it defined over $Z_n$?

I am reading this explanation of zkSnark written by Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf

Here he has a polynomial $$p(x) = x^3 − 3x^2 + 2x$$

and the homomorphic encryption defined as $$E(c) = g^c \bmod 7$$

It's a little unclear as to where the polynomial is defined over $$Z$$ or is it defined over $$Z_7$$ - it's left a little ambiguous in the text.

This matters in the st ...

Score: 0
How to prove lifted ElGamal encryption with square root communication?

I'm looking for a more efficient solution to prove the correctness of multiple ciphertexts sent to different parties are correct.

The background is that $$P_i$$ uses lifted ElGamal encryption to encrypt a message $$x_j$$ to party $$P_j$$, where $$j\in[N]$$. Therefore, the ciphertext will be $$Enc_{pk_j}(x_j;r_j)$$.

Now I need to generate a proof for $$P_i$$ to show all the ciphertexts he generated is correct.

Score: 1
Why the Kate Commitment and the Algebraic Group Model is used a lot in zk-SNARKs proving system since 2019？

I am engaged in the research of zk-SNARKs. After I read some papers about zk-SNARKs, I realize the Kate Commitment and the Algebraic Group Model is used a lot since 2019. They are used in Sonic, Plonk, Marlin and etc. Most of these papers are about "universal and updatable zk-SNARKs". I want to know if the Kate Commitment, the AGM and the "universal and updatable zk-SNARKs" have some kind of connectio ...

Score: 2
zkSnark: Restricting a Polynomial

I am reading this explanation of zkSnark written by Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf

I have understood everything in the first 15 pages.

In 3.4 Restricting a Polynomial (Page 16)

We do already restrict a prover in the selection of encrypted powers of s, but such restriction is not enforced, e.g., one could use any possible means to find some arbitrary values

Score: 0
Quantum secure algorithms

I want to know if the below algorithm , secure against quantum computing attack, and how I can compute the running time for the original algorithm and the proposed attack

Source: Yan Zhu, HuaiXi Wang, ZeXing Hu, Gail-Joon Ahn & HongXin Hu, Zero-knowledge proofs of retrievability, in Sci. China Inf. Sci. 54, 1608 (2011).

Score: 0
Proof that the encrypted content is the same as the promised original

Context : Alice has some content (C) and published its hash (Chash) publically. She wants to send C to Bob in a way it's visible only to Bob. This can be done by encrypting (Cenc) in using his Public Key (PubKeyBob). And Bob can decrypt it using his private key and compute the hash to see it matches Chash.

We have Eve who plays the role of an Escrow. Bob pays for the C, which is held by Eve. Now Alice  ...

Score: 0
Prove that string exists in source file of sha256 hash

How to prove that hashed data includes specific string without exposing rest of the string?

Practical example is calculating digest to be signed of the PDF file and before signing the digest we need to make sure that this PDF contains specific part in the middle. Whole PDF contents can not be show to the signing application.

When the signing application is sure that PDF indeed contains specific part ...

Score: 3
Is it common/valid to hardcode an element of a language into a simulator?

Short version: Is it a common practice (and a valid practice) to hardcode an element $$d \in \mathcal{L}$$ of a language into a simulator? (making the simulator non-uniform and non-constructive)

Long version:

I have a prover $$P$$ that does the following: it takes a bit string $$d \in \mathcal{L}$$ for some languages in $$\textsf{NP}$$, then it encrypts $$d$$ using a CPA-secure encryption to obtain an encryption

Score: 1
Procedure for finding consensus on selected numbers without sharing selection

I was wondering if there exists an algorithm, paper, etc. for the following problem:

Assume we have a public list of numbers, let's say {1, 2, 3, 4, 5}. Alice and Bob both pick any subset of those numbers in secret. Is there a way for Alice and Bob to exchange their selections in such a way that neither Alice nor Bob know what the other person has picked, however they still see which numbers they ...

Score: 2
Extending the OR-proof to more than two statements