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.

Filter by
Sorted by
Tagged with
2 votes
1 answer
55 views

Can we pad witness of bulletproof and dory to be exponential size?

Bulletproof and dory reduce the witness size by a half during each interaction, until the witness is compressed to be only one element. But what about the witness is not precisely exponential size? ...
Walker's user avatar
  • 61
1 vote
1 answer
61 views

ZKP vs disposable addresses [closed]

In other words, what does ZKP brings on top of the practice of not reusing addresses? From my research, ZCash is currently a state of the art example of ZKP application, but what extra benefits does ...
Jp_'s user avatar
  • 111
3 votes
1 answer
97 views

How do I construct a recursive polynomial as required in PLONK?

I am going through Dan Boneh's video on PLONK - https://www.youtube.com/watch?v=LbpPCN-f_XA&t=952s At around 19 minutes, he gets to the Prod Check Gadget. Background: $\omega \in F_p$ is the ...
user93353's user avatar
  • 2,200
1 vote
1 answer
61 views

Prod Check Gadget in PLONK - any polynomial which satisfies the prod check seems to be the trivial polynomial

In Dan Boneh's PLONK Video - https://www.youtube.com/watch?v=vxyoPM2m7Yg he refers to the Prod Check Gadget $\omega \in F_p$ is a primitive $k$-th root of unity ($\omega^{k-1} = 1$) $H = \{1, \omega, \...
user93353's user avatar
  • 2,200
2 votes
1 answer
105 views

What security problem would cause if I reuse a NIZK proof?

