Lamport's one-time signature scheme

From CRYPTUTOR

Lamport's one-time signature scheme is a simple digital signature scheme for fixed-length messages, using a one-way function.

[edit]

Construction

Let $f$ be a one-way function. Lamport's scheme for $\ell(n)$ -bit messages (where $\ell$ is a polynomial) is defined by the following algorithms:

KeyGen: Take n as the security parameter of the scheme, and return:
- $SK = \begin{pmatrix} S_1^0 & \cdots & S_{\ell(n)}^0 \\ S_1^1 & \cdots & S_{\ell(n)}^1 \end{pmatrix}$ , where each $S_i^b$ is a randomly chosen $n$ -bit string.
- $VK = \begin{pmatrix} V_1^0 & \cdots & V_{\ell(n)}^0 \\ V_1^1 & \cdots & V_{\ell(n)}^1 \end{pmatrix}$ , where each $V_i^b = f(S_i^b)$ .
$\mathsf{Sign}_{SK}(m_1 \cdots m_{\ell(n)}) = (S_1^{m_i}, \ldots, S_{\ell(n)}^{m_{\ell(n)}})$
$\mathsf{Ver}_{VK}(m_1 \cdots m_{\ell(n)}, (\sigma_1, \ldots, \sigma_{\ell(n)})) = 1$ if and only if $f(\sigma_i) = V_i^{m_i}$ for all $i$ .

Note that the signature is much longer than the message.

It is clear that the correctness condition holds for this scheme -- i.e, $\mathsf{Ver}_{VK}(m, \mathsf{Sign}_{SK}(m)) = 1$ for all key pairs $(SK,VK) \gets \mathsf{KeyGen}$ .

[edit]

Proof of security

We show that Lamport's scheme achieves the one-time unforgeability requirement for a digital signature scheme.

Let $A$ be any adversary for the one-time unforgeability experiment, with success probability $ε$ . We will show that this probability is negligible in $n$ . We construct an inverting adversary $A *$ for $f$ as follows:

$A *$ : Simulator for inverting $f$ :
On input $y$ , we wish to find $x$ such that $f (x) = y$ .
Generate a key pair $(S K, V K)$ for Lamport's scheme, but insert $y$ into a random position in $V K$ , (say, $V_i^b$ for random $i \gets \{1,\ldots, \ell(n)\}$ and $b \gets \{0,1\}$ ). Note that the distribution of keys is identical as in the unforgeability experiment, and independent of $i$ and $b$ .
Simulate $A$ . When it asks for a signature of message $m$ ,
If $m i = b$ , then exit (we don't have a preimage for $V_i^b$ ).
Otherwise give the prescribed signature for $m$ .

When $A$ outputs a final message/signature pair $(m',σ)$ ,
If $m' i = m i$ , then exit.
Otherwise, give $σ i$ as output (our guess for a preimage of $y$ )

Assuming $A *$ outputs a guess and $A$ gave a valid forgery, the guess $σ i$ must be a preimage of $y$ . The probability that we reach the final step is at least $1/2\ell(n)$ , since $A$ 's behavior is independent of $i$ and $b$ (we must have chosen $i$ to be one of the positions where $m$ and $m'$ will differ). The probability that $A$ then gives a valid forgery is at least $ε$ , so $A *$ inverts $f$ with probability at least $\epsilon/2\ell(n)$ .