Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

2
votes
1answer
40 views

Is there a rule of thumb for ZK protocols?

There's always a small chance for many zero knowledge protocols that the prover had a lot of luck to prove something to the verifier. Take the Ali Baba cave as an example: The prover has a 50% ...
2
votes
0answers
29 views

How do ZK-STARKs, ZK-SNARKs, and Bulletproofs compare in size and speed for range proofs?

How do ZK-STARKs, ZK-SNARKs, and Bulletproofs compare in size and speed for range proofs? The general behavior's here: https://imgur.com/a/TXREZj6. But do those numbers scale linearly to the proof ...
2
votes
1answer
65 views

Extending the Socialist millionaire problem to three parties

The usual solution of socialist millionaire problem allows to authenticate whether TWO parties have the same secret information. Are there any natural solution of the same problem for THREE parties?
1
vote
0answers
26 views

How to prove that a committed value is the square of other

Given two pedersen commitments $c_1=g^vh^{r_1}$ and $c_2=g^{(v^2)}h^{r_2}$, where the committed value in $c_2$ is the square of the committed value in $c_1$, is there a way to prove this relation in ...
-2
votes
0answers
38 views

Challenges to zero knowledge proof adoption at scale?

I am writing a layman thesis on the challenges of zero knowledge proof adoption at scale. Would like to know what are the 3-5 or more challenges of zero knowledge proof adoption at scale for ...
6
votes
4answers
149 views

Can you explain what an NP statement is when they refer to it in Zero knowledge proofs?

When I read about zero knowledge proof, I keep encountering the term NP-statement. I am aware of complexity classes but I am a little unclear on how it ties up to NP-statement. I came across the ...
0
votes
0answers
16 views

Zero Knowledge Schnorr’s Protocol persuade third party

I was reading Elliptic Curve Based Zero Knowledge Proofs and Their Applicability on Resource-Constrained Devices and on section 3.2 it shows the Schnorr’s Protocol. My question is: can the verifier ...
-2
votes
1answer
46 views

Would Zero Knowledge Proof (ZKP) remove the need for Quantum Key Distribution? (QKD)

Would Zero Knowledge Proof (ZKP) remove the need for Quantum Key Distribution? (QKD) Since we no longer need keys to be passed around?
-5
votes
0answers
33 views

Will Zero Knowledge Proof remove the need for centralized repository of password credentials, usernames and password?

Will Zero Knowledge Proof (ZKP) remove the need for centralized repository of password credentials, usernames and password? Since there is no need to exchange username/passwords with ZKP, this means ...
-2
votes
1answer
70 views

How Zero Knowledge Proof enables Privacy By Design [closed]

How does Zero Knowledge Proof (ZKP) enable Privacy By Design?
0
votes
0answers
29 views

Security parameter of double discrete log proof vs. Schnorr

I'm reading Section 5.3.3. of Group Signature Schemes and Payment Systems Based on the Discrete Logarithm Problem. Author states a double discrete log proof of knowledge is less efficient than a ...
1
vote
0answers
46 views

Simulatability of Diffie-Hellman Key Exchange

While reading through Shoup's paper on provably secure Diffie-Hellman key exchange (DHKE), I do not understand something rather simple. There are two parties $A$ and $B$. $A$ starts by sending $g^a$, ...
3
votes
1answer
95 views

Fiat-Shamir transform to Sigma protocols to turn to NIZK

I'm reading about the Schnorr's zero-knowledge proof for DLOG and the Sigma protocol for DH tuple proof, and I want to know how one applies Fiat-Shamir transform to both of them, to turn them into ...
-2
votes
1answer
62 views

Zero Knowledge Proof (ZKP) Threat Vectors / Attack Vectors [closed]

What are some Threat Vectors / Attack Vectors of Zero Knowledge Proof (ZKP)?
9
votes
3answers
2k views

Re-encrypting a message and proving that the message has not changed

Is there a method that allows for re-encryption of a message in a way that allows observers who only have access to the two cipher texts to prove that the plain text message is the same in each? More ...
0
votes
0answers
31 views

Difference between Zero Knowledge Range Proof (ZKRP), Zero Knowledge Set Membership (ZKSM) protocols and ZKP

Like to know the difference between Zero Knowledge Range Proof (ZKRP), Zero Knowledge Set Membership (ZKSM) protocols and ZKP? Nathan Aw
0
votes
0answers
40 views

