Is there a cryptographic hash algorithm that, given the hash of a plaintext, supports supports efficient recomputation of the hash after modifying a single byte of the plaintext?

Specifically, is there a hash function H() such that, given plaintext P and Q of the same length that differ only in the byte at position K, there exists another function R() such that R(P, Q, K, H(P)) = H(Q) and R is O(1)? If so, what are H and R?

Such a function would be interesting because it would allow creating a filesystem that efficiently tracks a cryptographic hash for each of its files. Such a filesystem could be useful for implementing highly efficient file transfer (like rsync) or version control (like git) systems.

  • $\begingroup$ Would a universal hash function family be acceptable? Many of those can be efficiently updated when the input changes, but the catch is that they're only "secure" (for any halfway sensible definition of the word) against adversaries who don't know the key used to select the particular hash function from the universal family. $\endgroup$ – Ilmari Karonen Jul 16 at 13:40
  • $\begingroup$ @IlmariKaronen I don't think this is relevant for the use-case I have in mind (a filesystem that tracks cryptographic hashes of its files). Since the key would be public (part of the filesystem implementation), the hash would not provide cryptographic security. $\endgroup$ – Kerrick Staley Jul 16 at 20:06

I don't have a proof, but I don't think an $O(1)$ R is possible. That would make it very easy to calculate the hash of a changed input, and while this wouldn't contradict any defining property of a hash, it would make the hash weak for constructs like key derivation. So it would have to be a pretty unusual hash.

The standard solution is hash trees, also known as Merkle trees. It's an old technique, older than all modern hash functions, but still very much relevant for filesystems with integrity checks. Hash trees give you an R function with $O(n)$ extra storage and $O(\log n)$ calculation time and data transfer to make an update. The idea is to divide the data into blocks and to maintain a tree whose leaves are the data blocks and whose inner nodes contain hashes of their children. Whenever a block is updated, you only need to update the path from that block to the root of the tree.

  • $\begingroup$ Accepting this since it mostly answers my question. Would love if someone would chime in with a rigorous proof (or link to a paper) about why O(1) R is impossible for a cryptographic hash :) $\endgroup$ – Kerrick Staley Jul 16 at 20:09

No. There are hash functions that would have that property, which could be used for checksums, hash tables, etc.

However, it would imply a fundamental weakness for such a function to be used as a cryptographic hash.

Specifically, such an R would need to be able to ignore arbitrarily much of the input, looking at just the changed location and at most some constant number of other locations. For the impact of the change to be assessed without the other input requires the hash to be based on operations with regularising properties like commutativity and invertibility. Those sorts of properties imply that it's easy to find preimages and collisions.


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.