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
23 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:...
0
votes
0answers
71 views

Equality of discrete logarithms

I'm currently trying to prove equality of discrete logarithms for an assignment. I understand the simple proof of $\log_g (g^r)=\log_h(h^r)$ which is pretty straight forward: $x = g^r$ $y = h^r$ $...
1
vote
0answers
35 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
37 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
33 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
110 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
48 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
52 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
59 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
30 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
45 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
102 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
52 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
30 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
79 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
39 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
66 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
157 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
43 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 ...
2
votes
1answer
46 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
98 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
54 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
vote
1answer
43 views

Impact of super-polynomial extractors on the security of a zero-knowledge proof

Interactive zero-knowledge arguments are proven to be secure in three parts: completeness (the verifier accepts if the prover is honest) soundness (a dishonest prover cannot convince a verifier) zero-...
0
votes
0answers
37 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 ...
1
vote
1answer
81 views

Proving I can solve an equation without disclosing the solution (zero-knowledge proof)

Given a (potentially multivariable) equation $f(x)=0$, Peggy wants to prove to Victor that she knows a solution $x^\star$ to it without actually disclosing anything information about the value of $x^\...
0
votes
1answer
47 views

Difference between a Polynomial Opening & a Polynomial Commitment

Going through the literature led me to think I understood the difference between these two things, but thinking about I am not actually certain. Could you help me correct my definitions of these two ...
0
votes
1answer
41 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 ...
1
vote
0answers
70 views

Efficiently prove the correctness of Paillier encryption in or “outside” a zk-SNARK

I'm working with a zk-SNARK library [1] that allows me to prove the correctness of arbitrary arithmetic circuits, and I now want to use these zk-SNARKs to prove that some Paillier [2] ciphertext $c$ ...
2
votes
1answer
65 views

How to construct a strong Fiat-Shamir in zero-knowledge proof?

I'm new to zero-knowledge proof. Recently, I'm implementing a non-interactive zero-knowledge proof using the Schnorr scheme. I understand the non-interactive zero-knowledge proof needs random oracle ...
2
votes
1answer
39 views

What language classes beyond NP allow constant-round zero-knowledge proofs?

While discussing proving a language in $\Sigma_2$ from a client to a server with a friend we realized that while we know that such a language is provable in zero-knowledge, we didn't know whether it ...
0
votes
1answer
50 views

Is this zero knowledge protocol for honest verifiers?

Assume the zero knowledge protocol where the prover knows a $x$ such that: $g^x = h \pmod{p}$. The prover chooses a random $t \in \mathbb{Z}^*_m$ and sends $y = g^t \pmod{p}$ The verifier sends ...
0
votes
0answers
28 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
62 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.. ...
1
vote
1answer
91 views

What is the difference between zk-SNARK and NIZK?

I am not exactly sure what is the difference between zk-SNARK and NIZK? Are NIZK not succinct? If so, why Pinocchio protocol considered itself a NIZK although they have succinct proof? I tried Google ...
0
votes
0answers
55 views

Prove that I know string that hash to h [duplicate]

Lets say p = str and h = SHA512(p) i send the h which is the SHA512 of ...
0
votes
2answers
105 views

Proof that a particular algorithm has been used

I’m looking for the existence (or the proof of non-existance) of a method to prove (with arbitrary certainty) that a particular output is the result of a particular algorithm applied on a particular ...
0
votes
0answers
34 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 ...
4
votes
1answer
82 views

How to construct a circuit in zkSNARK

I have a few questions about how to use zk-snark. Since the basic logic of using zk-snark is: using a circuit to represent a problem, generate an R1CS from the circuit, transform R1CS to QAP and then ...
0
votes
3answers
73 views

The challenge c in Sigma protocol (using Fiat Shamir)

As is known to all, the following picture depicts a sigma protocol, and to eliminate the interactivity, Prover can generate c by hashing (t, y) using Fiat Shamir transform. My question is: 1). Can c ...
1
vote
1answer
64 views

Show that there is an efficient zero knowledge proof for any language $L \in NP$

Let $(P,V)$ be an efficient zero-knowledge interactive proof for some language $A \in NP$ that is $(T,\epsilon)-\text{sound}$ and $(T,\epsilon)-\text{ZK}$. I want to show that for every language $L$ ...
0
votes
0answers
25 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
1answer
68 views

Finding a winner in mental poker game

In a mental poker game I am designing as an learning exercise, (One used in example is a 3 card flash with no desk cards) suppose I have a set of cards and other person also has a set of cards. each ...
1
vote
0answers
65 views

How does one go about implementing a range proof?

I've attempted to find a solution to this problem, but for the life of me I am unable to. I am attempting to solve whether a point an elliptic curve of prime order is between 2 points, given a ...
4
votes
3answers
319 views

Difference between Zero Knowledge Proof and Challenge Response Protocol

What exactly is the difference between Zero Knowledge Proof & Challenge Response Authentication? I searched online and the best I could find are these: techtarget.com Zero-knowledge password ...
1
vote
0answers
29 views

How to prove to recipient that we are using public parameters correctly in lattice IBE

Many lattice IBE scheme follow the scheme outlined in ABB10. In ABB10, the ciphertext is $c_0 = u^\top s + x$, where $u$ is a public parameter. (No consider message here.) I want to ask: Is it ...
2
votes
3answers
96 views

Reason for squaring and not arbitrary exponentiation in Wesolowski and Pietrzak verifiable delay functions (VDFs)

I'm working at understanding the Wesolowski and Pietrzak RSA group based VDFs (verifiable delay functions). These basically work by requiring the prover to do a bunch of repeated squaring within a ...
0
votes
0answers
31 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 ...
0
votes
0answers
103 views

Non-interactive zero-knowledge proof system for a language undecidable in polynomial time

I am studying through some material in an online course, and there is an exercise which I could not figure out. The problem is this: Let $L$ be a language that is not decidable in polynomial time (...
0
votes
0answers
21 views

Zero knowledge proof of symmetric keys and encrypted texts resulting in the same text, if the symmetric keys are encrypted with asymmetric ones

Suppose I have: text T, symmetric keys X, Y encrypted text T with symmetric keys X, Y = TX, TY accordingly asymmetric key Z, used to encrypt X, Y to transmit them to a person. Let the encrypted ...
5
votes
0answers
69 views

Understanding anonymous credentials. Does someone understand how it works?

After reading a series of papers CL01 CL02 CL04, I feel like I understand the intuition behind the anonymous credential framework but I don't understand some details the mathematics behind it. I ...

1
2 3 4 5
14