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
1answer
48 views

zkSNARKS: What prevents the prover from chosing a different polynomial than the one he is expected to know

I am reading this explanation of zkSnark written by Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf Here the Prover knows a polynomial of degree 3, 2 of the solutions of the ...
1
vote
1answer
55 views

How can I prove the preimage of a hash that contains a number is bigger than x?

So I want to create a zero-knowledge proving system for numbers (think loans and bank accounts, I want to prove my paycheck is more than x dollars per month). I was thinking about using a zero-...
2
votes
1answer
41 views
+50

Prover cost of QAP based zkSnark

In CGPR [https://link.springer.com/content/pdf/10.1007/978-3-642-38348-9_37.pdf] Section 3.5, it is mentioned that the cost of prover is $O(|C| \log(|C|))$, given the size of the circuit is $|C|$. It ...
1
vote
1answer
20 views

zkSNARKS - unable to understand the usage of polynomial to verify some condition

From Vitalik Buterin's Blogpost - An approximate introduction to how zk-SNARKs are possible From the sub-topic "Comparing a polynomial to itself", I understood till here In other words, any ...
2
votes
1answer
45 views

How to guarantee that a ZKP was generated honestly?

The following extracts were taken from the Zero-Knowledge Proof page on Wikipedia: In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can ...
0
votes
0answers
59 views

how do you prove you are not a bot with a zero knowledge proof?

I communicate with another person online, I know he is a person because sometimes he also writes real messages but at random timeframes whenever I send him a message he only responds with a dot maybe ...
2
votes
1answer
71 views

Commit the output of verifiable random functions

The problem setting is as follows. Suppose there exists a public input $x$ and the prover evaluates $y \gets VRF_{sk}(x)$, but the prover does not wish to reveal the output $y$. My question is would ...
1
vote
1answer
75 views

Could someone explain the protocol of Yevgeniy Dodis, Shai Halevi, and Tal Rabin in details?

This is from the paper of Yevgeniy Dodis, Shai Halevi, and Tal Rabin Could anyone provide some help about understanding how the following protocol is executed? The game is played based on the sequel ...
3
votes
1answer
589 views

It is possible to prove that two private keys are related?

Say Alice owns two keypairs: ($Pub_1$, $Priv_1$) and ($Pub_2$, $Priv_2$). The pair ($Pub_1$, $Priv_1$) is pretty mundane. $Priv_2$ was intentionally created by Alice by concatenating $Priv_1$ and the ...
1
vote
1answer
145 views

How to Prove Correct Decryption in ElGamal Cryptosystem

I am working on a project that uses ElGamal cryptography using multiplicative notation. The project is an internet voting implementation that uses the cryptosystem to encrypt the received ballots, re-...
1
vote
0answers
40 views

Deterministic $σ_i$ when implementing traceable ring signature on Curve25519

Fujisaki & Suzuki's Traceable Ring Signature paper, which allows for a signature by one private key out of a ring of public keys to sign, and for anyone to verify that one member of the ring ...
1
vote
0answers
29 views

Which cryptographic tool can be used to prove that a program passes a certain test?

Let's say I have a smart contract located at an address A, and another smart contract that runs tests on A located at ...
0
votes
0answers
31 views

Proving the output of a generic function

Is there any generic construction to prove the correctness of the output of a function? In other words, is there a general way to produce a witness for the statement $y = f(x)$? More formally, let $f: ...
3
votes
1answer
295 views

Grinding in the Fiat-Shamir heuristic

The Fiat-Shamir heuristic is assumed to substitute public-coin messages from the verifier by hashes of the prover's messages until this point, i.e.: $$H(\alpha_1) = \beta_1, \\ H(\alpha_1, \alpha_2) = ...
0
votes
0answers
26 views

Summarized steps for zero knowledge proof on a public blockchain transaction

Im triying to understand Zero knowledge proof and its applications, my first instict is a blockchain (I will use Bitcoin-like for simplicity sake) Im triying to wrap my head around it by describing ...
2
votes
1answer
108 views

Prove that Two Re-encryptions of the Same ElGamal Pair have the Same Decryptions

I'm working on an internet election system that requires the shuffling of ballots accompanied by an interactive proof of the legitimacy of the shuffle. I am working on this paper and I am stuck at the ...
3
votes
2answers
133 views

Is there a zero-knowledge proof of a hashed secret?

Alice wants to share a secret $S$ with Bob so she encrypts it with Bob's private key. Bob is not online at the moment so Victor will keep it safe for him in the meantime. Victor the verifier would ...
1
vote
2answers
90 views

Simulator vs Prover -- Zero Knowledge Property

I know this topic has been discussed many times on this platform; however, I still lack the intuition behind proof systems' zero-knowledge property. I understand that goal of the simulator is to ...
0
votes
3answers
95 views

Zero-knowledge proof of HMAC digest

I'm reading the Wikipedia for HMAC, and I feel a little bit lost. I'm wondering if there exists... $$digest = \operatorname{HMAC}(msg, key)$$ Is it possible to prove that $digest$ is computed from $...
1
vote
1answer
42 views

Current status of ring signatures/proof of set membership

I understand the original O(n) implementation of a ring signature, but I'm trying to figure out where the state of the art is on signing a message as an anonymous member of an ad hoc group without ...
1
vote
1answer
72 views

How does the simulator generate a correct transcript under HVZK with the Fiat-Shamir heuristic?

Background I understand the interactive version of Schnorr's protocol and I understand how the simulator can generate an output that is i.i.d to the output of the prover-verifier: Question What I don'...
0
votes
1answer
40 views

How to prove that paillier encryption is positive (zero-knowledge)?

Is it possible that the plaintext encrypted in a ciphertext using paillier encryption is positive without using a zero knowledge range proof?
2
votes
1answer
49 views

Is this a safe zero knowledge proof that two paillier encryptions are equal?

We have encryptions $c_1$ and $c_2$, the person who knows the plaintext and randomness in both wants to prove that they know it. Let $r_1$ and $r_2$ be the randomness values in $c_1$ and $c_2$ ...
0
votes
0answers
31 views

Zero-knowledge proofs for preventing data abuse

I am looking for a theoretical solution to the following problem: Alice receives a signed statement from her bank with information about her account and credit balance. Alice wants to prove this ...
4
votes
1answer
80 views

Groth16 simulate zero-knowledge proof for invalid statement

The zero-knowledge property of the Groth16 (https://eprint.iacr.org/2016/260, page 8) non-interactive zero-knowledge argument is based on the existence of a simulator $\text{Sim}$ generating "...
3
votes
2answers
80 views

Prove that $x$ is the sum of digitally signed numbers without revealing the summands

Imagine this: Charlie chooses two integers $x_1$ and $x_2$ and signs each of these integers with the same private key. Charlie sends the following to Alice: $x_1$ and $x_2$, the two signatures, and ...
5
votes
2answers
164 views

ZKP: Prove that >18 while hiding age

I am relatively new to cryptography, but I've been programming for a while. Here's a story that sets well the problem I'm trying to solve: Alice has a digital passport that's signed with her ...
1
vote
0answers
33 views

THe operation proof part of paper "Why and How zhSNARK works"

I'm reading the paper "Why and How zk-SNARK works" to learn zkSNARK, and I suffered some problem in section 4.4, when prove the ability of single operation. In this section, it tries to come ...
1
vote
1answer
60 views

Why Zk-SNARKs are Argument of Knowledge if a Knowledge Extractor exists?

From what I know, proving the existance of a Knowledge Extractor implies perfect soundness. So why in zk-SNARKs (and similar) we talk about Arguments of Knowledge, where the soundness property is only ...
0
votes
0answers
43 views

Are zk-STARKs a Sigma protocol? Is the communication interactive? And other doubts

I've heard that STARKS are not a non-interactive protocol, if so: What is (briefly) the mechanism they use to operate? Can they be considered a Sigma protocol? Why SNARKs are not interactive, instead?...
3
votes
2answers
156 views

Is "Witness" and "Proof" the same thing when talking about Zero Knowledge? What about "argument"? And "statement"?

I've seen people making lots of distinctions while reading papers about zero-knowledge. I've seen the term "Argument of Knowledge" that seems to be used as a weaker "Proof of Knowledge&...
0
votes
0answers
23 views

What are the main attacks that can be done against a ZK Σ-protocol like Schnorr's identification scheme?

I heard about the "Chess Grandmaster Problem", Eavesdropping attacks and Man-in-the-middle. Can they be applied in any way to a ZK protocol? I'm not looking for long examples, just what are ...
4
votes
0answers
60 views

Why do Lattice-based Proof Systems not use the $\ell_2$ norm and canonical embedding?

I was recently reading the paper A non-PCP Approach to Succinct Quantum-Safe Zero-Knowledge. Among other things, it discusses an adaption of the "folding" technique (from Bulletproofs) to ...
0
votes
0answers
50 views

Are there batched vector/polynomial commitment proofs with sublinear proof size for Verkle Trees?

High level goal: a Verkle tree (Merkle tree using algebraic vector commitments at each level rather than hashes) with depth d where I can prove the existence of <...
2
votes
0answers
80 views

Difference between an authentication scheme and a identification scheme in ZK proofs?

EDIT: I want to specify what I know about schemes security: Authentication schemes: P can prove V he is P, and nobody else can prove V that they are P. Identification schemes: P can prove V he is P, ...
0
votes
1answer
86 views

How to prove that the Fiat-Shamir identification scheme is zero-knowledge?

I'm trying to prove that this protocol https://de.wikipedia.org/wiki/Fiat-Shamir-Protokoll is zero-knowledge (the page is in german but it was the only good and simple image i could find) I'm a ...
1
vote
1answer
65 views

zkSnark: Converting R1CS to QAP

I am reading through Vitalin Buterin's page on R1CS & QAP - https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649 I understood upto the part where he gets ...
4
votes
1answer
468 views

What's the main difference between the Schnorr identification scheme and its Smart-Card implementation?

This question arises because I couldn't find any official paper for the Schnorr identification scheme, but only for the Smart-Card implementation of it. Also, it seems that everyone, when talking ...
5
votes
1answer
219 views

Why Zero-Knowledge protocols are used for NP problems if IP is the class of interactive proof systems where they come from?

As stated in the title, I'm studying ZKPs and I see they are just interactive proof systems that respect the zero-knowledge property. Now, if that's true, why aren't they used for IP problems, the ...
2
votes
1answer
124 views

Altering a subroutine PPT's output to fit a reduction proof

I have a protocol that operates in the malicious setting which involves parties sending each other group elements $u\in \mathbb{G}$ of a specific form (For example, these are messages of the form $u=g^...
0
votes
1answer
94 views

zkSnark Intro by Maksym Petkus: Is the polynomial defined over $Z$ or is it defined over $Z_n$?

I am reading this explanation of zkSnark written by Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf Here he has a polynomial $p(x) = x^3 − 3x^2 + 2x$ and the homomorphic ...
0
votes
0answers
24 views

How to prove lifted ElGamal encryption with square root communication?

I'm looking for a more efficient solution to prove the correctness of multiple ciphertexts sent to different parties are correct. The background is that $P_i$ uses lifted ElGamal encryption to encrypt ...
1
vote
0answers
79 views

Why the Kate Commitment and the Algebraic Group Model is used a lot in zk-SNARKs proving system since 2019?

I am engaged in the research of zk-SNARKs. After I read some papers about zk-SNARKs, I realize the Kate Commitment and the Algebraic Group Model is used a lot since 2019. They are used in Sonic, Plonk,...
2
votes
1answer
122 views

zkSnark: Restricting a Polynomial

I am reading this explanation of zkSnark written by Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf I have understood everything in the first 15 pages. In 3.4 Restricting a ...
0
votes
1answer
57 views

Quantum secure algorithms

I want to know if the below algorithm , secure against quantum computing attack, and how I can compute the running time for the original algorithm and the proposed attack Source: Yan Zhu, HuaiXi Wang,...
0
votes
0answers
21 views

Proof that the encrypted content is the same as the promised original

Context : Alice has some content (C) and published its hash (Chash) publically. She wants to send C to Bob in a way it's visible only to Bob. This can be done by encrypting (Cenc) in using his Public ...
0
votes
0answers
60 views

Prove that string exists in source file of sha256 hash

How to prove that hashed data includes specific string without exposing rest of the string? Practical example is calculating digest to be signed of the PDF file and before signing the digest we need ...
3
votes
1answer
82 views

Is it common/valid to hardcode an element of a language into a simulator?

Short version: Is it a common practice (and a valid practice) to hardcode an element $d \in \mathcal{L}$ of a language into a simulator? (making the simulator non-uniform and non-constructive) Long ...
1
vote
1answer
19 views

Procedure for finding consensus on selected numbers without sharing selection

I was wondering if there exists an algorithm, paper, etc. for the following problem: Assume we have a public list of numbers, let's say {1, 2, 3, 4, 5}. Alice and Bob both pick any subset of those ...
2
votes
1answer
64 views

Extending the OR-proof to more than two statements

I have been reading about the sigma protocols, specially the OR-Proof. Many examples just take into account two statements and provide a way to say that one of the statements is valid, but not which ...

1
2 3 4 5
16