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

Can zkSNARK or other zero-knowledge proofs be used to proof message authenticity without revealing private key?

The situation: Alice and Bob are exchanging messages encrypted by some known asymmetric encryption protocol. All their encrypted messages, as well as public keys are intercepted by Charlie. Can ...
0
votes
1answer
92 views

Example of a problem for which Zero-Knowledge proof is not sequentially composable

There are notions that a Zero-knowledge proof with auxiliary input is necessary for sequential composition. However, the authors here give a very convoluted example of a system which is not ...
0
votes
1answer
96 views

Second challenge in Fiat-Shamir for 5-round schemes

I'm not sure how to compute the second challenge when applying FS to a 5-round protocol. I've seen TWO different formulas (with and without including the first challenge) and don't know which one is ...
3
votes
1answer
144 views

Schnorr proof of group with unknown order (but the prover know the order)

We assume that we have $n = pq$, where $p = 2p'+1$, $q = 2q'+1$, and all $p, q, p', q'$ are large primes. Pick $g' \gets_R Z_n^*$, and compute $g = (g')^2 \bmod n$. Then we have a generator $g$ for $...
4
votes
1answer
570 views

Randomizable zero-knowledge proofs?

I was wondering whether there exists randomizable zero-knowledge proofs. What I mean by randomizable is that assume I have a zero-knowledge proof of knowledge $\pi$, stating that I know $x \in \mathbb{...
0
votes
1answer
61 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
81 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
106 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
59 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 ,\...
11
votes
1answer
398 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 ...
8
votes
1answer
350 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 ...
1
vote
1answer
192 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
356 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 ...
2
votes
2answers
197 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 ...
3
votes
2answers
260 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
298 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, ...
2
votes
0answers
124 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
348 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 ...
3
votes
1answer
74 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 ...
2
votes
1answer
156 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
104 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
82 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 ...
1
vote
0answers
124 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 ...
2
votes
1answer
214 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
87 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 ...
2
votes
0answers
105 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 ...
1
vote
0answers
153 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
580 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
180 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 ...
3
votes
1answer
172 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 ...
4
votes
2answers
663 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
79 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 ...
2
votes
1answer
73 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 ...
6
votes
2answers
1k 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
121 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}$...
2
votes
1answer
469 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
1answer
148 views

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

I'm studying the CL (Camenisch-Lysyanskaya) signature: Jan Camenisch and Anna Lysyanskaya, A signature scheme with efficient protocol, in proceedings of SCN 2002. However, I cannot understand the ...
2
votes
1answer
292 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'}$...
1
vote
1answer
52 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,...
6
votes
1answer
105 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
104 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
81 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
133 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 ...
4
votes
1answer
78 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 ...
3
votes
0answers
98 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
147 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
73 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 ...
0
votes
1answer
189 views

Breaking zero knowledge protocol for graph hamiltonicity

The FLS zero knowledge protocol for graph hamiltonicity proceeds as follows. The prover (proving graph hamiltonicity of graph G) picks a random cycle graph C, and sends its commitment to verifier. ...
2
votes
1answer
164 views

Problem with Fiat-shamir on poly-round interactive protocol?

I have read in many places that Fiat Shamir technique is used to convert constant round interactive protocols to non-interactive arguments. What would be the problem in applying Fiat Shamir to poly-...
1
vote
1answer
88 views

Is there a zero knowledge proof to show an encrypted blob is the key for a given public key?

Let's say I have a private key x with a corresponding public key y. If I encrypt x as ...

1
3 4
5
6 7
16