Identity-based signature

An identity-based signature scheme is a signature scheme in which a user’s verification key is its identity string: an authority holding a master secret key issues each identity its signing key, and signatures verify under the identity and the authority’s master public key — Sha84.

Syntax

An identity-based signature scheme is a tuple of efficient algorithms with respect to identity space and message space — BNN04:

  • , a randomized algorithm that outputs a master public key and a master secret key ,
  • , a (possibly randomized) algorithm that outputs a signing key for the identity ,
  • , a (possibly randomized) algorithm that outputs a signature on ,
  • , a deterministic algorithm outputting a bit .

Properties

Correctness

An identity-based signature scheme is -correct if for all , , and ,

over the randomness of , and . When , is perfectly correct.

Existential unforgeability

The adversary receives , may obtain the signing key of any identity, and has a signing oracle for every identity; each identity’s key is extracted once and reused. It wins with a valid signature on a message for an identity whose key it never obtained, provided it never asked for a signature on by — BNN04. Without these restrictions, wins with probability at least by querying and signing , or by outputting the answer to .

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\text{euf-id-cma}}_{\Pi,\calA}(\secpar)$}
\begin{algorithmic}
\State $(\mpk, \msk) \gets \Setup(1^\secpar)$; $C \gets \{\}$; $\calQ \gets \{\}$
\State $(\mathit{id}^*, m^*, \sigma^*) \gets \calA^{\calO_{\Extract}, \calO_{\Sign}}(1^\secpar, \mpk)$
\If{$\mathit{id}^* \in C$ or $(\mathit{id}^*, m^*) \in \calQ$}
\Comment{$\calA$ may not query $\calO_{\Extract}(\mathit{id}^*)$ or $\calO_{\Sign}(\mathit{id}^*, m^*)$}
\Return $0$
\EndIf
\Return $[\Vrfy(\mpk, \mathit{id}^*, m^*, \sigma^*)]$
\end{algorithmic}
\end{algorithm}
\begin{algorithm}
\algname{Oracle}
\caption{$\calO_{\Extract}(\mathit{id})$}
\begin{algorithmic}
\If{$\sk_{\mathit{id}}$ is undefined}
\State $\sk_{\mathit{id}} \gets \Extract(\msk, \mathit{id})$
\EndIf
\State $C \gets C \cup \{\mathit{id}\}$
\Return $\sk_{\mathit{id}}$
\end{algorithmic}
\end{algorithm}
\begin{algorithm}
\algname{Oracle}
\caption{$\calO_{\Sign}(\mathit{id}, m)$}
\begin{algorithmic}
\If{$\sk_{\mathit{id}}$ is undefined}
\State $\sk_{\mathit{id}} \gets \Extract(\msk, \mathit{id})$
\EndIf
\State $\calQ \gets \calQ \cup \{(\mathit{id}, m)\}$
\Return $\Sign(\sk_{\mathit{id}}, m)$
\end{algorithmic}
\end{algorithm}

An identity-based signature scheme is EUF-ID-CMA unforgeable if for all efficient ,

is negligible.

As an object, an identity-based signature scheme denotes a -correct, EUF-ID-CMA-unforgeable scheme whose identity space contains an identity, and whose message space two distinct messages, that an efficient algorithm outputs on input or ; correctness is required for the identities and messages so computed.

Other results

Participates in

Builds on Identity-based signature

Produces Identity-based signature