"Zero Knowledge Proof" is 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.

learn more… | top users | synonyms

11
votes
2answers
548 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 ...
10
votes
3answers
532 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 ...
10
votes
1answer
209 views

Shadowed identity in cryptography

I was trying to implement zero knowledge protocol for authentication based on the paper "A Practical Zero-Knowledge Protocol Fitted to Security Microprocessor Minimizing Both Transmission and Memory". ...
8
votes
1answer
581 views

Can I construct a zero-knowledge proof that I solved a Project Euler problem?

Is there a practical method, and if so what is the method, to reveal that I have the following type of answer but conceal the answer itself? The answer is, let's say, the solution to a Project Euler ...
8
votes
2answers
284 views

What is the sign bit for in Feige-Fiat-Shamir?

The Feige-Fiat-Shamir identity scheme is based on a ZKP assuming that square roots are "hard" modulo an integer of unknown factorization. The "parallel version" of this protocol includes a "sign bit" ...
7
votes
1answer
416 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 ...
6
votes
4answers
327 views

How to forge Schnorr signatures if you can guess the challenge

Underlying the Schnorr signature is an identification protocol: let $G$ be a cyclic group where discrete log is "hard" and choose $g$ as a generator of $G$. Now have Alice pick a random (secret) ...
6
votes
1answer
628 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 ...
6
votes
1answer
1k 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 ...
6
votes
2answers
559 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 ...
6
votes
2answers
152 views

Why Victor must not know which tunnel Peggy chooses?

In the classic description of Zero Knowledge Proof of Knowledge, Victor must wait outside the entrance to the cave while Peggy goes to the fork and choose a side. It's only once Peggy has entered a ...
6
votes
2answers
331 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 ...
5
votes
2answers
483 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: ...
5
votes
2answers
143 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 ...
5
votes
1answer
304 views

Zero knowledge proof of possession of key

