Join Log in
Score:0
caveman avatar Crypto

Hashing functions that allow to walk back to parts of cleartext?

in flag
caveman

Say $m$ is some clear text, and $h_n(m)$ is its $n$ bits hash.

The question: How can we design $h_n$ so that we can extract maximum information about $m$ from $h_n(m)$?

The reason I ask this is because, I think, if we answer that question, we will identify the perfect lossy compression function.

And the reason I think that's so, is because every bit of the $n$ bits in $h_n(m)$ contain information about every bit in $m$.

Note: I know that, if $h_n$ satisfied the criteria in the question, then it won't be useful for most cryptographic purposes any more.

35
1 + 0
Score:1
Meir Maor avatar Crypto
in flag
Meir Maor

To preserve information you need to make the output larger. The maximal amount of information we can preserve is all of it. This can be achieved by: e.g the identity function. $h(m)=m$

Obviously this provides no compression at all. Information theory teaches us we can not compress general data, some data is compressible with some functions but no function can compress all data.

If you are looking for lossy compression this requires you to decide which information is less important, this is fairly well understood in images video and sound, however not for general data. For general data if you don't care what you lose you can truncate the message and preserve some information, you won't get better than that from information theory reasons. a hash output of n bits can have no more than n bits of information.

If you are hoping to keep a lot of information about non random messages of unknown structure, cryptographic hash functions are very good. Apply e.g SHA3-256 to an arbitrary compressible message and you are likely to get very close to 256 bits of information.

Sadly(Luckily) finding the set of possible messages producing such a hash or saying anything interesting about them is beyond us.

0 + 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.