Skip to main content

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
3 votes
4 answers
332 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 ...
makerofthings7's user avatar
4 votes
1 answer
547 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, ...
imichaelmiers's user avatar
5 votes
2 answers
1k 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 ...
Eugen's user avatar
  • 219
2 votes
1 answer
509 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\}$ ...
user4811's user avatar
  • 589
3 votes
2 answers
665 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 ...
user avatar
3 votes
1 answer
1k 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 ...
Thomas Lieven's user avatar
4 votes
1 answer
226 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 ...
user236501's user avatar
2 votes
1 answer
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 ...
user avatar
3 votes
1 answer
872 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. ...
Peter De Vries's user avatar
3 votes
0 answers
343 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) ...
Peter De Vries's user avatar
5 votes
4 answers
672 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 ...
chmike's user avatar
  • 251
3 votes
0 answers
145 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 ...
KeithS's user avatar
  • 540
7 votes
2 answers
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: $...
SDL's user avatar
  • 1,897
1 vote
1 answer
824 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 : $$ \mathrm{ShuffleEncrypt}...
SDL's user avatar
  • 1,897
1 vote
1 answer
121 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 ...
Peter Taylor's user avatar
7 votes
4 answers
1k 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 ...
SDL's user avatar
  • 1,897
15 votes
2 answers
3k 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 ...
Jaska's user avatar
  • 151
8 votes
2 answers
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 ...
Thomas Tank Engine's user avatar
0 votes
1 answer
428 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 ...
niklr's user avatar
  • 103
9 votes
1 answer
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 ...
Robert I. Jr.'s user avatar
3 votes
1 answer
1k 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". ...
Thomas Lieven's user avatar
1 vote
1 answer
923 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 ...
johny's user avatar
  • 13
10 votes
1 answer
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 ...
Grant BlahaErath's user avatar
4 votes
1 answer
799 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 ...
statham's user avatar
  • 81
25 votes
3 answers
6k 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$...
fgrieu's user avatar
  • 143k
9 votes
1 answer
1k 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 ...
minopret's user avatar
  • 191
8 votes
3 answers
6k 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 ...
hobeau's user avatar
  • 823
6 votes
4 answers
1k 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) ...
Fixee's user avatar
  • 4,168
9 votes
2 answers
759 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" ...
Fixee's user avatar
  • 4,168

1
18 19 20 21
22