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.

Filter by
Sorted by
Tagged with
22
votes
3answers
3k views

Proving knowledge of a preimage of a hash without disclosing it?

We consider a public hash function $H$, assumed collision-resistant and preimage-resistant (for both first and second preimage), similar in construction to SHA-1 or SHA-256. Alice discloses a value $h$...
22
votes
1answer
4k views

Is a hash a zero-knowledge proof?

I’m trying to wrap my head around zero knowledge proofs, but I’m having trouble understanding it. In my current understanding, zero-knowledge proofs prove to the recipient that the sender has a ...
3
votes
1answer
1k views

Zero knowledge proof for sign of message value

I am using ElGamal encryption to encrypt an integer message $m$ as, $E[m]$ = ($g^x$, $g^m.h^x$) Can I write a zero-knowledge proof to prove to a verifier that $m > 0$ ? I can create the bit ...
4
votes
1answer
969 views

Proof of correctness of a homomorphic ElGamal sum

Let's suppose we are using the exponential ElGamal as a public-key encryption scheme, so that we encrypt $g^m$ instead of $m$, for some generator $g$. Let $x$ be the private key, and $h=g^x$ be the ...
27
votes
1answer
7k views

Zero knowledge proof protocol example?

Alice is color blind. She never knows if her gloves are matched. Her brother Bob always teases her saying her gloves are mismatched and she should go change them. Alice wants to know if Bob ...
13
votes
3answers
6k views

Perfect zero knowledge for the Schnorr protocol?

Can somebody explain (or point to a reference) why the Schnorr protocol cannot be proved zero knowledge?
11
votes
4answers
5k views

Proof of non-membership on a Merkle tree?

Assume a user $U$ and a server $S$. $U$ uploads its data and wants later to perform an authenticity check. It also sends a Merkle tree to the server. Let’s say we would like $U$ to ask for a specific ...
11
votes
2answers
2k views

Is Using Digital Signatures to prove identity a zero knowledge proof?

Suppose Alice publishes a book with a public key in it, and later wants to prove that she wrote the book. She could sign challenge messages with her private key, and others could verify those signed ...
5
votes
2answers
977 views

How to verify a number encrypted with an unknown key

Alice and Bob are going to follow the protocol below. Are there any crypto-constructions to help Bob verify the correctness of the answer he gets?: Alice encrypts a set of numbers using some ...
9
votes
1answer
2k views

How realistic is a dictionary attack on a secure remote password protocol (SRP) verifier?

I'm deploying a secure remote password protocol implementation and I'm wondering what the consequences are when the client generated verifier gets leaked to an attacker. I've read Thomas Wu's paper ...
7
votes
3answers
849 views

Is there a public key semantically secure cryptosystem for which one can prove in zero knowledge the equivalence of two plaintexts?

If Alice encrypts two messages $a$ and $b$, such that $x=E(a)$, $y=E(b)$. Can Alice prove (without revealing $a$, $b$ or the private key) that $a = b$? Obviously the proof must not be too long and it ...
1
vote
2answers
371 views

Using two elliptic curves to do a range proof

