Questions tagged [fiat-shamir]
The Fiat–Shamir heuristic takes an interactive proof of knowledge and uses this as base to create a digital signature.
30
questions
1
vote
0answers
39 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 ...
1
vote
1answer
29 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
60 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
52 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
37 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
68 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
64 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
134 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
66 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
337 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
160 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
244 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
203 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 ...
2
votes
1answer
429 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
751 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
119 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
93 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 ...
4
votes
1answer
350 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
41 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
169 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
162 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
163 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
206 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
216 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
289 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
626 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
130 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
366 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
581 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" ...
