Skip to main content

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
1 vote
1 answer
43 views

Question of section 1.3 Intuition for Aborting in "Fiat-Shamir With Aborts: Applications to Lattice and Factoring-Based Signatures"

When I'm reading this paper "Fiat-Shamir With Aborts: Applications to Lattice and Factoring-Based Signatures" by Lyubashevsky. I have trouble understanding section 1.3 Intuition for Aborting....
Solaris's user avatar
  • 15
4 votes
1 answer
82 views

Security impact of weakened collision resistance for 128-bit Fiat-Shamir challenges

As I understand, to achieve a security level of $\lambda$, a hash function's output should be at least $2\lambda$ in length, since the search space is halved for collision resistance. However, I am ...
Taka's user avatar
  • 43
0 votes
0 answers
41 views

Showing the zero-knowledge property in a NI-ZK scheme

To my understanding, whilst the definition of zero-knowledge (zk) is the same in the non-interactive context, how one shows a non-interactive scheme is zk is very different from interactive zk ...
Proliferate309's user avatar
1 vote
0 answers
28 views

How to convert Lattice based signature to R1CS statements?

How can we convert a lattice-based signature (like based on Fiat Shmair with abort e.g. Dilithium) to R1CS?
Kanchan Bisht's user avatar
0 votes
2 answers
111 views

Can a Sigma protocol be transformed into a signature of knowledge through Fiat-Shamir transform?

As is well known, a sigma protocol can be transformed into a NIZK protocol through a Fiat-Shamir transform. But can the Sigma protocol be transformed into a signature of knowledge in a similar manner? ...
user109993's user avatar
1 vote
0 answers
40 views

Disjunctive ZK Proof of knowledge of discrete log

I want to construct a non-interactive ZK proof that in a set of pairs of group (where the DDH-assumption holds true) elements: $(g_1, Y_1), (g_2, Y_2), ..., (g_n, Y_n)$ , the prover knows at least one ...
drydrydesert's user avatar
3 votes
1 answer
178 views

Fischlin vs. Fiat-Shamir Performance

Using Fiat-Shamir, an interactive 3-round sigma protocol can be compiled into a non-interactive zero-knowledge proof in the random oracle model. A NIZK through Fiat-Shamir is not UC-Secure due to ...
Atonal's user avatar
  • 155
1 vote
2 answers
258 views

How to prove that a Pedersen commitment has the same value as at least one of a set of other Pedersen commitments, without revealing which

A prover has two pedersen commitments, $V_{a}=G\cdot a+H\cdot r_a$ and $V_{b}=G\cdot b+H\cdot r_b$, which commit the values $a$ and $b$ respectively. The prover has another commitment $S_{\sigma}=G\...
user105684's user avatar
2 votes
1 answer
50 views

batch Fiat-Shamir

The prover has $n$ group elements $g_1, ..., g_n$ and wishes to demonstrate the knowledge of the discrete logarithm to base $g$ for each of them, i.e, for each $i \in [1,n]$ she knows some $e_i$ s.t. $...
Sean's user avatar
  • 99
1 vote
1 answer
101 views

Ensure deniability of an interactive zero knowledge proof

Suppose that Peggy(prover) and Victor(verifier) are running some zero knowledge proof protocol that does not rely on hidden verifier secrets. The verifier generates randomly chosen challenge values ...
Richard Thiessen's user avatar
2 votes
1 answer
113 views

Fiat-Shamir with interactions

Suppose we have a standard $\Sigma$-protocol for proving the knowledge of a witness $x$ for the statement $y$. It has an honest-verifier ZK and special soundness. Now we do an unusual modification to ...
pintor's user avatar
  • 558
3 votes
0 answers
212 views

Prove DSA signature scheme is EUF-CMA secure

I want to prove that the DSA signature scheme is EUF-CMA secure in the random oracle model, if the discrete logarithm problem is hard. I know it can be proved by the following two parts: Discrete ...
Vincent's user avatar
  • 31
2 votes
1 answer
107 views

Lagrange interpolation in the exponent

I am going over the paper https://verifiable-timed-signatures.github.io/web/assets/paper.pdf and on page 5, it says the following: Suppose I have a t-out-of-n threshold sharing scheme for the secret $\...
sadtroll's user avatar
2 votes
1 answer
195 views

Real-world instantiation of NIZK protocol from Fiat-Shamir

So I understand how one can use Fiat-Shamir to turn a HVZK sigma protocol into a non-interactive zk protocol in the random oracle model. My problem though is I don't understand why is this useful. If ...
Proliferate309's user avatar
4 votes
1 answer
207 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, \...
Bean Guy's user avatar
  • 752
0 votes
1 answer
69 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 ...
jimmytann's user avatar
  • 177
2 votes
2 answers
313 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 ...
sthorm's user avatar
  • 23
1 vote
1 answer
110 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 ...
Anon's user avatar
  • 403
2 votes
0 answers
162 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 ...
fgrieu's user avatar
  • 142k
2 votes
1 answer
92 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?
Crypto_researcher's user avatar
2 votes
0 answers
135 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. ...
pintor's user avatar
  • 558
4 votes
1 answer
89 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 ...
New2Math's user avatar
  • 141
3 votes
1 answer
630 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) = ...
Bean Guy's user avatar
  • 752
3 votes
1 answer
288 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'...
Lieu Zheng Hong's user avatar
1 vote
1 answer
275 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 - ...
Кирилл Волков's user avatar
0 votes
2 answers
167 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 ...
Кирилл Волков's user avatar
0 votes
1 answer
199 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 ...
Кирилл Волков's user avatar
0 votes
1 answer
47 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 ...
Кирилл Волков's user avatar
1 vote
1 answer
94 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-...
Ruben De Smet's user avatar
3 votes
1 answer
616 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 ...
Chao Liu's user avatar
0 votes
3 answers
301 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 ...
user1794567's user avatar
2 votes
0 answers
121 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 ...
user avatar
7 votes
1 answer
529 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 ...
Bean Guy's user avatar
  • 752
1 vote
0 answers
73 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'...
JohnnyP's user avatar
  • 43
5 votes
1 answer
223 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 ...
Lecter's user avatar
  • 113
3 votes
1 answer
620 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 ...
UTF-8's user avatar
  • 264
0 votes
1 answer
164 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 ...
pintor's user avatar
  • 558
0 votes
1 answer
163 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%...
user76328's user avatar
2 votes
1 answer
303 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)$ ...
Leafar's user avatar
  • 325
0 votes
0 answers
54 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 ...
Sam's user avatar
  • 1
0 votes
2 answers
294 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 ...
drone123321's user avatar
7 votes
2 answers
2k 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, ...
user1936752's user avatar
1 vote
0 answers
103 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 ...
jimmytann's user avatar
  • 177
2 votes
1 answer
345 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-...
satya's user avatar
  • 1,414
5 votes
1 answer
390 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 ...
joakimb's user avatar
  • 243
1 vote
1 answer
140 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?
WeCanBeFriends's user avatar
0 votes
1 answer
58 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 ...
Mike Gallagher's user avatar
1 vote
1 answer
132 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 ...
bit's user avatar
  • 33
2 votes
2 answers
160 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 ...
DaWNFoRCe's user avatar
  • 872
0 votes
1 answer
345 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 ...
Mohamed's user avatar
  • 205