Questions tagged as ['zero-knowledge-proofs']

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

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

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 ...

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" ...

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 ...

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  ...

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)$

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 ...

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?

2. 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 ...

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 ...

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!

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  ...

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. ...

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.

https://link.springer.com/content/pdf/10.1007%2F3-540-47721-7_1 ...

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 ...

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}  ...

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 ...

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 ...

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 ...

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 ...

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.

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 ...

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

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).

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

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

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 ...

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

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 ...

I have been reading about the sigma protocols, specially the OR-Proof.

Many examples just take into account two statements and provide a way to say that one of the statements is valid, but not which one. For example this question zero-knowledge proof of disjunctive statements (OR proofs), or protocol 3 in this article Zero Knowledge Proofs with Sigma Protocols, the section 4 of this work On Σ-protocols ...

Given a group where the computational Diffie–Hellman (DH) assumption holds and generator G.

Say there is a set of private randomly selected keys {a, b, c, d, e,...} and corresponding public keys set {A, B, C, D, E,...} calculated as A=aG. Each public key is publicly linked to its corresponding user/owner.

Alice can use its private key a and the public key of Bob, B, to calculate K=aB. This K is  ...