"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.
1
vote
0answers
68 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 ...
1
vote
1answer
81 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\}$
...
0
votes
2answers
51 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 ...
2
votes
0answers
65 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, ...
1
vote
2answers
112 views
How to verify a number encrypted with an unknown key
Are there any crypto-constructions to do the following kind of "zero-knowledge proof":
Alice encrypts a set of numbers using some cryptosystem and a secret key (e.g. Paillier crypto-system).
Bob ...
1
vote
2answers
135 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
91 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 ...
0
votes
0answers
40 views
SRP6a client server exchanged message order
In SRP6a, the public key of server is send after receiving the public key of client A. Its that okay that B send along together with s right after client send the username, and then later on client ...
2
votes
0answers
97 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
264 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 ...
0
votes
2answers
105 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
...
1
vote
0answers
99 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. ...
0
votes
0answers
60 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 ...
0
votes
0answers
45 views
ZeroBin security [closed]
ZeroBin is a cool concept, but it seems to be flawed because the identifier and key are both publicly accessible on the internet. Even though the database theoretically never deals with the data, the ...
2
votes
0answers
163 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
137 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
94 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 ...
4
votes
3answers
211 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 ...
9
votes
2answers
317 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 ...
1
vote
1answer
225 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. ...
5
votes
2answers
181 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
290 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
99 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 ...
5
votes
1answer
215 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
3answers
601 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 ...
1
vote
0answers
87 views
Efficient zero knowledge proof of least significant bits either RSA or Rabin?
I need to reveal the log(n) least significant bits of $x^2 mod\ N$ or $x^3 mod\ N$ without revealing x.
So far the best I have involves a Boudot range proof and is not a very nice construction
1
vote
1answer
147 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 ...
2
votes
1answer
254 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 ...
2
votes
1answer
168 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 ...
5
votes
1answer
377 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 ...
5
votes
4answers
239 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
186 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" ...
