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.

1
vote
0answers
31 views

Could you design something like a ring signature that uses website accounts instead of keys?

Ring signatures allow one to prove that you own a private key corresponding to a public key from a set of keys, without revealing which private key you control. This is useful if you are part of some ...
0
votes
0answers
45 views

Prove I know a value v in a set s.t. K = H(v) [duplicate]

Is it possible to prove that I know a value v in a finite set, such that the hash of the value v is K. Where v is private and K is public
2
votes
1answer
56 views

Prove I know a value $v$ in a Pedersen Commitment without revealing it

Given a Pedersen Commitment: $P = aG + vH$ Where $G$ and $H$ are points in some group. $a$ is a blinding value/mask and $v$ is the value I wish to commit to. Is there a way to prove I know $v$ ...
1
vote
1answer
29 views

Prove in Zero Knowledge the execution of a function

Given a function: $$Y = a * b$$ Is there a way to prove in zero knowledge that a value $Y$ was gotten, without revealing $a$ and $b$? Alternatively, that we have knowledge of $a$ and $b$ such that ...
2
votes
1answer
59 views

How to make the interactive Schnorr identification protocol become non-interactive

I am reading about ZKP and I found this interesting question about changing this protocol from interactive Schnorr identification protocol to non-interactive and I need help in solving it : Peggy (...
0
votes
2answers
71 views

zero knowledge proof of encryption

I am trying to see if there is a way to prove that a ciphertext c was encrypted under a given Public Key, Pk, without revealing the plain text message m.
3
votes
1answer
96 views

Fiat-Shamir zero knowledge protocol

In Fiat-Shamir protocol, the final calculation is $$y^2=x\,v^c$$ Where $c$ is the random $\{1,0\}$, $x$ is the witness and $v$ is the public key $s^2 \bmod n$. My questions are: What stops the ...
1
vote
1answer
66 views

Using zk-snarks to check if value is greater than another

Can I use Zk-SNARKS to prove that a given secret value is greater than another public value. for Example to prove that secret_value >10 . if so How would such a circuit look I am using snarks.js ...
0
votes
0answers
20 views

NIZKP that El-Gamal ciphertext is encryption of a prime number among a predefined set of prime numbers

I am working on designing an open source blockchain-based voting platform. Users receive a common public key $K_{pub}$. They cast their ballot, encrypt it with $K_{pub}$ and an ephemeral key $k$ (El-...
2
votes
1answer
82 views

libSTARK TinyRAM private inputs (Zero-knowledge proofs)

I am looking into libSTARK and specifically TinyRAM and I cannot find out how to provide private inputs in a TinyRAM program. As private input I mean a variable that only the prover knows; i.e. the ...
1
vote
1answer
54 views

What is the role of a circuit in ZK-SNARKS

What role does a circuit play in ZK-SNARKS? Is it executed on both the prover's and the verifier's machine? If so, how would you program it to check if one value is greater than another value?
7
votes
1answer
90 views

SNARK-friendly one-way compression functions

I'm looking for a one-way compression function that is secure and efficient within a zk-SNARK circuit. The motivation behind this comes from these considerations: SHA256-compression is highly ...
0
votes
1answer
50 views

How to prove that work is done without actually knowing the payload

Is there a way for an algorithm to run securely on one end, whilst the other end is able to be notified and also verify that it has run and done the work without knowing what the actual payload is? ...
3
votes
0answers
25 views

What is the precise NP statement of Zcash?

It would be great if you can point out the mathematical formulation or R1CS form of the NP statement of Zcash.
2
votes
1answer
64 views

Can we use PHE or SWHE instead of bilinear pairings in ZK-SNARKS?

In ZK Snarks bilinear pairings are used to do "encrypted computation". I was wondering if we can use Partial Homomorphic Encryption or Somewhat Homomorphic Encryption instead of bilinear pairings. Can ...
2
votes
1answer
50 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
62 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 is depicted in this chart. But do those numbers scale linearly to the proof and ...
2
votes
1answer
77 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?
2
votes
1answer
62 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 ...
7
votes
4answers
181 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 ...
-2
votes
1answer
51 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?
-2
votes
1answer
75 views

How Zero Knowledge Proof enables Privacy By Design [closed]

How does Zero Knowledge Proof (ZKP) enable Privacy By Design?
1
vote
0answers
49 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
135 views

Fiat-Shamir transform to Sigma protocols to turn into 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
79 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
49 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
-1
votes
0answers
49 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
185 views

Are zero-knowledge proofs quantum-resistant?

Are zero-knowledge proofs quantum-resistant?
3
votes
1answer
122 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
51 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
63 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
67 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
64 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
93 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
2answers
78 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. ...
2
votes
1answer
110 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
86 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
1answer
48 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
85 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
36 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
113 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
37 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
93 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
1answer
109 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
77 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
48 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
114 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 ??