Questions tagged [fiat-shamir]
The Fiat–Shamir heuristic takes an interactive proof of knowledge and uses this as base to create a digital signature.
49
questions
0
votes
1answer
71 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 - ...
0
votes
2answers
52 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 ...
0
votes
1answer
45 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 ...
0
votes
1answer
33 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 ...
1
vote
1answer
51 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-...
3
votes
1answer
84 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 ...
0
votes
0answers
64 views
Why in the Fiat-Shamir heuristc for proving the knowledge of a discrete logarithm an hard to invert function has to be used to create the challenge?
Consider this example from Camenisch, J., & Stadler, M. (1997). Proof systems for general statements about discrete logarithms. Technical Report/ETH Zurich, Department of Computer Science, 260..
...
0
votes
3answers
85 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
0answers
75 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
455 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
57 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'...
5
votes
1answer
150 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
219 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
91 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
55 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
144 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
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 ...
0
votes
2answers
199 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 ...
4
votes
2answers
615 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
73 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
153 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
204 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
103 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
46 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
88 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 ...
2
votes
2answers
92 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
245 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
308 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
737 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
336 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
385 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
305 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
660 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 ...
4
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
185 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
110 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
560 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
48 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
187 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
177 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
177 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
272 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
246 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
296 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
708 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
143 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
468 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
668 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" ...
Hot Network Questions
- Supernumerariness
- What happens if a vampire tries to enter a residence without an invitation?
- What is the opposite of deus ex machina?
- Is it okay to mention a mathematical fact that intrigues me in SOP when I don't understand its technical details?
- Is it possible that two neutrons can merge?
- Is it the Job of Physics to Explain Consciousness?
- Compact way to generate variable with 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ
- Inverse Kirby knot
- How can I remove the solder bridges?
- Can an ethernet cable look OK to a cheap cable tester but still have a problem?
- Can the word "rook" be used as a verb in chess?
- What does the word "scalability" mean in terms of Big O?
- Table of content in uppercase
- How might a motile monolith move?
- How do I get over my fear of using power tools?
- train-tests split for extreme multilabel classification
- Explain seemingly non-random figures which arise from random Poisson points with normalization
- Is moving into a rotating frame a Galilean transformation?
- When is swap file harmful?
- Double Spirit Shroud with Death Domain
- Why is the L3 Lagrangian point not perfectly stable? And why is the Earth-Sun L3 point a bit less than one A.U.?
- Is this aerodynamic braking procedure normal in a 747?
- Parentheses Clusters
- Is it right to textually and contextually insist that Revelation 3:10 is a "slam dunk" for the pretrib rapture position?