"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

1
vote
1answer
40 views

How to prove NIZK proof of knowledge?

Assuming we have an El-Gamal pk tuple $(G,q,g,g^s)$. Someone, knows only the first three parameters. In round $i$, I send him $X_i=(g^s)^{t_i}$ (the $t_i$ values are chosen randomly for each round), ...
1
vote
1answer
40 views

Fiat–Shamir: why do r and s have to be smaller than n?

I have a question regarding the Fiat–Shamir identification protocol. In this source (pdf) for example it says on pages 9 and 10 that the random commitment $r$ and the private key $s$ have to be ...
1
vote
1answer
55 views

Fiat-Shamir security problem question

I am trying to understand the Fiat-Shamir identification protocol, but have a problem with understanding how this protocol is supposed to be save, even if you repeat it several times. I am using ...
0
votes
1answer
35 views

server aid secure equality test

The scenario is like this: $P_1$ has $m_1$, $P_2$ has $m_2$, they want to compare whether $m_1=m_2$ via the server $S$. After the protocol, only $S$ knows the result, and there is no interaction ...
2
votes
2answers
90 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$ ?
1
vote
1answer
89 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
3answers
143 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 ...
3
votes
1answer
160 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 ...
1
vote
2answers
58 views

Are ZKPPs possible with server-side hashed passwords?

A basic ZKPP (Zero Knowledge Password Proof) is based on the server being able to challenge the client, and the client can then prove it knows the password (in such a way that is verifiable to the ...
0
votes
1answer
87 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 ...
4
votes
2answers
132 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 ...
0
votes
1answer
120 views

Burn after read algorythm. Software verification on compromised environment. Software smart card

please help me pick right design of software I have to design client-server software, where server should verify that client runs software from exact source code. And where software doesn't simulate ...
2
votes
1answer
208 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$. ...
1
vote
0answers
48 views

Reliability of a single-pass deniable authentication protocol?

I look for one-pass deniable authentication protocol with a short message payload for my project and find a solution: ...
3
votes
1answer
121 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. ...
2
votes
1answer
76 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 ...
1
vote
1answer
94 views

Rock-paper-scissors over network, how to protect from cheating server?

I'm trying to design cryptographic protocol to play Rock-Paper-Scissors with two parties, neither trusting each other, nor trusting server they use for communication, so game is 'provably fair'. So ...
1
vote
2answers
84 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 ...
-1
votes
1answer
88 views

Zero Knowledge Proof for Correctness of the product of additive ElGamal Ciphers [duplicate]

Suppose we use Additive ElGamal defined as follows: Let $(K,E,D)$ be a triple. The key-generator $K$ outputs the description of a finite multiplicative group $G$ of prime order $q$, with three ...
6
votes
2answers
138 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 ...
1
vote
1answer
91 views

Homomorphic crypto allowing anonymous yes/no votes?

I'd need a crypto system allowing online yes/no votes but without revealing who voted what. Is a "partial" homomorphic crypto system what I'm after? Would, for example, Damgard-Jurik work in my case? ...
1
vote
1answer
121 views

Non-interactive Zero-knowledge proof signature validation without public key

I'm looking for a method for a scenario with following requirements: At least 3 people (A,B,C,...) are in a Network where they can broadcast messages to everyone but not communicate with a specific ...
1
vote
1answer
96 views

Simplified Fiat-Shamir example generates wrong output

I am trying to implement the Fiat-Shamir identification protocol, however the end results always fail to match. I am using algorithm's description from here. Preparation: Select 2 prime integers ...
10
votes
3answers
344 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 ...
1
vote
1answer
112 views

How to prove that a ciphertext is encrypting multiplication of two values?

Zero-knowledge proofs with soundness, completness and zero-knowledge enable a prover to convince a verifier that a witness validates successfully a predicate without giving any information about the ...
9
votes
1answer
200 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". ...
6
votes
1answer
814 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 ...
0
votes
1answer
59 views

Authentication mechanism for low memory, low computing power device

I am looking for an authentication mechanism that works best with low memory, low computing power devices. I came across a paper "A Practical Zero-Knowledge Protocol Fitted to Security Microprocessor ...
1
vote
2answers
83 views

Can a zero knowledge proof (or MAC) be generated from human-typable input?

Edit: My goal is to create a voting scheme that doesn't require a lot of crypto infrastructure to be deployed on the client side. Smartcards, and tokens are impractical for these purposes. I ...
1
vote
0answers
172 views

What would make it impossible to deny that decryption of a package has taken place?

I'm part of a team designing a system where a user have to be able to read a certain package, if he has preformed an action or series of actions that makes it legal for him to do so. The tricky part ...
1
vote
1answer
90 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
0answers
60 views

Any functioning system for interactive proof?

My problem is to outsource an array of data and ask the prover to sort the data. I am wonder if there is any working system out there that support interactive proof for the above computation? Or if ...
4
votes
1answer
112 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
121 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
266 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 ...
3
votes
1answer
241 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

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
157 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 ...
5
votes
3answers
381 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
129 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
203 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
154 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) ...
4
votes
1answer
171 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. ...
2
votes
0answers
98 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 ...
2
votes
2answers
111 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
1answer
172 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
205 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
169 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\}$ ...
1
vote
2answers
188 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
224 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 ...