§19 Public-Key Identification Schemes

Identification Experiment $\operatorname{Ident}_{\mathscr{A},\Pi}(n)$

• Fix an Identification scheme $\Pi = (Gen, \mathscr{P}_1, \mathscr{P}_2, V)$ and define the Identification experiment $\operatorname{Ident}_{\mathscr{A},\Pi}(n)$ as:

  1. $Gen(1^n)$ is run to obtain keys $(pk, sk)$.

  2. Adversary $\mathscr A$ is given $pk$ and oracle access to $\texttt{Trans}_{sk}$ that it can query as often as it wants.

  3. At any point during the experiment, $\mathscr A$ outputs a message $I$.

     A uniform challenge $c \in \Omega_{pk}$ is chosen and given to $\mathscr A$, who responds with some $s$.

     $\mathscr A$ may continue to query $\texttt{Trans}_{sk}$ even after receiving $c$.

  4. Adversary succeeds and the experiment evaluates to $1$ if and only if $V(pk, c, s) = I$.

Security of Identification Scheme

• Definition. An Identification scheme $\Pi = (Gen, \mathscr{P}_1, \mathscr{P}_2, V)$ is secure against a passive attack, or just secure, if for all probabilistic polynomial-time adversaries $\mathscr A$, there exists a negligible function $\epsilon(n)$ such that:

  $$\Pr[\operatorname{Ident}_{\mathscr{A},\Pi}(n)=1]\le\epsilon(n)$$

Fiat-Shamir Transform: From Identification schemes to Digital Signatures

• Let $({Gen}_{id}, \mathscr{P}_1, \mathscr{P}_2, V)$ be an Identification scheme, and construct a Signature scheme as follows:

  • $Gen$: On input $1^n$, run $Gen_{id}(1^n)$ to obtain $pk, sk$.

    The public key specifies a set of challenges $\Omega_{pk}$.

    As part of key generation, a function $H : \{0,1\}^* \rightarrow \Omega_{pk}$ is specified.

  • $Sign$: On input a private key $sk$ and a message $m \in \{0,1\}^*$.

    1. Compute $(I, st) \leftarrow \mathscr{P}_1(sk)$.
    2. Compute $c := H(I, m)$.
    3. Compute $s := \mathscr{P}_2(sk, st, c)$. Output signature as $\sigma = (c, s)$.

  • $Vrfy$: On input a public key $pk$, a message $m \in \{0,1\}^*$, and a signature $(c, s)$,

    compute $I := V(pk, c, s)$. Output $1$ if and only if $H(I, m) = c$.

Security of Signature Scheme obtained by Fiat-Shamir Transform

• Theorem. Let $\Pi$ be an Identification scheme, and let $\Pi'$ be the Signature scheme that results by applying the Fiat-Shamir transform to it. If $\Pi$ is secure and $H$ is modeled as a random oracle, then $\Pi'$ is secure.

Schnorr Digital Signature Scheme

• Let $\mathscr G$ be a PPT algorithm that on input $1^n$, outputs $(\mathbb{G}, q, g)$. The Schnorr signature scheme works as:

  • $Gen$: On input $1^n$, run $\mathscr G(1^n)$ to obtain $(\mathbb{G}, q, g)$,

    Choose uniform $x \in \mathbb{Z}_q$, and set $h := g^x$.

    The public key is $(\mathbb{G}, q, g, h)$ and private key is $x$.

    As part of key generation, a function $H : \{0,1\}^* \rightarrow \mathbb{Z}_q$ is specified.

  • $Sign$: On input a private key $x$ and a message $m \in \{0,1\}^*$,

    Choose uniform $r \in \mathbb{Z}_q$, and set $I := g^r$. Compute $c := H(I, m)$, and $s := [cx + r \bmod q]$.

    Output the signature as $(c, s)$.

  • $Vrfy$: On input a public key $(\mathbb{G}, q, g, h)$, a message $m \in \{0,1\}^*$, and a signature $(c, s)$, compute $I := g^{s} \cdot h^{-c}$. Output $1$ if and only if $H(I, m) = c$.

Security of Schnorr Identification Scheme

• Theorem. If the Discrete-Logarithm problem is hard relative to $\mathscr G$, then the Schnorr Identification scheme is secure (against passive attacks).
• Corollary. If the Discrete-Logarithm problem is hard relative to $\mathscr G$, and if $H$ is modelled as a random function, then the Schnorr Digital Signature scheme is secure.

— Apr 18, 2023

§19 Public-Key Identification Schemes by Lu Meng is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Permissions beyond the scope of this license may be available at About.