Samantha selects a secure hash function \(\mathcal{H}\) (e.g., SHA-256).

For each bit position in the message (total of \(m\) bits), she generates two random values:

• \(x_{i,0}\) for when the message bit is 0
• \(x_{i,1}\) for when the message bit is 1

For each value \(x_{i,j}\), she computes the hash \(y_{i,j} = \mathcal{H}(x_{i,j})\).

Samantha organizes the generated values into private and public keys:

• Private key \(sk\): All random values \(x_{i,j}\)
• Public key \(pk\): All hash values \(y_{i,j}\)

She sends the public key to Victor.

To sign a message, Samantha first converts it to its binary representation \(M = (M_0, M_1, ..., M_{m-1})\).

Each bit \(M_i\) will be either 0 or 1.

For each bit position \(i\) in the message:

• If \(M_i = 0\), Samantha selects \(x_{i,0}\)
• If \(M_i = 1\), Samantha selects \(x_{i,1}\)

The signature \(\sigma\) is the collection of all selected values: \(\sigma = (x_{0,M_0}, x_{1,M_1}, ..., x_{m-1,M_{m-1}})\)

Samantha sends the message \(M\) and signature \(\sigma\) to Victor.

After signing, Samantha must destroy this key pair to prevent reuse.

Reusing a Lamport-Diffie key pair would reveal both elements for some bit positions, allowing signature forgery.

Victor receives the message \(M\) and signature \(\sigma = (s_0, s_1, ..., s_{m-1})\).

First, he converts the message to its binary representation \(M = (M_0, M_1, ..., M_{m-1})\).

For each bit position \(i\) in the message:

• Victor computes \(z_i = \mathcal{H}(s_i)\)
• He checks if \(z_i = y_{i,M_i}\)

If all checks pass, Victor accepts the signature as valid.

If any check fails, Victor rejects the signature as invalid.