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.

223 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
8 votes
0 answers
585 views

What's the difference among Vector Commitment, Zero-knowledge Set, Zero-knowledge Accumulator, and Zero-knowledge Elementary Database?

Vector commitment allows one to commit to an ordered sequence of $q$ value ($m_1,\cdots,m_q$) in such a way that one can later open the commitment at specific positions(e.g., prove that $m_i$ is the $...
7 votes
1 answer
595 views

Zero knowledge proof for Paillier addition under multiple keys

Suppose $m_0, m_1, m_2 \in \mathbb{N}$ such that $m_0 = m_1 + m_2$, $m_i > 0$ (none of them can be 0 or lower) Under a Paillier cryptosystem, set $e_0 = E(m_0, r_0)$ for a public key $(g_0, n_0)$ ...
  • 71
6 votes
0 answers
664 views

Comparison of SNARK-friendly hash algorithms MiMC7, Poseidon, Pederson?

There are some cryptographically secure hash algorithms designed to be efficient for SNARKs, STARKs and FHE. Some of them already implemented in Zcash, Zokrates and circom. The ones that I know of are:...
  • 911
6 votes
0 answers
107 views

Understanding anonymous credentials. Does someone understand how it works?

After reading a series of papers CL01 CL02 CL04, I feel like I understand the intuition behind the anonymous credential framework but I don't understand some details the mathematics behind it. I ...
  • 531
5 votes
0 answers
76 views

Why do Lattice-based Proof Systems not use the $\ell_2$ norm and canonical embedding?

I was recently reading the paper A non-PCP Approach to Succinct Quantum-Safe Zero-Knowledge. Among other things, it discusses an adaption of the "folding" technique (from Bulletproofs) to ...
  • 8,777
5 votes
0 answers
261 views

How do they avoid Zero Knowledge Proofs in the paper Priced Oblivious Transfer: How to sell Digital Goods?

I don't understand a part of the paper Priced Oblivious Transfer - How to Sell Digital Goods. Particularly, the authors avoid using zero knowledge proofs and in section 3.3 they explain how they do ...
5 votes
0 answers
402 views

Additively homomorphic cryptosystem with non-interactive zero-knowledge proof of non-negativity

I need a cryptosystem that is additively homomorphic. Paillier preferably, but not neccessarily. Also, for every ciphertext the private key holder must be able to prove non-interactively that the ...
  • 250
5 votes
0 answers
889 views

How to prove that a commitment hides the decryption of an ElGamal ciphertext?

I've decided to remove a previous unanswered question of mine and break it down into smaller pieces so it's not such a loaded question. For this question I need to prove that I've committed to a ...
4 votes
0 answers
98 views

Applications of ZK proofs without proof of knowledge?

With the appearance of cryptocurrencies several applications of ZK proofs were envisioned. However, to the best of my knowledge, all of these are proofs of knowledge. My question is: are there any ...
  • 3,812
4 votes
0 answers
266 views

2 different definitions of Special Soundness

There are 2 different definitions of special soundness in the literature: (1) can be found in Damgard: We say that a Sigma-protocol $\Pi$ satisfies special soundness, if there exists a PPT extractor $\...
  • 173
4 votes
0 answers
83 views

Can zero-knowledge proof be used to determine if another person knows a certain movie with a twist ending?

Suppose I want to talk with a co-worker about a movie called "The Twist Movie". I know the movie contains an interesting twist, and bringing up the movie in a discussion about twists in movies might ...
  • 41
4 votes
0 answers
173 views

Transferable zero-knowledge proofs

Many interactive ZK-proofs satisfy non-transferability; that is, the prover performs a series of actions to convince the verifier of a certain fact, and this verifier can't use this proof to convince ...
4 votes
0 answers
289 views

How to modify the Socialist Millionaire Protocol to be symmetric.

In the Socialist Millionaire Protocol, the roles of Alice and Bob are almost symmetric. By this I mean they do almost the same thing, until the very last step. In the final step, both parties check a ...
  • 151
4 votes
0 answers
221 views

understanding the proof of knowledge

Recently I've been reading the paper “A New Family of Implicitly Authenticated Diffie-Hellman Protocols”. It's very hard for me to go further. Especially when it comes to the proof of knowledge. ...
  • 49
3 votes
0 answers
93 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 ...
  • 488
3 votes
1 answer
127 views

Zero knowledge proof for verifying a machine learning model

Imagine Alice has trained a machine learning model. Bob wants to verify that whether Alice actually trained the model or not, but Alice does not want to reveal her model (because the model is personal ...
  • 45
3 votes
0 answers
53 views

Applications of Shuffle Proofs

Shuffle proofs enable a prover to show that a vector of commitments or encryptions $(c_1, \dots, c_n)$ is permuted into a vector of commitments $(c'_1, \dots, c'_n)$ without revealing the permutation ...
  • 1,026
3 votes
1 answer
308 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. ...
  • 31
3 votes
0 answers
100 views

Is it possible to verify attributes of encrypted content?

Let's say that Alice has this information about her, { "name": "Alice", "age": 25, "eyes": "brown" } which she encrypts with a key pair so that no one access ...
3 votes
0 answers
79 views

What is the relation between honest verifier zero-knowledge and non-interactive zero-knowledge?

I'm not clear about the relation between the following definitions: zero-knowledge protocols; honest verifier zero-knowledge; non-interactive zero-knowledge. To my best understanding, zero-knowledge ...
3 votes
0 answers
92 views

Doubt in computing $g^\frac{1}{\delta+x}$ where $x \in \mathbb{Z}$

I was going through Zero Knowledge Set Membership and came across the following: Given $x \in \mathbb{Z}$ and $g$ is the generator of a multiplicative group $\mathbb{G}$ how do we compute $g^\frac{1}{...
  • 83
3 votes
0 answers
53 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 ...
  • 131
3 votes
0 answers
114 views

Proof of knowledge of exponentiations

I am reading a paper of Furukawa and Sako, "An efficient scheme for proving a shuffle" from 2001. This paper writes a protocol for verifiable shuffling in mixnets. Their protocol make use of ...
3 votes
0 answers
204 views

Weak Challenge Generation - Fiat-Shamir Heuristic

The Fiat-Shamir heuristic may be applied to transform a Sigma-Protocol on R(x,w) into a ZKPoK. Let's call the prover's first message ...
3 votes
0 answers
278 views

Shared-secret authentication with implicit session keys?

Consider a system with producers (P), consumers (C) and a server (S) with two TCP ports open where a consumer connects on one port and a producer on the other. The server is just a TCP relay which ...
  • 423
3 votes
0 answers
287 views

Question about proof of knowledge definition

I am just reading the "soundness" definition for proofs of knowledge by Bellare / Goldreich. A proof of knowledge is a proof between a prover $P$ and a verifier $V$. $P$ convinces $V$ of his knowledge ...
  • 569
3 votes
0 answers
329 views

Transforming simplest protocol into a Sigma-protocol

I have some questions from previous years exams, I hope you could help me with them. :) Suppose that a protocol satisfies the properties of a $\Sigma$-protocol, except that it is only (plain) ...
3 votes
2 answers
204 views

Why does the prover in an interactive proof run in exponential time with the space of the computation?

I'm currently trying to gain an understanding of verifiable computation and the strengths and weaknesses of past approaches. In particular, I've been watching the following YouTube video which talks ...
  • 131
2 votes
0 answers
80 views

Are digital signatures a type of zero-knowledge proof?

Are the digital signatures used in cryptocurrencies such as Bitcoin a type of zero-knowledge proof?
2 votes
0 answers
36 views

Identifying knowledge leakage in a deliberately non-zero-knowledge proof

Below is a suggestion for a zero knowledge proof for the existence of both a $k$-independent set (IS) AND a $k$-vertex cover (VC). It was given as an example of an interactive proof that is not ...
  • 311
2 votes
0 answers
33 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 ...
  • 166
2 votes
0 answers
37 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 ...
  • 1,252
2 votes
0 answers
95 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. ...
  • 412
2 votes
0 answers
24 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
2 votes
0 answers
99 views

Difference between an authentication scheme and a identification scheme in ZK proofs?

EDIT: I want to specify what I know about schemes security: Authentication schemes: P can prove V he is P, and nobody else can prove V that they are P. Identification schemes: P can prove V he is P, ...
2 votes
0 answers
112 views

It is possible to verify the computation of a hash function without actually proving it in zero knowledge?

Let me first introduce the context: Let's say that we have a hash function evaluation: $$h = H(x, y),$$ where $x$ and $y$ are the public and the private input of the hash function $H$, respectively. ...
  • 531
2 votes
0 answers
96 views

Verifiable execution of a program

I would like to know what cryptographic primitives could be used for Alice to prove to Bob that she actually executed a program. The goal is to make a Proof-of-useful work, where Alice proves she ...
  • 121
2 votes
0 answers
62 views

Trade-offs for more parties in PICNIC multi-computation

In the PICNIC post-quantum signature scheme, a zero-knowledge proof of the secret key for a symmetric encryption is produced by implementing the encryption as a Yao garbled circuit of a three-party ...
  • 12k
2 votes
0 answers
72 views

How does the rejection sampling lemma work in the proof of HVZK?

In this protocol, Q1: how does the commitment work? What if the prover sends $\textbf{t}$ directly, and then sends $s_m,s_r,s_{\textbf{e}}$? Q2: How does the rejection sampling lemma work? refer to ...
  • 419
2 votes
0 answers
153 views

Efficiently prove the correctness of Paillier encryption in or "outside" a zk-SNARK

I'm working with a zk-SNARK library [1] that allows me to prove the correctness of arbitrary arithmetic circuits, and I now want to use these zk-SNARKs to prove that some Paillier [2] ciphertext $c$ ...
  • 21
2 votes
0 answers
59 views

Demo a Proprietary Signal Processing Algorithm Without Cheating

I have a proprietary signal processing algorithm, $F(s)$, which I would like to demo to my customers. The demo starts with the customer uploading a binary signal $S_0$ to my website. I then generate a ...
  • 121
2 votes
0 answers
47 views

Predicting with a machine learning model while preserving the privacy

Imagine Alice has trained a machine learning model. She wants to store her model in a blockchain so that everyone can use it; however, she wants her model to be private so that no one can steal her ...
2 votes
0 answers
251 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 ...
2 votes
0 answers
40 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 ...
2 votes
0 answers
44 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 ...
  • 41
2 votes
0 answers
69 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 ...
  • 717
2 votes
0 answers
77 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-...
2 votes
0 answers
180 views

ZK Proof that a blinded message (for a blind signature) contains a certain value

I am toying with eCash systems and blind signatures, and I started with Chaum's original formulation. In particular, I'm using this formulation from this link: User ...
2 votes
0 answers
107 views

Verify commitment C commits to the same value that E encrypts

Given the following (using additive notation): $G$ - generator of an elliptic curve group of order $q$ $s$ - secret drawn uniformly from the distribution $1..q$ $k$ and $K$ - a private public keypair ...
2 votes
0 answers
104 views

Adaptation of Stern Zero-Knowledge protocol from coding to lattices

I'm currently working on Zero-Knowledge-proofs in lattice context, for which there exist two major frameworks. One of those two is the adaptation of Stern protocol from code-based-crypto. There is in ...
  • 21

1
2 3 4 5