# Is it more, or less, secure to use a different $F$ and $G$ for a Lamport signature?

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).

• 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? May 9, 2021 at 13:36
• (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.) May 19, 2021 at 9:28