Skip to main content

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
0 votes
0 answers
24 views

The zero-knowledge properties of lattice-based zero-knowledge proofs

I've been reading papers on lattice-based zero-knowledge proofs recently, and I have some questions about the proof of zero-knowledge properties of schemes. Why is Stern type proven to achieve ...
Solaris's user avatar
  • 15
0 votes
0 answers
28 views

How to implement zero-knowledge encryption with SSO?

I am developing an application, that supports single-sign-on (SSO) with external identity providers such as Google, Apple, GitHub, and others. Now I want to store user data end-to-end encrypted, so ...
Corbie's user avatar
  • 101
2 votes
1 answer
81 views

Languages $L$ that have perfect zero-knowledge that do not have any $AM$ proof system that is perfect or zero-knowledge on $L$

In the GMR[85] paper, a conjecture is made in section 3.7: There exist languages $L$ that have perfect or statistical zero-knowledge proof systems, but do not have any Arthur-Merlin proof system that ...
itstwelvehere's user avatar
0 votes
0 answers
34 views

Zero Knowledge Proof of a Time Machine

I'm a software engineer trying to wrap my brain around Zero Knowledge Proofs just out of curiosity. I came up with the following puzzle to test my understanding... but was unable to solve it. Your ...
vaebnkehn's user avatar
0 votes
0 answers
38 views

Can ring signatures be considered as non interactive set membership proofs?

Can ring signatures be considered as non interactive set membership proofs? For example, if the message msg is set to null, can the ring signature scheme proposed by Rivest et al. be regarded as a non ...
user109993's user avatar
0 votes
1 answer
47 views

Zero knowlede proof of linear relations

Suppose a prover publishes two perfectly hiding commitments for $s_1,s_2$, i.e. two Pedersen commitments $C_1=g^{s_1}h^{r_1}$ and $C_2=g^{s_2}h^{r_2}$ such that $s_1,s_2,r_1,r_2$ are secret field ...
Itamar Lishansky's user avatar
1 vote
0 answers
46 views

Simulating physical envelops: Will commitments work in this case?

I want to simulate following physical activity in cryptography. Person X has written integers 1, 2, ..., 10 in seperate paper slips. He needs to distribute these slips to 10 people without knowing ...
user60588's user avatar
  • 307
2 votes
1 answer
61 views

Equality check with Pedersen commitments

Does the Pedersen commitment scheme allow for checking whether two commitments are made - say by different people - for the same value?
user60588's user avatar
  • 307
1 vote
1 answer
57 views

Winner and individual vote counts in online voting in DRE-i and DRE-ip

I have seen few well-known related papers on online voting : DRE-i, DRE-ip and this one. They have explained most of the process such as vote casting and vote tallying. But I did not find when and ...
user60588's user avatar
  • 307
1 vote
0 answers
62 views

A problem involving Commitments

Suppose there is a set $P=\{p_1, p_2, ..,p_l\}$ of stock buyers who can make commitments to a share $s_i$ in a set $S=\{s_1,s_2,...,s_m\}$ of shares for an amount $a_i$ in a set $A=\{a_1,a_2,...,a_n\}$...
user60588's user avatar
  • 307
4 votes
1 answer
219 views

What prevents ZKP proofs to be misused by others?

In ZKP, if a prover P1 possesses a secret number S and generates a proof PRF for the possession of the same with the aim to prove it to a verifier V1. But, what prevents V1 from misusing the PRF and ...
user60588's user avatar
  • 307
3 votes
1 answer
123 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$ and $h_2$ of high order of $\mathbb{G}$, and Alice wants to prove to Bob that she knows some ...
Adam54's user avatar
  • 283
1 vote
0 answers
43 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
66 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
  • 131
0 votes
0 answers
43 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
55 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
104 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
270 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
130 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 ...
CLox's user avatar
  • 151
0 votes
0 answers
34 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
  • 307
1 vote
1 answer
190 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
  • 307
2 votes
0 answers
26 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
141 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
1 vote
0 answers
83 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
63 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
0 answers
104 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
311 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
  • 365
2 votes
0 answers
154 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
154 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
347 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
234 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
146 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
1 answer
108 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
106 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
2 votes
1 answer
145 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
2 votes
0 answers
41 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
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
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
3 votes
1 answer
98 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-...
tdMJN6B2JtUe's user avatar
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
4 votes
1 answer
107 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
129 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
  • 178
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
2 votes
1 answer
170 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
99 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
  • 143k
1 vote
0 answers
29 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
531 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
215 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
82 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