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.

179 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1
vote
0answers
198 views

Rewinding Argument and Forking lemma

In Dan Boneh's crypto book, there is a section describing the "Rewinding Lemma", however I cannot find it explained in other sources on the internet. How does this differ from the forking lemma?
1
vote
0answers
92 views

Could you design something like a ring signature that uses website accounts instead of keys?

Ring signatures allow one to prove that you own a private key corresponding to a public key from a set of keys, without revealing which private key you control. This is useful if you are part of some ...
1
vote
0answers
110 views

Simulatability of Diffie-Hellman Key Exchange

While reading through Shoup's paper on provably secure Diffie-Hellman key exchange (DHKE), I do not understand something rather simple. There are two parties $A$ and $B$. $A$ starts by sending $g^a$, ...
1
vote
0answers
80 views

Extractability property in Zero Knowledge Discrete Log problems

I am trying to construct a simulator and an extractor for a zero knowledge protocol. I just encountered this text that explains the construction of the simulator. Does someone know of a similar text ...
1
vote
0answers
62 views

Why isn't a range proof calculated using size?

For example a Pedersen commitment for an elliptic curve of maximum $2^{64}$, requires every number between $0 \to 2^{64}$ to be checked. Why do range proofs, in the case of a Pedersen commitment, not ...
1
vote
0answers
117 views

Drawbacks of Schnorr Authentication that require Fiat-Shamir and Random Oracles?

I've been going through G. Maxwell's paper on the Borromean Ring Signature, and I don't fully understand this part on Schnorr Signature. If some could explain it more intuitively thank you. "...
1
vote
0answers
51 views

Preserving location privacy

What are cryptographic techniques that could be used so that if I wanna to enable a server to send message to certain nodes in a network with preserving the privacy location for them ??
1
vote
0answers
231 views

zkSNARK and definition of Quadratic Span Program

In zkSNARKs in a Nutshell, page 12, what exactly are $I_{free}$ and $V_{free}$? Why do we have $V_{free}$ but not $W_{free}$?
1
vote
1answer
237 views

Why are logic gates assigned integers when checking QAP in zkSNARK algo?

I am trying to understand how zkSNARKs work. Going through this article by Vitalik, in the section on 'Checking the QAP' he says " If the resulting polynomial, evaluated at every x coordinate ...
1
vote
0answers
44 views

Verifier choose a random challenge to send to prover

Could anyone explain me why the verifier in Honest verifier zero-knowledge Simulator, has to choose a random challenge to send to prover? I have not understood well. Thank you in advance.
1
vote
0answers
108 views

Sigma protocol compiler?

Is there a well maintained, preferably documented, Sigma protocols compiler library? i.e. takes an abstraction of statements to prove, and outputs a cryptographic protocol between verifier and prover? ...
1
vote
0answers
121 views

ZK proof of committed value

I'm looking for a scheme that a prover can commit to a value $d$, via a commitment $C$, while also provide ZK-proof that this value $d$, together with a public key $e$, are RSA pairs. (i.e private and ...
1
vote
0answers
86 views

Explaining Low-Degree Extension in layman terms

I am trying to learn the sumcheck protocol used in different interactive zero knowledge proof systems, however I can't move forward due to my little understanding of Low-Degree Extension (see Chapter ...
1
vote
0answers
44 views

Constructing a number different than x without revealing x

My question is not really about ZKP but is related to the socialist millionaire problem where A and B can check that their message x and y are different without revealing them. I would actually be ...
1
vote
0answers
101 views

Zero Knowledge Proof

