With a little bit of money a server could be built capable of 35 teraflops. That is around 2^45 operations a second, with overhead and other considerations I think generating 32-40 bits of information can be done in a second. A 1 MB file could take about 70 hours to generate doing 32 bits a second.
I have a certain use-case in mind where taking 700 hours to "uncompress" a 1MB file from 100KB is useful. I am familiar with the pigeon hole principle, birthday paradox, and why recursive compression isn't really possible. However, stubbornly can't help but think we could enumerate all 32bit possibilities and hit a match for some hash function output or some brute force method and utilize the nature of mathematics to help shrink the problem space.
I originally approached thinking about this by using sha-256 or some other hash function that has no yet found collisions (although there are infinitely many collisions with any hash function given pigeon hole, if i happen to hit a collision with sha-256 then at least it is significant and important for research).
224 bits of original data is provided, along with the 256 bit hash. The last 32 bits of information is enumerated until a match for the hash is found. Now storing 224+256 bits of information to get back 256 bits isn't really any type of compression of data but it's the approach that first came to mind.
The biggest overhead is sending the hash, so I attempted to look at 32bit hash functions like CRC32 but the probability of a collision is far too high. It seems like a normal hash just isn't viable, you would need the output of the hash to be less than what we can compute reasonable (~40 bits) and there just isn't enough hash space to avoid collisions. Now if we can do 2^256 calculations (quantum?) then 256 bit hash could be used as the probabilities of a collision are low enough to be usable.
I looked a little bit into locality sensitive hash functions hoping that given the locality I could limit the problem space to just 2^32 calculations even if the hash is larger than 32 bits but that hasn't really shown promising
I am looking for ideas/suggestions on how data could be verified and generated assuming you have say ~100 days to uncompress/generate given todays computing power (less than $10k of equipment, but ASIC/FPGAs are fair game). Understandably, I am probably chasing something that isn't viable or even possible but exploring these ideas and expanding my knowledge of computer science beats just playing video games all day.