Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

3
votes
1answer
87 views

Zero Knowledge and Computational Indistinguishability

Having some trouble understanding the following line: “Alice conveys zero knowledge to Bob if Bob can sample from a distribution of messages that is computationally indistinguishable from the ...
0
votes
0answers
18 views

Fiat-Shamir identification protocol how work with prpoabilty for following case study?

Consider a Fiat-Shamir identification protocol run between a prover and a verifier. To start, the prover selects a secret s(1 ≤ s ≤ n) co-prime to a RSA like modulus n, and computes v = s^2 mod n and ...
0
votes
2answers
88 views

How to compute secure sum using secure multparty computation?

Suppose there are three voters $P$, $Q$ and $R$, and each will vote only on one candidate out of $X$, $Y$ or $Z$, with a 6 bit vote vector corresponding to $X $, $Y$ and $Z$ respectively (with 2 bits ...
1
vote
0answers
27 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 ...
0
votes
0answers
17 views

Are the cryptographic primitives of ZKPs more closely related to an encryption scheme or to a DSA?

I've read about how the Fiat-Shamir heuristic has been used to construct Non-Interactive Zero Knowledge Proof systems, Schnorr signatures, and encryption schemes. From my understanding, the ...
5
votes
1answer
71 views

How is ZKPP better than signing nonces?

I am trying to understand the use case for zero knowledge password proofs. Clearly, it is not ideal for a remote server to store a password hash. Then I need to upload the password to the server for ...
5
votes
0answers
65 views

True/False if a user is a customer without revealing the actual customer

I have a user A and a third party company B. I want to check if A is a customer of B. B cannot reveal any information about their customer list to me. If A is a customer of B, I do not want B to ...
2
votes
1answer
53 views

What is the relationship between a NIZK protocol and a digital signature scheme?

I am reading about the Fiat-Shamir heuristic to take a $\Sigma$-protocol into a non-interactive zero-knowledge proof (NIZK). I am now wondering whether there is a relationship between a NIZK proof and ...
1
vote
0answers
28 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
1answer
62 views

Implementing a zero-knowledge proof [duplicate]

I'm trying to get my head around zero-knowledge proofs and my definition of a zero-knowledge proof is as follows. A zero-knowledge proof is a method by which one party can prove to another party ...
1
vote
0answers
40 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
1answer
61 views

Check if $a<b$ in a trustless scenario

Let's say Alice has access only to a value $a$ and Bob has access to both $a$ and $b$. I need ...
2
votes
1answer
56 views

Is a zk-SNARK the hash of a Linear Interactive Proof?

zk-SNARK researcher Eran Tromer came up with the following workflow when describing how these proofs are created: What I am struggling to understand is how a LIP becomes a zk-SNARK. Is the SNARK a ...
6
votes
2answers
125 views

Practical consequences of a honest-verifier zero-knowledge of the Schnorr protocol

Schnorr protocol is known to be honest-verifier zero-knowledge and not perfectly zero-knowledge. What are the practical consequences of this fact? Does it mean a dishonest verifier can do something ...
3
votes
1answer
64 views

Zero-knowledge proof of knowledge without replay

Given a hash function: $H(x)$ = y $y$ is publicly known. Alice wants to prove to Bob that she knows $x$. ...
2
votes
1answer
82 views

Zero knowledge proof of the sum of two values

Given $v \in Z$, a prover knows $v$ and the verifier knows an encryption of $v$. The prover provides the verifier with the encryptions of two values $m$ and $n$ How can the verifier verify that $m+n=...
2
votes
1answer
45 views

Bitwise operation on secret values revealing the result only to the participants

Given the following situation, what sort of cryptographic construction am I looking for? Alice has a bitfield (vector, polynomial representation, etc.) Bob has a different bitfield of the same length ...
4
votes
0answers
65 views

Zero knowledge proof for a discrete logarithm

Say a have a group $G$ chosen as $Z_N^*$ where $N=pq$ and both $p$ and $q$ are safe primes. The algorithm for discrete logarithm is as follows: Pick $g$ as a random element from $Z_N^*$ Pick $x$ as a ...
2
votes
1answer
60 views

Expected Polynomial time Simulator in Interactive ZKP

I was reading the Zero knowledge property for Interactive Proofs. It said that for the proof to be zero knowledge, there should exist a simulator that runs in expected polynomial time for all ...
1
vote
0answers
42 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}$?
2
votes
0answers
31 views

