Questions tagged [fiat-shamir]
The Fiat–Shamir heuristic takes an interactive proof of knowledge and uses this as base to create a digital signature.
69
questions
1
vote
0
answers
20
views
How to convert Lattice based signature to R1CS statements?
How can we convert a lattice-based signature (like based on Fiat Shmair with abort e.g. Dilithium) to R1CS?
0
votes
1
answer
67
views
Can a Sigma protocol be transformed into a signature of knowledge through Fiat-Shamir transform？
As is well known, a sigma protocol can be transformed into a NIZK protocol through a Fiat-Shamir transform.
But can the Sigma protocol be transformed into a signature of knowledge in a similar manner?
...
- 63
1
vote
0
answers
31
views
Disjunctive ZK Proof of knowledge of discrete log
I want to construct a non-interactive ZK proof that in a set of pairs of group (where the DDH-assumption holds true) elements:
$(g_1, Y_1), (g_2, Y_2), ..., (g_n, Y_n)$
, the prover knows at least one ...
- 21
2
votes
0
answers
73
views
Fischlin vs. Fiat-Shamir Performance
Using Fiat-Shamir, an interactive 3-round sigma protocol can be compiled into a non-interactive zero-knowledge proof in the random oracle model.
A NIZK through Fiat-Shamir is not UC-Secure due to ...
- 143
1
vote
2
answers
158
views
How to prove that a Pedersen commitment has the same value as at least one of a set of other Pedersen commitments, without revealing which
A prover has two pedersen commitments, $V_{a}=G\cdot a+H\cdot r_a$ and $V_{b}=G\cdot b+H\cdot r_b$, which commit the values $a$ and $b$ respectively.
The prover has another commitment $S_{\sigma}=G\...
- 11
2
votes
1
answer
42
views
batch Fiat-Shamir
The prover has $n$ group elements $g_1, ..., g_n$ and wishes to demonstrate the knowledge of the discrete logarithm to base $g$ for each of them, i.e, for each $i \in [1,n]$ she knows some $e_i$ s.t. $...
- 99
1
vote
1
answer
73
views
Ensure deniability of an interactive zero knowledge proof
Suppose that Peggy(prover) and Victor(verifier) are running some zero knowledge proof protocol that does not rely on hidden verifier secrets. The verifier generates randomly chosen challenge values ...
- 1,701
2
votes
1
answer
82
views
Fiat-Shamir with interactions
Suppose we have a standard $\Sigma$-protocol for proving the knowledge of a witness $x$ for the statement $y$. It has an honest-verifier ZK and special soundness. Now we do an unusual modification to ...
- 548
3
votes
0
answers
112
views
Prove DSA signature scheme is EUF-CMA secure
I want to prove that the DSA signature scheme is EUF-CMA secure in the random oracle model, if the discrete logarithm problem is hard. I know it can be proved by the following two parts:
Discrete ...
- 31
2
votes
1
answer
61
views
Lagrange interpolation in the exponent
I am going over the paper https://verifiable-timed-signatures.github.io/web/assets/paper.pdf and on page 5, it says the following:
Suppose I have a t-out-of-n threshold sharing scheme for the secret $\...
- 45
1
vote
1
answer
164
views
Real-world instantiation of NIZK protocol from Fiat-Shamir
So I understand how one can use Fiat-Shamir to turn a HVZK sigma protocol into a non-interactive zk protocol in the random oracle model. My problem though is I don't understand why is this useful.
If ...
4
votes
1
answer
190
views
Alternatives of how the Fiat-Shamir transform random oracle is applied to a protocol
The Fiat-Shamir transform typically works by substituting (public) coin tosses from the verifier by hashes of the prover's messages until this point, i.e.: $$H(x,\alpha_1) = \beta_1, \\ H(x,\alpha_1, \...
- 722
0
votes
1
answer
64
views
Proof of equality without involving Peggy after the fact
The setup is the following:
Alice has a secret x
Alice can generate proofs P1, P2, P3, ...
Bob (an outsider) should be able to ...
- 177
2
votes
2
answers
245
views
Why are interactive Zero-Knowledge-Proofs deniable?
When reading about the comparison of interactive and non-interactive Zero-Knowledge-Proofs, I came across the statement that non-interactive Zero-Knowledge-Proofs are not deniable compared to ...
- 23
1
vote
1
answer
96
views
Why is the following not a ZKP for discrete log?
Before looking at the textbook ZKP for discrete log, I tried to construct one myself. This turned out quite different to the textbook one, and I've been wondering what might be wrong with it? (I was ...
- 383
2
votes
0
answers
132
views
Quantitative security of signature scheme obtained by Fiat-Shamir tranform
I'm looking for a quantitative yet simple proof of the EUF-CMA security of a signature scheme obtained by Fiat-Shamir transform.
Recall the Fiat-Shamir transform starts from a 3-pass identification ...
- 138k
2
votes
0
answers
66
views
Meta Reduction in Fiat Shamir Transformation
What is meant by meta reduction? What does it achieve and how is it different from the normal reduction technique?
2
votes
0
answers
123
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. ...
- 548
4
votes
1
answer
85
views
Can voters be authorities at the same time?
There is an encryption scheme where the votes are encrypted with ElGamal and the decryption key is the secret that is shared among the authorities. After everybody voted they publish their part of the ...
- 141
3
votes
1
answer
558
views
Grinding in the Fiat-Shamir heuristic
The Fiat-Shamir heuristic is assumed to substitute public-coin messages from the verifier by hashes of the prover's messages until this point, i.e.: $$H(\alpha_1) = \beta_1, \\ H(\alpha_1, \alpha_2) = ...
- 722
3
votes
1
answer
243
views
How does the simulator generate a correct transcript under HVZK with the Fiat-Shamir heuristic?
Background
I understand the interactive version of Schnorr's protocol and I understand how the simulator can generate an output that is i.i.d to the output of the prover-verifier:
Question
What I don'...
1
vote
1
answer
243
views
Zero Knowledge Discrete Logarithm on Elliptic Curves
Can the Discrete Logarithm ZK be implemented on elliptic curves? It seems that such an implementation should look like the following:
$Y = \alpha G$
Random pick $v$
$t = vG$
$c = H(G, y, t)$
$r = v - ...
- 141
0
votes
2
answers
156
views
Discrete Logarithm Fiat-Shamir Parameters Selection
According to Fiat–Shamir heuristic there are two parameters of the algorithm: big prime number $p$ and primitive root $g$. Thus several questions arise:
How big should the prime number $p$ be? How to ...
- 141
0
votes
1
answer
168
views
Several Discrete Logarithm Zero Knowledge Proof
According to Wiki there is an approach for proving knowledge of $x$ such that $g^x = y$. How can I prove that I know $x_1, x_2$ such that $g^{x_1} = y_1, g^{x_2}=y_2$. Of course, I can make these ...
- 141
0
votes
1
answer
45
views
Parameter c in Fiat–Shamir heuristic
According to Wiki there is a possibility of non-interactive Zero-Knowledge Proof of discrete logarithm if challenge $c$ is computed via a hash function. But what is the purpose of $c$? Why can not I ...
- 141
1
vote
1
answer
90
views
Impact of super-polynomial extractors on the security of a zero-knowledge proof
Interactive zero-knowledge arguments are proven to be secure in three parts:
completeness (the verifier accepts if the prover is honest)
soundness (a dishonest prover cannot convince a verifier)
zero-...
- 2,330
3
votes
1
answer
492
views
How to construct a strong Fiat-Shamir in zero-knowledge proof?
I'm new to zero-knowledge proof. Recently, I'm implementing a non-interactive zero-knowledge proof using the Schnorr scheme. I understand the non-interactive zero-knowledge proof needs random oracle ...
- 31
0
votes
3
answers
253
views
The challenge c in Sigma protocol (using Fiat Shamir)
As is known to all, the following picture depicts a sigma protocol, and to eliminate the interactivity, Prover can generate c by hashing (t, y) using Fiat Shamir transform. My question is:
1). Can c ...
2
votes
0
answers
113
views
Why Fiat-Shamir based signatures incur a security loss?
I read here that assuming we have a Fiat-Shamir (FS) signature $\Sigma$ that is secure based on the hardness of a particular hard problem $\Pi$. Then, the security proof of $\Sigma$ in the classical ...
user4936
7
votes
1
answer
506
views
What does it mean to be "sound"?
I've been reading this in many places and I still don't properly understand what it means to be "sound". As an example of what I am asking for:
The Fiat-Shamir transfrom is sound in the ...
- 722
1
vote
0
answers
71
views
Is using Fiat-shamir Heuristic safe?
What I'd like to do is to have the Prover store a value x where x remains hidden.
From x, I'...
- 43
5
votes
1
answer
213
views
Fiat-Shamir for $(2n + 1)$
Consider the following $(2n+1)$ protocol:
$\mathcal{P}$ and $\mathcal{V}$ engage in an interaction where $\mathcal{P}$ consecutively sends a message $a_i$ answered by $\mathcal{V}$ with a random ...
- 113
3
votes
1
answer
544
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 ...
- 264
0
votes
1
answer
152
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 ...
- 548
0
votes
1
answer
142
views
How many rounds is needed to implementing Schnorr Non-Interactive zero-knowledge protocol
We can use Fiat-Shamir heuristic to replace 3-move Schnorr's protocol with 1-move non-interactive protocol.
When I implement this non-interactive protocol( ref. https://en.wikipedia.org/wiki/Fiat%E2%...
2
votes
1
answer
292
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)$ ...
- 325
0
votes
0
answers
54
views
Why do we hash the random challenge in Fiat-Shamir heuristic? [duplicate]
I had a quick question for all.
Why do we hash the random challenge in Fiat-Shamir heuristic? If we hash the public key of Prover it should be enough for the verifier to prove non-repudiation?
What ...
- 1
0
votes
2
answers
262
views
Fiat-Shamir transform: reliance on hash input by interactive proof
Peggy would like to prove to Victor that she knows the discrete logarithm of $y$ based $g$; that is, she knows $x$ such that $y = g^x \bmod p$. One round of the interactive proof protocol consists of ...
7
votes
2
answers
1k
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, ...
- 693
1
vote
0
answers
98
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 ...
- 177
2
votes
1
answer
311
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,394
5
votes
1
answer
382
views
Zero-Knowledgeness of Fiat-Shamir heuristic
I have read about the Fiat-Shamir heuristic for making an interactive proof of knowledge into a non-interactive proof of knowledge. If I apply this to zero-knowledge proof of knowledge, it seems to me ...
- 243
1
vote
1
answer
135
views
How would P=BPP affect zero knowledge proofs?
If there were a proof to show that P=BPP, how would this affect zero knowledge proofs and the fiat-shamir heuristic for Turing an interactive proof into a non-interactive proof?
- 1,303
0
votes
1
answer
57
views
Difficulty understanding 'random square root' in enhancement to fiat-shamir
This was published in 1986 and I'm trying to reproduce it in an assignment. It's a small variation on fiat-shamir, by the original author, which does away with a public key (and supposedly drastically ...
1
vote
1
answer
125
views
Upper bound for the length of non-interactive zero-knowledge proofs of knowledge
In a hybrid protocol $\pi$ for which I want to proof uc-security in the absence of corrupted parties, there is an ideal functionality $\mathcal{F}_{SMT}$ for secure message transfer that leaks the ...
- 33
2
votes
2
answers
149
views
Zero Knowledge for Low Entropy Witness
For any PPT prover ($p$) and verifier ($v$), imagine I have a low entropy witness, say smaller than $2^8$. Now, let us say I have a dlog statement in the form of $y = g^w$. Theory says I could use a ...
- 862
0
votes
1
answer
329
views
How to compute a challenge c using Fiat Shamir?
I have a prover and verifier. They are engaged in a zero-knowledge proof protocol. A verifier sends a challenge $c$ to the prover so he can compute a proof using the value $c$. How to use Fiat Shamir ...
- 205
1
vote
0
answers
408
views
Need tips on how to break Fiat-Shamir sigma-protocol (programming challenge)
I'm completely stuck on an university programming challenge and I need some tips to get me out of the valley I'm in, you don't need to give the full answer if you do not wish to.
What we have:
Fiat ...
- 23
3
votes
1
answer
912
views
Fiat-Shamir zero knowledge protocol
In Fiat-Shamir protocol, the final calculation is
$$y^2=x\,v^c$$
Where $c$ is the random $\{1,0\}$, $x$ is the witness and $v$ is the public key $s^2 \bmod n$.
My questions are:
What stops the ...
- 247
3
votes
1
answer
529
views
What is the relationship between a NIZK protocol and a digital signature scheme?
I am reading about the Fiat-Shamir heuristic to take a $\Sigma$-protocol into a non-interactive zero-knowledge proof (NIZK). I am now wondering whether there is a relationship between a NIZK proof and ...
- 133