# Efficiently map $2^n$ unique 64-bit vectors to $2^n$ $n$-bit vectors where $n < 64$? [closed]

Is there an efficient way to map $2^n$ unique 64-bit vectors to $2^n$ $n$-bit vectors where $n < 64$?

• How are you going to represent the set of $2^n$ unique 64-bit vectors? What does that set look like? The answer is going to depend upon these details. Depending upon what your set of $2^n$ 64-bit vectors looks like, the answer might be very different. Therefore, we can't answer the question until you edit your question to give us that sort of information; I'm voting to close as "too broad". You can fix the question by editing it. (Also, I suggest you edit it to tell us what you tried and what research you've done on your own. You did do significant research before asking, right?)
– D.W.
Aug 24, 2014 at 23:22
• This question appears to be off-topic because it is about compressing or encoding data, not cryptography.
– otus
Aug 25, 2014 at 7:30
• I'll vote to close as well; but you might want to consider: "what properties do you want from your mapping?" If you want just any mapping, just chopping off $64-n$ bits off the vectors works fine -- is there a reason why that isn't sufficient? Aug 25, 2014 at 11:49
• Yes..Chopping bits will not create a one to one mapping
– Jean
Aug 25, 2014 at 12:19

In general, no. There are: $${2^{64} \choose 2^n} = \frac{2^{64}!}{2^{n}!(2^{64}-2^n)!}$$ possible ways of selecting $2^n$ distinct 64-bit vectors. This is a huge number; using Stirling's approximation of factorials, when $2^{n}$ is substantially smaller than $2^{64}$ (i.e. when $n$ is smaller than $55$ or so), this number of combinations is approximately equal to: $$\sqrt{\frac{1}{2\pi}} 2^{-n/2} 2^{(64-n)2^n}$$ Therefore, any generic method for doing the mapping you seek must, necessarily, use enough memory on average to accommodate that many possible combinations. For instance, if $n = 32$, then you will need a minimum of 137 gigabytes. In fact, the naive method of storing all $2^{32}$ 64-bit vectors in a sorted array, using a binary search to locate the index of a given value, will use twice as much, but if the values are sorted and more or less uniformly spread over the space of 64-bit vectors, then the difference between two successive vectors will fit in less bits (a bit more than 32) so you could, realistically, do your mapping with 160 gigabytes or so.

Of course, the argument above is for generic methods. If you know how the $2^n$ 64-bit vectors are generated, then a more efficient method may be possible. As an extreme case, if the 64-bit vectors all end with 32 bits of value 0, then simple truncation will work for your mapping.

• I agree that there are too many mappings possible.Should that be a concern ? I can implement a cheap hash function to create a mapping out=(in*rand1+rand2)mod2^n with the risk of many collisions. I was wondering if it is theoretically impossible to create a function with almost no collisions.
– Jean
Aug 23, 2014 at 13:43
• @Jean You can always use a standard hash function, if the number of collisions is acceptable is for you to decide. Aug 23, 2014 at 16:56
• I have tried using many hash functions. When tried to map 64million 64bit vectors to 128million buckets I was getting 22% collision. stackoverflow.com/questions/25221410/…
– Jean
Aug 24, 2014 at 2:03
• @Jean, with 64 million vectors you need at least something like $2^{52}$ buckets to have a chance of avoiding collisions.
– otus
Aug 25, 2014 at 9:09
• @otus - Is there some hashing function which can give me less than 1% collision without using prohibitive number of buckets ?
– Jean
Aug 25, 2014 at 12:22

I believe this can be reduced to a case of format-preserving encryption. http://en.m.wikipedia.org/wiki/Format-preserving_encryption Using one of the many algorithms for FPE, you should be able to do such a mapping.

EDIT: As Seth points out in the comments to my original answer, the "cycling" method of FPE doesn't work here, but the first method described by Black & Rogaway might be practical if n<30. But this is really no more efficient than a straightforward array mapping as described in Thomas's answer to the question. The Black-Rogaway paper on format preserving encryption is at http://www.cs.ucdavis.edu/~rogaway/papers/subset.pdf

• The "cycle-walking" method wouldn't work here because your target space is not your source space. For example, you could have two inputs X1 and X2 in your source space such that AES_K(X1) = X2 (it would make slightly more sense to use DES here, but same thing would happen). In this case, X1 and X2 would then map to the same point in your target space, unless X2 was already in it.
– Seth
Aug 23, 2014 at 18:46
• @Seth, I think it would still work, as no two inputs would map to the same output. If you cycle until you have a value less than 2^n, unique inputs would never collide if a block cipher (DES or whatever 64-bit block cipher). A block cipher is not a hash function. I agree you could hit an input value after X iterations, but so long as every input gets at least one iteration by definition that is not a problem. Aug 23, 2014 at 20:37
• I'm not sure what you're arguing. For concreteness, let's use the example I gave earlier, and suppose that, say, n = 63, both x1 and x2 are at least 2^63, x2 = DES_K(x1), and suppose that y = DES_K(x2) < 2^63. My understanding of your proposal is that both x1 and x2 would map to y because this is the first value in [0, 2^63) we reach by repeated application of DES_K, regardless of whether we start from x1 or from x2. If this is incorrect, could you please clarify how the mapping is computed?
– Seth
Aug 23, 2014 at 22:00
• @Seth, I just re-read the major Black-Rogaway paper at cs.ucdavis.edu/~rogaway/papers/subset.pdf and realize you are correct. I was assuming their first method and the second method had the same properties; they clearly do not due to the large storage+sort required for the first method. If n<<2^64, the first method in the B-R paper might apply. So I now think you are right and I'm wrong; cycling won't work. What's the etiquette here, do I edit my answer or suck it up and take the pummeling of down-votes? Aug 23, 2014 at 23:18