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
0answers
77 views

Why is a two-round Feistel Network not a PRF?

I am a student studying PRP and PRF in school, my prof gave us a thinking question: "Why is a two-round Feistel network not a PRF, even while the component function is a PRF?" I've seen that ...
1
vote
1answer
91 views
+50

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
67 views
+50

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
18 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
55 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,...
1
vote
0answers
39 views

What is the difference between "Proof of Knowledge" and a "Interactive proof system"?

Stating to the Wikipedia pages of "Proof of Knowledge" and "Interactive Proof System" and also this question: When would one prefer a proof of knowledge instead of a zero-knowledge ...
2
votes
1answer
112 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
48 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
19 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
57 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
77 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
16 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
55 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
84 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
82 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. ...
1
vote
0answers
26 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
88 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
47 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
31 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
75 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
47 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
34 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
51 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
77 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
50 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
38 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
76 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
90 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
64 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
48 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
28 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
163 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
36 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
74 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
54 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
46 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 ...
0
votes
0answers
28 views

How are zero-knowledge proofs used in blockchains to achieve anonymity?

The idea of blockchain is clear to me - If we reach consensus and all participants have the same state, it is easy to verify transactions. But new mechanisms (like Z-Cash) allow this without the ...
0
votes
1answer
34 views

Parameter c in Fiat–Shamir heuristic

According to Wiki there is a possibility of non-interactive Zero-Knowledge Proof of discrete logarithm if challenge $c$ is computed via a hash function. But what is the purpose of $c$? Why can not I ...
1
vote
0answers
29 views

Proof that interactive proof system is equivalent to generalized interactive proof system

I did try to prove the interactive proof system and generalized interactive proof system are equivalent. According to both definitions are in the pictures. However, I still struggling to do it. Please ...
4
votes
1answer
98 views

Which is the relation between Zero-Knowledge Proofs of Knowledge and circuits?

With the risen popularity of Zero-Knowledge Proofs of Knowledge (ZKPoKs) such as Pinocchio, Groth16 and Sonic, to name some ZKPoKs that are popularly known as zk-SNARKs, I got engaged to understand ...
1
vote
1answer
39 views

ZK-SNARK basics: knowing t(x), what prevents the prover from creating random h(x) to forge L, R, and O

After reading a number of ZK-SNARK explainers from here, here, and here, I still don't understand a few things. The setup of the algorithm uses QAP to calculate polynomial P(x) = L(x) * R(x) - O(x), ...
2
votes
1answer
57 views

Pedersen Commitment and Computational Zero Knowledge

I am curious at how "good" is computational zero knowledge? Consider Pedersen Commitment $z = g^x h^y$. There exists perfect ZK protocol (based on Schnorr's) to prove that one knows the ...
1
vote
0answers
40 views

How to use OR Proof of sigma protocol to prove a commitment C is a commitment to 0 or a commitment to 2

Such as the following relation: $\mathcal{R} = \{(C,g;r): C = g^r \vee C = g^r h^2 \}$
0
votes
1answer
58 views

Set membership proof for private value and set

This set membership proof is used in P2P networks, when one party possesses a private value, and the other party possesses a set. They would have to broadcast some data associated with the value and ...
2
votes
1answer
41 views

non-interactive secure computation with a twist?

non-interactive secure computation (NISC) (introduced by this paper, followed by others) is a variant of secure 2PC/MPC defined as the following setting: Alice publishes an encrypted version of f(*, y)...
5
votes
1answer
129 views

Zero-Knowledge Proof of Equality between RSA Modulus and Prime Order Group

Assume there is an RSA public key $(e,n)$ such that factarization of $n$ is unknown to both prover and verifier parties. We also have a prime order group $G$ and a generator $g$ for the group. For $m\...
1
vote
3answers
158 views

Using zk-snarks to verify a highest bid

I understand that we can verify that given a private input a and a public input b that we can verify ...
1
vote
1answer
35 views

Encrypted verifiable schema with hidden content

I'm having a problem with an encryption scheme. There are two entities, $A$ and $B$. $A$ give a simple message $m \in [0,1]$ to $B$. $B$ should generate an encrypted message of $m$: $e=Enc_{pk}(m)$ ...
1
vote
1answer
55 views

Zero-knowledge proof of committed value

I am considering the following questions and would appreciate any help. Problem formulation: Suppose Alice holds a secret value $x$ and there is a public Boolean predicate function $\texttt{Pred}$ ...

1
2 3 4 5
15