Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# Questions tagged [fiat-shamir]

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

34 questions
Filter by
Sorted by
Tagged with
33 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)$ ...
46 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 ...
109 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 ...
123 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, ...
45 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 ...
44 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-...
81 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 ...
56 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?
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 ...
70 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 ...
71 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 ...
155 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 ...
101 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 ...
394 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 ...
192 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 ...
267 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, ...
214 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 ...
450 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 ...
837 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 ...
140 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 ...
94 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 ...
378 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 ...
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?
171 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 ...
167 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 ...
166 views

390 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 ...