# Schnorr’s identification protocol

## Definition
- **Schnorr’s Identification Protocol** is a cryptographic protocol used for entity authentication. It enables one party (the prover) to prove its identity to another party (the verifier) without revealing any information that could later be used to impersonate the prover. This protocol is based on the hardness of the discrete logarithm problem, making it secure under specific assumptions in cryptographic settings.
- **Goal:** $\textbf{Prover}$ convinces $\textbf{Verifier}$ that they know $x$ such that $h = g^{x}$
## Key Components:
- Parameters:
- A large prime $p$
- A smaller prime $q$ such that $q$ divides $p-1$ $(p = 2q + 1)$
- A generator $g$ of a subgroup of order $q$ in the multiplicative group $Z^{*}_{p}$
- Secret and Public Keys:
- The prover has a secret $x(0<x<q)$
- The public key is $h = g^{x} \bmod p$
## Interactive Protocol:
## Non-Interactive Protocol:
## Security Weakness
- **Weak Fiat-Shamir transformation:** In the non-interactive protocol, it is a common occurrence that some parameters are missing on the hash computation $\textbf{Hash(g, q, h, u)}$
- $h$ or $u$ missing: high severity issue.
- $g$ or $q$ missing: usually no issue, but it might be one if the $\textbf{Prover}$ uses these parameters directly from the proof structure. This way, the $\textbf{Prover}$ can provide bad generators or orders to forge the proof
- **Weak randomness:** Bad randomness may cause the secret $x$ to leak. If $r$ is reused twice with two different interactive challenges, or different data on the non-interactive version then
## Reference
- https://www.zkdocs.com/docs/zkdocs/zero-knowledge-protocols/schnorr/
- https://www.zkdocs.com/docs/zkdocs/protocol-primitives/fiat-shamir/
- https://crypto.stanford.edu/cs355/19sp/lec5.pdf