6
$\begingroup$

I am studying the Lamport signature scheme, and I found that in many sources (eg: Hash-based Digital Signature Schemes) the input and output bitstring of the OWF and the message digest have the same size, generally 256.

As the minimal requirement for the OWF is to be pre-image resistant, it seems that 128 bits for the output is "sufficient", this is explained in this discussion: Hash collision resistance requirements for Lamport signatures (basically the theoretical security is 119 bits in that case).

Questions

  1. What about the input? Does a 128-bits input keep the security parameter?
  2. If the answer is positive, what could be the most efficient OWF with 128 bits input -> 128 bits output in terms of implementation? Is there a block cipher (AES-128 ?) that would be more efficient than a cryptographic hash function, for the same level of security requirements?
$\endgroup$

1 Answer 1

3
$\begingroup$

(Q1) Assuming that you talk about the size of the secret key elements which equals the input size of the OWF when you talk about the "input", this should be at least as much as the output size.

Consider a function $f: \{0,1\}^m \rightarrow \{0,1\}^n$.The thing to worry about when you choose $m < n$ is a brute force search for a preimage, which in this case takes about $2^m$ queries to $f$. The second thing is the collision probability, i.e. the probability of choosing the same value for two different secret key elements. As these are sampled from the uniform distribution, the probability for this is $2^{-m/2}$. Please note that this is a constant probability that an adversary cannot influence, so you are perfectly fine if this is, e.g., $2^{-64}$. Moreover, you can also let your implementation check that this doesn't happen. So, $m = n$ is perfectly fine.

Also, a $128$-bit output is fine as Lamport does only rely on the one-wayness of the "internal" hash function. However, as you mentioned, the hash function used to compress the message still needs collision resistance and hence has to be at least $256$-bit (or you use some kind of randomized hashing).

Summing up: For OWF $f: \{0,1\}^m \rightarrow \{0,1\}^n$, $m = n = 128$ is fine for classical security (if you want security against quantum attackers you need to make it $256$ bit because of Grover's algorithm).

(Q2) Good question, as proposed in the XMSS paper, you can use AES and the Matyas-Meyer-Oseas construction to build a $n$ to $n$ bit hash function. This works with any block cipher that has same key and block size. The advantage of AES is the available hardware acceleration on many different platforms, incl. modern general purpose CPUs and many smartcard micro controllers.

$\endgroup$

Your Answer

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

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