Skip to main content

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.

286 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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:...
Habib's user avatar
  • 951
8 votes
1 answer
737 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)$ ...
Guillem's user avatar
  • 81
7 votes
0 answers
323 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 ...
George Herbert's user avatar
6 votes
0 answers
99 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 ...
Mark Schultz-Wu's user avatar
  • 13.5k
6 votes
0 answers
140 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 ...
Bean Guy's user avatar
  • 752
5 votes
0 answers
609 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 ...
user2284570's user avatar
5 votes
0 answers
264 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 ...
user2234174's user avatar
5 votes
0 answers
435 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 ...
haael's user avatar
  • 285
5 votes
0 answers
1k 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 ...
Mike Carpenter's user avatar
4 votes
0 answers
141 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 ...
Andrei Florian's user avatar
4 votes
0 answers
124 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 ...
Daniel's user avatar
  • 3,972
4 votes
0 answers
1k 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 $\...
jvdh's user avatar
  • 173
4 votes
1 answer
499 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. ...
Mamun's user avatar
  • 41
4 votes
0 answers
92 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 ...
reatter's user avatar
  • 41
4 votes
0 answers
241 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 ...
user10294026's user avatar
4 votes
0 answers
152 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. ...
Ian MathWiz's user avatar
4 votes
0 answers
306 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 ...
cowlicks's user avatar
  • 151
4 votes
0 answers
246 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. ...
T.B's user avatar
  • 49
3 votes
1 answer
97 views

Rigorous Proof on Malicious Zero-Knowledge Property of Schnorr Protocol

Let us recall the Schnorr Protocol, following Chris Peikert's excellent Notes on the Theory of Cryptography. Protocol. Let $G=\langle g \rangle$ be a cyclic group of order $q$. We consider an ...
Chris's user avatar
  • 236
3 votes
0 answers
18 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-...
darkFunction's user avatar
3 votes
0 answers
26 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 ...
mti's user avatar
  • 655
3 votes
0 answers
65 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 ...
Dontmilkme's user avatar
3 votes
0 answers
391 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/#...
Ricardo Martínez's user avatar
3 votes
0 answers
159 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 ...
Nic's user avatar
  • 498
3 votes
0 answers
64 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 ...
Cryptonaut's user avatar
  • 1,076
3 votes
0 answers
127 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-...
kentakenta's user avatar
3 votes
0 answers
103 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 ...
Maxim Gaina's user avatar
3 votes
0 answers
130 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 ...
Olivier's user avatar
  • 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 ...
Tracy Hu's user avatar
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}{...
Abhijit's user avatar
  • 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 ...
2080's user avatar
  • 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 ...
Meghann Jones's user avatar
3 votes
0 answers
241 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 ...
Arya Pourtabatabaie's user avatar
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 ...
DurandA's user avatar
  • 453
3 votes
0 answers
295 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 ...
user4811's user avatar
  • 579
3 votes
0 answers
343 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) ...
Peter De Vries's user avatar
3 votes
0 answers
145 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 ...
KeithS's user avatar
  • 540
3 votes
2 answers
231 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 ...
kw3rti's user avatar
  • 131
2 votes
0 answers
46 views

Succinct proof of evaluation of known polynomial

Consider the zeroes polynomial $$ zeroes_n(X) = \prod_{0\leq i< n} (X-i) . $$ Fix a large prime $p$, and fix some $n$ that is less than $p$ but which may still be very large (e.g. $p\approx 2^{256}...
Jim's user avatar
  • 131
2 votes
0 answers
82 views

How does Fast Reed-Solomon Interactive Oracle Proof (FRI) protocol work using polynomial commitments in zk-STARKs?

Over a few days, I have been trying to understand the FRI protocol discussed in the link https://aszepieniec.github.io/stark-anatomy/fri . It explains Fast Reed-Solomon Interactive Oracle Proof (FRI) ...
INDUKURI MANI VARMA 21911012's user avatar
2 votes
1 answer
132 views

Is it safe to "sign" a message with such a zk proof

I am building an application in which I need to sign a message without revealing my entire identity. To do so, I just compute a zk proof with the following purpose: prove I own the secret key sk ...
Makubu's user avatar
  • 21
2 votes
0 answers
54 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)>\...
ohmygoddess's user avatar
2 votes
0 answers
52 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 ...
pintor's user avatar
  • 558
2 votes
0 answers
153 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 ...
Seed Barret's user avatar
2 votes
1 answer
141 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 ...
P S's user avatar
  • 71
2 votes
0 answers
95 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 ...
Paul Yu's user avatar
  • 156
2 votes
1 answer
181 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 ...
Jason L. B.'s user avatar
2 votes
0 answers
88 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),...
tesoke's user avatar
  • 181
2 votes
0 answers
38 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 ...
John dow's user avatar
  • 149
2 votes
0 answers
80 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 ...
G Pavithra 's user avatar

1
2 3 4 5 6