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.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Could you add a reference to the definition of the signature scheme? $\endgroup$– ckamathDec 23, 2017 at 9:35
-
$\begingroup$ In a strict sense, not really, because CMA usually implies ability to query the oracle for arbitrarily many signatures, so the usual security notion doesn't apply. But you can find a reduction to various preimage-related security properties of the underlying hash function for modern multi-message hash-based signature schemes in Andreas Hülsing, Joost Rijneveld, and Fang Song, ‘Mitigating Multi-Target Attacks in Hash-based Signatures’, PKC 2016, preprinted in IACR Cryptology ePrint Archive: Report 2015/1256. $\endgroup$– Squeamish OssifrageDec 24, 2017 at 3:22
-
$\begingroup$ @SqueamishOssifrage That looks very suspiciously like an answer hiding as a comment. Hell, it's even got references :) $\endgroup$– Maarten Bodewes ♦Oct 8, 2018 at 12:49
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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'$.