In the following protocol $(P,V)$, prover $P$ and verifier $V $have common input $(N,X) \epsilon QR$ while the prover also has private input $x \epsilon SR(N,X)$. Let $SR(N,X) = \{x \epsilon$ $Z_{n}^{*...
1
vote
0answers
127 views

Methods for converting from HVZKP to ZKP: Precommitting the Initial Communication

In my studies, I have seen two common ways that an Honest Verifier Zero Knowledge Proof can be converted to a Zero Knowledge Proof. Either make the proof non-interactive with Fiat-Shamir's Heuristic (...
1
vote
0answers
308 views

For the discrete log zero-knowledge proof, can all challenges be done at once?

Section 2 of this paper (page 5 in the PDF) gives a protocol for a zero-knowledge proof to prove Alice has $x$ for $y = a^x \mod p$ to Bob without revealing the value of $x$. The protocol is as ...
1
vote
0answers
178 views

Whcih one is computationally more expensive: Zero knowledge proof or cut-and-choose

As we know, in order to have multi-party protocol secure against the malicious parties, researchers usually utilise the standard techniques such as zero-knowledge proofs or cut-and-choose technique. ...
1
vote
0answers
111 views

Can zk-snark proof generation be parallelised across multiple parties in a trustless manner

Can multiple parties using the same snark protocol, the same verification strings, inputs etc, generate separate proofs and then combine the proof strings somehow to get a proof of the desired ...
1
vote
0answers
266 views

Simulation-Based Proof: When a Secret Key is Involved

Assume we have a protocol in which a party receives an encrypted random polynomial. The polynomial is encrypted using his public key. We want to construct a simulator for this party (so this party ...
1
vote
0answers
127 views

Non-interactive zero-knowledge proof for discrete logarithm without random oracle

Is there any non-interactive zero-knowledge proof for discrete logarithm without random oracle over the group $\mathbb Z_p$?
1
vote
0answers
67 views

Commitment scheme to share money

I have such problem: party $X$ has an amount of money $M$, which it needs to share with $n$ other parties. Every week the amount of money is different. Let say not, that I am a party A, which is one ...
1
vote
0answers
708 views

Zero Knowledge Non Interactive Proof with random oracle

I am trying to write an assay about Non Interactive Zero-Knowledge proofs and would like to take the simple discrete logarithm problem example fallowing the Feige-Fiat-Shamir heuristics. I understand ...
1
vote
0answers
102 views

Is there a way to "shorten" a Merkle chain?

If I have a Merkle chain of 3 items, is it possible to create a zero knowledge proof of the existance of a correct chain between hash 1 and hash 3? Editing to clarify (Thanks Ricky), what I mean my a ...
1
vote
0answers
210 views

What would make it impossible to deny that decryption of a package has taken place?

I'm part of a team designing a system where a user have to be able to read a certain package, if he has preformed an action or series of actions that makes it legal for him to do so. The tricky part ...
1
vote
2answers
306 views

ZKP: Asymmetric encryption with confidential message and known hash

I'm searching for a ZKP package that supports asymmetric encryption so I can implement the following scenario: Carol encrypts message $m$ with Alice's public key and sends the ciphertext to Alice. ...
0
votes
0answers
19 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 ...
0
votes
0answers
20 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
58 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 ...
0
votes
1answer
89 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, ...
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$...
0
votes
0answers
39 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 ...
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 ...
0
votes
1answer
65 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 ...
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
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
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
78 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
1answer
100 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 ...
0
votes
0answers
80 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 ...
0
votes
0answers
48 views

Is there any application for ZKP that prove that "I know the pre-image of Hash function"

I'm looking for any applications that using ZKP to prove that "I know the pre-image for Hash function". As far as I know, POUR operation in Zcash uses this concept but I can't find any ...
0
votes
1answer
66 views

How to prove identity in this peculiar case

Lets say Alice wrote a book under the name Alyssa. The only other person who has read the book is Bob. Bob then publishes the same book but under the name Bobby. Is there a way for Alice to prove that ...
0
votes
0answers
31 views

Is there a secure way of allowing users of my app to selectively share data from an external service?

Is there a secure way of allowing users of my app to selectively share data from an external service with my app? In order for the users of my app to get their personal data from the external service ...
0
votes
0answers
64 views

Why in the Fiat-Shamir heuristc for proving the knowledge of a discrete logarithm an hard to invert function has to be used to create the challenge?

Consider this example from Camenisch, J., & Stadler, M. (1997). Proof systems for general statements about discrete logarithms. Technical Report/ETH Zurich, Department of Computer Science, 260.. ...
0
votes
0answers
47 views

Constructing efficient zero knowledge proof card game

I had asked an unanswered question earlier and now, I think I have an answer (sort of), not really but I think I know where to look for it. We assign each type of card combination a score such that a ...
0
votes
0answers
28 views

Whether the proof created by prover can be tampered in zero knowledge proofs?

I am studying zokrates recently. I know that the prover will finally generate a proof, and then the verifier can use this proof and public input as input to verify whether the prover has certain ...
0
votes
0answers
39 views

How to construct inequality, padding, and truncation in R1CS?

I'm trying to reimplement the zkSNARKs used in zcash using the libsnark library. It involves checking for inequality, and bit manipulation such as padding and truncation. How do I implement those in ...