Stack Exchange Network

Stack Exchange network consists of 175 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
2answers
20 views

Zero Knowledge for Low Entropy Witness

For any PPT prover ($p$) and verifier ($v$), imagine I have a low entropy witness, say smaller than $2^8$. Now, let us say I have a dlog statement in the form of $y = g^w$. Theory says I could use a ...
0
votes
1answer
28 views

Extractor for Oblivious Transfer Protocol

In a paper that I have been reading (https://cs.nyu.edu/~ganesh/zk.pdf), in one of the proofs, this has been said: The simulator works as follows: It uses the OT simulator to extract the prover’s ...
0
votes
0answers
26 views

What is a rank-1 constraint system?

Why not rank-2 constraint system or rank-3 constraint system? How do rank-1 constraint systems link to circuits?
2
votes
0answers
15 views

Strategies for fast integrity attestation over multi party computation for large messages

I am looking for ways to efficiently perform integrity attestation over large messages using multi party computation. While, hashing (SHA1, 256...) is one alternative but it's painfully slow and grows ...
2
votes
0answers
47 views

Is this an error in the Pinocchio Protocol paper

I am going through the Pinocchio protocol paper and I need 2 clarifications in the section Protocol 1 (Verifiable Computation from strong QAP). The part that explains the Verify process, which ...
2
votes
1answer
82 views

Disjunctive zero knowledge proof of equality of committed values

I have read on ZK proof of equality of committed values, that is for $g^xh^y$ and $g^{x'}h^{y'}$, prove in ZK that $x = x'$ (can also be generalized if generators are different using sigma-protocols). ...
0
votes
0answers
42 views

Simple proof of knowledge

It seems to me that signing the hash of the public key with ECDSA should be a sufficient non-interactive proof of knowledge. In my use case, I only need the guarantee that "someone even had ...
1
vote
1answer
101 views

What is purpose of a simulator and extractor in zero knowledge proof protocols?

I am new to zero knowledge proofs. I read the paper Efficient Protocols for Set Membership and Range Proofs by Jan Camenisch, Rafik Chaabouni and Abhi Shelat. The author proposed a zero knowledge ...
2
votes
1answer
49 views

In constraint systems for ZK proofs, why are multiplications counted but are additions not?

For example, If I wanted to prove that: $$x^2 + x^3 = 45$$ This cost of this would be calculated by counting the number of multiplications that need to be done, and not the addition of $x$ squared ...
2
votes
1answer
40 views

Subtracting one pederssen commitment from another

I am building a range proof to prove that a secret number x lies between a specific range a prover commits to a values a<x<b prover generates a pedersen ...
2
votes
0answers
41 views

The theory of transformation of arithmetic expressions into boolean circuits in zkboo

I've read the sources of ZKBoo where they transformed arithmetic operations of the SHA hash functions into a bunch of boolean ones. Where does this transformation arise from? How do you construct such ...
0
votes
0answers
52 views

Can we build a zero knowledge mapping using public-key encryption?

I'm trying to understand if this design is possible. I want to build a mapping that is zero-knowledge, between a (pubkey, proposalId) => bytes form, without ...
1
vote
1answer
51 views

Proof of ignorance to prevent “double-spend”?

Suppose I have some knowledge that I want to transfer securely from Alice's computer to Bob's computer, and prove that future breaches to Alice's computer will not reveal that information to someone ...
2
votes
1answer
45 views

Witness-Extended Emulation

I am reading up on Sonic: Zero Knowledge SNARKS from Linear - Sized Universal And Updateable Structured Reference Strings. An excerpt: For soundness, we do not use the standard definition of ...
1
vote
1answer
59 views

ZK due to rewinds, why we need poly number of rewinds?

I've been looking into rewinding techniques for proving ZK and got a bit confused. This answer is good, but I still have questions about challenge size and the number of rewinds. Consider an ...
1
vote
0answers
36 views

Rewinding Argument and Forking lemma

In Dan Boneh's crypto book, there is a section describing the "Rewinding Lemma", however I cannot find it explained in other sources on the internet. How does this differ from the forking lemma?
0
votes
0answers
42 views

Helios voting system voting verification

In the decryption step in helios, why do we need Chaum-Pedersen to prove that a certain plaintext $m$ corresponds to a given ciphertext $c$? Why can we just encrypt $m$ and see if it's equal to $c$?
0
votes
1answer
60 views

How to compute a challenge c using Fiat Shamir?

I have a prover and verifier. They are engaged in a zero-knowledge proof protocol. A verifier sends a challenge $c$ to the prover so he can compute a proof using the value $c$. How to use Fiat Shamir ...
2
votes
2answers
94 views

How do I create a cryptographic signature and commitment scheme with accountable evidence?

This is a weird one... I am looking for a method which I don't even know how to call, nor whether it actually exists! Given a pair of asymmetric keys $s_{k}/P_{k}$ and defining $Sig_{k} \dagger B_{i}$...
1
vote
1answer
78 views

Zero knowledge set membership protocol

I read that paper Efficient Protocols for Set Membership and Range Proofs of Camenisch et. al that describes the zero knowledge range proof. The paper applications looks interesting like if you want ...
0
votes
0answers
45 views

Could any one suggest alternative Zero knowledge proof protocol to Schnorr protocol ZKP?

I read that Schnorr protocol cannot be proved zero knowledge on that link: Perfect zero knowledge for the Schnorr protocol? Could any one suggest alternative Zero knowledge proof protocol so a prover ...
2
votes
1answer
89 views

Zero Knowledge range proof

I like the idea of a Zero Knowledge range proof. But I read that, to prove my age in a range, a commitment is required by a trusted party (TP) stating my age. How does that work? is the commitment a ...
1
vote
2answers
40 views

NIZK proof for randomization of DLOG

One can have a NIZK proof for DLOG by applying Fiat-Shamir heuristic to Sigma protocol, such that one can prove non-interactively that $x$ is discrete logarithm of $X = g^x$. Then, in simulation based ...
3
votes
1answer
78 views

How can Peggy prove she knows one of Victor's passwords in zero knowledge?

Say Peggy wants to prove to Victor that she knows one of his passwords. She doesn't want Victor to know which password she knows, because she knows that some passwords are more valuable to Victor than ...
3
votes
1answer
132 views

Zero knowledge proofs for a Merkle Tree

Say I have a publicly available Merkle tree, and I want to prove the existence of a leaf (containing a number, maybe) in the tree. I could give the path along with the siblings, for a normal Merkle ...
3
votes
1answer
155 views

Is it possible to validate an email address without the user actually revealing the email address?

Say hypothetically I want a service where users express their opinions. But those opinions are heavily dependent upon where they work, and the best way to prove that they actually work at a specific ...
-1
votes
1answer
42 views

Verification of the NI-ZK Proof

I'm currently learning about ZKP and Non-interactive zero knowledge (NI-ZK) but I'm confused in the process of NI-ZK verification. I have taken the following example to learn about NI-ZK from this ...
4
votes
2answers
85 views

Why does libSTARK use binary fields as opposed to prime fields for zk-SNARKs?

zk-STARKs make use of FRI for low degree testing of polynomials. The zk-STARKs paper states on page 11: we stress that ZK-STARK could also operate over prime fields but we have not realized this ...
1
vote
0answers
49 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
50 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
3
votes
2answers
137 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
47 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
80 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
110 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
138 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
95 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 ...
2
votes
1answer
113 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
67 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
116 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
56 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? ...
6
votes
1answer
61 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
76 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
57 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% ...
3
votes
0answers
94 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
85 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?
3
votes
1answer
93 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 ...
8
votes
4answers
247 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
59 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
81 views

How Zero Knowledge Proof enables Privacy By Design [closed]

How does Zero Knowledge Proof (ZKP) enable Privacy By Design?
1
vote
0answers
61 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$, ...