A Lamport signature is made as follows:

  1. Alice stores $k_1, \cdots, k_{n'} \leftarrow K $ as her "private key", with one-way function $F: K\to V$, $n'>n$, and (easily enough) all $F(k_i)\neq F(k_j)$.

  2. Alice publishes $F$, $G$, and $\alpha = \left(F(k_1), \cdots, F(k_{n'})\right)$ as her "public key", with one-way function $G:M\to \binom{\{1, \cdots, n'\}}{n}$ [notation].

  3. Alice later publishes $\sigma_\alpha(m)=(k_{i_1}, \cdots, k_{i_n})$ as her "signature" on $m$, with $(i_1, \cdots, i_n) = G(m)$.

    • Alice then destroys all stored $k_i|i\notin G(m)$ to prevent any subsequent $\sigma_\alpha(m')$ from being created, which would leak additional values of $k_i$ and rapidly destroy the scheme's security.
  4. To verify $\sigma_\alpha(m)$, Bob simply checks that $F(\sigma_\alpha(m)_j)=\alpha_i$ forall $i\in G(m)$ and $G(m)_j=i$.

Now, Wikipedia provides a reference implementation:

  • $n=256$, $n'=2n$
    (the original paper only bothered specifying $n=20$ and $n'=2n$, to allow an apples-to-apples comparison with Rabin's scheme which Lamport intended to obsolete by his own.)

  • $F=\phi=\text{SHA}_n: \{0,1\}^*\to\{0,1\}^n$
    (the original paper did not even bother specifying any $K$, $V$, or $\phi$.)

  • $G(m)=R\circ\phi(m)=(1 + \phi(m)_1, \cdots, 2n - 1 + \phi(m)_n)$
    (Wikipedia's construction of $R$, despite not being surjective and effectively constraining $n':=2n$, is nevertheless a clear improvement over the original paper's construction, which was a partial function thus might, “undesirabl[y]”, require the sender to brute-force a valid value via a nonce on $m$.)

Clearly, in this instance, $F$ and $G$ are "pretty much the same function"; each is a "thin wrapper" around $\phi$, i.e. with a trivial left-inverse.

So I'm wondering: does it harm, or help, the security of this scheme to have $F$ and $G$ be "the same function" like this? (And is it any particular risk for $G$ not to be surjective?)

Dr. Lamport seems to have mostly proposed similar constructions to Wikipedia's in his paper and raised no similar concerns on them, so I assume this is probably OK, but I don't know what all (if anything) modern cryptography or cryptanalysis has to say about either point.

The reason I'm asking is: I'm writing a reference software implementation that includes PKCS#8 serialization and deserialization, and I'm wondering if I should create separate parameters for $F$ and $G$ or have them "hard-coded" to be the same (and/or if I should hard-code in the behavior of $R$ despite the lack of a trivially correct choice for it).

  • $\begingroup$ In particular: it would seem that skimping on $F$ saves a lot of space and resources compared to skimping on $G$ for minimal weakening of the scheme; is this intuition off-base? $\endgroup$ May 9, 2021 at 13:36
  • $\begingroup$ (As for the non-surjectivity of Wikipedia's construction of $R$ vs the partiality of Lamport's preliminary construction: you gotta pick one, so WP's approach is probably the most correct.) $\endgroup$ May 19, 2021 at 9:28


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.