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
2 answers
111 views

Can a Sigma protocol be transformed into a signature of knowledge through Fiat-Shamir transform?

As is well known, a sigma protocol can be transformed into a NIZK protocol through a Fiat-Shamir transform. But can the Sigma protocol be transformed into a signature of knowledge in a similar manner? ...
0 votes
2 answers
240 views

Does Schnorr identification protocol using commitment scheme?

In schnorr identification protocol, a prover needs to choose a random,let's say $r$ at the beginning, then commit to this randomness as $g^r\bmod p$. When we say "commit", does it really mean we are ...
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 ...
1 vote
1 answer
48 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 ...
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 ...
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 ?
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, ...
1 vote
2 answers
574 views

Proof of knowledge and replay attacks

I was reading the ZK proof of knowledge of Schnorr and fiat shamir transformation, and I figured out that replay attacks are possible. Why these protocols don't take into account this attack? That ...
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 ...
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 ...
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}...
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 ...
0 votes
1 answer
42 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 ...
0 votes
0 answers
62 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" ...
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 ...
1 vote
1 answer
263 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. ...
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 ...
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?
1 vote
2 answers
150 views

Where can I find 2 of the steps/proofs described in Dan Boneh's video on PLONK in the PLONK Paper? The 2 don't seem to match

This is Dan Boneh's video on PLONK - https://www.youtube.com/watch?v=vxyoPM2m7Yg I went through the video multiple times & also tried to go through the original PLONK paper - https://eprint.iacr....
1 vote
0 answers
60 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\}$...
0 votes
1 answer
103 views

Given pedersen commitments of some elements, how to prove that the sum of only one subset of these elements is equal to the given element θ?

Assume that Prover have $n$ pedersen commitments ($V_{a_1},V_{a_2},\cdots,V_{a_n}$ where $V_{a_i}=G \cdot a_i + H \cdot r_{a_i}$) of $n$ elements $a_1,a_2,\cdots,a_n$. The Prover have another element $...
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 ...
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 = ...
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 ...
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? ...
2 votes
1 answer
195 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 ...
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 ...
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 ...
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}(...
3 votes
1 answer
177 views

Fischlin vs. Fiat-Shamir Performance

Using Fiat-Shamir, an interactive 3-round sigma protocol can be compiled into a non-interactive zero-knowledge proof in the random oracle model. A NIZK through Fiat-Shamir is not UC-Secure due to ...
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)$ ...
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 ...
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 ...
1 vote
1 answer
48 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 ...
4 votes
1 answer
121 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 ...
0 votes
0 answers
40 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. ...
1 vote
2 answers
219 views

Is there a ZKP that proves knowledge of a particular elliptic curve point?

Let E be an elliptic curve of prime order n. If we assume that Alice and Bob both know a scalar value ...
1 vote
1 answer
132 views

Unable to understand Eli Ben Sasson's STARK arithmetization & proof example

This is from this video - https://www.youtube.com/watch?v=9VuZvdxFZQo Bob has a list of length $10^6$. Bob wants to convince Alice that every number in the list is between 1 & 10. Alice needs to ...
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?
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\...
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 ...
0 votes
0 answers
40 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 ...
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 ...
0 votes
1 answer
108 views

Proving anonymous credential presentation

In a CL-based or CKS-based anonymous credential system, how can a verifier $V$ prove that a credential holder $H$ has presented it a credential that has been issued by an issuer $I$ without ...
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 ...
2 votes
4 answers
294 views

Is it possible to verify and relay an encryption key with a trusted but transparent third party?

I'm wondering if it would be possible to implement this functionality with a trusted but transparent third party (maybe an Ethereum smart contract?): Bob has an encryption key. Alice has the ...
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) ...
2 votes
1 answer
224 views

How to understand this detail of a zkSNARK-protocol?

As a beginner in cryptography and zk-SNARKs, I am currently working through the paper "Why and How zk-SNARK Works". There, I don't understand the last section at the bottom of page 15: ...
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. ...
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 ...

1
2 3 4 5
22