ZK verifiable shuffle of ElGamal encryption with different public keys

I need a zero-knowledge proof of correctness of a shuffle of $k$ El-Gamal ciphertexts, but where the public key is different for each ciphertext. However, each public key can be generated from the ...
0
votes
2answers
134 views
0
votes
0answers
23 views

Efficiently proving $PK\{ n : \bigwedge_{1 \leq i \leq k} c'_i = c_i^n\}$ for El Gamal ciphertexts $c_i$

Given El Gamal ciphertexts $c_1,...,c_k$, can $PK\{ n : \bigwedge_{1 \leq i \leq k} c'_i = c_i^n\}$ be efficiently proven (in zero-knowledge)? Notation: $(\alpha,\beta)^n = (\alpha^n,\beta^n)$.
3
votes
1answer
108 views

Are SSH key-pairs an example of a zero knowledge proof?

Quoting from source, authentication using SSH key pairs goes something like this: 1) The client begins by sending an ID for the key pair it would like to authenticate with to the server. 2) ...
-1
votes
1answer
45 views

Zero Knowledge Interactive Proof vs zero knowledge proof

What is the difference between Zero Knowledge Interactive Proof and zero knowledge proof? Nathan Aw
1
vote
1answer
53 views

Pairing-based cryptography VS ZK-proofs: what's more efficient for threshold systems?

