Is perfect hashing without buckets possable?

Okay, since you've clarified what you're trying to do, I rewrote my answer.

Okay, since you've clarified what you're trying to do, I rewrote my answer. To summarize: Use a real encryption algorithm. First, let me go over why your hashing system is a bad idea.

What is your hashing system, anyway? As I understand it, your proposed system is something like this: Your embedded system (which I will call C) is sending some sort of data with a value space of 10^11. This data needs to be kept confidential in transit to some sort of server (which I will call S).

Your proposal is to send the value hash(salt + data) to S. S will then use a rainbow table to reverse this hash and recover the data. Salt is a shared value known to both C and S.

This is an encryption algorithm An encryption algorithm, when you boil it down, is any algorithm that gives you confidentiality. Since your goal is confidentiality, any algorithm that satisfies your goals is an encryption algorithm, including this one. This is a very poor encryption algorithm First, there is an unavoidable chance of collision.

Moreover, the set of colliding values differs each day. Second, decryption is extremely CPU- and memory-intensive even for the legitimate server S. Changing the salt is even more expensive.

Third, although your stated goal is avoiding key management, your salt is a key! You haven't solved key management at all; anyone with the salt will be able to crack the message just as well as you can. Fourth, it's only usable from C to S.

Your embedded system C will not have enough computational resources to reverse hashes, and can only send data. This isn't any faster than a real encryption algorithm on the embedded device Most secure hashing algorithm are just as computationally expensive as a reasonable block cipher, if not worse. For example, SHA-1 requires doing the following for each 512-bit block: Allocate 12 32-bit variables.

Allocate 80 32-bit words for the expanded message 64 times: Perform three array lookups, three 32-bit xors, and a rotate operation 80 times: Perform up to five 32-bit binary operations (some combination of xor, and, or, not, and and depending on the round); then a rotate, array lookup, four adds, another rotate, and several memory loads/stores. Perform five 32-bit twos-complement adds There is one chunk per 512-bits of the message, plus a possible extra chunk at the end. This is 1136 binary operations per chunk (not counting memory operations), or about 16 operations per byte.

For comparison, the RC4 encryption algorithm requires four operations (three additions, plus an xor on the message) per byte, plus two array reads and two array writes. It also requires only 258 bytes of working memory, vs a peak of 368 bytes for SHA-1. Key management is fundamental With any confidentiality system, you must have some sort of secret.

If you have no secrets, then anyone else can implement the same decoding algorithm, and your data is exposed to the world. So, you have two choices as to where to put the secrecy. One option is to make the encipherpent/decipherment algorithms secret.

However, if the code (or binaries) for the algorithm is ever leaked, you lose - it's quite hard to replace such an algorithm. Thus, secrets are generally made easy to replace - this is what we call a key. Your proposed usage of hash algorithms would require a salt - this is the only secret in the system and is therefore a key.

Whether you like it or not, you will have to manage this key carefully. And it's a lot harder to replace if leaked than other keys - you have to spend many CPU-hours generating a new rainbow table every time it's changed! What should you do?

Use a real encryption algorithm, and spend some time actually thinking about key management. These issues have been solved before. First, use a real encryption algorithm.

AES has been designed for high performance and low RAM requirements. You could also use a stream cipher like RC4 as I mentioned before - the thing to watch out for with RC4, however, is that you must discard the first 4 kilobytes or so of output from the cipher, or you will be vulnerable to the same attacks that plauged WEP. Second, think about key management.

One option is to simply burn a key into each client, and physically go out and replace it if the client is compromised. This is reasonable if you have easy physical access to all of the clients. Otherwise, if you don't care about man-in-the-middle attacks, you can simply use Diffie-Hellman key exchange to negotiate a shared key between S and C.

If you are concerned about MitMs, then you'll need to start looking at ECDSA or something to authenticate the key obtained from the D-H exchange - beware that when you start going down that road, it's easy to get things wrong, however. I would recommend implementing TLS at that point. It's not beyond the capabilities of an embedded system - indeed, there are a number of embedded commercial (and open source) libraries available already.

If you don't implement TLS, then at least have a professional cryptographer look over your algorithm before implementing it.

The plan is to us it as part of a one way function to make the number secure so we can send it by insecure means. We will then look up the original number at the other end using a rainbow table. The problem is that the source the devices generally have 512k-4Meg of memory to use.

– Dreaddan Feb 3 at 14:02 @Dreaddan, updated my answer. In short: A hash is the wrong tool to use for the job. – bdonlan Feb 3 at 14:54 AES was my first choise but we've been told it's not really possable on the devices and keymanigment would be a nightmare if we could.

– Dreaddan Feb 3 at 15:53 1 @Dreaddan, there are other options for encryption beyond AES - and many of them aren't any more expensive than SHA1 or other hashes, but what you're trying to do is encryption, pure and simple. Doing silly things with hashes won't buy you any security at all - key management (and the existence of a key) is fundamental to security in cases like this. And there will always be the possibility of a collision.

If you're really short on processing power, try RC4, but make sure you drop the first few kilobytes of the stream. – bdonlan Feb 4 at 1:17 1 @bdonlan cheers - this is kinda what I expected for the implementation. I think the real answer there is that if generating a hash isn't more intensive than using a proper encryption method then we might as well do that.

– Dreaddan Feb 4 at 16:13.

There is obviously no such thing as a "perfect" hash unless you have at least as many hash buckets as inputs; if you don't, then inevitably it will be possible for two of your inputs to share the same hash bucket. However, it's unlikely you'll be storing all the numbers between 0 and 10^11. So what's the pattern?

If there's a pattern, there may be a perfect hash function for your actual data set. It's really not that important to find a "perfect" hash function anyway, though. Hash tables are very fast.

A function with a very low collision rate - and when hashing integers, that means nearly any simple function, like modulus - is fine and you'll get O(1) average performance.

1 +1. Perfect hashing without absolutely no knowledge about the input data is insane. – R.

Martinho Fernandes Feb 3 at 11:00 it must be perfect - we 100% cannot have a collision . @Martinho Fernandes: We know the data range, it's a number between 0 and 10000000000 (10^10). – Dreaddan Feb 3 at 14:02 @Dreaddan: you should make that clear in the question: "I have 10^10 numbers" is not the same as "I have numbers between 0 and 10^10".

Compare "I have 3 numbers: 42, 23, 17" with "I have numbers between 1 and 3: 1, 2, 3". – R. Martinho Fernandes Feb 3 at 14:37 @Martinho Fernandes: done – Dreaddan Feb 3 at 15:49.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.