Geology professor Peter McMenteur gets interested in Lamport’s authentication scheme. After a brief study, he claims that the scheme works even if the hash function is substituted by a function that is only easy to compute and hard to invert (i.e., a hash function without the property of collision resistance

Can anyone point me in the right direction with this ?

  • $\begingroup$ that's called OWF (one-way-function) and this statement is true. Lamport WP, OWF WP $\endgroup$
    – SEJPM
    Aug 15 '16 at 18:27
  • $\begingroup$ Its the Collision resistance that has me stuck, because lamports scheme is a One Time Password does the Collision resistance matter ? $\endgroup$
    – eggberteh
    Aug 15 '16 at 18:36
  • $\begingroup$ IIRC collision resistance doesn't matter for lamport. But I'd have to check the security reduction / the authoritative source for the details. $\endgroup$
    – SEJPM
    Aug 15 '16 at 19:00
  • $\begingroup$ @SEJPM: Despite the tags, the question quoted by the OP seems to be about Lamport's one-time password scheme (which is basically S/KEY), not about Lamport signatures. That said, your answer is still true. $\endgroup$ Aug 15 '16 at 19:01

Lamport's one-time authentication scheme requires a one-way function. In terms of cryptographic hash functions, one-wayness is (practically, modulo some technical differences in the definitions) equivalent to first preimage resistance. In particular, a function does not need to be collision resistant in order to be one-way.

(A practical way to construct a non-collision-resistant one-way function is to take any given one-way function, such as a secure hash function, and make it ignore one of the bits of its input. This weakens the first preimage resistance of the function only slightly, but completely destroys both collision resistance and second preimage resistance.)

Indeed, the original description of the scheme (Lamport, 1981) does not mention hash functions at all, but rather suggests constructing a by encrypting a fixed plaintext with any secure encryption algorithm, using the input as the key and the resulting ciphertext as the output (citing Diffie & Hellman, 1976). Such a construction generally does not guarantee collision resistance and, in particular, will trivially lack it if the encryption scheme has equivalent keys.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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