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
1answer
37 views

The magic box puzzle: How to implement a verifiable self-contained secret system?

Imagine we have a magic box that will open only if we pronounce the secret words. Everybody at the beginning of the game have some verifiable proof of the correct secret words. During the first phase ...
0
votes
1answer
54 views

Secret community forming based on zero-knowledge proof (IOT)

I want to discuss a simplistic scheme that comes to my mind, after I read about zero-knowledge proof and some fermentation time. I should mention that this is not born out of a business need or ...
1
vote
1answer
64 views

Is there any encryption system where the sender cannot prove that a specific ciphertext belongs to a specific plaintext

I'm trying to create a message-transfer system where The encrypted messages are stored in a public database. It is possible to verify who is the sender of this message. The sender cannot prove to ...
1
vote
0answers
39 views

NIZK arguments for QAP GRO16 proof simulation

I'm studying how zero knowledge for quadratic arithmetic programs works (GRO16 page 17) and try do understand proof simulation part. If I understood right, if malicious party knows $\alpha , \beta ,\...
10
votes
1answer
179 views

Minimizing exchanges for ZK proof of a message with given SHA-256

Consider the problem of proving knowledge of a message $m$ which has a certain public SHA-256 hash $h$, without disclosing $m$ or usable information about it, while minimizing the information exchange ...
6
votes
1answer
165 views

Sigma protocol when order is unknown

In the following paper (page 5) they have a proof that a triple $\left(g,b_{i-1},b_{i}\right)$ is of the form: $\left(g,g^{x},g^{x^{2}}\right)$ for some x. The relevant text from the paper is as ...
0
votes
1answer
83 views

Zero-knowledge proofs vs. “Identification schemes”? (as in Katz--Lindell)

