"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

5
votes
2answers
181 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| ...
5
votes
2answers
219 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 ...
7
votes
1answer
507 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
1answer
467 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
151 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 ...
2
votes
1answer
316 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 ...
8
votes
3answers
1k 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?
3
votes
2answers
159 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$ ...
2
votes
2answers
227 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 ...
3
votes
2answers
390 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) ...
6
votes
2answers
479 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. ...
3
votes
0answers
118 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
182 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 ...
4
votes
1answer
241 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, ...
2
votes
2answers
343 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
241 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\}$ ...
3
votes
2answers
271 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
348 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 ...
4
votes
1answer
190 views

Changing SRP-6a message order

In SRP-6a, the public key $B$ of the server is normally sent after receiving the public key of the client $A$. Is it okay to send $B$ and $s$ after the client sends its username $I$, but before the ...
2
votes
2answers
393 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 ...
2
votes
1answer
267 views

Sigma-protocol for 3SAT problem

I have some questions from previous years exams, I hope you could help me with them. :) Let $g,h$ denote generators of a group $G$ of large prime order $n$ such that $\log_g h$ is unknown to anyone. ...
2
votes
0answers
209 views

Transforming simplest protocol into a Sigma-protocol

I have some questions from previous years exams, I hope you could help me with them. :) Suppose that a protocol satisfies the properties of a $\Sigma$-protocol, except that it is only (plain) ...
4
votes
4answers
348 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 ...
2
votes
0answers
109 views

Is this a valid real-time authentication scheme?

The scenario in Alice/Bob/Cindy terms: Alice approaches someone she doesn't know, but thinks is Bob, and asks for some secret information. Bob doesn't know and doesn't trust Alice, but Alice says she ...
5
votes
2answers
626 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: ...
1
vote
1answer
372 views

How can I prove in zero knowldege that an ElGamal shuffle is correct for a special setting? [closed]

In a special ElGamal encryption scheme, every user has an ElGamal encryption key-pair using the same cyclic group $G$ and generator $g$. The system has a special function : $$ ...
1
vote
1answer
109 views

Is secure remote snap possible?

Scenario: We have a central server $S$. We have a number of peripheral servers $P_i$ We have some individuals $U_j$ A given individual may be "known" to one or more peripheral servers. Each ...
5
votes
3answers
412 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 ...
6
votes
2answers
436 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 ...
6
votes
2answers
813 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 ...
0
votes
1answer
223 views

Zero Knowledge auth schemes with weak secret

In Zero Knowledge auth schemes the public DH factor of each peer is encrypted with a potentially weak pre-shared secret and the resulting ciphertexts are exchanged over an insecure channel. Why is no ...
7
votes
1answer
560 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 ...
2
votes
1answer
516 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. ...
1
vote
1answer
329 views

ZKIP for Paillier public key correctness

I'm using the Paillier cryptosystem in a protocol similar to mental poker. In the beginning of the protocol, each player generates a Paillier public key $(n,g)$. Later in the protocol, a player may ...
8
votes
1answer
830 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 ...
4
votes
1answer
307 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 ...
11
votes
2answers
700 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 ...
8
votes
1answer
712 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 ...
7
votes
3answers
3k 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 ...
7
votes
4answers
383 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) ...
8
votes
2answers
364 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" ...