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
21 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
18 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
33 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
0answers
42 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
68 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
24 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
33 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
27 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
33 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
votes
0answers
36 views

zero-knowledge protocol implies the existence of an interactive protocol

How can we prove that for every zero-knowledge protocol there exists an interactive protocol. Any possible hint is welcome.
2
votes
1answer
71 views

Why is the Fiat-Shamir heuristic deemed secure in the ROM?

In their paper On the (In)security of the Fiat-Shamir Paradigm, Goldwasser and Tauman show that the Fiat-Shamir heuristic does not work with any hash function. From the paper: The most important ...
1
vote
1answer
47 views

Is there a simplified article, video, or blog about bulletproofs?

I'm trying to learn about bulletproofs for my master "Enhancing Privacy in E-voting Systems", but the original paper was too hard for me. I also tried to look at this, but it was also too difficult. ...
1
vote
2answers
37 views

Non-trivial examples of a system being a zero-knowledge proof system but not zero-knowledge proof of knowledge

It got me confused these days when I encountered the notions of zero-knowledge proofs (ZKP) and zero-knowledge proofs of knowledge (ZKPoK). As far as I know, the two terms are not the same, but all ...
1
vote
0answers
26 views

How to securely and noninteractively generate a blinding factor in MimbleWimble Pedersen commitment?

I'm working on a prototype which will use MimbleWimble Confidential Assets transaction protocol using Cosmos as the blockchain layer. In my prototype a user is always sending a whole amount to ...
1
vote
2answers
115 views

Sigma protocol with Pedersen commitment and Hash function

Suppose I construct a Pedersen commitment as $g^m h^r$. I could pick the randomness in a "pseudo-random" fashion, such that $r = H(m)$. My questions are as follows: Given that $H$ is collision-...
0
votes
0answers
39 views

How to use libsnark to prove a polynomial like (x-a1)(x-a2)(…)(x-an)=0?

I am just starting to learn zksnark. I am tring to write a demo which supply the set membership proof using libsnark. I was thinking using the polynomial : $(x-a_1)(x-a_2)(\ldots)(x-a_n)$ The "ai" is ...
1
vote
1answer
51 views

Are there any algorithms for which generating any zero-knowledge proofs is not practical?

It is related to my earlier question: Can zkSNARK or other zero-knowledge proofs be used to proof message authenticity without revealing private key? Are there any algorithms for which generating ...
0
votes
0answers
45 views

Discrete log zero knowledge proof lying case

I read the Wikipedia page on a discrete log zkp, but I don't understand how $$C' = g^{r'} \cdot (g^x)^{-1} \bmod p$$ would be calculated. Would it be $$C' = g^{r} \cdot \frac{1}{y} \bmod p$$ ...
0
votes
1answer
53 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
0answers
72 views

How do I prove that a user encrypted the data?

I am using homomorphic encryption, and I need to check whether or not a user's data is actually encrypted. For example, an eCommerce website pulls data from a user called Alice and wants to prove to ...
0
votes
1answer
53 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
42 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 ...
2
votes
1answer
46 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
533 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
50 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
68 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
73 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
48 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
215 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 ...
7
votes
1answer
201 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
102 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
98 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
38 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
2answers
160 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
23 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
237 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
97 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
61 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
253 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
42 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
49 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
56 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 ...
1
vote
0answers
56 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
67 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
76 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
33 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
71 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
96 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
48 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
46 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 ...

1
2 3 4 5
12