Questions tagged [zero-knowledge]

A zero-knowledge proof is a cryptographic demonstration of the truth of a statement such as "I know a number $x$ such that $g^x\mod p =y$", that can be verified by a sceptical party but provides no information beyond the truth of the statement.

Filter by
Sorted by
Tagged with
1 vote
0 answers
24 views

Zero knowledge proof of a linear expression in the exponent

Alice sends to Bob a value $B$ in $\mathbb{G}$ a group of high order. There are distinct elements $h_1$, $h_2$ and $h_3$ of high order of $\mathbb{G}$, and Alice wants to prove to Bob that she knows ...
Adam54's user avatar
  • 261
1 vote
0 answers
29 views

On public coin zero knowledge protocols

Goldwasser and Sipser proved that a private coin interactive proof system can be converted into a public coin system. This conversion preserves round complexity (up to an additive factor of 2), but ...
884d88baaa's user avatar
1 vote
1 answer
58 views

Zero knowledge commitment to a "strictly positive integer" and "nonzero element"

Suppose I want to commit to the following information: I have an integer $i\in\mathbb Z$ and I want to commit to $i$ and that $i\gneq 0$, without revealing $i$. I have an element of a prime field $x\...
Jim's user avatar
  • 111
0 votes
0 answers
34 views

Showing the zero-knowledge property in a NI-ZK scheme

To my understanding, whilst the definition of zero-knowledge (zk) is the same in the non-interactive context, how one shows a non-interactive scheme is zk is very different from interactive zk ...
Proliferate309's user avatar
0 votes
1 answer
40 views

Can Cryptographic Proofs Directly Attest to Function Call Results?

In systems where computations are performed in remote or potentially untrusted environments(e.g. Ethereum NaaS providers such as Infura), how can we gain confidence in the accuracy of the results? ...
MShakeG's user avatar
  • 101
3 votes
1 answer
90 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
1 vote
1 answer
238 views

Zero knowledge proof applied to a chess position

