Re: Why unhashing is not possible?

roberson@xxxxxxxxxxxx (Walter Roberson) writes:

In article <barmar-C819FC.17045927122007@xxxxxxxxxxxxxxxxxxxxxxxx>,
Barry Margolin <barmar@xxxxxxxxxxxx> wrote:

In article <k1hcj.12858$vd4.5964@pd7urf1no>,
roberson@xxxxxxxxxxxx (Walter Roberson) wrote:

In article <uvgcj.20007$wy2.19474@edtnps90>,
Unruh <unruh-spam@xxxxxxxxxxxxxx> wrote:
"Sebastian G." <seppi@xxxxxxxxx> writes:
Barry Margolin wrote:
How could the hash possibly be guaranteed to be unique?
For a limited set of inputs, this is very easy.
Yes. then it is not a hash. It may be an encryption, or a translation.

"Minimal perfect hashing"

But the types of hashes and their properties are very dependent on WHY
you're hashing. The algorithms you use to implement a symbol table
(which is where perfect hashing becomes useful) are completely different
from those used for cryptography (where it's important that it be
difficult to generate the same hash) or password encryption (where
irreversibility is critical).

Types of hashes and their properties exist apart from why
you are hashing. Why you are hashing governs your choice of which
type of hash (and thus which properties) you would rationally
select. Your choice of whether to use an axe or a shovel to dig
a hole in the ground does not change the properties of axes and
shovels, but sometimes the axe would be the better choice (e.g.,
ice axes in ice, or digging axes when dealing with a forest fire);
sometimes a shovel would be better.

And sometimes I can use a shovel as an axe and an axe as a shovel. But this
does not mean that we should take the meaning of both to be so broad that
there is no distinction between them ( eg, an axe is something made of
metal with a handle-- purpose comes into the definition of axe).

The point is not relevant to Bill Unruh's statement that a "hash"
which is unique is "not a hash", which is what this subthread is about.
Your paragraph, quoted above, implicity agrees that "perfect hashing"
is a type of hashing; as perfect hashing hashes to a unique result
(over input it was designed for), Bill's statement appears to
be incorrect in context (which the original poster did not restrict
to cryptographic hashes.)

I will admit that my statement was technically wrong. However, in the
context that the OP seemed to be asking his question, it was I believe not.
The OP wanted to have some explanation for a friend as to why hashes were
hard to invert, since you knew the process which produced the hash. Now,
the typical time that hashes are hard to invert ( find a preimage ) is if
they are cryptographic hashes. Clearly the hash which takes the first bit
of the input as the output is NOT hard to invert, and thus the OPs question
makes no sense for that hash. However, I will admit that it is a hash.
The OP was clearly confused over the question he was asking, and as such
one had to try to understand what he really meant. I may have misunderstood
the context, but I do not think so. I do believe that he WAS asking about
cryptographic hashes. That is the context in which I answered the question.
Also, a hash which is unique and invertible to me is an encryption, but I
agree that in some contexts it could be a hash and in some an enctyption. I
for example would not call the messages sent using PGP a hash, even though
they are a mapping from the space of input function to the space of output
functions of length m where m=10^80. On the other hand, I could imagine
using the encryption of a 10 character input as a 10 character hash in some
contexts.

Thus this message, under the definition of any function from input to output
being a hash, could be considered a hash, but anyone who used that
definition would in most context be considered an idiot.



Sebastian's definition of what a "hash" is appears to me to be valid.

No, it is overbroad. It certainly captures an aspect of a hash, but is so
broad that it does not distinguish a has from anything else. Ie, it is so
broad that the word loses all meaning. So it is true, but meaningless.

It's just that most things which are technically hashes are not
very useful for specific purposes (just like most things that
are "compression" functions aren't very useful for much.)

And use/purpose should be part of the meaning of hash to make the meaning
useful. Words should be specific, so that when they are used, the person
listening actually gets some information transfered to them.


.

Relevant Pages

  • Re: "index" efficiency... any help or ideas?
    ... no general purpose hashing method, no matter how good, is good enough ... to prevent the possibility that everything hash into the same place. ... > Downside of hashes; if the data is stored externally, ... > perfect hashing are techniques that require analysis of the data in advance, ...
    (alt.lang.asm)
  • Re: A question on an article dealing with pass phrase and keys
    ... In the section Keys vs. Passphrases He mentions using a hashing ... first and it goes through the hash function first. ... Hashing the passphrase to produce a key will not increase ... This can be useful for various crypto applications, ...
    (sci.crypt)
  • Re: PAQ compression
    ... >> next 12 bits hold a hash value computed from previous bytes. ... In early versions of PAQ the context ... numeric data, not so much for "ordinary" data, eg, text). ... A group of 4 elements forms a bucket. ...
    (comp.compression)
  • Re: "index" efficiency... any help or ideas?
    ... > dealing with different searching algorithms. ... > cons of hashing vs. binary searching. ... That's the killer reason for using hashes in this application. ... Searching a hash table is ...
    (alt.lang.asm)
  • Re: Hashing
    ... using elfhash() for the hash function, and a closed hash table 30,241 in ... tokens, but for a first alpha version system is acceptable. ... However, I've isolated the whole hashing functionality, so that swapping it ... (just a little slow when getting above 20,000+ labels). ...
    (alt.lang.asm)