In some papers (e.g. 1, 2) the authors approve that pairings are more efficient than classic zk-proofs (e.g. proof of discrete logarithm knowledge) for the described applications (threshold encryption,...
3
votes
2answers
63 views

Post-quantum SNARGs with near-constant verification?

We're building a private computation platform similar to Zexe, where nested proofs are used to preserve the privacy of the programs being computed. We may use different proof systems for the inner and ...
0
votes
1answer
57 views

Zero knowledge proof in smart parking managment systems

I read this paper on protecting user privacy in smart parking management system. It talks about using zero knowledge proofs to protect privacy but I am not certain how they do it. My assumption is ...
2
votes
1answer
81 views

Verification of encryption for ElGamal cryptosystem

Suppose Alice wants to convince Bob that ciphertext c = (a, b) = (gr, m*hr) is some properly encrypted plaintext (not just random numbers). Obviously she can use zk-proof of discrete logarithm ...
0
votes
0answers
22 views

Existence of a NIZK proof demonstrating that a ciphertext does not encrypt some specified plaintexts

Given a (El Gamal, for instance) ciphertext, can I (efficiently) prove that the ciphertext does not decrypt to plaintexts in a small set? For instance, given ciphertext $c = Enc(pk,2; r)$, can I (...
0
votes
2answers
66 views

Difference between Zero Knowledge Proofs and Multi Party Computation

I am struggling with understanding the difference between the two. From what I am putting together, they have different adversarial models, MPC adds the condition of collusion between parties i.e. ...
1
vote
1answer
75 views

How much time to generate a proof in ZK-snark?

I know that zk-SNARK takes in range of milliseconds to verify statements. But what about the time to generate the proof. For example, if I have a circuit that tests the ...
6
votes
1answer
84 views

Zero Knowledge Police Check

I’m curious if there’s a zero-knowledge protocol for the following. Suppose a Passer-by is stopped by a Vigilante who has a list of wanted criminals. Can the Passer-by prove he has a valid ID and he’s ...
0
votes
0answers
25 views

How to get the time to generate a proof or to verify it in Zk-SNARKs? [duplicate]

My understanding of Zk-SNARKs is that it consists of 3 algorithms(Gen, Prove(Pk, X, W), verify(VK, X, pi)). According to 1, the time to generate a proof or to verify in range of milliseconds. If I ...
0
votes
1answer
45 views

Verification of data on an untrusted remote storage server

I was looking at tahoe-lafs which accepts a file, encrypts it, does erasure coding on it which generates n shares and then distributes it over the storage servers. The distribution is Share 1 = Server ...
4
votes
1answer
75 views

Is this Sigma Protocol zero knowledge or is it just a proof of knowledge?

Suppose I have the witness $x$ and need to prove that I correctly computed $(g^x)^x$ to a verifier. $g$ and $g^x$ are public. The verifier asks me for $(g^x)^x$, but wants proof that I've given them ...
1
vote
0answers
33 views

Extractability property in Zero Knowledge Discrete Log problems

I am trying to construct a simulator and an extractor for a zero knowledge protocol. I just encountered this text that explains the construction of the simulator. Does someone know of a similar text ...
3
votes
1answer
110 views

Zero Knowledge and Computational Indistinguishability

Having some trouble understanding the following line: “Alice conveys zero knowledge to Bob if Bob can sample from a distribution of messages that is computationally indistinguishable from the ...
0
votes
2answers
107 views

How to compute secure sum using secure multparty computation?

Suppose there are three voters $P$, $Q$ and $R$, and each will vote only on one candidate out of $X$, $Y$ or $Z$, with a 6 bit vote vector corresponding to $X $, $Y$ and $Z$ respectively (with 2 bits ...
1
vote
0answers
36 views

Why isn't a range proof calculated using size?

For example a Pedersen commitment for an elliptic curve of maximum $2^{64}$, requires every number between $0 \to 2^{64}$ to be checked. Why do range proofs, in the case of a Pedersen commitment, not ...
5
votes
1answer
87 views

How is ZKPP better than signing nonces?

I am trying to understand the use case for zero knowledge password proofs. Clearly, it is not ideal for a remote server to store a password hash. Then I need to upload the password to the server for ...
7
votes
0answers
74 views

True/False if a user is a customer without revealing the actual customer

I have a user A and a third party company B. I want to check if A is a customer of B. B cannot reveal any information about their customer list to me. If A is a customer of B, I do not want B to ...
2
votes
1answer
66 views

What is the relationship between a NIZK protocol and a digital signature scheme?

I am reading about the Fiat-Shamir heuristic to take a $\Sigma$-protocol into a non-interactive zero-knowledge proof (NIZK). I am now wondering whether there is a relationship between a NIZK proof and ...
1
vote
0answers
37 views

Drawbacks of Schnorr Authentication that require Fiat-Shamir and Random Oracles?

I've been going through G. Maxwell's paper on the Borromean Ring Signature, and I don't fully understand this part on Schnorr Signature. If some could explain it more intuitively thank you. "...
1
vote
1answer
100 views

Implementing a zero-knowledge proof [duplicate]

I'm trying to get my head around zero-knowledge proofs and my definition of a zero-knowledge proof is as follows. A zero-knowledge proof is a method by which one party can prove to another party ...
1
vote
0answers
43 views

Preserving location privacy

What are cryptographic techniques that could be used so that if I wanna to enable a server to send message to certain nodes in a network with preserving the privacy location for them ??
1
vote
1answer
68 views

Check if $a<b$ in a trustless scenario

Let's say Alice has access only to a value $a$ and Bob has access to both $a$ and $b$. I need ...
2
votes
1answer
71 views

Is a zk-SNARK the hash of a Linear Interactive Proof?

zk-SNARK researcher Eran Tromer came up with the following workflow when describing how these proofs are created: What I am struggling to understand is how a LIP becomes a zk-SNARK. Is the SNARK a ...
6
votes
2answers
138 views

Practical consequences of a honest-verifier zero-knowledge of the Schnorr protocol

Schnorr protocol is known to be honest-verifier zero-knowledge and not perfectly zero-knowledge. What are the practical consequences of this fact? Does it mean a dishonest verifier can do something ...
3
votes
1answer
73 views

Zero-knowledge proof of knowledge without replay

Given a hash function: $H(x)$ = y $y$ is publicly known. Alice wants to prove to Bob that she knows $x$. ...
2
votes
1answer
87 views

Zero knowledge proof of the sum of two values

Given $v \in Z$, a prover knows $v$ and the verifier knows an encryption of $v$. The prover provides the verifier with the encryptions of two values $m$ and $n$ How can the verifier verify that $m+n=...
2
votes
1answer
48 views

Bitwise operation on secret values revealing the result only to the participants

Given the following situation, what sort of cryptographic construction am I looking for? Alice has a bitfield (vector, polynomial representation, etc.) Bob has a different bitfield of the same length ...
4
votes
0answers
78 views

Zero knowledge proof for a discrete logarithm

Say a have a group $G$ chosen as $Z_N^*$ where $N=pq$ and both $p$ and $q$ are safe primes. The algorithm for discrete logarithm is as follows: Pick $g$ as a random element from $Z_N^*$ Pick $x$ as a ...
2
votes
1answer
73 views

Expected Polynomial time Simulator in Interactive ZKP

I was reading the Zero knowledge property for Interactive Proofs. It said that for the proof to be zero knowledge, there should exist a simulator that runs in expected polynomial time for all ...