5

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?

Connor
  • 51
  • 1

1 Answers1

5

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.

kodlu
  • 22,423
  • 2
  • 27
  • 57
  • 4
    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. – Gilles 'SO- stop being evil' Mar 25 '19 at 23:18
  • 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. " – Connor Mar 27 '19 at 07:51
  • 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? – kodlu Mar 27 '19 at 07:57
  • In fact, it's in my answer to another question on general hashing. https://crypto.stackexchange.com/questions/56404/what-was-the-first-hash-and-what-problem-was-it-supposed-to-solve/56410?r=SearchResults#56410 – kodlu Mar 27 '19 at 08:03