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
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

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.

2
votes
2answers
54 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
1answer
33 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
63 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
39 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 ...
-1
votes
0answers
51 views

How to hide Public Keys?

I was just wondering since the main advantage of blockchain is its decentralised nature and inherent anonymity, what is a way in which one could hide a public key. I was thinking of either using a ...
0
votes
0answers
19 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
16 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
28 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
64 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
33 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
45 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
32 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 ...
6
votes
0answers
78 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
44 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
76 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
45 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
30 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
31 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? ...
5
votes
0answers
69 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
39 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 ...
0
votes
2answers
125 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
22 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
108 views

Zero-knowledge transfer of value protocol II

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
156 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
49 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
49 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
90 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}(...
5
votes
1answer
81 views

Extractability for Simulator in Malicious Model

It is sometimes required while proving the security of a protocol in the malicious setting that the simulator is able to extract the witness set of the adversary, who tends to be the prover of ...
2
votes
1answer
58 views

Is the following protocol perfect zero knowledge or computational zero knowledge?

So I have this protocol for the hamiltonian cycle: repeat t times: Peggy chooses a random permutation $\pi$ on $V$, and computes $G_1=\pi(G)$ For each of the $\frac{|V|(|V|-1)}{2}$ possible edges of ...
1
vote
1answer
62 views

Is there any additively homomorphic schemes that can make range proof?

I want to know whether there is any additively homomorphic schemes that can make a non-interactive range proof. For example, I have a pair of public and private key pairs $(K_p,K_v)$ that satisfying ...
-1
votes
1answer
293 views

Underflow-resistant zero-knowledge proof of addition

I am looking or an efficient way to prove addition of two integers in zero-knowledge. Specifically: Alice holds a secret value $a$ to which she's publicly committed to by publishing $A = C(a)$, where ...
1
vote
1answer
139 views

Zero-knowledge integer comparison

This question is a follow up to the question I asked here. Basically, the protocol I described has a flaw (as pointed out in this answer), and I am trying to figure out how to address it. The setup ...
3
votes
3answers
253 views

Zero-knowledge transfer of value protocol inspired by EC El Gamal

This is a follow up on the question I asked here. I designed a scheme that allows the following: Alice has a value $a$ which she wants to keep secret Bob has a value $b$ which he wants to keep secret ...
2
votes
1answer
71 views

Advantages of group signature schemes without encryption over with encryption

Many group signature schemes follow sign-encrypt then prove paradigm, where a membership certificate, is encrypted using some public-key encryption scheme. There are some encryption free group ...
1
vote
1answer
97 views

Commutative homomorphic encryption for zero-knowledge transfers

I am trying to design a scheme that would allow the following: Alice has a number $a$ which she wants to keep secret Bob has a number $b$ which he wants to keep secret Alice can "transfer" a number ...
1
vote
1answer
80 views

How can I construct a proof that the decryption of a certain encrypted file matches a hash?

Let's say Alice has file $F$ and she generates key $K$. She widely publishes the $hash(F)$ for identification. She wants to sell the file to Bob. She encrypts the file with $K$ and sends both $E_f = E(...
0
votes
1answer
67 views

What is the difference between 'completeness' and 'soundness' in ZKP?

I'm reading Matthew Green's great blog, especially the Zero Knowledge Proofs: An illustrated primer post and I'm wondering what is the difference between completeness and soundness? In the post, ...
0
votes
1answer
55 views

Zero knowledge proof for a double discrete log

I would appreciate some help with the following: Let $v = a^c$ and $c = g^s h^r$, where $g$ and $h$ are generators. Is there an "easy way" to prove knowledge of $a, c, s, r$ that satisfy the ...
0
votes
0answers
52 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 ...
3
votes
1answer
68 views

Trouble understanding the correctness of this Zero-Knowledge proof of posession of a discrete log

I came across the following protocol for a "Zero-Knowledge Proof of a Discrete Logarithm" in Bruce Schneier's Applied Cryptography (second edition) book. I simply cannot prove to myself that this ...
2
votes
1answer
90 views

How to prove I know an x without revealing x or f(x)?

Suppose a set of $u_1, u_2, ..., u_N$ users each knows an associated secret $x_1, x_2, ..., x_N$ they do not wish to reveal. We have a public $f(x)$ such as the discrete logarithm $f(x)=g^x\,\mathrm{...
0
votes
0answers
82 views

How trapdoor key exposure affects security of trapdoor-based simulatable NIZKs?

I wonder if revealing a trapdoor key would help the verifier to distinguish real and fake proofs in NIZKs that are based on substituting the challenge with the result of a chameleon hash. I don't ...
0
votes
1answer
62 views

Groth-Sahai proofs and the hidden-bits model

In the Groth-Sahai proof system, the authors mention (section 1.2) that one of the reasons behind the inefficiency of previous NIZK proof systems is their reliance on the hidden-bits model. Then, they ...
0
votes
1answer
58 views

Sigma protocol ZK-proof of a pair of pedersen commitments

Let's say you are using a $\Sigma$ protocol ZK proof to prove knowledge of $x_1, x_2$ so that $Y = g_1^{x_1}g_2^{x_2}$. Of course $g_1$, $g_2$ are generators within cyclic group G of prime order q, ...
1
vote
0answers
31 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
40 views

Difference between special honest verifier zero-knowledge and zero-knowledge property

Special honest verifier zero-knowledge and zero-knowledge property is defined as follows: Special honest verifier zero-knowledge(SHVZK):There exists a polynomial-time simulator M, which on input x ...
1
vote
1answer
45 views

Why is computational zero knowledge the most generic notion of zero knowledge?

GMR88 (Goldwasser, Micali, Rackoff) in chapter 3 mentions that computational zero knowledge, in comparison to statistical or perfect zero knowledge is the most general amongst the three definitions. ...
0
votes
1answer
36 views

Disjunction of several instances of sigma protocol

Assume there exists zero-knowledge interactive protocol for a language $L \in NP$ i.e., if an instance $x \in L$ then prover can convince the verifier, that $x \in L$ with high probability without any ...
1
vote
1answer
63 views

What hash functions can be (efficiently) computed over GF(2^m)?

Given an arithmetic circuit over a finite field of characteristic 2, what families of cryptographic hash functions can be efficiently computed with this circuit? Can standard hash functions be ...
3
votes
1answer
90 views

Complexity of Boudot's zero-knowledge range proof scheme

According to Camenisch et al. in Efficient Protocols for Set Membership and Range Proofs (see Section 1.2), the range proofs devised by Boudot in Effcient Proofs that a Committed Number Lies in an ...