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.
270
questions with no upvoted or accepted answers
9
votes
0
answers
2k
views
Comparison of SNARK-friendly hash algorithms MiMC7, Poseidon, Pederson?
There are some cryptographically secure hash algorithms designed to be efficient for SNARKs, STARKs and FHE. Some of them already implemented in Zcash, Zokrates and circom. The ones that I know of are:...
- 951
8
votes
1
answer
711
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)$
...
- 81
7
votes
0
answers
244
views
Proof of Knowledge & Rewinding Lemma
I'm somewhat confused about how the definition of a proof of knowledge relates to the Theorem 19.1 in Boneh-Shoup (http://toc.cryptobook.us/book.pdf), particularly in relation to Schnorr's protocol ...
6
votes
0
answers
127
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 ...
- 722
5
votes
0
answers
581
views
How the mimc bug from circomlib was safely exploited to fake the merkle root in the witness in practice?
Several years ago, there was an unenforced constraint on verification in the cirmcomlib library : a tool for building projects using ZsNarks. The error allowed to forge cryptographic nullifiers/proofs ...
- 153
5
votes
0
answers
91
views
Why do Lattice-based Proof Systems not use the $\ell_2$ norm and canonical embedding?
I was recently reading the paper A non-PCP Approach to Succinct Quantum-Safe Zero-Knowledge.
Among other things, it discusses an adaption of the "folding" technique (from Bulletproofs) to ...
- 11.6k
5
votes
0
answers
263
views
How do they avoid Zero Knowledge Proofs in the paper Priced Oblivious Transfer: How to sell Digital Goods?
I don't understand a part of the paper Priced Oblivious Transfer - How to Sell Digital Goods. Particularly, the authors avoid using zero knowledge proofs and in section 3.3 they explain how they do ...
- 51
5
votes
0
answers
430
views
Additively homomorphic cryptosystem with non-interactive zero-knowledge proof of non-negativity
I need a cryptosystem that is additively homomorphic. Paillier preferably, but not neccessarily.
Also, for every ciphertext the private key holder must be able to prove non-interactively that the ...
- 275
5
votes
0
answers
982
views
How to prove that a commitment hides the decryption of an ElGamal ciphertext?
I've decided to remove a previous unanswered question of mine and break it down into smaller pieces so it's not such a loaded question.
For this question I need to prove that I've committed to a ...
- 107
4
votes
0
answers
118
views
Applications of ZK proofs without proof of knowledge?
With the appearance of cryptocurrencies several applications of ZK proofs were envisioned. However, to the best of my knowledge, all of these are proofs of knowledge.
My question is: are there any ...
- 3,922
4
votes
0
answers
826
views
2 different definitions of Special Soundness
There are 2 different definitions of special soundness in the literature:
(1) can be found in Damgard:
We say that a Sigma-protocol $\Pi$ satisfies special soundness, if there exists a PPT extractor $\...
- 173
4
votes
1
answer
451
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.
...
- 41
4
votes
0
answers
88
views
Can zero-knowledge proof be used to determine if another person knows a certain movie with a twist ending?
Suppose I want to talk with a co-worker about a movie called "The Twist Movie". I know the movie contains an interesting twist, and bringing up the movie in a discussion about twists in movies might ...
- 41
4
votes
0
answers
219
views
Transferable zero-knowledge proofs
Many interactive ZK-proofs satisfy non-transferability; that is, the prover performs a series of actions to convince the verifier of a certain fact, and this verifier can't use this proof to convince ...
- 41
4
votes
0
answers
141
views
Are zkSTARKs simulation sound extractable in the random oracle model?
I've recently become interested in simulation sound extractable zero-knowledge proofs for use in UC-secure protocols. I've also become interested in the recent instantiation of PCIPs called zkSTARKs. ...
- 505
4
votes
0
answers
300
views
How to modify the Socialist Millionaire Protocol to be symmetric.
In the Socialist Millionaire Protocol, the roles of Alice and Bob are almost symmetric. By this I mean they do almost the same thing, until the very last step.
In the final step, both parties check a ...
- 151
4
votes
0
answers
240
views
understanding the proof of knowledge
Recently I've been reading the paper “A New Family of Implicitly Authenticated Diffie-Hellman Protocols”. It's very hard for me to go further. Especially when it comes to the proof of knowledge. ...
- 49
3
votes
0
answers
17
views
If a trusted entity is required to attest to a user's data accuracy, what is the value-add of ZKP's?
I think I understand the value of using ZKP's for proving things about data in isolated systems, like for privacy and computation roll-ups in blockchains L2's.
But I hear a lot about real-world use-...
- 31
3
votes
0
answers
23
views
Verifiable encryption: Comparison between FS01 and CS03
Consider the following two verifiable encryption schemes for Discrete Logarithm.
FS01: “One Round Threshold Discrete-Log Key Generation without Private Channels” by Pierre-Alain Fouque and Jacques ...
- 529
3
votes
0
answers
55
views
Arithmetic Circuit to Square Arithmetic Program (SAP)
I'm trying to figure out how to convert a circuit into a Square Arithmetic Program (SAP). This is to eventually use it for zk-SNARKs such as Groth16.
I do however understand how to convert arithmetic ...
- 31
3
votes
0
answers
114
views
Zero Knowledge Proofs for Microsoft SEAL (Homomorphic Encryption)
I am working on a system involving multiple parties performing homomorphic cryptographic operations using Microsoft SEAL (BFV). Because of the nature of the system, it would be preferable for the ...
3
votes
0
answers
326
views
Why is ZKP authentication not used in practice?
I have been reading about Zero Knowledge Proof (ZKP) protocols for a while now. Among the applications I have seen the most is authentication (https://ethereum.org/en/zero-knowledge-proofs/#...
3
votes
0
answers
150
views
Proving equivalence of discrete logarithms over a modulus of unknown factorization
A prover has a secret exponent $x$, two public bases $g$ and $h$, and a public RSA modulus $N$ of which no party knows the totient/factors. All inputs other than $N$ are coprime with $N$ with ...
- 498
3
votes
0
answers
58
views
Applications of Shuffle Proofs
Shuffle proofs enable a prover to show that a vector of commitments or encryptions $(c_1, \dots, c_n)$ is permuted into a vector of commitments $(c'_1, \dots, c'_n)$ without revealing the permutation ...
- 1,066
3
votes
0
answers
120
views
Groth-Sahai Proof of multi-exponentiation
I want to create a NIZK proof of a multi-exponentiation via Groth-Sahai proofs. In the lectures of Jens Groth in a winter school of Bar-Ilan University, he shows a way to transform multi-...
- 125
3
votes
0
answers
102
views
Is it possible to verify attributes of encrypted content?
Let's say that Alice has this information about her,
{ "name": "Alice", "age": 25, "eyes": "brown" }
which she encrypts with a key pair so that no one access ...
- 31
3
votes
0
answers
120
views
Adaptation of Stern Zero-Knowledge protocol from coding to lattices
I'm currently working on Zero-Knowledge-proofs in lattice context, for which there exist two major frameworks. One of those two is the adaptation of Stern protocol from code-based-crypto.
There is in ...
- 31
3
votes
0
answers
89
views
What is the relation between honest verifier zero-knowledge and non-interactive zero-knowledge?
I'm not clear about the relation between the following definitions:
zero-knowledge protocols;
honest verifier zero-knowledge;
non-interactive zero-knowledge.
To my best understanding, zero-knowledge ...
- 31
3
votes
0
answers
94
views
Doubt in computing $g^\frac{1}{\delta+x}$ where $x \in \mathbb{Z}$
I was going through Zero Knowledge Set Membership and came across the following:
Given $x \in \mathbb{Z}$ and $g$ is the generator of a multiplicative group $\mathbb{G}$ how do we compute $g^\frac{1}{...
- 83
3
votes
0
answers
55
views
Avoiding multiple use of signed identities while not learning anything about them
There is an authority A with an associated public/private key pair (A.priv, A.pub).
A can issue new "identities" by signing data (numbers or bytestrings).
Each number associated with a signature by A ...
- 131
3
votes
0
answers
120
views
Proof of knowledge of exponentiations
I am reading a paper of Furukawa and Sako, "An efficient scheme for proving a shuffle" from 2001. This paper writes a protocol for verifiable shuffling in mixnets. Their protocol make use of ...
3
votes
0
answers
229
views
Weak Challenge Generation - Fiat-Shamir Heuristic
The Fiat-Shamir heuristic may be applied to transform a Sigma-Protocol on R(x,w) into a ZKPoK.
Let's call the prover's first message ...
3
votes
0
answers
282
views
Shared-secret authentication with implicit session keys?
Consider a system with producers (P), consumers (C) and a server (S) with two TCP ports open where a consumer connects on one port and a producer on the other. The server is just a TCP relay which ...
- 453
3
votes
0
answers
292
views
Question about proof of knowledge definition
I am just reading the "soundness" definition for proofs of knowledge by Bellare / Goldreich. A proof of knowledge is a proof between a prover $P$ and a verifier $V$. $P$ convinces $V$ of his knowledge ...
- 579
3
votes
0
answers
340
views
Transforming simplest protocol into a Sigma-protocol
I have some questions from previous years exams, I hope you could help me with them. :)
Suppose that a protocol satisfies the properties of a $\Sigma$-protocol, except that it is only (plain) ...
3
votes
0
answers
143
views
Is this a valid real-time authentication scheme?
The scenario in Alice/Bob/Cindy terms:
Alice approaches someone she doesn't know, but thinks is Bob, and asks for some secret information. Bob doesn't know and doesn't trust Alice, but Alice says she ...
- 530
3
votes
2
answers
219
views
Why does the prover in an interactive proof run in exponential time with the space of the computation?
I'm currently trying to gain an understanding of verifiable computation and the strengths and weaknesses of past approaches.
In particular, I've been watching the following YouTube video which talks ...
- 131
2
votes
0
answers
21
views
knowledge soundness in IVC paper
In "On Defining Proofs of Knowledge" by Mihir Bellare and Oded Goldreich, the definition of knowledge soundness (KS) is (See Definition 3.1):
Validity (with error $\kappa$): Let $p(x)>\...
- 121
2
votes
0
answers
42
views
How can we combine circuits for complex ZKBoo proofs?
I'm a bit lost. I know that ZKBoo can be used for proving $y = C(x)$ for any boolean or arithmetic circuit $C$. However, I'm unsure how to combine several circuits when we want to do more complex ...
- 548
2
votes
0
answers
125
views
Equality of ElGamal plaintext & Pedersen commitment message
Let's imagine two entities: Bob and Alice. Bob's public key is $B = bG$. Alice's public key is $A = aG$.
Alice encrypts her number $n$ with Bob's public key so Bob could decrypt it ($n$ is small ...
- 33
2
votes
0
answers
67
views
Fischlin vs. Fiat-Shamir Performance
Using Fiat-Shamir, an interactive 3-round sigma protocol can be compiled into a non-interactive zero-knowledge proof in the random oracle model.
A NIZK through Fiat-Shamir is not UC-Secure due to ...
- 143
2
votes
1
answer
97
views
Prove with ZKP that I have encrypted a message $v + random\_number\cdot c$ given an RSA public key?
I want to create an application in which users can cast vote to blockchain in encrypted form using RSA. The private key will be revealed only after completion of the election.
My major use case is as ...
- 71
2
votes
0
answers
91
views
PLONK: Rationale Behind Specific Polynomial Evaluations in Round 4
In round 4, protocol evaluates a(zeta), b(zeta), c(zeta), Sσ1(zeta), Sσ2(zeta). I know linearisation trick in round 5 implies the identity of other terms. Can we ...
- 122
2
votes
1
answer
95
views
Parameters needed for Chaum-Pedersen Protocol
I've came across a Stackexchange question about the Chaum-Pedersen Protocol which is based on the generalised schnorr protocol. As I understand it, it uses discrete logs and cyclic groups of prime ...
- 21
2
votes
0
answers
63
views
Poly-commitment based on Bulletproofs
I am reviewing the ZKP course, represented by the university of Berkley (https://zk-learning.org/). In pages 41 and 42 of lecture 6 that is attached below (https://zk-learning.org/assets/lecture6.pdf),...
- 181
2
votes
0
answers
36
views
ZKP of knowledge of EC keys preimage
There is a random scalar seed $s$ which we may call a master secret.
There are 2 public strings or scalars: $m1, m2$ and 2 corresponding EC keypairs: $a, A=a*G$ and $b, B=b*G$
$a$ and $b$ are somehow ...
- 149
2
votes
0
answers
65
views
To prove equality/inequality of plaintexts of 2 ciphertexts encypted under different encryption schemes
We have 2 ciphertexts, one encrypted using Paillier and another encrypted under Elgamal encryption schemes. Is there a way to design ZK-proof to prove equality of the underlying plaintexts of these 2 ...
- 21
2
votes
0
answers
22
views
How to choose the value of state width of Plonk with lookup?
I noticed that it seems the original Plonk paper introduced that there were two extensions with state width = 3 or 4 (as described in https://github.com/matter-labs/proof_system_info_v1.0/blob/master/...
- 932
2
votes
0
answers
19
views
Set value of SMT leaf proof
I would like to make a zk proof that would set the leaf of an SMT tree at an index that is an eth address to 1. The SMT is built offchain.
I already have the SMT and the root of the tree onchain.
I ...
- 21
2
votes
0
answers
73
views
Efficient Zero Knowledge Proof for proving a reencryption shuffling for an arbitrary table
I have a problem where I have a table of various reencryptable/rerandomizable ciphertexts (Paillier, Elgamal, EC Additive Elgamal). Each row on a given table has the same structure, but each column ...
- 313