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

662 questions
Filter by
Sorted by
Tagged with
48 views

### Why in the Fiat-Shamir heuristc for proving the knowledge of a discrete logarithm an hard to invert function has to be used to create the challenge?

Consider this example from Camenisch, J., & Stadler, M. (1997). Proof systems for general statements about discrete logarithms. Technical Report/ETH Zurich, Department of Computer Science, 260.. ...
27 views

### What is the difference between zk-SNARK and NIZK?

I am not exactly sure what is the difference between the zk-SNARk and NIZK? Is NIZK not succient? If so, why Pinocchio protocol considered itself NIZK although they have succient proof? I tried Google ...
212 views

### Why are logic gates assigned integers when checking QAP in zkSNARK algo?

I am trying to understand how zkSNARKs work. Going through this article by Vitalik, in the section on 'Checking the QAP' he says " If the resulting polynomial, evaluated at every x coordinate ...
39 views

### How to construct a circuit in zkSNARK

I have a few questions about how to use zk-snark. Since the basic logic of using zk-snark is: using a circuit to represent a problem, generate an R1CS from the circuit, transform R1CS to QAP and then ...
56 views

### The challenge c in Sigma protocol (using Fiat Shamir)

As is known to all, the following picture depicts a sigma protocol, and to eliminate the interactivity, Prover can generate c by hashing (t, y) using Fiat Shamir transform. My question is: 1). Can c ...
96 views

### Proof that a particular algorithm has been used

I’m looking for the existence (or the proof of non-existance) of a method to prove (with arbitrary certainty) that a particular output is the result of a particular algorithm applied on a particular ...
45 views

### Prove that I know string that hash to h [duplicate]

Lets say p = str and h = SHA512(p) i send the h which is the SHA512 of ...
3k 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 $h$...
46 views

### Finding a winner in mental poker game

In a mental poker game I am designing as an learning exercise, (One used in example is a 3 card flash with no desk cards) suppose I have a set of cards and other person also has a set of cards. each ...
19 views

### Constructing efficient zero knowledge proof card game

I had asked an unanswered question earlier and now, I think I have an answer (sort of), not really but I think I know where to look for it. We assign each type of card combination a score such that a ...
99 views

### Can I prove in zero knowledge that the public key corresponding to a secret that I committed is in the Accumulator?

I have a set of users in my system, each having a private/public keypair of a digital signature scheme. I also have an accumulator in my system, where all the public keys of the users are accumulated. ...
50 views

### Show that there is an efficient zero knowledge proof for any language $L \in NP$

Let $(P,V)$ be an efficient zero-knowledge interactive proof for some language $A \in NP$ that is $(T,\epsilon)-\text{sound}$ and $(T,\epsilon)-\text{ZK}$. I want to show that for every language $L$ ...
162 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 ...
16 views

### Whether the proof created by prover can be tampered in zero knowledge proofs?

I am studying zokrates recently. I know that the prover will finally generate a proof, and then the verifier can use this proof and public input as input to verify whether the prover has certain ...
39 views

### How does one go about implementing a range proof?

I've attempted to find a solution to this problem, but for the life of me I am unable to. I am attempting to solve whether a point an elliptic curve of prime order is between 2 points, given a ...
116 views

### Difference between Zero Knowledge Proof and Challenge Response Protocol

What exactly is the difference between Zero Knowledge Proof & Challenge Response Authentication? I searched online and the best I could find are these: techtarget.com Zero-knowledge password ...
370 views

### Zero knowledge proof for Paillier addition under multiple keys

Suppose $m_0, m_1, m_2 \in \mathbb{N}$ such that $m_0 = m_1 + m_2$, $m_i > 0$ (none of them can be 0 or lower) Under a Paillier cryptosystem, set $e_0 = E(m_0, r_0)$ for a public key $(g_0, n_0)$ ...
106 views

### Relationship between special RSA modulus and quadratic residue in CL (Camenisch-Lysyanskaya) signature

I'm studying the CL(Camenisch-Lysyanskaya) signature (A signature scheme with efficient protocol proposed by Camenisch-Lysyanskaya). However, I cannot understand ...
77 views

### Reason for squaring and not arbitrary exponentiation in Wesolowski and Pietrzak verifiable delay functions (VDFs)

I'm working at understanding the Wesolowski and Pietrzak RSA group based VDFs (verifiable delay functions). These basically work by requiring the prover to do a bunch of repeated squaring within a ...
21 views

### How to prove to recipient that we are using public parameters correctly in lattice IBE

Many lattice IBE scheme follow the scheme outlined in ABB10. In ABB10, the ciphertext is $c_0 = u^\top s + x$, where $u$ is a public parameter. (No consider message here.) I want to ask: Is it ...
16 views

### How to construct inequality, padding, and truncation in R1CS?

I'm trying to reimplement the zkSNARKs used in zcash using the libsnark library. It involves checking for inequality, and bit manipulation such as padding and truncation. How do I implement those in ...
80 views

### Non-interactive zero-knowledge proof system for a language undecidable in polynomial time