Most modern papers on zero-knowledge proofs (for example, BBB+16) recycle essentially the same list of boilerplate definitions, concerning soundness (formulated using extraction or some form of "...
1
vote
1answer
68 views

Complexity of computing zk-SNARK Proofs

Disclaimer: I have no background in cryptography, and everything I'm asking about is what I've learnt from last couple of days of frantic reading on this topic. Any help is much appreciated. Q: What ...
0
votes
0answers
28 views

Zero-Knowledge proof of inequality, question on the auxiliary commitment

An extension to question Zero-Knowledge proof of inequality. The paper by Camenisch and Shoup in Section 6 of Practical Verifiable Encryption and Decryption of Discrete Logarithms (CRYPTO'03). ...
2
votes
1answer
133 views

Bijection Between Real View and Simulated View

I have some basic idea about cryptography and trying to understand zero knowledge proof, so pardon my ignorance and stupidity. I am trying to formalize sigma protocol in Coq theorem prover, and so far ...
0
votes
0answers
19 views

How to intuitively realize the Diverse Group System in the Hash Proof System(HPS)?

In the paper Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption by Cramer & Shoup, projective hash family derived from group system can be easily ...
3
votes
2answers
227 views

Concept Question for Secure Computation

I think this should be a simple question and I might be missing something fairly fundamental, but I haven't been able to find the answer. Basically, suppose there are parties $A$ and $B$. Party $A$ ...
0
votes
1answer
70 views

What does public-coin mean in interactive proof and zero-knowledge?

For related materials I read, it seems that for the public-coin setting, the verifier will always send random messages to the prover. In this setting, can we regard the verifier as an honest verifier, ...
1
vote
0answers
52 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
6answers
242 views

Proving a secret is known without revealing it

Let's say Alice wants to prove to Bob that she knows a secret S that Bob is also supposed to know. Alice can't be sure Bob is really who he pretends to be, so she needs to make sure Bob can't deduce S ...
0
votes
0answers
27 views

Zero knowledge proof with accumulators

I am working on a proof of concept on cryptographic accumulators. delta: The current size of the tails file in the accumulator. witness: The current value of the accumulator when the entry of your ...
2
votes
0answers
42 views

ZKPoK for RLWE secret and error

I came across How to validate the secret of a Ring Learning with Errors (RLWE) key paper by Ding et al., which seems to provide a ZK proof that the given $p$ is of the form $as + e$ with $s, e$ small ...
3
votes
1answer
49 views

Is it possible to reduce the tail's file of accumulators for large data set

I am working on a proof of concept around cryptographic accumulators. The following is my understanding so far delta : the current size of the tails file in the accumulator. witness : the current ...
0
votes
0answers
48 views

Challenges of Fiat-Shamir Transformation of ZK Proof / Sigma Protocol

Let $\Sigma$ be a sigma protocol whose commitment, challenge and response phases are $\Sigma_1, \Sigma_2, \Sigma_3$, respectively. In Fiat-Shamir Transformation, the challenges are $H(\Sigma_1)$ ...
1
vote
0answers
55 views

Why group signature based CL signature is in “sign-encrypt-prove” paradigm

In this paper, it referred that there are two paradigms used in constructing group signatures: the "sign-encrypt-prove"(SEP) paradigm and "sign-randomize-proof"(SRP) paradigm. As said in this paper, ...
1
vote
0answers
71 views

Can I prove that hash of modified preimage is valid

Assume that hash(X) == Y Alice knows both X and Y Bob only knows Y Alice generates a random nonce N and shares it with Bob. Alice calculates H = hash(X⊕N) and shares H with Bob. Can Alice prove to ...
0
votes
0answers
30 views

What is the main difference between Gap Sigma protocol and Sigma protocol?

I can understand and know how to use the Sigma protocol. My main question is that I cannot understand the main usage of the Gap-Sigma protocol. What is the main difference between the Gap Sigma ...
1
vote
0answers
50 views

TPM/FIDO Direct Anonymous Attestation practicality

DAA (Direct Anonymous Attestation) is not the only scheme to achieve anonymous attestation. In general, these schemes allow an entity to stay anonymous throughout the attestation process. The concern ...
1
vote
1answer
86 views

Zero-knowledge authentication to commercial VPN

For VPNs which only connect to the greater internet (as opposed to a VPN for accessing a private network), it is only necessary for the server to know that the client is a paying customer. It doesn't ...
0
votes
0answers
43 views

Prove knowledge of signature on committed value

Assume that a prover $P$, has previously obtained a signature $\sigma$ on a value $x$ from a verifier $V$. At a later stage, $P$ produces a Pedersen commitment $C$, to this value: $C = g^x h^r$ I'm ...
1
vote
0answers
41 views

Zero-knowledge commitment verification

Assume everything takes place in a prime field. Given the following: $g$ - generator $s$ - secret $E(K, m)$ - a public-key encryption function using public key $K$ and plaintext $m$ The ...
0
votes
0answers
30 views

Implemetation of a Sigma Protocol for a paper “Anonymous Identification in Ad Hoc Groups, 2004”

I read the paper Anonymous Identification in Ad Hoc Groups, 2004 Dodis et. al. My understanding is that it basically generates a group public key, whose identity can be controlled (to verify ...
1
vote
0answers
82 views

Why is this functionality chosen for UC-NIZK?

A correct proof (a proof which is indistinguishable from previously sent proof) can be tagged as wrong by the ideal functionality here if the adversary sends no witness. And, let's say P is a party ...
1
vote
1answer
172 views

Why does the Fiat-Shamir heuristic not work without a random oracle?

Consider the following three stage interactive zero knowledge proof in round $i$ The prover sends some commitment $a_i$ to the verifier. The verifier picks a challenge $c_i\in \{0 ,1\}$ Depending on ...
1
vote
0answers
71 views

Proof of membership on a merkle tree

I read the zcash paper recently. But I have been puzzled by a question. How did the authors prove that the coin commitment appears as a leaf of a Merkle tree with root rt? Apparently, the authors ...
2
votes
0answers
66 views

How does ZK-snark work in zcash?

For a public one-way function $f()$, we can use zero proof to prove I know some secret $x$, such that the output of $x$ is a specific number $y$. However, in zcash, I need to prove that I have some ...
2
votes
2answers
173 views

Fiat Shamir transformation of zero knowledge proof

Consider the following three stage interactive zero knowledge proof The prover sends some information $a$ to the verifier. The verifier picks a challenge $c\in \{0 ,1\}$ Depending on the challenge, ...
0
votes
0answers
29 views

Zercoin: I have to store an infinity number of commitments?

When I want to spend a zero coin, I reveal some sequence number S and a zero-knowledge proof that I know some r and ...
0
votes
0answers
70 views

Practicality of zero-knowledge proofs

I have on more than one instance come across statements which suggest that zero-knowledge proofs are not practical. One example is: "Our theoretical constructions use zero-knowledge proofs, and ...
0
votes
0answers
45 views

Zercoin: Where is the “interaction” in the zero-knowledge-proof?

Unlike Zerocash, Zerocoin's zero-knowledge-proof is always referred to as being interactive? Otherwise, Zercoin would be called non-interactive zero-knowledge-proof. Interaction in a zero-knowledge-...
2
votes
1answer
44 views

Maintaining validity of ZKP throughout re-randomization of homomorphic ciphertext without linkability to previous ciphertext

Question: How is it possible to adapt a ZKP for a homomorphic ciphertext to still be valid after said ciphertext has been re-randomized? Context: In a lot of e-voting systems homomorphic encryption ...
2
votes
1answer
177 views

zk-SNARKs vs. Zk-STARKs vs. Bulletproofs: definitions

I have become quite familiar with Bulletproofs the last few months. Bulletproofs is the name given to a zero-knowledge proof system for arithmetic circuits, by Benedikt Bünz et al. It is a specific ...
2
votes
1answer
115 views

Proof of application of $f(x)$ without disclosing input $x$

I have three nodes in a network: $\mathcal{S}$,$\mathcal{T}$,$\mathcal{R}$. $\mathcal{S}$ supplies data $x$ to $\mathcal{T}$. $x$ is signed so $\mathcal{T}$ knows it actually comes from $\mathcal{S}$...
1
vote
1answer
110 views

Zero knowledge proof for opening of Pedersen commit and discrete logarithm

I am looking for a proof of knowledge as such: $PK\{ (x,r) : C = g^xh^r \land V = g^x\}$ Where $C, V, g$ and $h$ are public information and $x$ and $r$ is known only to the prover. I.e. I have a ...
0
votes
0answers
40 views

Relationship between special RSA modulus and quadratic residue in CL (Camenisch-Lysyanskaya) signature

I'm studying the CL(Camenisch-Lysyanskaya) signature (A signature scheme with efficient protocol proposed by Camenisch-Lysyanskaya). However, I cannot understand ...
1
vote
1answer
124 views

Zero knowledge proof of equality of discrete log and hash preimage

So my question is as follows: We know that we can prove in zero-knowledge equality of discrete logs, for example to prove equality of committed values we can prove in ZK for $g^xh^y$ and $g^{x'}h^{y'}$...
0
votes
1answer
35 views

Practical probabilistic proof systems not based on polynomials

All practical probabilistic proof/argument systems I know of are based upon polynomial identity testing in finite fields. These constructions include QAPs, STARKs, GKR and many variants. In particular,...
7
votes
1answer
72 views

Is SZK better than CZK?

Is it better to have statistical zero-knowledge or computational zero- knowledge in a system? If it depends, is there a slightly accurate generalisation that can be made? Maybe one can be somewhat ...
1
vote
0answers
80 views

System of constraints in Sonic zk-SNARK protocol

I am reading up on Sonic: Zero Knowledge SNARKS from Linear - Sized Universal And Updateable Structured Reference Strings. There is an example of representing $\ x^2 + y^2 = z $ constraint (page 7 of ...
4
votes
0answers
77 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 ...
2
votes
1answer
121 views

Zero Knowledge Proofs: to establish a public key cryptography encryption

I am very interested to know in the general sense how two parties who know each other are able to continue a conversation IF and ONLY IF they both earn the same salary. For example, we have a person X ...
3
votes
1answer
56 views

Bulletproofs with ranges not in power of two

I am new to bulletproofs. From what I understand, if I was to do a range proof using bulletproofs, both the start and end number have to be a power of 2. is there any algorithm/approach which can be ...
2
votes
0answers
84 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 ...
1
vote
2answers
88 views

In zero knowledge proofs, would it make a difference if the prover is deterministic or probabilistic?

In zero knowledge proofs, would it make a difference if the prover is deterministic or probabilistic? As the verifier can simulate the prover's interaction with him, I assumed that the prover would ...
1
vote
0answers
51 views

Sigma Protocol with Privacy-preserving Discrete Logarithms?

I've been reading up on Sigma Protocols and Fiat-Shamir Heuristic. There is a small problem I see here that is possibly already solved, but I'd like to know if it has a solution. Peggy wants to prove ...