Questions tagged [fiat-shamir]

The Fiat–Shamir heuristic takes an interactive proof of knowledge and uses this as base to create a digital signature.

Filter by
Sorted by
Tagged with
4 votes
1 answer
143 views

Alternatives of how the Fiat-Shamir transform random oracle is applied to a protocol

The Fiat-Shamir transform typically works by substituting (public) coin tosses from the verifier by hashes of the prover's messages until this point, i.e.: $$H(x,\alpha_1) = \beta_1, \\ H(x,\alpha_1, \...
  • 593
0 votes
1 answer
51 views

Proof of equality without involving Peggy after the fact

The setup is the following: Alice has a secret x Alice can generate proofs P1, P2, P3, ... Bob (an outsider) should be able to ...
  • 177
2 votes
2 answers
140 views

Why are interactive Zero-Knowledge-Proofs deniable?

When reading about the comparison of interactive and non-interactive Zero-Knowledge-Proofs, I came across the statement that non-interactive Zero-Knowledge-Proofs are not deniable compared to ...
  • 23
1 vote
1 answer
69 views

Why is the following not a ZKP for discrete log?

Before looking at the textbook ZKP for discrete log, I tried to construct one myself. This turned out quite different to the textbook one, and I've been wondering what might be wrong with it? (I was ...
  • 311
2 votes
0 answers
91 views

Quantitative security of signature scheme obtained by Fiat-Shamir tranform

I'm looking for a quantitative yet simple proof of the EUF-CMA security of a signature scheme obtained by Fiat-Shamir transform. Recall the Fiat-Shamir transform starts from a 3-pass identification ...
  • 131k
2 votes
0 answers
57 views

Meta Reduction in Fiat Shamir Transformation

What is meant by meta reduction? What does it achieve and how is it different from the normal reduction technique?
2 votes
0 answers
103 views

How to extract witness from a non-interactive lattice-based proof?

I'm trying to figure out how to construct an extractor for a non-interactive lattice-based proof. Specifically, I'm curious about the Fiat-Shamir transform applied to a five-move interactive protocol. ...
  • 474
4 votes
1 answer
83 views

Can voters be authorities at the same time?

There is an encryption scheme where the votes are encrypted with ElGamal and the decryption key is the secret that is shared among the authorities. After everybody voted they publish their part of the ...
  • 141
3 votes
1 answer
423 views

Grinding in the Fiat-Shamir heuristic

The Fiat-Shamir heuristic is assumed to substitute public-coin messages from the verifier by hashes of the prover's messages until this point, i.e.: $$H(\alpha_1) = \beta_1, \\ H(\alpha_1, \alpha_2) = ...
  • 593
3 votes
1 answer
150 views

How does the simulator generate a correct transcript under HVZK with the Fiat-Shamir heuristic?

Background I understand the interactive version of Schnorr's protocol and I understand how the simulator can generate an output that is i.i.d to the output of the prover-verifier: Question What I don'...
1 vote
1 answer
164 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
2 answers
103 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
1 answer
104 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
1 answer
38 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
1 answer
77 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
1 answer
227 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
3 answers
192 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
0 answers
94 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 ...
  • 1,145
7 votes
1 answer
489 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 ...
  • 593
1 vote
0 answers
67 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'...
  • 43
5 votes
1 answer
189 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 ...
  • 113
3 votes
1 answer
374 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 ...
  • 264
0 votes
1 answer
123 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 ...
  • 474
0 votes
1 answer
113 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
1 answer
230 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)$ ...
  • 325
0 votes
0 answers
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 ...
  • 1
0 votes
2 answers
234 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 ...
6 votes
2 answers
1k 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
0 answers
86 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 ...
  • 177
2 votes
1 answer
238 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-...
  • 1,344
5 votes
1 answer
343 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 ...
  • 243
1 vote
1 answer
122 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
1 answer
56 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
1 answer
111 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 ...
  • 33
2 votes
2 answers
127 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 ...
  • 842
0 votes
1 answer
299 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 ...
  • 195
1 vote
0 answers
384 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 ...
  • 23
3 votes
1 answer
857 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 ...
  • 247
3 votes
1 answer
430 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 ...
  • 133
3 votes
1 answer
518 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
1 answer
403 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 ...
  • 229
3 votes
1 answer
712 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
3 answers
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 ...
  • 533
3 votes
0 answers
206 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
0 answers
125 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 ...
6 votes
1 answer
692 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
0 answers
55 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
1 answer
191 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 ...
  • 31
1 vote
1 answer
185 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 ...
  • 113
1 vote
0 answers
180 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 ...
  • 11