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.
1,014
questions
0
votes
0
answers
64
views
MPC model used in Ligero and Limbo
Ligero (https://dl.acm.org/doi/10.1145/3133956.3134104) and Limbo (https://eprint.iacr.org/2021/215.pdf) use a somewhat unique MPC model for their zk-PCP where not all parties communicate with each ...
- 1,365
0
votes
1
answer
54
views
Transforming a encryption of binary representation of a number to an encryption of vector representation
Suppose Alice chooses a number $n\in Z_q$ and decompose it to its binary representation $b_0,b_1,...,b_d$. Then Alice encrypts these bits (can be any encryption scheme). Is it possible for Bob (who ...
- 79
1
vote
0
answers
35
views
How does Diogenes prove equivalence of discreet logs despite the candidates not being composed of safe primes
In the paper describing a protocol for distributed RSA modulus generation, Diogenes, "[they] employ a special-purpose $\Sigma$-protocol based on [Sho00] for proving correctness of exponentiations ...
- 498
3
votes
0
answers
143
views
Proving equivalence of discrete logarithms over a modulus of unknown factorization
A prover has a secret exponent $x$, two public bases $g$ and $h$, and a public RSA modulus $N$ of which no party knows the totient/factors. All inputs other than $N$ are coprime with $N$ with ...
- 498
1
vote
0
answers
54
views
Verifiable computation examples where verification is much faster than re-execution
Verifiable computation (VC) has been practical since Pinocchio and the field has evolved significantly since.
What are some of the best examples today where computation is significantly faster than ...
- 155
1
vote
1
answer
394
views
What is about the Groth16's time complexity？
The Groth16 is the zero-knowledge proof scheme,I want know what is the time complexity of Groth16，including generate proof and verify proof.Thanks.
- 11
1
vote
0
answers
30
views
Any zero knowledge proof system for the Set Cover Problem?
Since the Set Cover Problem is an NP problem, Zero Knowledge System for Set Cover will definitely exist, but I cannot find such a proof system.
- 11
3
votes
3
answers
224
views
Is it possible to prove that an encrypted message was encrypted with some public key without divulging the plaintext or secret key?
I know this seems a bit contrived, but I’m a layperson to cryptographic systems and have been trying to think if it’s possible to devise a scheme where it’s possible for a sender to prove, in a public ...
- 141
1
vote
1
answer
242
views
Zero-knowledge proof that the exponents of a Pedersen commitment are not zero
Given a value $v = g^ah^b$, with $a,b$ secret, I was wondering whether there was a way to prove in zero knowledge that neither exponent is zero. In other words, given $v$ and $g,h \in \mathbb{G}$, I ...
- 23
2
votes
1
answer
73
views
Pinocchio protocol: Is this equation meaning polynomial's dot product or multiplication?
In Pinocchio paper, I'm confused by the equation in section 2.2.1. (image below)
Is the product of two polynomials $v_0(x)+\sum(cv(x))$ and $w_0(x)+\sum(c_w(x))$ of dot product or just a simple ...
- 23
0
votes
2
answers
100
views
Encryption algorithm where proving the decryption is equal to spoiling the key?
Is there an encryption algorithm or MAC algorithm for which NO zero-knowledge-proof exists, provably? I want people who want to prove that a ciphertext decrypts into some plaintext to have to spoil ...
- 125
2
votes
1
answer
192
views
How to understand this detail of a zkSNARK-protocol?
As a beginner in cryptography and zk-SNARKs, I am currently working through the paper "Why and How zk-SNARK Works".
There, I don't understand the last section at the bottom of page 15:
...
- 21
1
vote
1
answer
229
views
Proof of Zero Knowledge Groth16
I understand that in the non-interactive linear form (page 15 of Groth16: https://eprint.iacr.org/2016/260.pdf), given $A$ and $B$ in the proof $(A,B,C)$,
the simulator can compute the $C$ by:
$C =\...
- 89
4
votes
1
answer
403
views
Is RSA-signing zero knowledge?
Is RSA-signing a given challenge $x$ a zero-knowledge proof of holding the RSA private key, for the modern definition of zero-knowledge proof (which I don't know!)
Assume public and genuine RSA public ...
- 137k
1
vote
1
answer
186
views
Why is the SHA256 in libsnark so slow?
When I use the merkle proof example of libsnark, I find that it takes more time to calculate the merkle tree than to calculate the proof. As shown in the log below, it takes 0.04s to calculate a ...
- 23
7
votes
1
answer
2k
views
Did digital signatures come from Zero Knowledge Proofs?
I am reading the Real-World Cryptography book and in the chapter on signatures it says:
The best way to understand how signatures work in cryptography is to understand
where they come from. For this ...
- 484
1
vote
0
answers
54
views
Signature delegation without secret keys
Scenario: have an entity A that cannot hold any secret keys. A concrete example would be: an application that needs to be open sourced and cannot be modified. In order to send any signed messages, it ...
- 111
1
vote
1
answer
180
views
Schnorr based ZK scheme
TL;DR: This ABSOLUTELY does not work and presents a huge security risk. Posting it anyways in case there are other threats I missed or to dissuade any other person who comes up with this idea.
Hi! I’m ...
- 55
1
vote
1
answer
293
views
Σ-protocol that proves an even number was committed using Pedersen commitment scheme
I need to design a Σ-protocol ZKP using Pedersen commitment scheme that proves knowledge of a, y such that statement A = h^y * g^a only holds for even y (y=2x).
Of course, the protocol needs to be ...
- 13
2
votes
1
answer
263
views
Range proof for ElGamal ciphertext
Alice has an ElGamal public key $y=g^x$. Bob encrypts a value $g^b$ based on Alice's Elgamal public key and he ends up with a ciphertext $(g^by^r, g^r)$. Can Bob prove that the value $b$ is in some ...
1
vote
0
answers
44
views
Proving stategies for computational properties
As far as I understand, a property is computational if it holds in a computationally-bounded context, so for ANY computationally-bounded involved entity (even if an unbounded one could discover the ...
- 680
1
vote
0
answers
94
views
Can I prove that from a set of ciphertexts one is encrypting $g^0$ and the others are encrypting $g^b$ where $b$ is a negative value?
Consider for example this set of encrypted values under the Elgamal keys $y_0$,$y_1$,$y_2$: $$
Enc_{y0}(g^0),Enc_{y1}(g^{-20}),Enc_{y2}(g^{-10})
$$
Can I prove that one value is $g^0$ and the others ...
0
votes
0
answers
200
views
Can a circuit in a zk-SNARK be reversed-engineered?
The definition of zk-SNARK involves not leaking any information from the prover-verifier interaction, but what about leaking information from the circuit itself? e.g., could there be a circuit to ...
- 3
1
vote
0
answers
62
views
Should proving key be kept as a secret in NIZK?
Hi I am quite new to NIZK. I know a trusted party (Generator) generates proving key and verifying key and then distributes them to Prover and Verifier. Apparently, the verifying key can be seen as ...
- 31
1
vote
1
answer
491
views
Zero Knowledge proof of correct ElGamal encryption
Suppose for $sk = x$, $pk = g^x$ we encrypt message $m$ with ElGamal encryption as $(g^r,m\cdot pk^r)$. My goal is to prove that I performed the encryption correctly, i.e. that the same $r$ is used ...
- 294
5
votes
2
answers
339
views
Understanding the "rewinding argument"
I read through related questions on this SE, but I still do not understand why we can use the rewinding argument. Specifically, rewinding seems like a really strong superpower to me, and I don't ...
- 53
2
votes
1
answer
74
views
Authenticated Diffie-Hellman with no proofs that each one keys are the right keys. Is it possible?
Let's suppose that Bob has only Alice's IP and no more information about Alice's key, nor the digest of Alice's key.
They exchange keys and need proof that the received keys are the same keys that ...
- 867
0
votes
0
answers
83
views
How to prove knowledge of a secret and allow the receiver to deduplicate it?
Consider the following scenario:
We have two agents, A and B.
B needs to prove that they know a secret to A, without sharing the actual secret.
e.g.: A needs a way to de-duplicate the secrets they ...
1
vote
0
answers
199
views
Proving the range of a blinded value in a Pedersen commitment in zero knowledge
A prover has the following value:
$$C = (h^ag^x)^b$$
and he needs to prove in zero knowledge to a verifier that $x < t$, for some public threshold $t$.
The verifier knows $h$, $g$, $C$, and $t$. ...
- 23
1
vote
1
answer
619
views
Why are zk-STARK quantum secure?
I have a rough idea of how STARK work, but I want to know which part makes them quantum secure. Is it because when the prover generates the proof they use the random number from the Merkle root, which ...
- 11
1
vote
1
answer
72
views
Create an or-proof for a given list of elements with public input
Let $g\in G$ and $h\in H$ be two group generators. Given a list L of m group elements, where $L=(L_1,...,L_m)$, a prover wants to convince a public verifier (namely, a verifier who only has public ...
- 79
3
votes
1
answer
144
views
How to do a non-membership proof for a committed value?
Assume that the verifier is given three commitments $C_i=g^{m_i}h^{r_i}, i=1,2,3$. Now a prover knowing $m_i, r_i, i=1,2,3$ wants to prove $m_3\neq m_1\wedge m_3\neq m_2$. Specifically, the relation ...
- 777
4
votes
2
answers
751
views
Relation between Knowledge extractor and soundness in ZKPoK
Reading Why Zk-SNARKs are Argument of Knowledge if a Knowledge Extractor exists? I feel confused by OP first statement:
From what I know, proving the existance of a Knowledge Extractor implies ...
- 680
1
vote
1
answer
400
views
Chaum–Pedersen Protocol explanation for dummies. What I'm doing wrong?
The screenshot from a book with Chaum–Pedersen Protocol description is below.
I'm trying to implement it for my own. And I don't get math here.
My assumptions:
Discrete Logarythm functions:
The dot ...
4
votes
1
answer
2k
views
Chaum-Pedersen Protocol
I'm junior software developer and I need to implement a very simple authentication system based on Chaum-Pedersen ZKP Protocol.
I know nothing about cryptography and I ask you to help me understand ...
- 43
1
vote
0
answers
64
views
Detailed Proof of Knowledge for Discrete Log
I'm having difficulty finding a detailed proof for one of the most basic protocols in cryptography, that is the Schnorr protocol, or the sigma protocol for proving knowledge of a discrete log.
Most ...
- 357
2
votes
0
answers
129
views
IS there a way to do zk proof on string?
For example: "I am a very secret person".
I'd like to show someone that this string includes 'secret' without revealing the rest of the string. Is there anyway?
- 121
1
vote
0
answers
377
views
What is required to verify a zk-SNARK?
I am trying to verify a zk-SNARK from a solidity contract offline, in Rust.
This is the verifying contract that checks the proof in the solidity side.
And this is the transaction that carries the ...
- 111
0
votes
1
answer
102
views
Zero knowledge proof of integer factorization
If I have public element $W=K^r$, and $K=v^x$ should be kept secret where $v$ is a generator in $\mathbb G$, is there a way to produce a zero knowledge proof on x and r such that $W=v^{x \cdot r}$ ...
- 1
2
votes
1
answer
224
views
Zero Knowledge Proof: groth16. Can prover key be public?
Here is quote from gnark documenation.
Note that careful consideration must be given to this step in production environment. groth16.Setup uses some randomness to precompute the Proving and Verifying ...
- 123
2
votes
1
answer
184
views
What's the meaning of without loss of generality in cryptography? [closed]
What's the meaning of without loss of generality in the cryptography (Zero Knowledge Proof)?
Without loss of generality, suppose we want to check if a 1 = a 2 . In
the following description, j ∈ { 1, ...
- 215
2
votes
0
answers
120
views
How to extract witness from a non-interactive lattice-based proof?
I'm trying to figure out how to construct an extractor for a non-interactive lattice-based proof. Specifically, I'm curious about the Fiat-Shamir transform applied to a five-move interactive protocol. ...
- 528
2
votes
1
answer
165
views
What's the meaning of verifier is "ppt" ? and why we need verifier is ppt in Interactive Proof?
I have been studying Zero Knowledge Proof. I found the Definition of Interactive Proof says that Verifier is ppt.
And I only found in PP (Complexity) Wikipedia says that ppt:
Turing machines that are ...
- 215
0
votes
1
answer
87
views
zkSNARKs: Doing the setup for the Single Variable Operand Polynomial
I am reading this explanation of zkSnarks written by Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf
My question is about Section 4.6.1
Setup
construct the respective operand ...
- 2,167
2
votes
1
answer
719
views
Range proof for elements in Vector Pedersen commitment
If I construct a vector pedersen commitment $c = a_1G_1 + a_2G_2 + ... + a_nG_n$ with an arbitrary scalar vector $(a_1, a_2, ..., a_n)$ and group elements $(G_1, G_2, ..., G_n)$, is it possible to ...
- 123
14
votes
5
answers
2k
views
Cryptographically safe lookup of value in a set
I'm looking for an elegant solution to the might-seem-trivial problem of looking up for specific value in a known set of values without disclosing what value we look for. Let me describe it in a ...
- 266
3
votes
2
answers
260
views
What exactly does "Extension of a polynomial" mean?
This from the manuscript of a book on Zero Knowledge Proofs - https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf
3.5 Low Degree and Multilinear Extensions Let $\mathbb F$ be any finite ...
- 2,167
2
votes
0
answers
34
views
Probabilistic Verifiers for NIZK in the CRS model
Can we assume without loss of generality that the verifier for non-interactive zero-knowledge proofs in the common reference string model is deterministic, or does random randomization add extra power?...
- 21
1
vote
0
answers
125
views
Is it possible to prove possession of AES-128 key?
My question is kind of related to this topic: Can we prove possession of an AES-256 key without showing it?
But I couldn't figure out how to apply it to my problem.
Description:
Lets say I have a ...
- 11
1
vote
1
answer
94
views
Proof of knowledge of constant discrete log in the bilinear setting
Consider a pairing $\mathbb{e}: \mathbb{G}_1\times \mathbb{G}_2\longrightarrow \mathbb{G}_T$ with generators $g_1$, $g_2$ for $\mathbb{G}_1$, $\mathbb{G}_2$ respectively. The groups $\mathbb{G}_1$, $\...
- 190