5
$\begingroup$

Hash linking is used to prove the integrity of a blockchain, or similar systems. When was that technique first used? I would guess it was early, maybe 1950s/1960s?

$\endgroup$

1 Answer 1

5
$\begingroup$

Lamport suggested the use of hash chaining in 1981 in Password Authentication with Insecure Communication, Communications of the ACM 24.11 (November 1981), pp 770-772.

He cites 3 prior papers:

  1. Diffie, W., and Hellman, M.E. New directions in cryptography. IEEE Trans. Inform. Theory 1T-22 (Nov. 1976), 644-654.

  2. Evans, A., Kantrowitz, W., and Weiss, E. A user authentication scheme not requiring secrecy in the computer. Comm. A CM 17, 8 (Aug. 1974), 437-442.

  3. Wilkes, M.V. Time-Sharing Computer Systems. American Elsevier, New York, 1972.

[1] is the paper which essentially invented Public Key Cryptography in the open literature. Lamport refers to the use of a one way function F, as described there, as hash functions in his chain.

[2] and [3] are cited for "the widespread use of such a function", e.g., storing $y=F(x)$ instead of $x$.

So it seems to me Lamport may well be the first to suggest the use hash chaining.

Edit: Thanks to @Gilles for pointing out Merkle patented hash trees in 1979.

$\endgroup$
4
  • 4
    $\begingroup$ Merkle patented hash trees in 1979, and hash chains are a special case of that. I don't know if that special case had been used before. $\endgroup$ Mar 25, 2019 at 23:18
  • $\begingroup$ what about this reference that appears here and there, "In January 1953, Hans Peter Luhn wrote an internal IBM memorandum that used hashing with chaining. " $\endgroup$
    – Connor
    Mar 27, 2019 at 7:51
  • $\begingroup$ Interesting, but fid you forget a link/reference? Is it maybe for storage (hashing with chaining is such a method) with a well distributed hash which is in general not one way? $\endgroup$
    – kodlu
    Mar 27, 2019 at 7:57
  • $\begingroup$ In fact, it's in my answer to another question on general hashing. crypto.stackexchange.com/questions/56404/… $\endgroup$
    – kodlu
    Mar 27, 2019 at 8:03

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.