ZK-proof of usage in a seed of CSPRNG

Assume a Player chooses a seed $s$ and he wants to prove that he uses it as a seed to CSPRNG function, where the seed is not public. How can he prove it? Thanks.
0
votes
1answer
59 views

Zero-Knowledge Bingo

Bingo is the game of chance where each player matches the numbers on their card with the numbers that the caller draws at random. When the first player has collected enough called numbers on their ...
3
votes
1answer
73 views

How can an interactive ZKP become non-interactive?

From my understanding, random oracles (hash functions) are used in the Fiat-Shamir heuristic to generate non-interactive ZKPs. I think I have a good grasp of how interactive ZKPs in this scheme work, ...
1
vote
1answer
44 views

Searching for a zero knowledge proofs

I don't exactly know what I'm searching for but the scenario is at follows. Alice and Bob want to get married. According to the law, they have to make a set of medical investigations. Bob must show ...
2
votes
3answers
108 views

Non interactive zero knowledge proof with common reference string

I would like to have some explanations about Non Interactive Zero Knowledge Proof. I saw with an example how to use the Fiat-Shamir transformation on Schnorr identification scheme to get a NIZK and I ...
1
vote
3answers
68 views

How to ask for an Identity confirmation without revealing

Let us say Alice has a list of public keys of her contacts. Bob wants to contact Ted and Bob has public key of Ted. Now, Is it possible to confirm that Alice has the same public key, without ...
2
votes
1answer
75 views

Zero-knowledge-proofs on committed value

Assume user $A$ with corresponding public-private keys $(pk,sk)$ and a public information $r_1$ and $r_2$. Let $r_{1s} = Sign(sk, r_1)$ be the signature on $r_1$ generated using $sk$ and $c = Hash(...
1
vote
1answer
58 views

Limiting how many key pairs someone can generate without compromising their keys

Is there any way to assign someone a limited quota for how many cryptographic key pairs they can generate (ECC, RSA, any algorithm), and preferably non-interactively? By non-interactively I mean there ...
0
votes
0answers
24 views

Zero knowledge proof that a file d is stored at a point in time t, measured from blockhash

The host (server) stores a file, and submits a zero knowledge proof that they stored the file at a specific point in time. Is that possible, what would it look like?
1
vote
0answers
31 views

Non interactive Zero Knowledge Proof for Satisfiability of Pairing Product Equations

In the paper "Simulation-Sound NIZK Proofs for a Practical Language and Constant Size Group Signatures" from Groth, the section 6 describes a NIZK proof for pairing product equations. I only know ...
0
votes
0answers
37 views

Calculating private key from a chosen public key for Feige-Fiat-Shamir scheme

Motivation: This paper suggest calculating the private like so: *Precalculation: An arbitrator generates a random modulus $n$ (512-1024 bits) which is the product of two large primes.The arbitrator ...
2
votes
1answer
109 views

Zero-knowledge proofs in blockchain

I would like to know if I am understanding this correctly. Zero-knowledge proofs need a prover, verifier and witness. So if we have a blockchain where person A pays person B 100 dollars. In ...
1
vote
0answers
41 views

Necessity of the random number at Fiat-Shamir heuristic

Wikipedia article of Fiat-Shamir Heuristic goes like this: Alice wants to prove that she knows $x$: the discrete logarithm of $y=g^{x}$ to the base $g. She picks a random $v$ in $Z_q^*$ and computes $...
0
votes
1answer
68 views

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

I am trying to understand how zkSNARKs work. Going through this article by Vitalik - https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649 In the section on "...
0
votes
1answer
37 views

Why do a pair of interactive machines have a common input?

I know that an interactive proof system $(P,V)$ is a pair of interactive machines for a language $L$ if $V$ is polynomial-time and the following two conditions hold: 1) Completeness: For every $x \in ...
7
votes
0answers
91 views