I am studying through some material in an online course, and there is an exercise which I could not figure out. The problem is this: Let $L$ be a language that is not decidable in polynomial time (...
16 views

### Zero knowledge proof of symmetric keys and encrypted texts resulting in the same text, if the symmetric keys are encrypted with asymmetric ones

Suppose I have: text T, symmetric keys X, Y encrypted text T with symmetric keys X, Y = TX, TY accordingly asymmetric key Z, used to encrypt X, Y to transmit them to a person. Let the encrypted ...
56 views

### Understanding anonymous credentials. Does someone understand how it works?

After reading a series of papers CL01 CL02 CL04, I feel like I understand the intuition behind the anonymous credential framework but I don't understand some details the mathematics behind it. I ...
58 views

### How to securely deal cards?

Thanks to a certain pandemic going around I was wondering whether there is any cryptographic way to remotely deal cards without the dealer being able to know them and without requiring to trust a ...
35 views

### What is the adversary advantage for soundness of a sigma protocol?

Does a sigma protocol have an adversary advantage of zero for soundness? Or is this affected by the probability distribution of the indistinguishability of the simulator? Will in that case using the ...
205 views

### Is it possible to verify and relay an encryption key with a trusted but transparent third party?

I'm wondering if it would be possible to implement this functionality with a trusted but transparent third party (maybe an Ethereum smart contract?): Bob has an encryption key. Alice has the ...
75 views

### ZKP for product of two primes

I'm struggling to understand the intuition of the zero knowledge-ness of this proof from the following paper. The proof is a 2 round where the verifier asks the prover to extract square roots of ...
16 views

### Universal Computation “measurement” using SNARKs?

If SNARKs are able to prove computations of arbitrary complexity and difficulty were executed correctly, would it be possible to use them to create a Proof of Work consensus system where ANY ...
249 views

### ZKP: Asymmetric encryption with confidential message and known hash

I'm searching for a ZKP package that supports asymmetric encryption so I can implement the following scenario: Carol encrypts message $m$ with Alice's public key and sends the ciphertext to Alice. ...
288 views

### Minimizing exchanges for ZK proof of a message with given SHA-256

Consider the problem of proving knowledge of a message $m$ which has a certain public SHA-256 hash $h$, without disclosing $m$ or usable information about it, while minimizing the information exchange ...
118 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 ...
44 views

### Demo a Proprietary Signal Processing Algorithm Without Cheating

I have a proprietary signal processing algorithm, $F(s)$, which I would like to demo to my customers. The demo starts with the customer uploading a binary signal $S_0$ to my website. I then generate a ...
730 views

### In zkSNARKS, does R1CS require every step of the calculation, or just statements which confirm the calculation was performed correctly?

I was attempting to figure out a way to implement the modulo operation as a set of gates in an Rank-1 Constraint System, detailed by Vitalik Buterin here However, it occurred to me that maybe we don'...
33 views

### Zero knowledge proof of Paillier cryptosystem

I have read the paper recently and I am curious about part 3. According to part 3, Bob sends a zero-knowledge proof such that $c_B=b\times_{E}c_A+_E E_A(\beta')$. Then Alice should first decrypt the ...
36 views

### Predicting with a machine learning model while preserving the privacy

Imagine Alice has trained a machine learning model. She wants to store her model in a blockchain so that everyone can use it; however, she wants her model to be private so that no one can steal her ...
51 views

### Verification of NIZK proof with algebraic MACs

The paper Algebraic MACs and Keyed-Verification Anonymous Credentials, includes a way to instantiate a NIZK proof with algebraic MAC. This is given in Appendix E where this NIZK is a part of the ...
124 views

### Proof of using a literal from known set, inside a computed formula

Suppose I have publicly revealed the value of $\phi(u) = A+Bu$, where A, B, u are private values from a large group, that I want to keep in secret. Furthermore, I want to add proof that the value $u$...
112 views

### How can I combine Quorum and Zero Knowledge Range Proofs

I have 20 years of experience at java JEE coding, and 10 years in devops as well, but no experience with blockchains, or the Go language. I want to setup a cluster of Quorum blockchain nodes, ...
37 views

### Zero knowledge proof for verifying a machine learning model

Imagine Alice has trained a machine learning model. Bob wants to verify that whether Alice actually trained the model or not, but Alice does not want to reveal her model (because the model is personal ...
3k 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 ...
34 views

### how to verify the digital signature in a zero knowledge proof

I know that the zero knowledge proof is able to prove to the verifier that the holder does in fact posess the digital signature issued from an issuing 3rd party but... How does the verifier validate ...
32 views

### Can zk-SNARKs prove satisfiability for NP-hard languages?

In general, I think of zk-SNARK circuits representing a language in NP, meaning it is "computationally easy" to verify. However I was reading about a recent zk-SNARK (Sonic) which has as ...
75 views

### Zero-knowledge proof for multiplication in the exponent

We have $c_1=g_1^x$, $c_2=g_2^y$ and $c_3=g_3^{x/y}$, where $g_1,g_2,g_3$ are generator of a group of order $n$ and we don't know the DL between them. Is there any sigma protocol or zkp that can prove ...