13
votes
Accepted
What does it mean to be "sound"?
An interactive or non-interactive protocol is said to be sound for a language $\mathcal{L}$ if it is "hard" for a (malicious) prover $\textsf{P}$ to convince a verifier $\textsf{V}$ of a ...
- 5,408
9
votes
Accepted
Grinding in the Fiat-Shamir heuristic
What avoids the prover to grind over his messages to be able to forge a fake proof?
We could ask exactly the same question with respect to a random oracle as well! What prevents the prover to grind ...
- 20.8k
8
votes
Accepted
Fiat Shamir transformation of zero knowledge proof
You are correct about the attack, given the way you have defined the Fiat-Shamir-transformed protocol.
Since Fiat-Shamir is subtle for multi-round protocols, the standard way to resolve this is to ...
- 14.1k
6
votes
Fiat-Shamir vs Common Reference String to make NIZK
Since there are no answers here yet, I'll write down my own opinion.
The Fiat-Shamir heuristic for augmenting Sigma-protocols (or possibly any 3-move honest-verifier ZKPoK?) works as follows: For the ...
5
votes
How to construct a strong Fiat-Shamir in zero-knowledge proof?
Quick remarks:
the Fiat-Shamir transform is implemented with a standard hash function (e.g. SHA-256 or SHA-3). Random oracles do not exist in the real world: it is only in the security analysis that ...
- 20.8k
5
votes
Accepted
How would P=BPP affect zero knowledge proofs?
It would not affect this at all. Note that under reasonable complexity hardness assumptions, it holds that P=BPP. So, even though we don't know how to prove this unconditionally (and in fact seem far ...
- 28.1k
5
votes
Accepted
Problem with Fiat-shamir on poly-round interactive protocol?
Yes, there are examples of non-constant round interactive protocols that are unsound when the Fiat-Shamir transform is applied even in the random-oracle model. Note that for constant-round protocols ...
- 5,408
4
votes
Accepted
Zero-Knowledgeness of Fiat-Shamir heuristic
In the random-oracle model, it has been shown that the Fiat-Shamir transform preserves the soundness and zero-knowledge of certain families of zero-knowledge (proof of knowledge) protocols (e.g., ...
- 5,408
4
votes
Accepted
Alternatives of how the Fiat-Shamir transform random oracle is applied to a protocol
There are several points:
Your last Fiat-Shamir scheme can be viewed as $H(x, \alpha_1)$, $H(H(x, \alpha_1), \alpha_2)$, $H(H(H(x, \alpha_1), \alpha_2), \alpha_3), ...$. If $H$ is a random oracle, ...
- 939
3
votes
Accepted
Fiat-Shamir for $(2n + 1)$
You can find the security proofs for 5-round Fiat-Shamir:
Ming-Shing Chen and Andreas Hülsing and Joost Rijneveld and Simona Samardjiska and Peter Schwabe: From 5-pass MQ-based identification to MQ-...
- 2,186
3
votes
Accepted
Why is the Fiat-Shamir heuristic deemed secure in the ROM?
The paper by Goldwasser and Tauman is another paper in the series of the failure of the random oracle model; its novelty is applying this principle to the Fiat-Shamir paradigm and interactive ...
- 28.1k
3
votes
Accepted
Impact of super-polynomial extractors on the security of a zero-knowledge proof
The philosophy behind the extractor and knowledge is that if the prover can generate the proof, then it could itself run the extractor. Therefore, if it can prove, then it knows the witness.
If the ...
- 28.1k
3
votes
Accepted
What is the relationship between a NIZK protocol and a digital signature scheme?
Recall that in strong existential unforgeability for
digital signatures, we want it to be the case that even after seeing many signatures under different instances, it should still not be possible to ...
- 311
3
votes
Zero Knowledge for Low Entropy Witness
$\newcommand{\NP}{\mathsf{NP}}\newcommand{\lang}{\mathcal{L}}\newcommand{\rel}{\mathcal{R}}\newcommand{\bin}{\{0,1\}}$
Let $\lang\subseteq\bin^*$ be any $\NP$ language with a corresponding $\NP$ ...
- 7,038
3
votes
Why are the factors p and q (for n) secret in Fiat-Shamir Authentication?
Knowledge of $p$ and $q$ makes computing square roots modulo $n=pq$ easy.
Using the Tonelli-Shanks algorithm, one may determine square roots modulo $p$ and $q$ individually and then combine them to a ...
- 12.2k
3
votes
Accepted
Why is the following not a ZKP for discrete log?
Good question. Note that being "zero-knowledge" means more than "not learning x". It means that you shouldn't learn anything at all from the protocol (this is formalized with the ...
- 186
3
votes
Accepted
Fischlin vs. Fiat-Shamir Performance
Please check the work here: https://eprint.iacr.org/2024/526
Just quoting the number there, the running time of generating a single discrete log proof on secp256k1 curve on Apple M3 Pro CPU:
Fiat-...
- 46
3
votes
Accepted
Random Oracle in Fiat-Shamir Transform (from Katz-Lindell Textbook)
Anything can be encoded as a bitstring, we just need to be a bit careful as to preserve the security of the random oracle.
Let $I\in S$. Then what is meant here by $H(I,m)$ is actually $H(\psi(I,m))$, ...
- 7,038
2
votes
Accepted
Why am I getting a wrong output when implementing Feige-Fiat-Shamir ID protocol?
The first problem is, that you calculated $v_i$ wrong right at the start.
$$v_i = s_i^2 \mod n$$
This means:
$$v_1 = 5^2 = 25 \mod 77$$
$$v_2 = 12^2 = 67 \mod 77$$
$$v_3 = 37^2 = 60 \mod 77$$
Then at ...
- 12.8k
2
votes
Feige–Fiat–Shamir identification scheme: Question about a part of the ZK protocol
If $b$ was always the same value, you could convince the Verifier that you have the private key even though you actually don't!
Case $b = 1$:
Instead of sending $x = {\text{randNum}}^2 \bmod n$, the ...
- 21
2
votes
What is the benefit of zero knowledge identification (Fiat Shamir) over a standard digital signature?
Solution 1 has some weakness when the verifier is malicious. If the prover's private key $a$ is used for decryption, Solution 1 provides the verifier with a decryption oracle, i.e., a malicious ...
- 2,735
2
votes
Challenges of Fiat-Shamir Transformation of ZK Proof / Sigma Protocol
If the challenge is calculated as $H(\Sigma_1)$ the transform is called the weak Fiat-Shamir (wFS) transform. On the other hand, when the challenge is computed as $H(x\mathbin\Vert \Sigma_1)$ the ...
- 1,194
2
votes
Discrete Logarithm Fiat-Shamir Parameters Selection
There seems to be a confusion here. As fgrieu stated correctly, Fiat-Shamir is a method to make a public-coin (honest-verifier) zero-knowledge proof non-interactive. You do not need to select any ...
- 20.8k
2
votes
Accepted
Parameter c in Fiat–Shamir heuristic
Does it make the system vulnerable?
Yes; if the prover knew apriori what value of $c$ that will be used, the prover could easily issue a proof (even if she didn't know the discrete log).
To prove ...
- 150k
2
votes
Accepted
Zero Knowledge for Low Entropy Witness
Pedersen commitments would appear to address your problem.
A Pedersen commitment is a value $t = g^w h^r$ (for the witness value $w$ and a random value $r$); someone cannot recover $w$ from that ...
- 150k
2
votes
The challenge c in Sigma protocol (using Fiat Shamir)
No. Since 0x1234, 0x4321 is public and thus known ahead of the execution, the prover knows the challenge c before sending t. This violet the requirement of the sigma protocol: c is sent to P after t ...
- 21
2
votes
Accepted
Second challenge in Fiat-Shamir for 5-round schemes
These are equivalent. Given that the first challenge is a deterministic function of the statement and $\alpha_1$, it makes no difference. What is crucial is just to include the statement, and the ...
- 28.1k
2
votes
Meta Reduction in Fiat Shamir Transformation
pls refer to this paper which I'm studying: On the Impossibility of Tight Cryptographic Reductions.
Meta reduction is the reduction of a reduction! We can use it to rule out some impossibile results ...
- 48
2
votes
Accepted
Why are interactive Zero-Knowledge-Proofs deniable?
Let's begin with interactive ZKPs: the Zero-Knowledgeness is proved by the existence of a Simulator able to produce a transcript indistinguishable from the one obtained by the actual ZKP execution, ...
- 730
2
votes
Accepted
batch Fiat-Shamir
One way to answer your question is to check if the following proof system is sound:
Prover sends $R_1,\dots,R_n$
Verifier sends challenge $c$
Prover responds with $s_1,\dots,s_n$
Verifier checks for ...
- 950
Only top scored, non community-wiki answers of a minimum length are eligible