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
1 vote
0 answers
18 views

Are there any "hard lower bounds" to zero-knowledge proving space/time/commmunication complexity?

There is a lot of "retail investor" hype implying a zk revolution in the future where we have circuits for common instruction sets and many software backends are zk-proven. I'm wondering, ...
user avatar
0 votes
0 answers
18 views

Groth'16 trapdoor for simulator

In the zero knowledge definition of the Groth16 scheme (https://eprint.iacr.org/2016/260.pdf) [Section 2.2], why would the simulator be allowed a trap-door in set up? The trap-door information ...
user avatar
  • 75
1 vote
1 answer
39 views

How to generate a SNARK arithmetic circuit for SHA256?

I am using zkSNARK to prove knowledge of preimage for SHA256. However, the library used only supports field operations (such as add and multiply), and it compiles down to arithmetic circuits. Thus, ...
user avatar
0 votes
1 answer
49 views

encrypting a document with 2 different keys

Is there a way to encrypt a file with 2 (or more) keys and then access it with only 1? scenario : Bob and Alice have a tight memory and can only remember ONE key. Bob and Alice encrypt a file with ...
user avatar
1 vote
2 answers
84 views

Prove a plain text belongs to encrypted data

Given an encrypted (RSA) message and it's original plain text, is there a way to prove that the plain text belongs to the encrypted message ?
user avatar
1 vote
0 answers
55 views

Creating a basic SHA256 hasher in Circom

I want to create a SHA256 hasher in Circom so I can validate that a person knows the pre-image of a SHA256 hash without revealing the pre-image. This is my current code but it doesn't work: ...
user avatar
0 votes
1 answer
64 views

Simplest recursive SNARK working example

I have been doing some research into recursive SNARKs. But I haven't found a working code example such as this one using Zokrates or this one using snarkjs. Anyone knows one such example, say, for ...
user avatar
0 votes
0 answers
11 views

Algorithms to secretly distribute elements from a known set / with a known global characteristic

I am assuming a set of $n$ players and a central "dealer" $C$ through which all communication is routed. The state I want to end up with is that each player $i$ has a secret $s_i$ unknown to ...
user avatar
  • 1
2 votes
0 answers
30 views

How to prove an RSA ciphertext matches a Paillier ciphertext?

Suppose I know an RSA public key $(n,e)$ and I create two ciphertexts: An RSA ciphertext $C_1 = m^e \mod n$ and a Paillier ciphertext $C_2 = g^m \cdot r^n \mod n^2$. Is there a known efficient method ...
user avatar
  • 166
2 votes
0 answers
23 views

Reducing number of constraints in R1CS from an arithmetic circuit

The article Ligero++ (https://dl.acm.org/doi/pdf/10.1145/3372297.3417893) says "The number of constraints in R1CS maps to the number of multiplication gates in arithmetic circuits." But I ...
user avatar
  • 962
1 vote
2 answers
118 views

Is there a scheme to enforce a random seed without leaking the seed?

End-to-end encrypted web services (like cryptpad) often include a 128-bit seed in the hash part of the URL (that is not sent to the server), to derive both an identifier that is sent to the server, ...
user avatar
  • 113
0 votes
0 answers
13 views

What is stored in a register method using the OPAQUE protocol?

I am currently studying OPAQUE, and have no prior deep experience with cryptography. I am currently trying to develop a login/register system using OPAQUE for the authentication process. Should I ...
user avatar
4 votes
2 answers
411 views

Is there anything like "Proof of Computation"?

Is there any cryptographic method for Proof Of Computation ? If i am running my program on untrusted hardware (remote server), after some time i want to verify the ...
user avatar
  • 41
0 votes
0 answers
31 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 ...
user avatar
  • 962
0 votes
1 answer
35 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 ...
user avatar
  • 31
1 vote
0 answers
30 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 ...
user avatar
  • 488
3 votes
0 answers
88 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 ...
user avatar
  • 488
1 vote
0 answers
31 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 ...
user avatar
0 votes
1 answer
62 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.
user avatar
  • 1
1 vote
0 answers
27 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.
user avatar
  • 11
1 vote
1 answer
74 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 ...
user avatar
0 votes
0 answers
19 views

Best way to hash a string in Circom

The specific case I'm asking this question for is a ZK-version of a Wordle game that I'm working on: https://github.com/alxkzmn/zk-wordle/blob/master/circuits/wordle.circom I represent the 5-letter ...
user avatar
0 votes
0 answers
34 views

Is this a valid construction of ZKP for this class of problems?

Let's say we have a problem $P$ that can be described in $a_1$ bits and that its solution can be described in $a_2$ bits. Say there exists a program $S$ that can check whether the described solution ...
user avatar
  • 115
1 vote
1 answer
55 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 ...
user avatar
  • 23
0 votes
0 answers
19 views

Pinocchio protocol: what if no extractability check

In Pinocchio protocol, prover submits extractability terms below so that counterfeiting fake proof is infeasible under q-PKE assumption. But, I don't understand why it is even necessary. What kind of ...
user avatar
  • 23
2 votes
1 answer
42 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 ...
user avatar
  • 23
0 votes
2 answers
77 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 ...
user avatar
  • 115
1 vote
1 answer
128 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: ...
user avatar
  • 11
1 vote
1 answer
95 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 =\...
user avatar
  • 75
4 votes
1 answer
141 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 ...
user avatar
  • 125k
1 vote
1 answer
89 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 ...
user avatar
7 votes
1 answer
1k 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 ...
user avatar
1 vote
0 answers
43 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 ...
user avatar
  • 111
1 vote
1 answer
65 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 ...
user avatar
  • 35
1 vote
1 answer
139 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 ...
user avatar
  • 13
1 vote
1 answer
85 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 ...
user avatar
1 vote
0 answers
42 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 ...
user avatar
  • 458
0 votes
0 answers
15 views

Bounded honest-verifier simulator and unbounded prover

I have a honest-verifier zero knowledge simulator $M$. The conversation between prover and verifier has the usual $(a, b, z)$ form. How can the bounded model $M$ generate $a$ and $z$ is the prover is ...
user avatar
1 vote
0 answers
68 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 ...
user avatar
0 votes
0 answers
71 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 ...
user avatar
  • 1
0 votes
0 answers
10 views

What do we mean by "Efficient Computing" of a Span Program (SP)?

I'm reading "Quadratic Span Programs and Succinct NIZKs without PCPs" and I'm having trouble understanding the "Efficiency" of a span program. I can see that a span program cannot ...
user avatar
1 vote
0 answers
27 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 ...
user avatar
  • 31
0 votes
1 answer
88 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 ...
user avatar
  • 164
3 votes
2 answers
173 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 ...
user avatar
  • 33
2 votes
1 answer
63 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 ...
user avatar
0 votes
0 answers
78 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 ...
user avatar
0 votes
0 answers
34 views

How to Run the Public Key Protocol for a Zero-Knowledge Proof of Identity?

In the paper Zero-Knowledge Proofs of Identity (by Feige, Fiat, and Shamir) a ZK protocol is described that leverages quadratic residues. Section 3 describes an "Efficient Identification Scheme,&...
user avatar
1 vote
0 answers
51 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$. ...
user avatar
  • 23
1 vote
1 answer
128 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 ...
user avatar
1 vote
1 answer
58 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 ...
user avatar
  • 31

1
2 3 4 5
17