# 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.

734 questions
Filter by
Sorted by
Tagged with
28 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? Long version: I have a prover $P$ that does the following: it ...
14 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 ...
45 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 ...
71 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 {...
75 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. ...
22 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{...
46 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, ...
43 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 ...
28 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 ...
69 views

42 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 ...
27 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 ...
49 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$...
76 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 ...
48 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 ...
33 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 ...
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$ ...
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 ...
89 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; ...
63 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 ...
46 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&...
27 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 ...
159 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, ...
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?
71 views

155 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 ...
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)$ ...
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}$ ...
59 views

### Definition of soundness (a different approach) in "Witness Indistinguishable and Witness Hiding Protocols"

In any other context where I encountered the concept of soundness it was very simple: if the input does not belong to the language then the protocol fails or fails with great probability. But in the ...
98 views

### Role of AND operation in FHE, MPC and ZK

Going through LowMC, one of the main advantage of it seems to be useful in Fully Homomorphic Encryption (FHE), Multi-party Computation (MPC) and Zero Knowledge (ZK) proofs. I have no idea about any of ...
134 views

### How can I prove "single-use authorization" from multiple parties without revealing identity?

I've been trying to create a distributed authorization protocol where identities are not revealed. Let me explain with an example. Let's assume we have 4 actors, Alice, Bob, Charlie, and Dan. Alice is ...
49 views

### Let (P, V) be any ZK protocol, then the protocol is WI. --> help with proof

In the amazing paper "Witness Indistinguishable and Witness Hiding Protocols " by Shamir and Feige. Theorem 3.3: Let (P, V) be any ZK protocol, then the protocol is WI. The sketch of the ...
88 views

### IS zk-SNARK not suitable for constructing anonymous authentication scheme?

zk-SNARK was a powerful tool for privacy-respecting e-cash. However, recent years, in the literatures about anonymous authentication scheme, such as group signatures, anonymous credential, blind ...
72 views

### Some information about zero knowledge proofs

How do I start studying Zero-Knowledge proofs? What are some good books and entry-level research papers on that topic? What are some prerequisites of the same?
35 views

### Range proofs and Groth-Sahai PPEs

I'm looking for a set of pairing product equations (ala Groth-Sahai) which allow a prover to prove that the output of a VRF is in a specific range. In the E-cash system in [BCKL] there is a ...