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
0 votes
0 answers
37 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
1 vote
0 answers
36 views

Mask-Shuffle in Mental Poker Revisited from Barnett and Smart

I am going through the paper "Mental Poker Revisited" by Barnett and Smart. I understood Section 5 in which the author explains Chaum-Pedersen (CP) protocol and how it is used in methods ...
user60588's user avatar
  • 297
0 votes
0 answers
25 views

In groth16, how restricting public Inputs to the prime field instead of the snark scalar field can be used?

Recently such an overflow was fixed in snarkjs but given the small difference between the 2 and that it was restricted to the prime field anyway, how could this be exploited ?
user2284570's user avatar
2 votes
0 answers
47 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
0 votes
1 answer
43 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
0 votes
0 answers
63 views

Is the PLONK paper incorrect? [duplicate]

I'm having some confuses while implementing the PLONK by following the instruction in the Plonk paper. Could someone please help me with it? In step 6th of the "Verifier preprocessed input" ...
Steve Nguyen's user avatar
1 vote
0 answers
45 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
  • 297
2 votes
1 answer
58 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
  • 297
1 vote
1 answer
52 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
  • 297
1 vote
0 answers
61 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
  • 297
4 votes
1 answer
213 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
  • 297
0 votes
0 answers
45 views

Peer-to-Peer message verification

I have a chat application that uses AES and RSA encryption to establish a peer-to-peer connection between two clients. Although the messages pass through a server, they are encrypted using a single ...
Higgs's user avatar
  • 1
0 votes
1 answer
31 views

GKR & Sum-check Protocol - how are the random numbers split across different variables?

I am reading about GKR protocol from Justin Thaler's book - Proofs, Arguments & Zero Knowledge Section 4.6.5 - Page 64 - Description of GKR Protocol $S_0$ is the number of gates in layer 0. $k_0 = ...
user93353's user avatar
  • 2,245
0 votes
0 answers
27 views

Implement true serverless (decentralized) online multiplayer game with cryptography

TLDR, this will be a discussion rather than my private problem. Nowadays, most game developers or publishers have central servers to manage player transactions such as movement, mouse position, and so ...
Muhammad Ikhwan Perwira's user avatar
0 votes
1 answer
63 views

ZK is not preserved under parallel composition! - Witness Indistinguishability

Referring to an old but very nice paper on Witness Indistinguishability and Witness Hiding (link). On page 4, in theorem 3.2, the author explained it in three points, but I have few queries. In point ...
user60588's user avatar
  • 297
1 vote
1 answer
114 views

GKR Protocol - does it matter which gate in each layer the SumCheck Protocol is run on?

I am reading about GKR protocol from Justin Thaler's book - Proofs, Arguments & Zero Knowledge Page 61, Lemma 4.7 $W_i(z) = \sum_{b,c \in \lbrace 0,1 \rbrace^{k_{i+1}}} add_i (z,b,c)\cdot (W_{i+1}(...
user93353's user avatar
  • 2,245
1 vote
1 answer
79 views

Why is zero knowledge defined via simulation w.r.t. inputs *in* the language?

In every definition of zero-knowledge (ZK) proof systems that I have seen (see, e.g., this one on Wikipedia, or this primer by Goldreich), a proof system $\langle p, v \rangle$ for a language $L$ is ...
Lewis Hammond's user avatar
3 votes
1 answer
122 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
0 votes
0 answers
20 views

Trustless anonymization problem

Imagine a message exchange system where every actor publicly exposes his identity. In such a system, Alice wants to exchange messages with an entity run by Bob, but neither Alice nor Bob wants to ...
s0me0ne's user avatar
  • 101
1 vote
1 answer
49 views

Zero Knowledge formalism for proof of knowlege of an exponent

I'm looking to understand the appropriate formalism to represent a protocol step where Alice sends Bob a proof of knowledge of an exponent. Is it accurate to depict this step using an arrow annotated ...
Adam54's user avatar
  • 283
0 votes
0 answers
41 views

What is the Halo2 zkp scheme's time complexity?

The Halo2 is the zero-knowledge proof scheme which is the improvement of HALO. However, it is not clear for me what is the time complexity of this scheme,including generating and verifying the proof. ...
John's user avatar
  • 1
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
39 views

Constraints needed to express a + b + c = d in zkp circuit

I am writing an ECC based zkp circuit and need to express the constraints: a + b + c = d a, b, c, d >= 0 a, b, c, d will be represented by points on the curve so addition can wrap around the ...
gws's user avatar
  • 101
1 vote
0 answers
75 views

Efficiency of interactive versus non-interactive zero-knowledge proofs?

