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
39 views

Can I use zero-knowledge proofs on pre-image of symmetric encryption?

Let $e_x$ be a symmetric encryption function in regards to key $x$. Let $y_1 = e_1(x_1), y_2 = e_2(x_2)$. My goal is to prove that: $$x_1 = x_2$$ Is there a way of proving this using ZKP? I can't seem ...
1
vote
0answers
54 views

zero knowledge proof of a number greater than zero

Is there a way to prove in zero knowledge that an element (h) of a group is less than (or greater than) another element from the group? In other words, can we prove that the difference of elements is ...
0
votes
0answers
23 views

two-to-one hash in libsnark, what is it “exactly”?

I'm reviewing this test which prepares a zero knowledge proof of the preimage of an hash: https://github.com/mariogemoll/libsnark-tutorial/blob/sha256/src/test-knowledge-of-preimage.cpp In my (wrong) ...
3
votes
0answers
45 views

Constructing division gate in R1CS

One thing I don't quite understand is how to naively handle division operation in rank-1 constraint systems (R1CS). supposedly A.s * B.s - C.s = 0 allows you to ...
2
votes
0answers
31 views

Non-interactive proof of friendship

Alice would like to make public a proof that she is friends with Bob that has the following characteristics: Creation of the proof requires the agreement of both Alice and Bob Anyone who is also ...
1
vote
0answers
35 views

An aggregate signature scheme for transactions

Suppose A and B communicates where A makes B some payments by sending signatures as the following, $$ \sigma_1 \leftarrow Sign(v_1, sk_A), \sigma_2 \leftarrow Sign(v_2, sk_A), \dots \sigma_n\...
0
votes
0answers
20 views

Verification of NIZK proof with algebraic MACs

The paper Algebraic MACs and Keyed-Verification Anonymous Credentials, includes a way to instantiate a NIZK proof with algebraic MAC. This is given in Appendix E where this NIZK is a part of the ...
3
votes
0answers
36 views

Sigma proofs for Pedersen commitments arithmetic under different bases

I was wondering if it's possible to prove an equality of openings between $3$ Pedersen commitments $P\cdot Q$ and $R$ when $P, Q, R$ have different commitment keys. Suppose that commitment $R$ commits ...
0
votes
0answers
13 views

Sigma-Protocol to prove a commitment to a commitment

