Questions tagged [fiat-shamir]
The Fiat–Shamir heuristic takes an interactive proof of knowledge and uses this as base to create a digital signature.
58
questions
4
votes
1
answer
143
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, \...
- 593
0
votes
1
answer
51
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
140
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
69
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 ...
- 311
2
votes
0
answers
91
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 ...
- 131k
2
votes
0
answers
57
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
103
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. ...
- 474
4
votes
1
answer
83
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
423
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) = ...
- 593
3
votes
1
answer
150
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
164
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
103
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
104
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
38
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
77
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,230
3
votes
1
answer
227
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
192
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
94
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 ...
- 1,145
7
votes
1
answer
489
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 ...
- 593
1
vote
0
answers
67
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
189
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
374
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
123
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 ...
- 474
0
votes
1
answer
113
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
230
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
53
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
234
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 ...
6
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, ...
- 659
1
vote
0
answers
86
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
238
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,344
5
votes
1
answer
343
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
122
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,263
0
votes
1
answer
56
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
111
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
127
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 ...
- 842
0
votes
1
answer
299
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 ...
- 195
1
vote
0
answers
384
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
857
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
430
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
3
votes
1
answer
518
views
How can an interactive ZKP become non-interactive?
From my understanding, random oracles (hash functions) are used in the Fiat-Shamir heuristic to generate non-interactive ZKPs. I think I have a good grasp of how interactive ZKPs in this scheme work, ...
0
votes
1
answer
403
views
Proof of knowledge and replay attacks
I was reading the ZK proof of knowledge of Schnorr and fiat shamir transformation, and I figured out that replay attacks are possible. Why these protocols don't take into account this attack? That ...
- 229
3
votes
1
answer
712
views
Feige–Fiat–Shamir identification scheme: Question about a part of the ZK protocol
My question (at the bottom) is in regards to the part of the protocol where the Verifier challenges the Prover by sending a bit b where ...
- 31
4
votes
3
answers
1k
views
What is the benefit of zero knowledge identification (Fiat Shamir) over a standard digital signature?
Let's say there is a public key $v$.
Peggy has to prove to Victor that she has the corresponding private key $a$. Of course she doesn't want to disclose $a$ to Victor, but just to prove that she has ...
- 533
3
votes
0
answers
206
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 ...
2
votes
0
answers
125
views
Could be El-Gamal signature scheme constructed via Fiat-Shamir heuristic?
For example, Schnorr signature is pretty similar to El-Gamal.
And everywhere where Schnorr signature is explained (for example - on Wikipedia),
there's said that there's Schnorr scheme which is ...
- 684
6
votes
1
answer
692
views
Fiat-Shamir vs Common Reference String to make NIZK
I was introduced to NIZK from the notion of CRS: since we have a trusted CRS, then a prover can simulate a challenge by querying the CRS.
Similarly, the prover can simulate the challenge of a ...
- 743
1
vote
0
answers
55
views
Valid reencryption of simple mixnet
How can I provide a non interactive proof using the Fiat Shamir method for the valid reencryption of a simple mixnet?
- 21
3
votes
1
answer
191
views
Why are the factors p and q (for n) secret in Fiat-Shamir Authentication?
I am studying about this authentication and I don't understand why the factors of $n$ are kept secret as I can't see how they would give the prover or verifier anymore information.
My professor said ...
- 31
1
vote
1
answer
185
views
Why am I getting a wrong output when implementing Feige-Fiat-Shamir ID protocol?
I am trying to implement the Feige-Fiat-Shamir identification protocol. I've read another posting here on this site and I tried to adapt - however the end results always fail to match. Maybe because ...
- 113
1
vote
0
answers
180
views
Fiat Shamir with S^3
I'm trying to do Fiat Shamir but with $I = S^3 \pmod n$ where $S$ is the secret key. How will I prove that I know the cube root? I tried doing the old formula but with instead with $(RS)^3 = x*I \pmod ...
- 11