Questions tagged [fiat-shamir]
The Fiat–Shamir heuristic takes an interactive proof of knowledge and uses this as base to create a digital signature.
41
questions
2
votes
0answers
59 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 ...
7
votes
1answer
425 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 ...
1
vote
0answers
42 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'...
4
votes
1answer
123 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 ...
2
votes
1answer
125 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 ...
0
votes
1answer
59 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 ...
0
votes
1answer
39 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
1answer
91 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)$ ...
0
votes
0answers
52 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 ...
0
votes
2answers
170 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 ...
2
votes
2answers
388 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, ...
1
vote
0answers
64 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 ...
2
votes
1answer
104 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-...
5
votes
1answer
157 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 ...
1
vote
1answer
90 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?
0
votes
1answer
43 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
1answer
81 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 ...
1
vote
2answers
78 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 ...
0
votes
1answer
203 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 ...
1
vote
0answers
233 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 ...
3
votes
1answer
628 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 ...
2
votes
1answer
282 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 ...
3
votes
1answer
335 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
1answer
244 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 ...
3
votes
1answer
603 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 ...
3
votes
3answers
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 ...
3
votes
0answers
167 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
0answers
105 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 ...
5
votes
1answer
488 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 ...
1
vote
0answers
44 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?
3
votes
1answer
183 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 ...
1
vote
1answer
171 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 ...
1
vote
0answers
175 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 ...
1
vote
1answer
242 views
Stern identification scheme to signature scheme
I'm trying to understand the comment in the page 103 of the book Postquantum Cryptography. about convert the identification Stern procedure for signing. Can you write an example of signature of this ...
0
votes
2answers
238 views
Would the Fiat Shamir identification scheme be more secure if I design it with an exponents higher than 2?
Let's say both Prover and Verifier would use nth power instead of 2nd when creating public keys and when verifying. I know it would slow it down but would that cause the protocol to be more secure?
1
vote
1answer
294 views
How does knowing the factorization of N help to obtain the secret?
Assuming $x=a^2 \pmod n$ and knowing $x$, $p$, $q$ how is it possible to obtain $a$?
1
vote
0answers
683 views
Zero Knowledge Non Interactive Proof with random oracle
I am trying to write an assay about Non Interactive Zero-Knowledge proofs and would like to take the simple discrete logarithm problem example fallowing the Feige-Fiat-Shamir heuristics.
I understand ...
1
vote
1answer
135 views
Fiat–Shamir: why do r and s have to be smaller than n?
I have a question regarding the Fiat–Shamir identification protocol. In this source (pdf) for example it says on pages 9 and 10 that the random commitment $r$ and the private key $s$ have to be ...
1
vote
1answer
440 views
Fiat-Shamir security problem question
I am trying to understand the Fiat-Shamir identification protocol, but have a problem with understanding how this protocol is supposed to be save, even if you repeat it several times. I am using ...
1
vote
1answer
3k views
Simplified Fiat-Shamir example generates wrong output
I am trying to implement the Fiat-Shamir identification protocol, however the end results always fail to match. I am using algorithm's description from here.
Preparation:
Select 2 prime integers and ...
8
votes
2answers
633 views
What is the sign bit for in Feige-Fiat-Shamir?
The Feige-Fiat-Shamir identity scheme is based on a ZKP assuming that square roots are "hard" modulo an integer of unknown factorization. The "parallel version" of this protocol includes a "sign bit" ...