Let $Com$ be a pedersen commitment function with publicly known $g$, $h$, and $p$ values s.t. $Com(x,r)$ is a commitment on $x$ with random number $r$. Is there a $\Sigma$-protocol to prove $ZKPoK\{ (...
2
votes
0answers
32 views

Sakumoto 3-pass MQ IDS Zero-Knowledge proof

In this paper: Public-Key Identification Schemes Based on Multivariate Quadratic Polynomials it is explained in Theorem 2 that the 3-pass protocol is statistically zero knowledge when the commitment ...
1
vote
1answer
41 views

Could PAKE via smooth projective hash function protect agaist replay attacks?

I came across some password-based authenticated key exchange (PAKE) protocols that are based on the smooth projective hash function (SPHF) in the standard model. And I checked some related works, and ...
2
votes
1answer
41 views

Is there a way to prove knowledge of a limited resource like a phone number just to the people who already know about it?

For instance, let's say Bob's phone number is X and Alice has somehow identified that Bob's phone number is X. Now she doesn't have a direct way to contact Bob, so she wants to post in a public forum ...
0
votes
0answers
21 views

A zero knowledge protocol with a deterministic verifier

Given a language $L$ and $ZKP$ between $v$ and $p$, when $v$ is deterministic polynomial time algorithm, I wish to obtain a probabilistic-polynomial algorithm which solves $L$. Which, if I am not ...
0
votes
0answers
19 views

How to prove properties of pre-image of random oracle in zero-knowledge proof?

A signature Sig is given as input to random oracle H, such that y = H(Sig) and Sig should be hidden from the verifier. How to prove in zero-knowledge to the verifier that y is the correct output from ...
1
vote
1answer
63 views

Proving equality of two Schnorr Signatures

Given two Schnorr Signatures that were made from the same $x$, where each $x$ is private. Is there a way to prove that they came from the same $x$ without revealing $x$? I heard about Chaum-Pedersen ...
1
vote
0answers
39 views

Is using Fiat-shamir Heuristic safe?

What I'd like to do is to have the Prover store a value x where x remains hidden. From x, I'...
2
votes
0answers
55 views

How to construct a set in which the elements in $\mathbb{Z}[x]/(x^n+1)$ and their differences are invertible and with coefficients in $\{-1,0,1\}$?

I know that in IACR - Better Zero-Knowledge Proofs for Lattice Encryption and Their Application to Group Signatures it constructs such a challenge set: {$ x^i $}. But the inverse of the difference of ...
1
vote
0answers
28 views

Fixed variable in Groth16

In the paper On the Size of Pairing-based Non-interactive Arguments by Jens Groth, it is always referred in the equations to satisfy that $a_0 = 1$ and the others $a_1, ..., a_m \in \mathbb{F}$. I am ...
1
vote
0answers
24 views

Range Proof without trusted set-up

If verifiers are public blockchain nodes, which might leak information. Does this imply that range proofs such as Boudot's and Lipmma's (squaring based) approach could not be applied, unless a trusted ...
0
votes
1answer
51 views

ZKP for product of two primes

I'm struggling to understand the intuition of the zero knowledge-ness of this proof from the following paper. The proof is a 2 round where the verifier asks the prover to extract square roots of ...
0
votes
0answers
33 views

How to determine if a protocol is a Zero knowledge proof

If the given protocol is non interactive then how can one prove that the modified protocol is complete and determine whether it is zero-knowledge? Let $N = p q$ as in an RSA algorithm, with $\text{gcd}...
0
votes
1answer
53 views

why people don't use the same generators?

i want to make many pederson commitments $C=g^s h^r$ for a long time , do i have to change the generators $g$ and $h$ or its ok if i always used the same ones
1
vote
1answer
39 views

Why does the verifier have to send a challenge in Shnorr protocol?

In the Shnorr protocol where the prover wants to prove he has a witness $w$ for $g^w$ the following interactions happen: the prover chooses a random $r$, calculates $y=g^r$ and sends $y$ the ...
2
votes
1answer
45 views

Non-interactive proof of value in MPC

Does it exist? Specifically using Shamir secret sharing based MPC and looking for a (non-)interactive way to prove that the secret value is valid. A value is valid if it is part of a set for example $[...
1
vote
1answer
60 views

Question of proving the opening of Pedersen Commitment

Given an opening $(m, r)$ of a Pedersen commitment $c = g^m h^r$, where $g, h$ are the generators of a group $G$ with prime order $q$ (public), a PPT prover wants to prove to a verifier the opening of ...
0
votes
0answers
29 views

Does Schnorr identification protocol using commitment scheme?

In schnorr identification protocol, a prover needs to choose a random,let's say $r$ at the beginning, then commit to this randomness as $g^r\bmod p$. When we say "commit", does it really mean we are ...
1
vote
2answers
97 views

how do i implement zero knowledge proof?

I am new to this concept of zero knewledge proofs, from what I understand it is not a mathematical general equation like RSA or ECC cryptography has, but its a methodology that varies from problem to ...
0
votes
1answer
88 views

How can create a proof that we have a sequence of binary digits?

Given a sequence of bits (either a 0 or 1), for example: 0110100110110001 How can one create a proof that we have this bit sequence, without actually revealing ...
7
votes
1answer
176 views

Is this a safe way to prove the knowledge of an ECDSA Signature?

I think that I've found a good solution to prove the knowledge of an ECDSA signature without revealing it. In short terms it consists in generating an ECDSA signature using the point $R$ as generator, ...
3
votes
1answer
32 views

Allow message inspection by proxy without ability to modify it

My client creates a private/public key pair and sends it securely to a server (the "public" key is not really public, only the server is supposed to know it). The server then sends messages to the ...
4
votes
1answer
119 views

Fiat-Shamir for $(2n + 1)$

Consider the following $(2n+1)$ protocol: $\mathcal{P}$ and $\mathcal{V}$ engage in an interaction where $\mathcal{P}$ consecutively sends a message $a_i$ answered by $\mathcal{V}$ with a random ...
4
votes
2answers
85 views

Can zksnark prove DLP?

Can one use zksnark to prove the knowledge of a discrete logarithm? In another word, can zksnark (R1CS) encode exponentiation?
0
votes
1answer
49 views

Are there any zero knowledge protocols which do not rely on a Group?

To me (new), it seems that a lot of cryptography relies on group theory. Are there any zero knowledge protocols which do not rely on a group?
0
votes
0answers
11 views

Non-interactive zero-knowledge proofs used in zk-ledger and how do they work?

I was reading ZK-Ledger paper and I found out that they are using NIZKs in their program. The question is I could not find any explanation about how they actually work. For example: Can someone who ...
5
votes
1answer
140 views

Why invent new hash functions for zero-knowledge proofs?

Recently, new hash functions were invented. Their primary purpose is serving the needs of zero-knowledge proof systems. I'm talking about Poseidon-256, Starkad-256, etc. See the paper. What is the ...
1
vote
1answer
65 views

How can we tell if there is a Zero-Knowledge Proof for a given problem?

I remember my cryptography instructor saying that in math, we can use logic to find out what we can prove and what we can't prove. Assuming this, how would we use logic to find out if a given problem ...
0
votes
1answer
86 views

Zk-Snarks vs Homomorphic Encryption

I have been reading a bit about encryption algorithms. I have come across these two algorithms.My use case is the ability to work with encrypted data and my data will be string data. I see that ...
0
votes
0answers
38 views

Range Proofs based on Polynomial Commitment Scheme (PCS)

I have been trying to implement the PCS-based Range Proofs as described here. My code is in a public repository. I am not able to understand this part: This w_cap is a linear combination of f and ...
1
vote
1answer
48 views

Examples of flattening code to create an R1CS

When preparing logic for use in a zkSnark, one needs to first "flatten" the code so it can be written as a series of constraints. I'm finding it hard to find examples of doing this. For instance, how ...
4
votes
3answers
125 views

Construct Schnorr Protocol can only verify by designated verifier

Currently I have a DLP as following, $y = g^x \bmod p$, I can easily construct a proof of knowledge by using Schnorr Protocol. But I would like to put it a a system of 2 parties with public key and ...
0
votes
0answers
53 views

Converting R1CS to QAP - checking the last step

from reading Vitalik Buterin's excellent post on creating a QAP from an R1CS, I understood to translate a function into three groups of vectors, the number of vectors being the number of "gates" or ...
0
votes
1answer
41 views

Is security of zk-SNARKS related to the size of the arithmetic circuit they evaluate?

In the context of zk-SNARKS, we are given an arithmetic circuit $C$, public outputs $y_1, \ldots, y_n = \mathbf{y}$ and some public inputs $x_1, \ldots, x_ℓ$. The prover wants to prove knowledge of ...
2
votes
0answers
40 views

Groth-Sahai Proof of multi-exponentiation

I want to create a NIZK proof of a multi-exponentiation via Groth-Sahai proofs. In the lectures of Jens Groth in a winter school of Bar-Ilan University, he shows a way to transform multi-...
1
vote
1answer
71 views

Can I prove in zero knowledge that the public key corresponding to a secret that I committed is in the Accumulator?

I have a set of users in my system, each having a private/public keypair of a digital signature scheme. I also have an accumulator in my system, where all the public keys of the users are accumulated. ...
2
votes
1answer
79 views

Creating a private cryptocurrency without trusted setup

I am interested in creating a cryptocurrency which keeps the sender, the receiver and the amount private and does not require a trusted setup. I have already read the Zerocash protocol but It uses zk-...
0
votes
1answer
81 views

Difference between using Schnorr Protocol and just compare hash function to prove knowing something?

I am studying Schnorr Protocol and I just come up a case. For example I am a Prover and have a secret $x$. By using Schnorr Protocol, I create $h=g^x \bmod p$ and save $h$ to a public place. When ...
0
votes
0answers
38 views

Proving anonymous credential presentation

In a CL-based or CKS-based anonymous credential system, how can a verifier $V$ prove that a credential holder $H$ has presented it a credential that has been issued by an issuer $I$ without ...
0
votes
0answers
45 views

How to encode SHA-256 as a quadratic span program?

I'm trying to understand the step-by-step zkSNARK's generation process for proving the knowledge of the hash pre-image (as in this example). However, I don't understand how exactly SHA-256 is turned ...
0
votes
0answers
35 views

Is it correct using Sigma Protocol to do the knowledge proof?

For this background, the prover knows a secret $x$ for $h=gx$. Prove to the verifier that he knows $x$. (I know $h=gx$ is not a NP problem, I just want to practice the Sigma Protocol) Step 1 : $P \...
0
votes
1answer
64 views

Zk-SNARK against Sigma Protocols and for Secure Function Evaluation

I have a couple of questions on ZK-SNARK: Based on what I understand, a ZK-SNARK is an "Argument of knowledge". That means that it should be equivalent to Sigma Protocols like Fiat-Shamir and ...

1
2 3 4 5
13