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
35 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
20 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
133 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
28 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
53 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
44 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
0answers
18 views

Using a Zero Knowledge Proof to reveal only specific user preferences and using a blockchain to maintain a record

I am researching zero knowledge proofs and I am keen to propose a potential application. I have a bunch of users and I want my users to share their preferences with third parties, but only relevant ...
0
votes
1answer
32 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
20 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
27 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
23 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
79 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
24 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
46 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
32 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
47 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
37 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
117 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
145 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
32 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
51 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
54 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
93 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
125 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
47 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 ...
1
vote
1answer
73 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
68 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
32 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
100 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
68 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
vote
0answers
50 views

Does there exist a provably correct and recipient hiding encryption scheme?

I am looking for an encryption scheme $E$ and a commitment scheme $C$ which allow encrypting the message $m$ for the public key $y$ as $e = E_y(m)$, so that the ciphertext $e$ does not reveal any ...
2
votes
1answer
51 views

Dishonest verifier running a concurrent zero-knowledge protocol

Suppose Alice and Bob are engaged in the graph 3-colorability Zero-knowledge protocol in which Alice permutes a coloring $\varphi:V\rightarrow \{1,2,3\}$ for a graph $G(V,E)$, and then sends a ...
1
vote
0answers
46 views

Honest Verifier Zero-Knowledge (HVZK) composability

Let protocol A and protocol B be HVZK proof systems. If we construct a protocol C composed of protocol A and protocol B, will it be HVZK as well? Is there some formal proof in the literature regarding ...
4
votes
3answers
223 views

Why it is said that “zk-SNARKs need a trusted setup” to work?

What is the meaning of a "trusted setup" in this context? It is often said all around that zk-STARKs and Bulletproofs does not require a trusted setup. How do zk-STARKs and Bulletproofs ...
2
votes
1answer
73 views

Intuition Behind Commitment-Challenge-Response a.k.a. Sigma Protocols

In How To Prove Yourself: Practical Solutions to Identification and Signature Problems, Fiat and Shamir introduce a zero-knowledge identification scheme where The prover sends a commitment to the ...
4
votes
1answer
65 views

What is meant by the probability distribution of a verifier?

I'm having trouble understanding the role of probability distributions in the definitions of computational/statistical indistinguishability, especially in the definition of zero-knowledge. From A ...
1
vote
0answers
102 views

Zero-knowledge proof of knowledge of a plaintext in exponential ElGamal

Consider the exponential ElGamal cryptosystem over some group $G$ with generator $g$. Let $m$ be a plaintext, and $(R, C) = (g^r, g^m \cdot y^r)$ an encryption thereof for some public key $y$. Assume ...
0
votes
0answers
38 views

Practicality of dangerous/unsafe content safety proof as follows

Suppose I am building a cloud storage with client side encryption. My policy is that I would not allow anyone to store pornographic, violent or otherwise unsafe content but must ensure full privacy. ...
0
votes
0answers
64 views

Zero Knowledge Proof: Prove correct ElGamal encryption without leaking message

I know it is possible to prove zero knowledge that a given ElGamal ciphertext $(c,d)$ encrypts a plaintext belonging to some set ($\{0,1\}$ is frequently used for electronic voting applications). Next ...
0
votes
2answers
127 views

Given ciphertexts C1, C2 of different messages P1 and P2; how can we prove that both C1 and C2 were encrypted using public keys of the same pair?

I vaguely recall reading about a scheme that accomplished this but am not able to figure out which one it was. For the sake of brevity I'm gonna omit any nonces. Let's say we have an asymmetric ...
1
vote
0answers
69 views

Security of an ECDSA Adaptor Signature Implementation

I'm currently working on an implementation of ECDSA Adaptor Signatures, and part of the signature scheme calls for a NIZK proof to verify knowledge of exponent over two public keys that share a ...
1
vote
0answers
40 views

Simple description of a multi-party fair exchange protocol with trusted third-party

Imagine Alice wants to sell a file with important information to Bob for money. The file must be encrypted, so nobody can eavesdrop. It must also be signed upfront, so Bob knows it has not been ...
0
votes
1answer
90 views

Honest players in ZKP proofs

Trying to study ZKPs, I have seen that proofs qualify players (a part from -of course- simulator and extractor): so honest prover, honest verifier. Is it needed because usually examples deal with ...
2
votes
0answers
47 views

Trade-offs for more parties in PICNIC multi-computation

In the PICNIC post-quantum signature scheme, a zero-knowledge proof of the secret key for a symmetric encryption is produced by implementing the encryption as a Yao garbled circuit of a three-party ...
0
votes
0answers
78 views

Request for a zero-knowledge proof (or hint)

I want to design a zero-knowledge proof (ideally a NIZK, but could be a sigma protocol) so that Alice can prove that a certain encryption contains a value that has been signed by a certain key. More ...
1
vote
1answer
180 views

ElGamal encryption of concatenated messages

Suppose an encrypter separately produces three ElGamal ciphertexts $c_1 = E(m_1)$, $c_2 = E(m_2)$ and $c_3 = E(m_3)$, which encrypt the messages $m_1$, $m_2$ and $m_3$, respectively. Is it possible ...
2
votes
0answers
52 views

How does the rejection sampling lemma work in the proof of HVZK?

In this protocol, Q1: how does the commitment work? What if the prover sends $\textbf{t}$ directly, and then sends $s_m,s_r,s_{\textbf{e}}$? Q2: How does the rejection sampling lemma work? refer to ...
3
votes
1answer
77 views

CRS vs SRS in zk-SNARK

Are Common Reference String (CRS) and Structured Reference String (SRS) is the same in preprocessing phase of zk-SNARK? Is there any difference between them?
1
vote
1answer
128 views

Hash and (MAC) based signatures using zk-SNARK

I was wondering if we could use any general symmetric key MAC, a collision resistant hash $H$ and zk-SNARK (or any general NIZK scheme) to construct a signature scheme. I have a MAC key $k$, which is ...
0
votes
1answer
76 views

Construction of R1CS vs QAP

I have been following the medium post of Vitalik, where he shows step by step how to convert program --> Circuit --> R1CS --> QAP. I am aware of the Pinocchio protocol, where they utilize the ...

1
2 3 4 5
15