Questions tagged [fiat-shamir]
The fiat-shamir tag has no usage guidance.
27
questions
1
vote
1answer
43 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
36 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
64 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
62 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
111 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
56 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
302 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
145 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
228 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
188 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
0answers
399 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
702 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
115 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
91 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
337 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
40 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
167 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
161 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
162 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
203 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
617 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
129 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
356 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
573 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" ...