Suppose Alice has at some point in time produced ciphertext $C$ from message $M$ with key $k$. Suppose Alice has then passed $C$ to Bob, and also made a commitment to her key $k$ (thanks to ...
5
votes
3answers
463 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?
5
votes
1answer
217 views

How do zero knowledge protocol with vertex-3-coloring work?

I'm currently not sure if I understood how the zero knowledge protocol with vertex-3-coloring works. I'll describe what I think I've understood and I'll write my questions in bold. ...
4
votes
3answers
2k 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 ...
4
votes
3answers
344 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 ...
4
votes
3answers
185 views

How to prove identity without revealing identity

Let us say Alice publishes a book under the name of Claire. The book becomes wildly popular and now Bob comes along, claiming to be Claire, to reap all the success. How does Alice prove that she wrote ...
4
votes
4answers
320 views

How to prove membership of a list without disclosing the list members?

I'm designing a messaging system where the sender A sends a message m with a signature s to n Receivers. A Receiver Ri should then be able to prove to a Verifier V that he is one of the receivers of ...
4
votes
1answer
178 views

Proving the possession of signature in zero-knowledge

Does anybody know an efficient mechanism to prove the possession of a digital signature (e.g. RSA) on a certain attribute (message) in zero-knowledge? That is, without revealing the actual signature ...
4
votes
2answers
167 views

Can I prove set membership and uniqueness without revealing the element?

Assuming a publicly known set $\Psi$ with $N$ unique elements. I have a set $\Sigma=\{\sigma_1,\sigma_2,...,\sigma_m\}$ where $m\leqslant N$. I would like to publicly prove that all the elements in ...
4
votes
1answer
253 views

How to construct a zero-knowledge proof of a number of the form $n=p^a q^b$

Let $n = p^a$$q^b$ where p and q are distinct primes and a and b are positive integers. How to construct a zero knowledge proof that n is of such form? This is actually a homework problem with a ...
4
votes
1answer
130 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| ...
4
votes
1answer
185 views

State of the art in zero knowledge proof compilers?

What is the current state of the art zero knowledge proof compiler ? I need one that can minimally handle double exponentiation by a known value E.g. $$Pok\{(\alpha):h=g^{\alpha^b}\} $$ where b, ...
4
votes
0answers
118 views

understanding the proof of knowledge

Recently I've been reading the paper “A New Family of Implicitly Authenticated Diffie-Hellman Protocols”. It's very hard for me to go further. Especially when it comes to the proof of knowledge. ...
3
votes
1answer
324 views

Proof of correct construction of a private key in distributed cryptography

In an exponential ElGamal encryption scheme where the key generation is done in a distributed way among $n$ trustees we have that each trustee $i$ (where $1 \leq i \leq n$): Selects a private key ...
3
votes
2answers
138 views

Could this be a valid variation of the Schnorr protocol?

The Schnorr protocol is a 3-steps proof of knowledge of a discrete logarithm, whose interactive version works as follows. Let $p$ and $q$ be two public primes, such that $q \mid (p-1)$, and let $G$ ...
3
votes
3answers
147 views

How can two UProve token holders prove to a 3rd party that they aren't the same user?

Suppose I have two users who are issued two different UProve IDs. The Issuer has guaranteed that one UProve token bearer will never have more than one UProve token ID. How can I use UProve to ...
3
votes
2answers
140 views

Feedback requested on a method of posting a message without revealing the author

So I was thinking about variations on the Dining Cryptographers problem - In some cases, it's useful to be able to post a message without revealing the source, but with the additional constraint of ...
3
votes
1answer
131 views

Zero-knowledge proof for committing a choice?

Let's say there are 100 choices (which are publicly known), each represented as a different string, and today you have to choose one of them. You need not reveal what that choice is right now, though. ...
3
votes
1answer
46 views

NIZK Proof of knowledge N of M discrete logarithms (threshold)

It is well known how to produce a NIZK that curvepoints $aG$ and $aP$ have the same discrete logarithm $a$ with respect to the curvepoints they are multiplied by. There is also a way to prove that a ...
3
votes
0answers
103 views

Question about proof of knowledge defintion?

I am just reading the "soundness"-definition for proofs of knowledge by Bellare / Goldreich. A proof of knowledge is a proof between a prover $P$ and a verifier $V$. $P$ convinces $V$ to know a secret ...
3
votes
3answers
123 views

Zero Knowledge Example using discrete log

I've been exploring Zero Knowledge Proofs and while the classic cave example by Jean-Jacques Quisquater makes sense, I find the discrete log example problematic. Since the Verifier is given p, g and ...
2
votes
2answers
118 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$ ?
2
votes
2answers
148 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 ...
2
votes
2answers
206 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
2answers
227 views

Zero-knowledge proof using quadratic residue: why two options?

In the zero knowledge proof using QR, why do we even bother with the server sending us $b = 0$ back? As I understand it, the server selects $b = 0$ or $b = 1$. If $b = 0$, then the client (Alice) ...
2
votes
2answers
230 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 ...
2
votes
1answer
189 views

Zero-knowledge proof that a group element is a quadratic residue?

In a paper it says: "To convince a verifier that a group element is a quadratic residue, the prover executes the following proof with the verifier": $PK \left\{ (\alpha) : y = \pm g^\alpha \right\}$ ...
2
votes
1answer
101 views

What is adaptive zero-knowledge?

In this paper on pg. 1241 the authors discuss bullet point on Adaptive Zero-Knowledge : I am new to Zero-Knowledge and I am having trouble understanding what they are saying. I think they are ...
2
votes
1answer
195 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 ...
2
votes
2answers
206 views

Zero-Knowledge Challenge-Responce Protocol

Good day to everyone. I am trying to implement an e voting system (just for reference -it is not important though-it is described at the Internet Voting Protocol Based on Improved Implicit Security ...
2
votes
1answer
218 views

Is there a simple zero knowledge proof of $x$ for $b=x^x\pmod p$?

We have a multiplicative cyclic group $G$ which is a subgroup of $(\mathbb{Z}/n\mathbb{Z})∗$. There are two parties, Alice and Bob: If: Alice knows: $b$ and $x$ such that $x^x = b$; Bob knows: $b$. ...
2
votes
2answers
96 views

Soundness idea of basic zero knowledge prood

I am having a hard time figuring out the soundness proof of the bellow zero knowledge protocol. As it is a typical proof, I would love to deeply understand it. zero knowledge argument that $h \in ...
2
votes
1answer
111 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 ...
2
votes
1answer
80 views

Generating shared secret random permutation

There are three blind card game players. Each player does not trust any other, even prejudicing other two players may not be blind, or there may be others in the room, peeking at their cards. In ...
2
votes
1answer
242 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 ...
2
votes
1answer
367 views

Several questions about Paillier cryptosystem

I have several questions concerning the original Paillier cryptosystem as described in Paillier, Pascal (1999). "Public-Key Cryptosystems Based on Composite Degree Residuosity Classes". EUROCRYPT. ...