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.

Filter by
Sorted by
Tagged with
0
votes
0answers
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.. ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
3
votes
0answers
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 ...
0
votes
3answers
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 ...
0
votes
2answers
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 ...
0
votes
0answers
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 ...
22
votes
3answers
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$...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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. ...
1
vote
1answer
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$ ...
1
vote
2answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
3
votes
3answers
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 ...
6
votes
1answer
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)$ ...
0
votes
1answer
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 ...
2
votes
3answers
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 (...
0
votes
0answers
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 ...
5
votes
0answers
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 ...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
2
votes
4answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
2answers
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. ...
10
votes
1answer
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 ...
0
votes
1answer
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 ...
2
votes
0answers
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 ...
4
votes
1answer
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'...
0
votes
0answers
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 ...
2
votes
0answers
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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$...
1
vote
1answer
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, ...
2
votes
0answers
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 ...
18
votes
2answers
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
5
votes
1answer
119 views

Given a ciphertext $c$ and a public string, how do we check whether $c$ encrypts something that is roughly equal to the string without decryption?

Let $𝑓$ be an encryption function, then we have $c = f(m)$ for some bit string $𝑚$. Here, we also have pattern matching function $𝑔(𝑚,𝑚′)$ which returns true whether $𝑚$ matches roughly with $𝑚′...
1
vote
0answers
21 views

How to prove in zero-knowledge that the attributes of Pointcheval Sanders signature is the opening of a commitment?

In anonymous credentials schemes, it is possible to anonymously prove knowledge of a signature. Proposals for anonymous credentials with attributes also include a method for proving statements about ...
0
votes
1answer
102 views

Is the following non-interactive zero-knowledge set membership protocol provable secure?

Given the following Zero-knowledge set-membership protocol https://infoscience.epfl.ch/record/128718/files/CCS08.pdf]. That is given in the following steps (Please refer to page 9). The Verifier -...
2
votes
1answer
79 views

Converting common reference string to common random string

I listened to a talk on NIZK a while ago and vaguely remembered the speaker mentioned something like - A scheme that is statistically sound and computationally ZK in common reference string model ...
3
votes
2answers
59 views

How to show that Cx is a commitment to a integer of length lm

With reference to Jan Camenisch and Anna Lysyanskaya's paper A Signature Scheme with Efficient Protocols, in proceedings of SCN 2002, I need some help to understand How to verify that $C_x$ is a ...
4
votes
1answer
103 views

Constructing division gate in R1CS

One thing I don't quite understand is how to naively handle division operation in rank-1 constraint systems (R1CS). supposedly A.s * B.s - C.s = 0 allows you to ...

1
2 3 4 5
14