3 ms·

Last night I was pondering about future "compression" schemes that relied on hyper-powerful quantum computers that can resolve hash collisions very, very quickl

Last night I was pondering about future "compression" schemes that relied on hyper-powerful quantum computers that can resolve hash collisions very, very quickly, so that rather than literally compressing the data, you'd just share a hash and then this hyper-powerful computer will enumerate possible strings of data that give that hash, and then check them against some secondary condition (another hash?) to find the right one. I don't know how feasible this actually is, but it made for an interesting sci-fi thought. edit: Thanks for all of the enlightening replies!

paulddraper 7y ago
The problem is that is a huge number of strings that becomes a hash. Each SHA-256 hash has 2^(8 * 1024 - 256) = 10^2389 possible 1KB inputs. So...perhaps it could be done, but the quantum computer would have programmed with a very good selection criteria.
- stouset 7y ago
  No, there is no way this could be done, because there is no way to know which of multiple colliding inputs was the right one. Imagine a one-bit hash function. You start your “decompression” process and read in a 0. What input produced that bit? Literally fifty percent of all possible strings would produce that same output. Without more information, you cannot choose between them. And the information needed to choose correctly is exactly the same amount of information in the original input. https://en.m.wikipedia.org/wiki/Pigeonhole_principle https://en.m.wikipedia.org/wiki/Pigeonhole_principle
  - greiskul 7y ago
    Yup, the pigeonhole principle really defines a hard limit on compression, in that it is impossible to compress (make smaller) ALL files. The way compression algorithms get around that, is by abusing the fact that we rarely want to send around arbitrary data, real world data has lots of redundancy in it, so we can make algorithms where real world data gets mapped into compressed files smaller then they are (by finding the redundancies in the data), and purely random data gets mapped into files that are actually slightly longer than the data.
    - caf 7y ago
      Often rendered as the pithy phrase "A compression algorithm is actually an expansion algorithm with some interesting failure cases."
CiPHPerCoder 7y ago
IIRC the best quantum attack against SHA256 clocked in at about 2^85 cost. It's still not practical for most modern hash functions.
- gdavisson 7y ago
  2^85 is for finding a collision; finding a preimage of a specific hash would take 2^128 steps of Grover's algorithm. That's thought to be beyond any possible future computer system.
  - CiPHPerCoder 7y ago
    Either way, 85 bits of post-quantum security makes me feel safe.
jhpriestley 7y ago
There are infinitely many strings that produce a given hash. Infinitely many of them will also produce a secondary hash that you check against. There is no general-purpose scheme to compress arbitrary data, regardless of available computational power, because if you can compress all length-N plaintext strings then you must end up with at least 2^N distinct compressed strings which will take on average at least N bits of storage.
eternalban 7y ago
It may turn out that finding those additional 'hint' bits ("another hash") that dramatically reduce the search space of your computer for a given input is NP hard.

paulddraper 7y ago

The problem is that is a huge number of strings that becomes a hash. Each SHA-256 hash has 2^(8 * 1024 - 256) = 10^2389 possible 1KB inputs. So...perhaps it could be done, but the quantum computer would have programmed with a very good selection criteria.

stouset 7y ago
No, there is no way this could be done, because there is no way to know which of multiple colliding inputs was the right one. Imagine a one-bit hash function. You start your “decompression” process and read in a 0. What input produced that bit? Literally fifty percent of all possible strings would produce that same output. Without more information, you cannot choose between them. And the information needed to choose correctly is exactly the same amount of information in the original input. https://en.m.wikipedia.org/wiki/Pigeonhole_principle https://en.m.wikipedia.org/wiki/Pigeonhole_principle
- greiskul 7y ago
  Yup, the pigeonhole principle really defines a hard limit on compression, in that it is impossible to compress (make smaller) ALL files. The way compression algorithms get around that, is by abusing the fact that we rarely want to send around arbitrary data, real world data has lots of redundancy in it, so we can make algorithms where real world data gets mapped into compressed files smaller then they are (by finding the redundancies in the data), and purely random data gets mapped into files that are actually slightly longer than the data.
  - caf 7y ago
    Often rendered as the pithy phrase "A compression algorithm is actually an expansion algorithm with some interesting failure cases."

CiPHPerCoder 7y ago

IIRC the best quantum attack against SHA256 clocked in at about 2^85 cost. It's still not practical for most modern hash functions.

gdavisson 7y ago
2^85 is for finding a collision; finding a preimage of a specific hash would take 2^128 steps of Grover's algorithm. That's thought to be beyond any possible future computer system.
- CiPHPerCoder 7y ago
  Either way, 85 bits of post-quantum security makes me feel safe.

jhpriestley 7y ago

There are infinitely many strings that produce a given hash. Infinitely many of them will also produce a secondary hash that you check against. There is no general-purpose scheme to compress arbitrary data, regardless of available computational power, because if you can compress all length-N plaintext strings then you must end up with at least 2^N distinct compressed strings which will take on average at least N bits of storage.

eternalban 7y ago

It may turn out that finding those additional 'hint' bits ("another hash") that dramatically reduce the search space of your computer for a given input is NP hard.