1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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?) $\endgroup$ – D.W. Aug 24 '14 at 23:22
  • $\begingroup$ This question appears to be off-topic because it is about compressing or encoding data, not cryptography. $\endgroup$ – otus Aug 25 '14 at 7:30
  • 1
    $\begingroup$ 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? $\endgroup$ – poncho Aug 25 '14 at 11:49
  • $\begingroup$ Yes..Chopping bits will not create a one to one mapping $\endgroup$ – Jean Aug 25 '14 at 12:19
3
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$ – Jean Aug 23 '14 at 13:43
  • $\begingroup$ @Jean You can always use a standard hash function, if the number of collisions is acceptable is for you to decide. $\endgroup$ – CodesInChaos Aug 23 '14 at 16:56
  • $\begingroup$ 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/… $\endgroup$ – Jean Aug 24 '14 at 2:03
  • $\begingroup$ @Jean, with 64 million vectors you need at least something like $2^{52}$ buckets to have a chance of avoiding collisions. $\endgroup$ – otus Aug 25 '14 at 9:09
  • $\begingroup$ @otus - Is there some hashing function which can give me less than 1% collision without using prohibitive number of buckets ? $\endgroup$ – Jean Aug 25 '14 at 12:22
1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – Seth Aug 23 '14 at 18:46
  • $\begingroup$ @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. $\endgroup$ – rmalayter Aug 23 '14 at 20:37
  • $\begingroup$ 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? $\endgroup$ – Seth Aug 23 '14 at 22:00
  • $\begingroup$ @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? $\endgroup$ – rmalayter Aug 23 '14 at 23:18

Not the answer you're looking for? Browse other questions tagged or ask your own question.