Tagged Questions

"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.

787 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 ...
237 views

Zero knowledge-proof for discrete log that is not honest-verifier

Take a cyclic group of prime order. The Schnorr-protocol for proving knowledge of the discrete logarithm of some group element is honest-verifier zero-knowledge, meaning that if the verifier chooses ...
86 views

Verifying Without Knowing Key

Say user Bob sends an encrypted message to a server. People can download the message from this server and later get the key directly from Bob. Is it possible for the server to somehow verify that ...
47 views

what is the difference between proofs and arguments of knowledge?

What is the difference between proofs and arguments of knowledge in the context of zero-knowledge? I have read this sentence in this ePrint: It is useful to distinguish between zero-knowledge ...
107 views

Two-party equality computation

Alice and Bob each secretly chooses an integer between 1 and 10, a and b. They want to know (with high probability) whether or ...
67 views

Why doesn't this operation reveal the voter's message?

I am working my way through this paper. I am trying to figure out the OR zero knowledge proof in figure 2. The prover is verifying that she has correctly voted, and that her input satisfies ...
170 views

Finding out the greater number under zero-knowledge conditions?

Is it possible to construct a zero knowledge proof that one encrypted number is larger (or not) than another encrypted number without releasing the values of either numbers?
307 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. ...
97 views

Zero Knowledge - Who is greater?

I just encountered the term "zero-knowledge" and wanted to know more about it. I understood that there is a zero knowledge protocol between two parties to determine whether $x$ is greater than, equal ...
3k 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 ...
249 views

Homomorphism and Zero Knowledge in FIPS 140-2 compliant systems

I am analyzing a system that needs to be at least level 3 FIPS 140-2 compliant. The system may leverage from homomorphic and Zero Knowledge constructs, but, as far as I can see, the algorithms ...
93 views

Is there any zero-knowledge technique to verify proof of knowledge of shared secret key?

Generally, to verify knowledge/key generated between two interacting parties in an authentication protocol uses Hash, MAC, Digital Signatures or encryption (based on random challenge). But I would ...
237 views

Simulation based proofs: Simple examples

I am aware that,(in theory) in order to proof that a scheme is secure using simulation based proof we replace an adversary in real world with a simulator in ideal world. Then we try to show that their ...
227 views

Hamiltonian Path Zero Knowledge Proof using Commitments to a Series of Edges

Commonly, Zero Knowledge Proofs based on the Hamiltonian Path or Cycle problems are given as follows: The Prover has a graph $G$, for which he knows a Hamiltonian Path (or Cycle). $G$ is also known ...
108 views

In interactive proofs, do we assume that the prover can always solve the problem?

I'm having a difficult time understanding a concept from interactive proofs: A trivial interactive proof for the graph isomorphism problem is having the prover just send a permutation that shows an ...
524 views

What is an example of a secure sigma proof?

I want to implement Threshold Elgamal as described in section 6.3.1 and in the decryption phase each party must broadcast a sigma proof to show that it actually has a valid secret share of the secret ...
200 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 ...
142 views

Zero-knowledge proof for the product of additive Paillier ciphers

Suppose that Alice received the cipher values: $E(x_1), E(x_2), ..., E(x_n)$ that are encrypted using Paillier cryptosystem by $n$ entities with Bob's public key. Alice computes $E(\sum x_i)$ from ...
128 views

Zero Knowledge Argument for Subset Sum

What is the currently most efficient (interactive) zero knowledge proof/argument for the subset sum problem? The most recent relevant paper I have found is Efficient Modular NIZK Arguments from Shift ...
212 views

Proof that a hash matches an encrypted file

Assume that Alice has a file $F$ which she is going to send, in encrypted form to Bob. Alice possesses $F$ and an encryption key $K$. She sends to Bob the encryption of $F$ using $K$, $E(F,K)$ as ...
145 views

Zero knowledge proof of shared secret

Alice holds a secret $a \in X$. Bob holds a secret $b \in X$. Is there a protocol that lets them compute $f(a, b) = \begin{cases} 1 & \textrm{if } a = b \\ 0 & \textrm{else} \end{cases}$ If ...
128 views

Additively homomorphic cryptosystem with non-interactive zero-knowledge proof of non-negativity

I need a cryptosystem that is additively homomorphic. Paillier preferably, but not neccessarily. Also, for every ciphertext the private key holder must be able to prove non-interactively that the ...
2k views

What are SNARKs?

What does it mean and what is it used for, I have been hearing this term a lot lately. From the context I've heard it talked about it seems to be connected with zero knowledge?
191 views

Zero-Knowledge Proof of a polynomial

I have two secret values $L_1$, $L_2$, and two Pedersen commitments $C_1 = C(L_1)$, $C_2=C(L_2)$. The commitments $C_1$, $C_2$ are public. Given a challenge $c$, I want to output $d = c*L_1+L_2$ and ...
2k 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 ...
107 views

How to prove secret value in Pedersen commitment is equal to secret value in Fujisaki commitment?

We have Pedersen commitment C to the secret value x, and Fujisake commitment C' to the secret value x. How can we make a zero-knowledge proof of equality for x value in the commitments?
193 views

Simulation-based proofs and universal composability proofs

I recently read Ran Canetti's famous UC paper but I'm still trying to wrap my head around the concepts. I think this answer has me confused a bit, particularly where it says The stand-alone ...
134 views

Consequence of a change on the Guillou-Quisquater Protocol

In the Guillou-Quisquater Protocol, the prover convinces the verifier that he knows an $e$-th root of an element $y \in \mathbb{Z}^*_n$ ($p, q, e$ are primes, $n = pq$ and $e$ is coprime with ...
82 views

With ECDSA is there a way for the verifier to calculate any properties of $k$?

With ECDSA, given $(r,s)$ and $m$, is there a way for a verifier to calculate any (boolean) properties of $k$, without knowing $k$ or the private key $D_A$? (I understand that $k$ should be random, ...
130 views

Salary Negotiation Problem

Imagine Alice is applying for a new job. Alice has an idea of the minimum salary that she is willing to accept—let's call this value A. Bob, the hiring manager for ...
155 views

How to prove knowledge of discrete logarithm in a product?

Definitions Suppose I have two large safe primes $p$ and $q$, and a composite number $N=pq$. I have $G$, a large cyclic subgroup of $\mathbb{Z}^{*}_{N}$; $g$ and $h$ are generators of $G$. I commit ...
118 views

How to prove that a commitment hides the decryption of an ElGamal ciphertext?

I've decided to remove a previous unanswered question of mine and break it down into smaller pieces so it's not such a loaded question. For this question I need to prove that I've committed to a ...
119 views

Is succinct verification of an arbitrary data transformation theoretically possible? Is it feasible? How?

Given input string S, and transformation (i.e. computer program) T, is it possible to provide a succinct proof that another binary string S' is identical to the output T(S)? By "succinct", I ...
119 views

Zero-Knowledge Proof of Subgraph Isomorphism

I'm trying to find a Zero-Knowledge proof of subgraph isomorphism in the following scenario: Alice and Bob both know about graphs G1 and ...
93 views

How to use “proof of knowledge” to verify the result of modular exponentiation

I am thinking about regarding proof of knowledge as the inverse of result verification in server aided computing. For example, a user asks the server to compute $R=x^y \bmod z$. Normally, the user ...
167 views

On the fly signatures and zero-knowledge

I am reading some articles which explain on the fly signatures (also called online/offine signatures). The principle is that a few operations do not depend of the message we want to sign, so these ...
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?
68 views