Some projects (e.g., https://zkpass.org/) are claiming that interactive ZKPs can be more efficient than non-interactive ZKPs. What is the rationale behind this?
mti's user avatar
  • 655
0 votes
0 answers
41 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
54 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
0 votes
0 answers
28 views

Obfuscation scheme wanted

I'd like to know if there's any cryptographic scheme that implements something similar to what I'm summarizing here below. Thanks a lot for reading and for any hint or question. Intro-Scenery: There's ...
Lorenzo's user avatar
  • 101
2 votes
0 answers
84 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
0 votes
1 answer
121 views

Zero-Knowledge Proof of Graph-Isomorphism with a union relation

In question (1.b) in Homework 10 for Brown University's Cryptography course, they present the problem of providing a zero-knowledge proof for $L = \{ ((G_0, G_1), (G'_0, G'_1)) \mid G_0 \cong G_1 \vee ...
Stevie's user avatar
  • 123
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
1 vote
1 answer
264 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
122 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
2 votes
1 answer
192 views

GKR Protocol - is it one Sum-Check per layer or is it one Sum-Check per gate?

I am reading about GKR protocol from Justin Thaler's book - Proofs, Arguments & Zero Knowledge On Page 59, In the first message, $P$ tells $V$ the (claimed) output(s) of the circuit. The protocol ...
user93353's user avatar
  • 2,245
0 votes
0 answers
33 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
  • 297
1 vote
0 answers
45 views

In zero-knowledge proof, can the selection of challenge r be non-uniform?

I recently started learning zero-knowledge proofs. I found that in many zero-knowledge arguments, the verifier is required to randomly select a challenge $r\in\mathbb{Z}_q$ and send it to the prover. ...
Wing Sky's user avatar
1 vote
1 answer
82 views

How does the verification step operations using FRI polynomial commitments in zk-STARKs?

I have been going through the lectures in ZKP MOOC here youtube series. I am trying to understand the zk-STARKs discussed in video ZKP MOOC Lecture 8: FRI-based Polynomial Commitments and Fiat-Shamir. ...
INDUKURI MANI VARMA 21911012's user avatar
1 vote
1 answer
151 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
  • 297
1 vote
0 answers
37 views

Is it possible to verify and prove the decryption of an FHE cyphertext without the verifier knowing the key with zkProof?

Suppose Bob encrypts a plaintext($p$) with an FHE scheme and a key($k$), then sends the $c$ to Alice. Alice wants to know the plaintext but can't trust that Bob won't send a different string. Can Bob ...
Vasily Sobolev's user avatar
2 votes
2 answers
84 views

Impact of security of schnorr's identification verifier when reducing the challenge space

I have been going through some old lecture notes of mine and found this interesting question. Assuming we reduce the challenge space for the verifier from $\mathbb ℤ_q$ to $\mathbb ℤ_{\log(𝑞)}$, does ...
user16100351's user avatar
0 votes
0 answers
24 views

Zero Knowledge Protocol for 3Coloring: Formal Proof

I am learning zero knowledge protocols, and studied the GMW protocol for 3-Coloring (https://www.wisdom.weizmann.ac.il/~oded/X/gmw1j.pdf). A similar proof is also presented in Oded Goldreich's ...
user31245's user avatar
1 vote
1 answer
152 views

Clarification on Modular Equivalence in Generalized Sumcheck in RZ21

I'm studying generalized sumcheck in RZ21 P.10 and have come across a modular equivalence that I'm trying to understand. The specific step that's unclear to me is the following equivalence: $$ \left(\...
Paul Yu's user avatar
  • 156
2 votes
1 answer
42 views

How is $\lambda_j(0) = N^{-1}$ for Lagrange polynomials in the Baloo paper's generalized sumcheck?

I'm reading inner product from generalized sumcheck in baloo paper (P.13), I'm confused with $\lambda_j(0) = N^{-1}$. Can anyone shed some light? Here's excerpt from the paper The intuition is that ...
Paul Yu's user avatar
  • 156
0 votes
0 answers
29 views

How do I instantiate ZK-STARKs using Polynomial Commitments?

In my exploration of zero-knowledge proofs, I have encountered various perspectives on the operational disparities among zk-SNARKs, zk-STARKs, and Bulletproofs, as documented in different blogs and ...
INDUKURI MANI VARMA 21911012's user avatar
1 vote
0 answers
46 views

Server parameters for Differential Zero Knowledge?

I'm working to use Differential Zero Knowledge proof on client local data before sharing with server. May I know which parameters need to be established at server side as to verify that the client is ...
Genie's user avatar
  • 83
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
1 vote
1 answer
59 views

Why the full $r$-torsion group contains $r^2$ many elements and consists of $r+1$ subgroups

let $F$ be a finite field, $E(F)$ an elliptic curve of order $n$, $r$ a factor of $n$, $k(r)$ for the embedding degree of $E(F)$ with respect to $r$. Then why the full $r$-torsion group contains $r^2$...
l4rmbr's user avatar
  • 111
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
0 votes
2 answers
134 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
77 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
0 votes
0 answers
39 views

How can I determine if the result of subtracting two Pedersen commitments is negative or positive?

I'm using Pedersen commitments to maintain the account balance in the ledger. Assume that when I create the account, I record the Pedersen commitment of 0 in a ledger (here, the blinding factor and ...
Prady Tej's user avatar

1
2 3 4 5
22