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.

160 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
6
votes
0answers
358 views

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

Vector commitment allows 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 $i$-...
6
votes
1answer
370 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)$ ...
5
votes
0answers
56 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 ...
5
votes
0answers
250 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
0answers
363 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 ...
5
votes
0answers
733 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
0answers
80 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 ...
4
votes
0answers
102 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
1answer
730 views

In zkSNARKS, does R1CS require every step of the calculation, or just statements which confirm the calculation was performed correctly?

I was attempting to figure out a way to implement the modulo operation as a set of gates in an Rank-1 Constraint System, detailed by Vitalik Buterin here However, it occurred to me that maybe we don'...
4
votes
0answers
170 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 ...
4
votes
0answers
206 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. ...
3
votes
0answers
40 views

How to construct a circuit in zkSNARK

I have a few questions about how to use zk-snark. Since the basic logic of using zk-snark is: using a circuit to represent a problem, generate an R1CS from the circuit, transform R1CS to QAP and then ...
3
votes
0answers
37 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 ...
3
votes
0answers
85 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}{...
3
votes
0answers
110 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
0answers
272 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 ...
3
votes
0answers
264 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 ...
3
votes
0answers
231 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 ...
3
votes
0answers
322 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
2answers
177 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 ...
2
votes
0answers
44 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 ...
2
votes
0answers
36 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
0answers
38 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 ...
2
votes
0answers
36 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
0answers
33 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 ...
2
votes
0answers
61 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 ...
2
votes
0answers
45 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
0answers
90 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
0answers
102 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
0answers
89 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 ...
2
votes
0answers
75 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 ...
2
votes
0answers
55 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 ...
2
votes
0answers
29 views

Strategies for fast integrity attestation over multi party computation for large messages

I am looking for ways to efficiently perform integrity attestation over large messages using multi party computation. While, hashing (SHA1, 256...) is one alternative but it's painfully slow and grows ...
2
votes
0answers
94 views

The theory of transformation of arithmetic expressions into boolean circuits in zkboo

I've read the sources of ZKBoo where they transformed arithmetic operations of the SHA hash functions into a bunch of boolean ones. Where does this transformation arise from? How do you construct such ...
2
votes
0answers
37 views

ZK-proof of usage in a seed of CSPRNG

Assume a Player chooses a seed $s$ and he wants to prove that he uses it as a seed to CSPRNG function, where the seed is not public. How can he prove it? Thanks.
2
votes
0answers
28 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 ...
2
votes
0answers
208 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
0answers
146 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}(...
2
votes
0answers
89 views

Can proofs be relayed to derived keys?

I am aiming to find out if this problem/puzzle can be solved with cryptography at all. Say there are these two parties: Subject S which has a master private/public key pair (MPriv, MPub) and a set of ...
2
votes
0answers
185 views

Post quantum zkSNARK?

Do there exist any zkSNARK constructions that are based on post quantum cryptography? The encryption scheme used in the zkSNARK that is employed in Zcash for instance uses an encryption scheme of the ...
2
votes
1answer
124 views

Proof of using a literal from known set, inside a computed formula

Suppose I have publicly revealed the value of $\phi(u) = A+Bu$, where A, B, u are private values from a large group, that I want to keep in secret. Furthermore, I want to add proof that the value $u$...
2
votes
0answers
101 views

Are zkSTARKs simulation sound extractable in the random oracle model?

I've recently become interested in simulation sound extractable zero-knowledge proofs for use in UC-secure protocols. I've also become interested in the recent instantiation of PCIPs called zkSTARKs. ...
2
votes
0answers
52 views

Unanimity for three (or more) players

The article Cryptographic Protocols with Everyday Objects by James Heather, Steve Schneider, and Vanessa Teague describes the following unanimity protocol for three players: Three players want to ...
2
votes
0answers
76 views

What is a discrete logarithmic assumption? How does it set up trustless proofs?

A pending proposal of bulletproofs as a ZK proof for confidential transactions relies on Fiat-Shamir heuristic to be non-interactive by creating a digital signature on interactive proof of knowledge. ...
2
votes
0answers
458 views

Functional signatures with ECDSA Verifier

Functional signatures use some master key to create a functional signature key. The functional key can be used to sign messages, but only if the message is accepted by some predicate function. For ...
2
votes
0answers
78 views

Can we use a pseudorandom function in both models of a simulation based proof?

Assume in the real model a party blinds a fixed element $b$ as: $v_i=r_i\cdot b$, where $r_i$ is a output of pseudorandom function. So we give $v_i$ to a semi-honest adversary. Now we want to sketch ...
2
votes
0answers
292 views

Proposed unidirectional authentication scheme

I've been looking around for a way to authenticate a client to the server and deliver a message, but in a unidirectional fashion - that is, the client sends messages to the server, but the server ...
2
votes
0answers
522 views

What does Set Membership actually prove?

While going through this paper, I came across the idea of Set Membership proofs. The proof allows a prover to prove that a value is contained in some set. The point where I am confused is, all the ...
2
votes
0answers
345 views

Groth-Sahai proofs and hardness assumptions

I am learning Groth-Sahai NIZK proof system for Bilinear groups. While going through the literature, I am getting confused on how the proof system is related to Subspace Decision, SXDH or DLIN ...
2
votes
0answers
109 views

Reliability of a single-pass deniable authentication protocol?

I look for one-pass deniable authentication protocol with a short message payload for my project and find a solution: ...