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
votes
2answers
33 views

How to sell a piece of data through blockchain?

User A attempts to sell a piece of data D (byte level) to user B at price C through the block chain. A and B do not trust each other. A worry: After the data D is delivered, B does not complete the ...
0
votes
0answers
52 views

zero knowledge proof of range and set membership

I have a large number of items with a unique serial number and a score (score isn't always unique). There is a list which contains all of the serial numbers and their respective scores. I select 3 ...
0
votes
0answers
8 views

Zero knowledge proof - Hash [duplicate]

How can I prove that I know the input value of a given hash output without revealing the input? Say for example: sha256("abc123") = "6ca13d52ca70c883e0f0bb101e425a89e8624de51db2d2392593af6a84118090"....
0
votes
1answer
31 views

Why does a transcript which is indistinguishable from a fake one show zero knowledge?

Is there an intuitive way to understand why having a transcript that the verifier could have created themselves and is indistinguishable from a real transcript , shows zero knowledge?
1
vote
0answers
57 views

Efficient protocols for set membership proofs with private sets

I found the paper on Efficient Protocols for Set Membership and Range Proofs in which efficient protocols for the following problem are discussed: Given a commitment $C_v$ to a value $v$ we want show ...
1
vote
0answers
48 views

How can I prove that the plaintext of an elgamal ciphertext is the discrete log of an element?

Is there any (efficient) method to prove that the plaintext of an ElGamal ciphertext is the discrete log of an element? In the scenario I concerned, I have an El Gamal key pair $(pk, sk) = (g^y, y)$....
3
votes
0answers
40 views

The existence of two-round zero-knowledge proofs

Does there exist any (im)possibility results for two-round private-coin non-auxiliary input zero-knowledge proofs for languages outside BPP?
2
votes
0answers
43 views

Adaptation of Stern Zero-Knowledge protocol from coding to lattices

I'm currently working on Zero-Knowledge-proofs in lattice context, for which there exist two major frameworks. One of those two is the adaptation of Stern protocol from code-based-crypto. There is in ...
1
vote
1answer
43 views

How would P=BPP affect zero knowledge proofs?

If there were a proof to show that P=BPP, how would this affect zero knowledge proofs and the fiat-shamir heuristic for Turing an interactive proof into a non-interactive proof?
0
votes
0answers
52 views

Comparisons in zero-knowledge proofs

There is already a great survey on how to do range checks in a zero-knowledge setting. A range check allows to constrain a variable to be in a certain range. Comparisons seem to be similar, but they ...
0
votes
0answers
7 views

question about using BulletProofLib code [migrated]

I'm having trouble understanding the library for generating non-interactive zero knowledge proofs without trusted setup (Bulletproofs) https://github.com/jpmorganchase/BulletProofLib The paper Zero ...
2
votes
1answer
59 views

NIZK proof for Order-preserving encryption

Suppose a cipher c=Enc(K,m), where Enc() is the order-preserving encryption scheme. Can NIZK be used to prove that c does indeed encrypt m? The Schnorr NIZK is based on discrete logarithms equality. I ...
1
vote
1answer
57 views

Zero knowledge proof with sum

All zero-knowledge protocols I have read so far for discrete log works like this: 1) Prover generate a random number $r$, creates a commitment $t=g^r$ and sends $t$ to the verifier. 2) Verifier ...
10
votes
2answers
110 views

Are interactive proofs more secure their non-interactive counterpart?

Given an interactive zk proof, if we use fiat-shamir to make it nizk proof, does the proof become less secure? Are there any new attack vectors that get introduced? Is there any reason to use the ...
8
votes
3answers
2k views

Examples of protocols that are insecure when run concurrently

I was reading Canetti00 Universally Composable security paper. The first page of introduction says that there are some MPC protocols and Zero knowledge protocols that are insecure under concurrent ...
2
votes
1answer
57 views

What does “simulatable” mean in security proofs?

I am reading a security proof in a paper as follows. Regarding the data confidentiality of users, all related public transcripts are simply the ciphertexts $\mathcal{C}_1,\ldots,\mathcal{C}_n$. The ...
4
votes
1answer
39 views

Is verification of ring signature always linear in the amount of members?

To me it seems that maybe we can prove that verification of a ring signature must be linear in the number of members, since we need to make sure each members component is correct and the ring is ...
0
votes
1answer
58 views

