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
4
votes
1answer
59 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
69 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 ...
4
votes
1answer
89 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
29 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
49 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
33 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
129 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
21 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
58 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
43 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
80 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
52 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
465 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
206 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
120 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
89 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
20 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
76 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
118 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
52 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
58 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
81 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
17 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
59 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
vote
2answers
105 views

Knowledge proof of private keys from DH key exchange

Given a group where the computational Diffie–Hellman (DH) assumption holds and generator G. Say there is a set of private randomly selected keys {a, b, c, d, e,...} and corresponding public keys set {...
2
votes
0answers
86 views

It is possible to verify the computation of a hash function without actually proving it in zero knowledge?

Let me first introduce the context: Let's say that we have a hash function evaluation: $$h = H(x, y),$$ where $x$ and $y$ are the public and the private input of the hash function $H$, respectively. ...
3
votes
1answer
38 views

Definition of Circuit Satisfiability In The Context of zk-SNARKs

A standard theorem is that boolean circuit satisfiability is NP-complete (shown in CLRS, for example). I am interested in what these statements formally mean. From CLRS, I can cite that $$\text{...
0
votes
1answer
106 views

Are zk-STARKs really quantum resistant?

I see lots of mention that zk-STARK proofs that are being developed notably for use in blockchain networks are labelled as "quantum resistant". Many articles and reports that state this, ...
1
vote
0answers
48 views

Is there a zero knowledge proof of knowledge of a Waters sigature?

I am looking for a ZK PoK of a digital signature. I have seen constructions that work for ElGamal signatures (see this older paper), but need to work with Waters signatures, as described here. Has ...
1
vote
0answers
32 views

ZK: Repetitions to lower simulator halt probability

I'm trying as autodidact to read chapter 4 of Foundation of Cryptography by Oded Goldreich (just to let you "tune" your answers, I have engineering background). If I'm correctly ...
4
votes
0answers
82 views

2 different definitions of Special Soundness

There are 2 different definitions of special soundness in the literature: (1) can be found in Damgard: We say that a Sigma-protocol $\Pi$ satisfies special soundness, if there exists a PPT extractor $\...
1
vote
1answer
48 views

Can interactive zero-knowledge proof systems be implemented using secure two-party computation?

I am defining multi-party computation using the real-ideal paradigm (see A Pragmatic Introduction to Secure Multi-Party Computation). That is, for any successful attack on an MPC protocol in the real ...
0
votes
0answers
39 views

How does one construct a SNARK circuit for proving the knowledge of a SHA256 pre-image?

Usually one explains how the R1CS/QAPs and SNARKs work using examples of circuits with multiplication and addition nodes, and constructing polynomials from that is relatively straightforward. SHA-2 ...
0
votes
0answers
52 views

Does the degree of this polynomial matter to achieve zero-knowledge? PlonK question

I was reading the paper PlonK and in the Round 1 of the claim to achieve zero-knowledge by adding random multiples (of degree one) of the polynomial $Z_H = x^n - 1$ to the secret polynomials. Here, $H$...
1
vote
1answer
87 views

Proof that someone has access to a private key whose public key is part of a known group

I'm a crypto newbie and hoping to get pointed in the right direction. I've seen some related questions like this but none that satisfy my requirements. Let's say Jane's Forum is a large community, and ...
2
votes
0answers
54 views

Verifiable execution of a program

I would like to know what cryptographic primitives could be used for Alice to prove to Bob that she actually executed a program. The goal is to make a Proof-of-useful work, where Alice proves she ...
0
votes
0answers
47 views

Zero Knowledge Proof for Merkle Tree Update

I have a Merkle tree that contains the balances of users in each leaf. Periodically, users are paid more, and their corresponding Merkle leaves are updated, which results in a new Merkle root. Is it ...
5
votes
1answer
78 views

Is the following proof scheme zero-knowledge?

Consider that I wish to prove knowledge of some RSA private key corresponding to a public key $(e,N)$. A naive interactive proof scheme would proceed as follows: $V$ generates some random message $m$ ...
0
votes
0answers
20 views

Zero-knowledge proof set - one time proof construction and different verifications

Is it possible to construct a zero-knowledge proof set and then change the verification query without reconstructing the proof? For instance, my set could include red, blue and green but while, at ...
3
votes
1answer
92 views

Proof that a message is signed by a member of a group

I'm a newbie at cryptography. Here is my question: Alice makes a list of people: Bob, Carol and Dan; Alice gives a unique secret key to every member on the list, so they can uniquely sign messages; ...
0
votes
1answer
66 views

ZKP but the verifier knows all possible secrets

Is there a (preferably simple) implementation of ZKP where the verifier already knows the set of possible secrets? Especially if the set is very small (even as few as 2 or 3 options). The prover must ...
0
votes
0answers
49 views

Comparing two private values and extracting the ciphertext corresponding to the minimum value

How can I solve this problem: I have a directed graph of nodes that can be malicious and all of them have a private value. Consider a node "B" with private value "BPrivateValue = b&...
0
votes
0answers
29 views

Efficient proof for Cartesian product

I am trying to find some efficient zero-knowledge arguments that could prove the vector ${\bf v}$ is the Cartesian product of two vectors ${\bf x}$ and ${\bf y}$. I know there are efficient inner ...
2
votes
2answers
171 views

Zero knowledge RSA public key

Suppose Bob has $k>1$ RSA public keys $(e_i, n_i)$ without any knowledge of their corresponding private keys. Alice also has all the public keys, but also has a private key for only one of them, ...
0
votes
0answers
37 views

Zero-knowledge composability

Suppose a protocol P is composed of two different zero-knowledge protocols. Can we assume P is also zero-knowledge?
0
votes
1answer
81 views

Zero Knowledge Discrete Logarithm on Elliptic Curves

Can the Discrete Logarithm ZK be implemented on elliptic curves? It seems that such an implementation should look like the following: $Y = \alpha G$ Random pick $v$ $t = vG$ $c = H(G, y, t)$ $r = v - ...
0
votes
2answers
56 views

Discrete Logarithm Fiat-Shamir Parameters Selection

According to Fiat–Shamir heuristic there are two parameters of the algorithm: big prime number $p$ and primitive root $g$. Thus several questions arise: How big should the prime number $p$ be? How to ...
0
votes
1answer
50 views

Several Discrete Logarithm Zero Knowledge Proof

According to Wiki there is an approach for proving knowledge of $x$ such that $g^x = y$. How can I prove that I know $x_1, x_2$ such that $g^{x_1} = y_1, g^{x_2}=y_2$. Of course, I can make these ...

1
2 3 4 5
16