Proving multiple products “in the exponent”

I'm trying to come up with a small-sized (non-interactive) proof for a Diffie-Hellman-like statement. I'll start by giving an example. The prover has $g^a, g^b, g^c, g^{ac}, g^{ab}, g^{bc}, g^{abc}$. ...
2
votes
1answer
51 views

Why Bulletproofs protocol needs to raise $u$ to power $x$ in Protocol 1?

The paper on the Bulletproofs Zero-Knowledge proof protocol states in paragraph 3: In Protocol 1 the element $u$ is raised to a verifier chosen power $x$ to ensure that the extracted vectors $a, b$ ...
5
votes
2answers
98 views

Socialist Millionaires variant, where only one party learns $x=y$?

In the Socialist Millionaires protocol, Alice selcts some $x$ and Bob selects some $y$, and both parties learn whether or not $x=y$ without learning the other party's selected value. However, on a ...
1
vote
1answer
50 views

How are Zero-Knowledge Proof protocols designed?

There are some classic ZKP examples out there (the alibaba cave, the colored balls, etc. See the Wikipedia page for details) To me it looks like these protocols were invented "ad-hoc". That is, ...
1
vote
0answers
31 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
38 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? ...
6
votes
1answer
116 views

Can Zk-SNARKs verify the results of turing-complete computations?

My understanding is that Zk-SNARKs (and zero-knowledge proofs in general) can be used to prove that a polynomial-time computation has a certain output, while keeping one or more of the inputs to that ...
0
votes
0answers
44 views

zk-SNARKs: Possible to deduce circuit/statement from verification key and proof?

Suppose Carol generated proving and verification key pk and vk (discarding $\lambda$) for some circuit $C$. If Alice then used pk to generate a proof $\pi$ for some witness $w$ then it is clear from ...
1
vote
2answers
162 views

Using two elliptic curves to do a range proof

Suppose Alice holds a secret value $a$ to which she has publicly committed to using two elliptic curves of distinct order. The curves are $g$ and $g'$ of orders $q$ and $q'$ (with $q < q'$) and ...
2
votes
0answers
24 views

Avoiding multiple use of sIgned identities while not learning anything about them

There is an authority A with an associated public/private key pair (A.priv, A.pub). A can issue new "identities" by signing data (numbers or bytestrings). Each number associated with a signature by A ...
1
vote
1answer
125 views

Zero-knowledge transfer of value protocol II [closed]

This is an improvement of the protocol described here. The protocol does not require trusted setup and is very efficient (much more efficient than anything else I could find). The protocol allows the ...
2
votes
1answer
190 views

Sigma protocol for AND-composition involving the same secret

Say we have two public cyclic groups $G_1$, $G_2$ of corresponding prime orders $p_1$, $p_2$, and known generators $g_1$, $g_2$. Say $g_3$ is also a generator of $G_2$. For publicly known $C_1$ and $...
1
vote
0answers
60 views

What's the difference between non-interactive zero knowledge proof of knowledge and proof of membership?

I'm trying to study the difference between non-interactive zero knowledge (NIZK) proof of knowledge and proof of membership. I have known that in NIZK proof of knowledge the prover wants to convince ...
2
votes
1answer
66 views

NIZKs for hash functions

Hash functions such as SHA are considered as non-algebraic statements. How can one construct a NIZK proof to show that the output of a hash is computed correctly in an efficient manner.
2
votes
1answer
99 views

Is there any way to prove two numbers that are equal after Paillier encryptions?

I have two numbers $x_1$ and $x_2$, and there are two Paillier homomorphic encryption (public, private) key pairs $(p_1,r_1)$ and $(p_2, r_2)$. I only know $p_1, r_1$ and $p_2$. Suppose $C_1=E_{p_1}(...