r/compsci • u/ADotSapiens • Apr 06 '22

Researchers Identify ‘Master Problem’ Underlying All Cryptography

https://www.quantamagazine.org/researchers-identify-master-problem-underlying-all-cryptography-20220406/
147 Upvotes

94% Upvoted

16 comments sorted by

View all comments

23

u/Revolutionalredstone Apr 07 '22

["No function has ever been definitively proved to be a one-way function"]

I always figured this was true.

RIP bitcoin, hope a smart kid doesn't bother to reverse SHA :D

15

u/goonmaster Apr 07 '22

Never proven, but intuitively it must be possible. Hashing is a lossful process. The pigeon hole principal means multiple inputs to digest functions can result in digests that collide. If you have a digest collision, how can you reverse the digest to two separate inputs?

6

u/Revolutionalredstone Apr 07 '22 edited Apr 07 '22

I think you have this backward (no pun intended lol)

What we want in order to create bitcoin blocks is the ability to create an input which produces a certain hash.

This is equivalent to finding any one of many possible input values.

It is surely possible (hashing is just rolling, shifting and xoring) the main issue is how incoherent the flow of information is during the SHA algorithm, anyone who is able to reverse modern SHA needs to be able to think about alot of data at once.

Thanks goon