# Fiat–Shamir Transformation ## Metadata **Status**:: #x **Zettel**:: #zettel/fleeting **Created**:: [[2024-03-06]] **Highlights**: [[Wikipedia Authors - Fiat–Shamir heuristic (Highlights)]] ## Synopsis ### Interactive Version 1. Peggy wants to prove to Victor, the verifier, that she knows $x$ satisfying $y\equiv g^x$ without revealing $x$. 2. She picks a random $v\in \mathbb {Z} _{q}^{*}$, computes $t=g^v$ and sends $t$ to Victor. 3. Victor picks a random $c\in \mathbb {Z} _{q}^{*}$ and sends it to Peggy. 4. Peggy computes $r=v-cx{\bmod {\varphi }}(q)$ and returns $r$ to Victor. ($\varphi$ is the [[Euler's totient function]]). 5. He checks whether $t \equiv g^ry^c$. This holds because $g^{r}y^{c}\equiv g^{v-cx}g^{xc}\equiv g^{v}\equiv t$ and $g^{\varphi (q)}\equiv 1$. ### Fiat–Shamir Transformation 1. Peggy wants to prove that she knows $x$ satisfying $y\equiv g^x$ without revealing $x$. 2. She picks a random $v\in \mathbb {Z} _{q}^{*}$, computes $t=g^v$. 3. Peggy computes $c = H(g, y, t)$, where $H$ is a cryptographic hash function.[^1] 4. Peggy computes $r=v-cx{\bmod {\varphi }}(q)$. The resulting proof is the pair $(t, r)$. 5. Anyone can use this proof to calculate $c$ and check whether $t \equiv g^ry^c$. [^1]: ==Replace c with a random oracle.==