I know next to nothing about cryptography. From what I have understood, anything that is provable can be done so using a zero knowledge proof (the result seems to be known from the 1980's or so, by S. ...
untreated_paramediensis_karnik's user avatar
4 votes
1 answer
105 views

In Zero Knowledge Proofs (ZKP) why does the simulator and extractor get the power to rewind "time" and not some other superpower?

Why was the simulator/extractor specifically given the power to rewind "time" instead of a different super power? Was it defined in the first ZKP paper that the simulator and extractor would ...
Reggad's user avatar
  • 141
0 votes
0 answers
31 views

Interactive Zero-Knowledge Proof for the Multiplication Gate

Refer to an interesting article (link) on Medium on the subject matter. To understand more about pRandomValue and vRandomValue. The article mentioned, "pRandomValue, on the other hand, is used to ...
user60588's user avatar
  • 191
1 vote
1 answer
83 views

How to write zk-snark arithmetic circuits

Paper: "Dispute-free Scalable Open Vote Network using zk-SNARKs" by Muhammad ElSheikh Available at: https://arxiv.org/pdf/2203.03363.pdf In this paper, the author has mentioned some pre-...
user60588's user avatar
  • 191
2 votes
0 answers
25 views

Zero Knowlege/Trust Architecture with shared encryption keys (maybe Shamir's secret sharing?)

I'm working on an idea for a backend data store that stores encrypted data that is zero knowledge/trust, however is shareable to a number of parties. I don't want the backend service to know anything ...
supertodda's user avatar
0 votes
2 answers
113 views

which zero knowledge proof technique is suitable for identity verification system?

I am a beginner in the cryptographic field but as a graduation project, I have to build an identity verification and management system using zero-knowledge proofs. I see a lot of zkp techniques, ...
Cocodile's user avatar
0 votes
0 answers
71 views

Zero Knowledge 3-coloring, but we allow malicious V to challenge two edges

So I think I understand how zero knowledge protocol with 3-coloring is supposed to work. But in an attempt to increase soundness of the protocol, we allow the verifier V to challenge two edges per ...
HughJass24's user avatar
3 votes
0 answers
62 views

Are there reputable public proving parameters for universal zkSNARK systems?

I have seen that Filecoin performed a public set-up ceremony for their zkSNARK system. Because Filecoin uses the Groth16 prover (which has a circuit-specific set-up), the output of this ceremony was ...
884d88baaa's user avatar
1 vote
1 answer
94 views

Encryption scheme with variable and provable key-length

I'm currently studying the possibility of a novel ransomware technique, where an adversary instead of forcing the victim to pay a ransom, forces them to brute force a key of given length and thus ...
limeeattack's user avatar
3 votes
3 answers
284 views

State of the art for Graph Isomorphism

I want to know the state of the art result for proving knowledge of graph isomorphism. As described here, the classical Goldreich-Micali-Wigderson (GMW) protocol is a $\Sigma$-protocol with soundness ...
Gareth Ma's user avatar
  • 350
2 votes
0 answers
147 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
1 vote
1 answer
143 views

Many-out-of-many proofs

I need to prove that given vector of commitments of length N contains N-1 commitments to zero (and one to an arbitrary number). More formally, given vector: $$\textbf{a} = \begin{bmatrix} C(0, r_1)...
Seed Barret's user avatar
1 vote
0 answers
272 views

ZK-STARK soundness

I've been reading about ZK-STARK. There's an example that appears in several blogs. The most detailed explanation of that specific example which I have found so far is in this blog. The description of ...
artificial_inspector's user avatar
0 votes
1 answer
160 views

PCD vs Recursive SNARK vs Non-uniform IVC

I was wondering if anyone could clarify the differences between PCD vs Recursive SNARKs(like pickles) vs Non-uniform IVC(like hypernova) They all seem very similar to me
questionman123's user avatar
1 vote
1 answer
120 views

Which Rust library is recommended if I would like to implement PLONK? [closed]

I think it should have APIs for polynomials, FFT and bilinear mapping if KZG commitment scheme is used.
Walker's user avatar
  • 61
2 votes
0 answers
82 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
1 vote
0 answers
104 views

Is the Lemma4.5 in the Plonk paper correctly described?

In lemma4.5, of PlonK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge they claim that we can construct a polynomial protocol $P^*$ with an $S$-ranged polynomial ...
mactep Cheng's user avatar
0 votes
0 answers
24 views

How can we construct a ZKPoK which hides both $x$ and the witness $W_x$ in dynamic accumulators?

Consider a verification equation $ e(\Delta,\tilde{G}) = e(W_x,x\tilde{G}+pk_{acc})$ from a pairing based accumulator which uses the value $x$ and the corresponding witness $W_x$ to verify that a ...
Kanchan Bisht's user avatar
2 votes
1 answer
135 views

Can a 3-coloring for a graph be represented as a circuit?

I was looking at a layman explanation for zero-knowledge proofs in zk-SNARKs here. The idea there is that if one knows a solution (3) to a question (find a value of ...
user1936752's user avatar
0 votes
0 answers
30 views

Data structures for linking blockchain accounts

I want to use a data structure like merkle tree in a hypothetical blockchain that, if needed, can fast check whether a wallet/account has received directly or indirectly from a specific list of ...
Houtee's user avatar
  • 1
2 votes
0 answers
37 views

Proving the minimal entropy of Dilithium-QROM?

I am working with the securit yof CRYSTAL's Dilithium signature in the QROM. I am working with Kiltz et al.'s approach through lossy ID-schemes and looking at the proof of minimal entropy for the $DFS[...
Rory's user avatar
  • 335
2 votes
1 answer
52 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
4 votes
1 answer
454 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,201
3 votes
1 answer
97 views

Does NordPass Make the Same Error SpiderOak Stopped Making in 2017?

According to a Reddit post I am participating in, SpiderOak “repented” of its incorrect usage of the term “zero knowledge” in 2017, as shown here: https://medium.com/@SpiderOak/why-we-will-no-longer-...
brethvoice's user avatar
1 vote
0 answers
29 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
4 votes
1 answer
92 views

sUF-CMA security of Lyubashevsky's ID and signature protocol

I have been working on the post-quantum safe ID/signature-schemes of Vadim Lyubashevsky (https://www.iacr.org/archive/asiacrypt2009/59120596/59120596.pdf). I am in particular studying the security ...
Rory's user avatar
  • 335
5 votes
2 answers
124 views

Coin flipping without commitments or random oracles

It's well known that two parties, Alice and Bob, can flip a fair coin using commitments. Alice picks a random number $a \in \mathbb{Z}_q$ and computes $c_a = Com(a, r_a)$ where $r_a \xleftarrow{R} \...
Ari's user avatar
  • 163
3 votes
1 answer
122 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,201
2 votes
1 answer
168 views

Zero knowledge proof for GCD

Let A(x) and B(x) be two secret polynomials. Suppose a user publishes commitments $C_A$ and $C_B$ to these polynomials (such that the lengths of $C_A$ and $C_B$ are sublinear in the degree of $A(x)$ ...
Doron's user avatar
  • 99
1 vote
0 answers
41 views

Zero-knowledge data storage with peace of mind. MAC/Encryption with two keys?

Background Bob's goal: Receive data E = E(D) (encryption of D) from Alice that he knows for sure is encrypted and that he can't possibly decrypt (without brute force). This gives his data backup ...
cryptonamus's user avatar
0 votes
0 answers
96 views

Definition of "zero-knowledge encryption"

I'm reading headlines on the tune of "…bring zero-knowledge encryption to file storage". Googling "zero-knowledge encryption" returns statements like "cloud storage or backup ...
fgrieu's user avatar
  • 141k
1 vote
0 answers
28 views

Design ZKP to satisfy x1*x2(mod n)=x3 from(Pallier encryptions)

I have 3 Pailler encryption p1=E(x1;r1),p2=E(x2;r2);p3=E(x3;r3) such that x1*x2(mod n)=x3. P(Prover) knows (x1,r1);(x2,r2);(x3,r3). Can I design a ZKP(interactive & non-interactive) for P to ...
akib g's user avatar
  • 11
3 votes
2 answers
513 views

How does taking the difference between commitments verifies that the messages are correct?

I have read that perdersen commitment can be used to hide the messages such as transactions by participants. The verifier will just have to make sure that the difference of the commitments is zero. ...
xenon's user avatar
  • 225
3 votes
1 answer
196 views

How can you use ZK-proofs and public key signatures in this situation?

Let us say that we have 3 entities: an Issuer I , a user/prover P and a verifier V. ...
jacobi_matrix's user avatar
1 vote
1 answer
73 views

Input Delayed Sigma-Protocol

In a Sigma-protocol, the steps are (1) commitment, (2) challenge, and (3) response. In general, the prover has a statement and witness that they can use to compute the commitment step. But in some ...
eternalmothra's user avatar