"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

0
votes
0answers
20 views

Hiding and Binding key in Groth-Sahai NIZK proof system

In context of Groth-Sahai NIZK proof system, I have a couple of doubts on Hiding and Binding keys. In case of hiding keys (highlighted in red), how is it ensured that $\tau(A) \subseteq \langle ...
-1
votes
0answers
24 views

Equality of commitments to group elements and exponents in Groth-Sahai proofs

In Groth-Sahai NIZK proof system, is it possible to show the equality of commitments to group elements and exponents without opening them? Assume, the group involved here is $\mathbb{Z_p}$, i.e. the ...
0
votes
0answers
48 views

How does multi platform encrypted cloud storage work?

I'm really interested in end-to-end encrypted cloud storage and couldn't find out how following scenario could work: A user of a cloud provider which provides zero-knowledge-authentication (like for ...
0
votes
0answers
64 views

Simplifying the zero-knowledge proof example? [duplicate]

There is this http://en.wikipedia.org/wiki/Zero-knowledge_proof#Abstract_example. Now I'm curious about this. Why is it not possible for Victor to stand at the entrance and watch Peggy take one path ...
1
vote
0answers
46 views

Is there a way to “shorten” a Merkle chain?

If I have a Merkle chain of 3 items, is it possible to create a zero knowledge proof of the existance of a correct chain between hash 1 and hash 3? Editing to clarify (Thanks Ricky), what I mean my a ...
0
votes
1answer
46 views

Explanation of the Fiat-Shamir heuristic

The Wikipedia page on the topic (http://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic) is completely useless as it only explains what it is and not how it works. I looked at the original paper ...
0
votes
1answer
118 views

Secure Multiparty Sum in malicious model using threshold encryption

Suppose $n$ actors each hold a plaintext $p_i$. We wish to find $\sum p_i$, without leaking any information about individual $p_i$. Any actor (or any link in the network) could be controlled by an ...
3
votes
3answers
141 views

Zero Knowledge Example using discrete log

I've been exploring Zero Knowledge Proofs and while the classic cave example by Jean-Jacques Quisquater makes sense, I find the discrete log example problematic. Since the Verifier is given p, g and ...
1
vote
2answers
207 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?
-1
votes
1answer
85 views

Isn't Groth-Sahai proof system applicable beyond Bilinear groups?

Classical paper by Groth-Sahai on NIZK proof system is titled as "Efficient Non-interactive Proof Systems for Bilinear Groups". To my understanding, only (Pairing Product Equation) PPE are defined ...
1
vote
1answer
73 views

Chess Grandmaster Problem and “Valid” Attacks on Zero-Knowledge Proofs of Identity

A long question here, but I really want to motivate why I'm confused. Consider the following attack on the Schnorr Identification Scheme. Alice chooses a random $k$, computes $\gamma = \alpha^k ...
1
vote
1answer
90 views

Correctness vs Completeness

What is the conceptual difference between the definition of correctness and completeness in verifiable cryptographic protocols? They justify that if a statement is correct then the verification should ...
3
votes
1answer
50 views

NIZK Proof of knowledge N of M discrete logarithms (threshold)

It is well known how to produce a NIZK that curvepoints $aG$ and $aP$ have the same discrete logarithm $a$ with respect to the curvepoints they are multiplied by. There is also a way to prove that a ...
0
votes
1answer
41 views

Group Dependent Language

The text below has been taken from the below paper Groth-Sahai Paper. The relevant part is highlighted in red. What does this group-dependent language mean in this context? From the definition of a ...
1
vote
2answers
113 views

Is it possible to find out whether a number is greater than another number without knowing the numbers?

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?
2
votes
1answer
60 views

Committing Bilinear equation in Groth-Sahai framework

Groth-Sahai framework enables us to commit to QE, MSME, PP equations. Now, is the equation below committable in GS framework? A bilinear map $e: G_1 \times G_2 \rightarrow G_T$. $g_1 \in G_1$ and ...
0
votes
0answers
25 views

Calculating cost of variables and equation in Groth-Sahai (DLIN) proof system

In Groth-Sahai proof system under DLIN assumption [Page 29], they have provided a few number denoting the cost of each variable and equation. Can anyone please explain how did they calculated the ...
2
votes
0answers
68 views

What does Set Membership actually prove?

While going through this paper, I came across the idea of Set Membership proofs. The proof allows a prover to prove that a value is contained in some set. The point where I am confused is, all the ...
1
vote
0answers
63 views

Groth-Sahai proofs and hardness assumptions

I am learning Groth-Sahai NIZK proof system for Bilinear groups. While going through the literature, I am getting confused on how the proof system is related to Subspace Decision, SXDH or DLIN ...
4
votes
0answers
123 views

understanding the proof of knowledge

Recently I've been reading the paper “A New Family of Implicitly Authenticated Diffie-Hellman Protocols”. It's very hard for me to go further. Especially when it comes to the proof of knowledge. ...
1
vote
1answer
53 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
48 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
63 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 ...
1
vote
1answer
47 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
3answers
147 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$ ?
4
votes
2answers
155 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
203 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 ...
4
votes
1answer
182 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
71 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 ...
2
votes
2answers
164 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
282 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 ...
-1
votes
1answer
138 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 the server should verify that the client runs software from specific source code. It has to be verifiable ...
2
votes
1answer
227 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$. ...
2
votes
0answers
62 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
135 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
83 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
180 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 ...
2
votes
2answers
104 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 ...
-2
votes
1answer
125 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 ...
7
votes
2answers
187 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
108 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
154 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
175 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
656 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
146 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 ...
10
votes
1answer
212 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". ...
7
votes
1answer
1k 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
65 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
90 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
181 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 ...