Given $P=xG$, prove in zero knowledge that I know $sqrt(x)$

Assuming that x has a sqrt. Given $P=xG$ is it possible to prove that I know the $sqrt(x)$ in zero knowledge?
1
vote
1answer
46 views

Given A, B, G, H prove the I know x s.t. $A=xG$ and $B=xH$

Given A, B, G, H .How would I prove that I know x such that $A=xG$ and $B=xH$
1
vote
0answers
117 views

Reduction to security of proof system for proving knowledge

I want to prove security of my system by reduction to the security of an underlying non-interactive proof system for proving knowledge. I know a game that captures the desired security property of my ...
1
vote
0answers
40 views

Verifiable Encryption of a Pedersen Commitment

Can the Verifiable Encryption of a Discrete Logarithm scheme of the paper https://www.shoup.net/papers/verenc.pdf (page 19) be used to verify that a ciphertext encrypts the same value committed in a ...
0
votes
0answers
28 views

How can I combine Quorum and Zero Knowledge Range Proofs

I have 20 years of experience at java JEE coding, and 10 years in devops as well, but no experience with blockchains, or the Go language. I want to setup a cluster of Quorum blockchain nodes, ...
1
vote
1answer
38 views

How to prove element equality in G1 using Groth-Sahai proofs

In the BeleniosRF e-voting scheme, Groth-Sahai proofs with the "Instantiation based on the SXDH assumption" are used (see https://eprint.iacr.org/2007/155, version 20160411:065033, page 24). In the ...
4
votes
2answers
249 views

Why is a common reference string needed in zero knowledge proofs?

Can we have a non-trivial language without a CRS? Why?
3
votes
0answers
70 views

As of 2019, what are the most important questions in zero-knowledge research? [closed]

Important meaning; where the most research is being focussed. Maybe because a break-though seems possible or a break-through would have big consequences. Any questions that are being researched ...
1
vote
1answer
55 views

Is it possible to change the generator without knowing the private key used?

For example, prover sends P = xG and verifier somehow sends back P = xH without learning x. Is this possible?
3
votes
1answer
67 views

How would I prove a number is not within a range?

This would be the opposite of a rangeproof. For example, I wanted to prove that my number was not between 0 and 200 in zero knowledge? On a separate note: how would I prove that I hold a number, but ...
0
votes
1answer
48 views

Is the following non-interactive zero-knowledge set membership protocol provable secure?

Given the following Zero-knowledge set-membership protocol https://infoscience.epfl.ch/record/128718/files/CCS08.pdf]. That is given in the following steps (Please refer to page 9). The Verifier -...
1
vote
2answers
50 views

What is the Knowledge Of Secret Key Assumption (KOSK)

From what I've read it seems to be where an entity must prove that they own the secret key. Which is done by signing a message M using said secret key. Is this ...
17
votes
1answer
3k views

Is a hash a zero-knowledge proof?

I’m trying to wrap my head around zero knowledge proofs, but I’m having trouble understanding it. In my current understanding, zero-knowledge proofs prove to the recipient that the sender has a ...
1
vote
1answer
101 views

Does such a cryptographic protocol exist?

Persons A, B and C put x€, y€ and z€ in a pot, respectively. Suppose that anyone can make a withdrawal from the pot as long as they prove they have such a right and that the y€ that B deposited is ...
3
votes
1answer
77 views

Given a ciphertext $c$ and a public string, how do we check whether $c$ encrypts something that is roughly equal to the string without decryption?

Let $𝑓$ be an encryption function, then we have $c = f(m)$ for some bit string $𝑚$. Here, we also have pattern matching function $𝑔(𝑚,𝑚′)$ which returns true whether $𝑚$ matches roughly with $𝑚′...
1
vote
1answer
29 views

Monero Ring CT sj calculation

For a university project, I am currently implementing the RingCT Ring signatures as used in Monero (before the introduction of Bulletproofs) as laid out in this paper. To close the ring we calculate ...
4
votes
1answer
259 views

ZKP: Proving knowledge of a variable length hash preimage

I am currently trying to implement a proof of knowledge of the preimage to a public hash image using different zkp system implementations. There are a lot of examples that do exactly this (see this ...
3
votes
0answers
51 views

Schnorr protocol is witness-hiding?

Regular 3-steps Schnorr protocol is a proof of knowledge system for discrete logarithm. It's honest-verifier zero-knowledge, but not full zero-knowledge. My question is, is it witness-hiding? (I guess ...
0
votes
0answers
30 views

The security of Zero knowledge proof performance

I recently learned to study the security of zero knowledge proof. As you can see on the wiki (link), it seems to be the most popular example of the Ali Baba cave. I have a question about the security ...
2
votes
0answers
44 views

What is the relation between honest verifier zero-knowledge and non-interactive zero-knowledge?

I'm not clear about the relation between the following definitions: zero-knowledge protocols; honest verifier zero-knowledge; non-interactive zero-knowledge. To my best understanding, zero-knowledge ...
2
votes
1answer
62 views

How does the Signature Scheme in Picnic Works

I am trying to understand how signature scheme proposed to NIST, Picnic, works. The propossal uses ZKboo and ZKboo++ as their basis. I can see how the ZKPoK works, where the witness x is some key ...
2
votes
1answer
90 views

Pedersen commitments in bulletproofs

In Bulletproofs range proof, Pedersen commitments look like $C=aG+bH$ If I need to proof several values' range proof and keep G as constant, do I need to change H everytime? I have found it doesn't ...
1
vote
0answers
30 views

Zero Knowledge Proof of Association

Assuming there are a group of individuals with static ecdsa keypairs, of which the public keys are in a shared database that all of them have access to, how can each participant publish an ephemeral ...
3
votes
1answer
52 views

Are multi move proof protocols still “sigma protocols”?

Conventionally, sigma protocols are defined as being a three-move protocol (1. commit, 2. challenge, 3. response). Reading papers like "Bulletproofs" (Bunz, Bootle, Boneh et al., 2018), it feels like ...
1
vote
1answer
102 views

Simulator in Zero Knowledge Proofs

I'm reading about Zero-Knowledge-Proofs, in particular the argument of building a Simulator in order to prove the zero-knowledge property. As expected, there's something that doesn't click yet. Since ...
4
votes
1answer
135 views

Could Diffie-Hellman protocol serve as a zero-knowledge proof of knowledge of discrete logarithm?

The Schnorr identification protocol is widely recognized as the simplest ZKPoK of the discrete logarithm (more clearly, Honest-Verifier ZKPoK). However, I can't figure out why this simple protocol, ...
3
votes
0answers
72 views

Doubt in computing $g^\frac{1}{\delta+x}$ where $x \in \mathbb{Z}$

I was going through Zero Knowledge Set Membership and came across the following: Given $x \in \mathbb{Z}$ and $g$ is the generator of a multiplicative group $\mathbb{G}$ how do we compute $g^\frac{1}{...
0
votes
0answers
26 views

Simulator in the ideal world computes the proof for parties for $F_{NIZK}$

In the definition of $F_{NIZK}$ in [GOS06b], on receiving prove from a party, the functionality forwards the statement to the ideal world adversary $S$. This ideal world adversary then creates a ...
1
vote
1answer
200 views

Simulation based proofs, what am I missing?

In the example given by in the top answer of Simulation based proofs: Simple examples claims that this is insecure the semi-honest, and I need assistance in where I am failing to reason why that this ...
0
votes
1answer
57 views

Searching for a dining cryptographers problem variant

When I frist read about the famous dining cryptographers problem, in a book years ago I remember the author made a twist on it, demonstrating the generalization of the problem. Basically the dining ...
1
vote
1answer
90 views

Proof of correctness of an ElGamal encryption given a specific public key

Suppose Alice sends an ElGamal encryption of a value $v$ to Bob (using either the normal or exponential version of ElGamal). E.g. assuming publicly-known $pk_{BOB} = h$ and a generator $g$, Alice ...
2
votes
1answer
62 views

Share secret non-interactively in a verifiable way

In an application, I need to share a secret (random number) with a Group of known receivers over a public channel (a Blockchain) but each receiver needs to be able to check that the others received ...
3
votes
1answer
62 views

Bulletproofs range proof of value provided from trusted third party

I'm really interested in range proofs, and bulletproof seems to be the most effective range proof. I saw an example of usage of bulletproofs range proof: You can generate a proof that your age is ...