Is the Lamport-Diffie signature secure in the standard model? I ask this question because I am reading the Postquantum-Cryptography book and the reductions the authors use one-way functions and not hash functions. According to my understanding, ROM is used to replace hash function for random oracles, but in Lamport-Diffie only pre-image resistance functions are sufficient.


1 Answer 1


Is the Lamport-Diffie signature secure in the standard model?

Technically, no, the Lamport(-Diffie) one-time signature scheme is not EUF-CMA secure, however, also technically "it depends".

Nominally, a signature scheme is typically called "secure" - especially in the public-key world - if for a polynomial number of adverserial interactions with it in the relevant model the advantage of said adversary is still negligible - with the negligibility coming from some security assumption typically.

However, you can easily construct an adversary which performs 2 interactions with the signature scheme in the EUF-CMA model and achieves an advantage of 1 from that. Such an adversary would e.g. query $0^n$ and $1^n$ as messages, revealing all private keys.

Also however, we can still construct a security statement, namely $$\mathbf{Adv}^{\textsf{EUF-CMA}}_{\text{LD-OTS}_F}(\mathcal A;q,n)\leq\begin{cases}\mathbf{Adv}^{\textsf{OWF}}_{F}(\mathcal A';n)&q\leq 1\\1&\text{else}\\\end{cases}$$ where $n$ is the security parameter, $q$ is the number of queries, $\mathcal A'$ is an existentially qualified adversary against the underlying OWF $F$ and $\mathcal A$ is the polynomially-bounded universally qualified adversary. The order of quantifiers is for all $\mathcal A$ exists $\mathcal A'$.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.