Suppose Alice holds a secret value $a$ to which she has publicly committed to using two elliptic curves of distinct order. The curves are $g$ and $g'$ of orders $q$ and $q'$ (with $q < q'$) and ...
4
votes
2answers
493 views

Why is a common reference string needed in zero knowledge proofs?

Can we have a non-trivial language without a CRS? Why?
19
votes
3answers
2k views

When would one prefer a proof of knowledge instead of a zero-knowledge proof?

I've just realized I find it hard to distinguish between these two terms (proof of knowledge, and zero-knowledge proof), specially where only the latter seems to be used in many cryptographic ...
13
votes
2answers
2k views

What is a “rewinding argument”?

I've been reading a bit about cryptographic protocols and I keep seeing the phrase "rewinding argument". I've been unable to find a good source that would explain what is meant by this. It seems like ...
13
votes
3answers
2k views

Can we prove possession of an AES-256 key without showing it?

Imagine this situation: Alice has an AES256GCM key $K$, a plaintext $X$, and $Y$ which is the ciphertext of $X$ encrypted by $K$ Bob has $X$ and $Y$ Alice and Bob can communicate with each other Bob ...
13
votes
2answers
2k views

What are zk-STARK's?

The zk-STARK is a proof zero-knowledge proof system that, in contrast to the zk-SNARK, no longer relies on a trusted setup where the "toxic waste" parameters are initialized. What are, in layman's ...
9
votes
2answers
2k views

Zero-knowledge proof of a product

I have non-negative integers $x,y,z$. I'm going to give you commitments $C(x),C(y),C(z)$ to them. Then, I would like to prove in zero knowledge that $xy=z$. I can choose the commitment scheme to ...
7
votes
2answers
2k views

Proof that lottery does not know outcome of draw

Could a variable participant lottery system cryptographically prove that they have zero knowledge of the outcome of a draw? Participants do not choose numbers in this lottery and winning numbers are ...
7
votes
3answers
487 views

Practical consequences of a honest-verifier zero-knowledge of the Schnorr protocol

Schnorr protocol is known to be honest-verifier zero-knowledge and not perfectly zero-knowledge. What are the practical consequences of this fact? Does it mean a dishonest verifier can do something ...
3
votes
2answers
426 views

Prove I know a value $v$ in a Pedersen Commitment without revealing it

Given a Pedersen Commitment: $P = aG + vH$ Where $G$ and $H$ are points in some group. $a$ is a blinding value/mask and $v$ is the value I wish to commit to. Is there a way to prove I know $v$ ...
2
votes
3answers
298 views

Is there an oblivious decryption scheme?

Alice has $K$; Bob has $E(K, m)$; Is there such a scheme that enables Alice decrypts $E(K, m)$ without knowing $m$, and Bob gets $m$ ?
0
votes
2answers
394 views

Finding out the greater number under zero-knowledge conditions?

Is it possible to construct a zero knowledge proof that one encrypted number is larger (or not) than another encrypted number without releasing the values of either numbers?
9
votes
1answer
1k views

Why does SRP-6a use k = H(N, g) instead of the k = 3 in SRP-6?

I've been reading up on the Secure Remote Pasword protocol (SRP). There are a couple different versions of the protocol (the original published version being designated SRP-3, with two subsequent ...
5
votes
1answer
805 views

Security of zero knowledge proof protocols

When designing a protocol based on zero knowledge proofs, be it based on the discrete log problem, or on a Hamiltonian cycle in a graph, or something else, I assume there are security considerations, ...
4
votes
1answer
1k views

Why is the Pedersen commitment perfectly hiding?

I learned today about the Pedersen commitment scheme. A quick reminder (I know there are some variants of this scheme, so I will present the one I learned about): Public parameters - 2 primes $p,q$...
4
votes
1answer
433 views

What is difference between Zero Knowledge proof and Zero Knowledge Proof of Knowledge?

In a zero knowledge proof, a prover interactively proves to a verifier that an NP statement is true. If the language is an NP complete language and if the prover runs in poly time, the only way a ...
2
votes
1answer
245 views

Commutative homomorphic encryption for zero-knowledge transfers

I am trying to design a scheme that would allow the following: Alice has a number $a$ which she wants to keep secret Bob has a number $b$ which he wants to keep secret Alice can "transfer" a number ...
3
votes
3answers
361 views

Zero-knowledge transfer of value protocol inspired by EC El Gamal

This is a follow up on the question I asked here. I designed a scheme that allows the following: Alice has a value $a$ which she wants to keep secret Bob has a value $b$ which he wants to keep secret ...
0
votes
0answers
72 views

Information sharing using interactive zero-knowledge system

I am trying to build a system that would allow information sharing in a kind of zero-knowledge way. Here is the set up: Let's say there is a trusted third party that has Alice's sensitive info M (e.g....
0
votes
1answer
121 views

Can we use non-adaptive zero-knowledge proof in group signatures

Group Signature schemes are used to provide anonymity of the signers. During signature generation, signers provide a NIZK proof to prove that they are certified group members. Verifiers check whether ...
74
votes
8answers
23k views

How do I explain zero knowledge proof to my 7 year old cousin? [duplicate]

How do I explain zero knowledge proof to my 7 year old cousin?
43
votes
1answer
17k views

What are SNARKs?

What does it mean and what is it used for, I have been hearing this term a lot lately. From the context I've heard it talked about it seems to be connected with zero knowledge?
28
votes
4answers
7k views

What is a Non-Interactive Zero Knowledge Proof?

I understand the concept of a Zero Knowledge Proof thanks to the easy to understand analogy of Alibaba's cave. However, this seems to require interaction between the verifier and the other party. I ...
7
votes
1answer
1k views

Simulation Based Proof: What Can / Can not Simulator Do?

I have seen some examples in "Foundation of cryptography" and "Efficient two party computation", in which simulator can do some things that in the real world model the parties cannot do, for instance: ...
8
votes
3answers
5k views

Zero Knowledge Password Proof

I'm working on implementing a cryptographic system and I'm trying to understand the Zero Knowledge Password Proof concept. So here's some background: To generate a secret key I am: Doing an ECDH key ...
4
votes
2answers
2k views

Simulation based proofs: Simple examples

I am aware that,(in theory) in order to proof that a scheme is secure using simulation based proof we replace an adversary in real world with a simulator in ideal world. Then we try to show that their ...
6
votes
2answers
1k views

Is there a practical zero-knowledge proof for this special discrete log equation?

We have a multiplicative cyclic group $G$ with generators $g$ and $h$, as in El Gamal. Assume $G$ is a subgroup of $(\mathbb{Z}/n\mathbb{Z})^*$. There are two parties, Alice and Bob: Alice knows: $...
8
votes
4answers
1k views

Schnorr protocol: how does malicious verifier win?

My question is about the challenge space size in Schnorr protocol. To be precise, I feel I've read all the Internet (twice) and I still don't understand why is it bad to allow challenge space to be ...
8
votes
2answers
880 views

Zero-knowledge proof system which is not proof of knowledge?

I have learned that a zero-knowledge (ZK) proof system can be constructed by making use of the three-color problem. In this particular case, the proof system also happens to be proof of knowledge (POK)...
7
votes
2answers
1k views

converting to rank one constraint system

I was reading Vitalik Buterin's post on ZK-snarks and I need some clarification on some points . since there aren't that many posts and articles regarding the subject , I had no choice other than ...
7
votes
2answers
449 views

Is there a cryptographic solution for this “dating protocol”?

The article Cryptographic Protocols with Everyday Objects by James Heather, Steve Schneider, and Vanessa Teague describes the following dating protocol (due to Bert den Boer): Alice and Bob wish to ...
4
votes
1answer
517 views

How to prove that a committed value is the square of other

Given two Pedersen commitments $c_1=g^vh^{r_1}$ and $c_2=g^{(v^2)}h^{r_2}$, where the committed value in $c_2$ is the square of the committed value in $c_1$, is there a way to prove this relation in ...
2
votes
2answers
288 views

Alice's forgetful banking

Alice has a bank account number, but has forgotten which bank it is for. There are 4 banks, run by Bob, Carlos, David, and Eve. She could find out by going to all of the banks and asking if they have ...
2
votes
1answer
1k views

Non-Interactive Zero-Knowledge-Proof for discret Logarithm?

In a Non-Interactive $Zero-Knowledge-Proof$, the challenge is chosen by the Prover. I am trying to find a Non-Interactive Zero-Knowledge-Proof based on the following problem: DISCRETE LOGARITHM ...
0
votes
1answer
398 views

Blum primes [x=3(mod 4)] zero knowledge proof?

Lets say we have 2 primes, $p \equiv q \equiv 3 \pmod{4}$, and we make $n=p \times q$ public. I can, without revealing factors, show that $n$ has two prime factors. How can i zero knowledge prove ...
10
votes
1answer
288 views

Minimizing exchanges for ZK proof of a message with given SHA-256

Consider the problem of proving knowledge of a message $m$ which has a certain public SHA-256 hash $h$, without disclosing $m$ or usable information about it, while minimizing the information exchange ...
6
votes
2answers
306 views

Hamiltonicity proof of knowledge

I'm learning the POK notion and definitions and as a self exercise I wante to prove the statement that the Hamiltonicity protocol is a POK system with knowledge error $1/2$. So the question will be ...
4
votes
2answers
289 views

Non-interactive proof that an element is in a subgroup

I am just reading the DAA paper (http://eprint.iacr.org/2004/205.pdf, Appendix A). A party $\mathcal{I}$ generates two group elements $g' \in \mathrm{QR}_n$ and $h = g'^r \bmod n$ with $r \in_R \left| ...
3
votes
1answer
782 views

Questions about proof of correct encryption in the Paillier cryptosystem

In the Paillier cryptosystem [1] the encryption of $m \in \mathbb{Z}_N$ with randomness $r \in \mathbb{Z}_n^*$ is $c = g^m r^n \bmod{n^2}$. A proof of correct encryption could look like presented in ...