We changed our privacy policy. Read more.

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
1
vote
0answers
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
1
vote
2answers
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 {...
2
votes
0answers
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. ...
1
vote
0answers
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{...
0
votes
1answer
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, ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
4
votes
0answers
69 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
votes
0answers
95 views

Is the proposed identification protocol based on zk-SNARK correct?

By studying the zk-SNARK technology and Schnorr's identification protocol, I tried to design a new identification protocol. Original Schnorr's protocol:(review) Prover sends its commitment value $u=g^...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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$...
1
vote
1answer
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 ...
2
votes
0answers
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 ...
0
votes
0answers
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 ...
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
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; ...
0
votes
1answer
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 ...
0
votes
0answers
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&...
0
votes
0answers
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 ...
2
votes
2answers
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, ...
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
71 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
52 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
45 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
27 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
33 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
28 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
92 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
37 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
54 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
55 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
124 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
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 ...
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}$ ...
0
votes
1answer
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 ...
2
votes
2answers
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 ...
0
votes
2answers
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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?
1
vote
0answers
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 ...
0
votes
1answer
108 views

Are zero knowledge proofs alternative private key encryption? [closed]

Are they the alternative to private keys. If I understand correctly, because of the increasing computational power in today's world, zero knowledge proofs are more safe than private keys ? Are these ...
1
vote
0answers
82 views

Comparison of SNARK-friendly hash algorithms MiMC7, Poseidon, Pederson?

There are some cryptographically secure hash algorithms designed to be efficient for SNARKs, STARKs and FHE. Some of them already implemented in Zcash, Zokrates and circom. The ones that I know of are:...

1
2 3 4 5
15