Forward-secure signature

A forward-secure signature scheme is a signature scheme whose verification key is fixed for time periods while the signing key is updated at the end of each period, such that no efficient adversary that learns the signing key of period can forge a signature for any period — BM99.

Syntax

A key-evolving signature scheme with periods is a tuple of efficient algorithms with message space — BM99:

  • , a randomized algorithm outputting a verification key and the signing key of period ,
  • , a (possibly randomized) algorithm which, for , takes the signing key of period and outputs the signing key of period , after which the signer erases ,
  • , a (possibly randomized) algorithm which takes the signing key of period and a message , outputting a signature for period ,
  • , a deterministic algorithm outputting a bit indicating whether is a valid signature on for period .

The verification key is the same in every period. Throughout, is polynomially bounded, and denotes the key obtained from by applications of .

Properties

Correctness

A key-evolving signature scheme is -correct if for all , and ,

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

Forward security

The adversary runs through the periods in order, with a signing oracle for the current period, and chooses when to move to the next period. At a period of its choice it breaks in and receives , or it ends period without breaking in, in which case and it receives ; it wins by forging a signature for some period on a message it did not submit to the signing oracle during period — BM99. The forgery must be for an earlier period because signs for period and, through , for every later period. The pair must not lie in because otherwise wins with probability at least by querying during period and outputting the reply.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{fs}}_{\mathsf{FSS},\calA}(\secpar, T)$}
\begin{algorithmic}
\State $(\vk, \sk_1) \gets \KeyGen(1^\secpar, T)$; $i \gets 1$; $\calQ \gets \{\}$
\State $\stA \gets \calA^{\calS, \calU}(1^\secpar, \vk)$
\Comment{$\calA$ halts to break in during period $i$}
\State $(j^*, m^*, \sigma^*) \gets \calA(\sk_i, \stA)$
\Return $[\Vrfy(\vk, j^*, m^*, \sigma^*) = 1 \wedge 1 \le j^* < i \wedge (j^*, m^*) \notin \calQ]$
\Comment{$j^*$ precedes the break-in; $m^*$ not signed in period $j^*$}
\end{algorithmic}
\end{algorithm}
\begin{algorithm}
\algname{Oracle}
\caption{$\calS(m)$}
\begin{algorithmic}
\If{$i > T$}
\Return $\bot$
\EndIf
\State $\calQ \gets \calQ \cup \{(i, m)\}$
\Return $\Sign(\sk_i, i, m)$
\end{algorithmic}
\end{algorithm}
\begin{algorithm}
\algname{Oracle}
\caption{$\calU()$}
\begin{algorithmic}
\If{$i < T$}
\State $\sk_{i+1} \gets \mathsf{Update}(\sk_i)$; erase $\sk_i$; $i \gets i + 1$
\Else
\State erase $\sk_T$; $\sk_{T+1} \gets \bot$; $i \gets T + 1$
\Comment{no break-in: $\calA$ receives $\bot$}
\EndIf
\end{algorithmic}
\end{algorithm}

A key-evolving signature scheme is forward-secure if for all polynomially bounded and all efficient ,

is negligible.

As an object, a forward-secure signature scheme denotes a forward-secure scheme that, for every polynomially bounded , is -correct in every period , and whose message space is non-trivial as for signature schemes: for every it contains two distinct messages that an efficient algorithm outputs on input , or on input when the message space depends on the key, in which case correctness is required for the messages so computed. For the period- algorithms of a forward-secure scheme form an EUF-CMA-secure signature scheme (DS ⇔ Forward-secure signature) — folklore.

Variations

Unbounded number of periods

In the syntax above is fixed at key generation. MMM02 construct, from any signature scheme, forward-secure schemes in which the number of periods need not be fixed in advance.

Forward-secure encryption

The analogous notion for encryption, in which the secret key of period reveals nothing about plaintexts encrypted for earlier periods, is forward-secure public-key encryption — CHK03.

Other results

  • EUF-CMA-secure signature schemes exist if and only if forward-secure ones do, for every polynomially bounded ; the construction from a signature scheme uses independent key pairs (DS ⇔ Forward-secure signature) — folklore.
  • If factoring Blum integers is hard, the Fiat–Shamir-type scheme of BM99, whose update squares each component of the secret key modulo a Blum integer, is forward-secure in the random-oracle model (Factoring ⇒ Forward-secure signature (Bellare–Miner)) — BM99.
  • IR01 give a forward-secure scheme based on Guillou–Quisquater signatures GQ88a, in the random-oracle model, whose signing and verification are as efficient as those of the underlying Guillou–Quisquater scheme.
  • The Fiat–Shamir characterization of ID ⇒ DS carries over to forward security, for key-evolving identification schemes and forward security against impersonation under passive attack — AABN02.
  • XMSS is a stateful hash-based signature scheme (Hash function + PRF ⇒ DS (XMSS)); its key is updated after every signature, and it is forward-secure in the variant of the game above in which answers one query per period — BDH11.

Participates in

Produces Forward-secure signature