Some statements are expensive to prove. If I need to make a proof for such kind of statement repeatedly (generate new proof $\pi$ for each new verifier), I think it might be a waste of time (as well ...
Yiyi's user avatar
  • 45
1 vote
1 answer
104 views

PLONK Prod Check Proof - why does it have to be proven upto the last element of the set? It should be enough to prove it upto last but one element

I am going through Dan Boneh's video on PLONK - https://www.youtube.com/watch?v=LbpPCN-f_XA&t=952s At around 19 minutes, he gets to the Prod Check Gadget. Background: $\omega \in \mathbb F_p$ is ...
user93353's user avatar
  • 2,200
2 votes
1 answer
262 views

Chaum-Pedersen protocol adapted to elliptic curves

Is it possible to adapt the Chaum-Pedersen protocol for using elliptic curves by simply replacing the exponentiation with scalar products? For example, if g is a ...
gagiuntoli's user avatar
2 votes
1 answer
110 views

PLONK Product Check Proof. Why is the 2nd condition required?

I am going through Dan Boneh's video on PLONK - https://www.youtube.com/watch?v=LbpPCN-f_XA&t=952s At around 19 minutes, he gets to the Prod Check Gadget. Background: $\omega \in \mathbb F_p$ is ...
user93353's user avatar
  • 2,200
1 vote
0 answers
36 views

How to design a Zero-Knowledge Proof of a message in a certain range? [duplicate]

Given a message $m$, how can I prove that $m$ lies between 0 and 31 without revealing the message using a Sigma protocol? The message is encrypted as: $$c = a^{\beta} \cdot g^m ,$$ where: $a$ is the ...
Daniel Chan's user avatar
0 votes
1 answer
84 views

Looking for the proof of the prod check gadget referred to by Boneh in his PLONK video

I am going through Dan Boneh's video tutorial on PLONK Polynomial IOPs - https://www.youtube.com/watch?v=vxyoPM2m7Yg He describes 3 type of proof gadgets he will use He gives a proof of the Zero Test ...
user93353's user avatar
  • 2,200
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
1 answer
173 views

zerocoin ZKSoK Pedersen commitment process

I am studying the zerocoin paper‡. More precisely I am stuck at page 6, on the Spend function (in paragraph "B. Our construction"). I am not understanding how the ZKSoK is computed. Let's ...
riccardo's user avatar
2 votes
1 answer
478 views

What is the difference between those two KZG Polynomial Commitment Schemes?

In short what are the differences (pros & cons) between multiplying by powers of Tau (from this lecture https://youtu.be/tAdLHQVW) and raising to powers of Tau (from this lecture https://youtu.be/...
ShAr's user avatar
  • 160
1 vote
1 answer
106 views

Textbook RSA security for fully random message

I am asking this since I can't find definite answer. Is it secure if I use textbook RSA provided all my data is 2048 bits ( or any N <=2048 for 2048 bit key ) and it is random ( using Secure Random ...
Jakub Rogacz's user avatar
1 vote
1 answer
388 views

NIZK Proof of Knowledge of a Standard RSA Signature on a message (without signer participation)

I'm looking for a protocol in which a Prover transforms a RSA signature $\sigma$ on a message $m$ that verifies under a public key $vk$ into a NIZK proof of knowledge, $\pi$ of that signature. A ...
Ethan Heilman's user avatar
3 votes
1 answer
108 views

What is the modern terminology for a digital signature scheme with a shadow?

In Guillou and Quisquater's 1988 paper "A 'Paradoxical' Indentity-Based Signature Scheme Resulting from Zero-Knowledge", they say that an RSA identity has a shadow and go on to state that ...
Ethan Heilman's user avatar
1 vote
0 answers
39 views

How can knowledge of a secret be compared among untrusted entities?

Lets say entity A sends a secret "token" to anybody that they trust. The token itself is the proof and its sent equally to everybody and it has or needs to be derived from application ...
secret-token'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
4 votes
1 answer
529 views

How can a verifier benefit from being malicious or dishonest in a Zero Knowledge interactive proof?

Several texts talk about malicious/dishonest verifiers in a zero-knowledge interactive proof but none of them properly detail how a dishonest verifier can gain extra knowledge over an honest verifier ...
user93353's user avatar
  • 2,200
2 votes
2 answers
517 views

How to compare two field elements in Arithmetic Circuit?

Given two field elements as input of Arithmetic Circuit (consists of adding gates and multiplicating gates only), how could I output the bigger one? Or, how to place the gates in order to distinguish ...
Yiyi's user avatar
  • 45
1 vote
0 answers
65 views

Pseudo-isomorphic graphs

Some famous cryptographical protocols rely on the construction of graphs $G_i= (V_i, E_i)$ for $i=0,1$ that are not isomorphic. For the safety of this protocol, it is central that one can not easily ...
Dominic van der Zypen's user avatar
0 votes
1 answer
153 views

Is this Zero Knowledge interactive proof for Quadratic non-residuosity proper?

This is from Alan Rosen's video on Interactive proofs - https://youtu.be/6uGimDYZPMw?t=1754 Here the proof is that the Verifier gets a random bit $b$ . If $b = 0$, then Verifier gets a random $y \...
user93353's user avatar
  • 2,200
4 votes
1 answer
107 views

Make sure of Quadratic Arithmetic Program validity

In the process of learning zk-SNARKs, I'm faced with this problem: I understand why if the prover sends a polynomial $P$ that can be divided by $T$, the target polynomial, the prover knows a valid ...
upavloff's user avatar
1 vote
0 answers
49 views

In Zcash, how does a recipient look up which transactions belong to him/her?

For Monero, the scheme for stealth addresses is pretty straightforward. (For example: https://monero.stackexchange.com/questions/1500/what-is-a-stealth-address) However, I haven't found any details on ...
frt132's user avatar
  • 23
0 votes
0 answers
51 views

What is this parameter? in Lyubashevsky's ID-scheme

I am studying Lybashevsky's ID-scheme from the article Fiat-Shamir With Aborts: Applications to Lattice and Factoring-Based Signatures(https://www.iacr.org/archive/asiacrypt2009/59120596/59120596.pdf) ...
Rory's user avatar
  • 335
1 vote
0 answers
59 views

Public seed expansion for uniform reference strings

Many cryptographic protocols are parameterized by a uniformly random reference string (e.g. the commitment key for Pedersen commitments). Our goal is to publicly generate the random values of this ...
Joseph Johnston's user avatar
1 vote
0 answers
46 views

Checksum algorithm using system of multivariate polynomials

I'm working on a protocol that uses zero-knowledge proofs. I'm looking at systems of polynomial equations as cheap solutions for checksumming data. Note, I'm not looking for trapdoor functionality ...
vimwitch's user avatar
  • 139
2 votes
1 answer
197 views

Real-world instantiation of NIZK protocol from Fiat-Shamir

So I understand how one can use Fiat-Shamir to turn a HVZK sigma protocol into a non-interactive zk protocol in the random oracle model. My problem though is I don't understand why is this useful. If ...
Proliferate309's user avatar
3 votes
0 answers
78 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
-1 votes
1 answer
54 views

Zero knowledge proof to validate/invalidate a claim

Have a look at the Twitter conversation below in the screenshots. @theveveshow asks if @trader1sz has sent ETH to the girl in question? @trader1sz responds that the girl in question has indeed sent ...
Mogambo's user avatar
  • 11
2 votes
1 answer
140 views

If SNARKs generally work in finite fields, how are non integer values handled - say fixed point decimal numbers?

In Vitalik Buterin's write-up on SNARKs Quadratic Arithmetic Programs: from Zero to Hero, he writes Note that the above is a simplification; “in the real world”, the addition, multiplication, ...
user93353's user avatar
  • 2,200
1 vote
0 answers
31 views

Honest verifier zero knowledge property for this protocol

This is zero-knowledge proof that show x is not a quadratic residue. I am trying to verify Honest verifier zero knowledge property. My steps were these: Let S be a simulator that does not know how to ...
tonythestark's user avatar
1 vote
0 answers
58 views

What is a reasonable statistical distance bound in a SZK construction?

Many works, such as [YCX21] cite that $2^{-40}$ is a reasonable statistical distance for zero-knowledge proof based signatures, even when the security level is $\lambda = 128$.. I was wondering if ...
Lev's user avatar
  • 468
2 votes
1 answer
428 views

In the Kate/KZG Polynomial Commitment Scheme, in which Polynomial Ring should the polynomial to be committed be?

In the Kate Polynomial Commitment scheme, a commitment of a Polynomial $f(x)$ at $x=s$ is defined as $Com_f = f(s).G$ where $G$ is the generator of the Elliptic Curve of prime order which is used. So ...
user93353's user avatar
  • 2,200
2 votes
0 answers
23 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 ...
Anthony's user avatar
  • 21
6 votes
1 answer
740 views

Arithmetic Circuits to R1CS. Do we consider addition gates or not?

Here is Ariel Gabizon's Blog for the process of converting Arithmetic Circuits into R1CS - https://electriccoin.co/blog/snark-explain5/ Here, he writes We assume multiplication gates have exactly two ...
user93353's user avatar
  • 2,200
2 votes
1 answer
69 views

Is a non-correlating signed identity proof possible?

Is it possible to receive from a party $I$ a signed message $M$ that can be presented to two independent other parties $V_1$ and $V_2$ as $M'_1$ and $M'_2$ in such a way that they cannot establish a ...
no1dea's user avatar
  • 31
1 vote
0 answers
59 views

Is it possible to make a (zero-knowledge) proof about the content of an asymmetric encrypted message?

I’m trying to understand the proposal presented in this papger zkKYC - A solution concept for KYC without knowing your customer, leveraging self-sovereign identity and zero-knowledge proofs. The ...
no1dea's user avatar
  • 31
1 vote
1 answer
228 views

What is a practical application of evaluating at a point in the Kate Polynomial Commitment Scheme?

I understand how the Kate Polynomial Commitment Scheme Evaluation Proof works however, I don't understand what is the purpose of it? In general, in a commitment scheme, Peggy commits to message & ...
user93353's user avatar
  • 2,200
2 votes
0 answers
89 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 ...
Zarquan's user avatar
  • 313
3 votes
1 answer
113 views

Question about the soundness of using a pairing map in the Kate Polynomial Commitment Scheme

I am looking at the paper on Kate Polynomial Commitments. On Page 7, VerifyEval, the verifier checks the following to verify commitment. $e(\mathcal C, g) \stackrel {?}{=} e(w_i, \frac {g(\alpha)}{g(i)...
user93353's user avatar
  • 2,200
2 votes
0 answers
180 views

Zk-snark range proof

The task is something like this. Alice must send Bob the money, but so that the amount remains hidden. How can this be done if only "hiding" balances are stored in the blockchain? How can I ...
pes oves's user avatar
3 votes
1 answer
130 views

Why is Lagrange interpolation required in Batch Opening case of KZG/Kate PCS?

From here - Batch Opening of KZG PCS One can prove multiple evaluations $(\phi(e_i) = y_i)_{i\in I}$,for arbitrary points $e_i$ using a constant-sized KZG batch proof, $\pi_I = g^{q_I(\tau)}$, where \...
user93353's user avatar
  • 2,200
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
1 vote
0 answers
93 views

Zero Knowledge Proof of Brainf*ck program execution

I have been trying to follow this paper for zk-SNARKs to create Zero Knowledge Proofs (ZKPs) for verifying computations. Specifically, given a public program $F$, a public input $x$, I would like to ...
Graviton's user avatar
  • 111
1 vote
1 answer
115 views

zk-SNARK: Encrypted Polynomial

I've read through, and roughly understand, Maksym Petkus' zk-SNARK paper (http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf). I'm re-reading it, and trying to code up the examples as I go along ...
Brendan's user avatar
  • 13
2 votes
0 answers
150 views

What good elliptic curve uses a scalar field the size of the Ristretto255 group?

I am implementing Bulletproofs over Ristretto255. (I am using libsodium, so can't switch to another Elliptic Curve implementation.) I need to implement zero knowledge verification of elliptic curve ...
Michael's user avatar
  • 31
0 votes
1 answer
258 views

How to proof Two CipherTexts holding same value with Zero Knowledge Proof?

I am a beginner in cryptography. I wonder is it possible to create by Zero Knowledge Proof, to prove Two cipherTexts that are encrypted by same Public Key with Paillier Encryption have the same value ...
Bertug's user avatar
  • 3
8 votes
0 answers
330 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
0 votes
1 answer
59 views

Honest programming language for malicious adversaries in MPC protocols

One method to create a secure MPC protocol against malicious adversaries is to create a secure protocol against semi-honest adversaries and then add some zero-knowledge proofs to ensure that the ...
user avatar

1 2 3
4
5
22