search

pauldreik / random_foreach

code for randomly generating all numbers in a range exactly once
Boost Software License 1.0
3 stars 0 forks source link

use a bijective mixer #4

Open martinus opened 4 years ago

martinus commented 4 years ago

Hi, I saw your talk and have a few suggestions concerning the encryption. I think it is enough to use a good bijective mixer like murmurhash's fmix:

uint64_t encrypt(uint64_t h) {
    h ^= h >> 33;
    h *= 0xff51afd7ed558ccd;
    h ^= h >> 33;
    h *= 0xc4ceb9fe1a85ec53;
    h ^= h >> 33;
    return h;
}

Node that the x ^= x>>n operation basically is used to mix the lower bits, and the multiplications are used to mix the upper bits. Enough of these operations and h is well mixed. Both operations are reversible, so they are bijective.

To support arbitrary number of bits, this should work:

uint64_t encrypt(int bits, uint64_t h) {
    uint64_t shift = bits/2;
    uint64_t mask = (1<<bits) - 1;

    h ^= h >> shift;
    h = (h * 0xff51afd7ed558ccd) & mask;
    h ^= h >> shift;
    h = (h * 0xc4ceb9fe1a85ec53) & mask;
    h ^= h >> shift;
    return h;
}

Although I don't know about the randomness quality.

It is also possible to support a seed for arbitrary random iteration sequences:

uint64_t encrypt(int bits, uint64_t seed, uint64_t h) {
    uint64_t shift = bits/2;
    uint64_t mask = (1<<bits) - 1;

    h ^= (seed & mask);
    h ^= h >> shift;
    h = (h * 0xff51afd7ed558ccd) & mask;
    h ^= h >> shift;
    h = (h * 0xc4ceb9fe1a85ec53) & mask;
    h ^= h >> shift;
    return h;
}

Not that only the last few bits of the seed are actually used, so this could certainly be improved.

pauldreik commented 4 years ago

Interesting idea, will give it a try! The best thing is that this also should be possible to accelerate with simd (as in the repo, but not shown in the presentation). I believe it should be below 9 cycles per output value. It is a fun fact that Björn Fahller rewrote my lazy fisher yates using guess what, the robin hood hash! Small world.

martinus commented 4 years ago

Ha, the world is really small :)

pauldreik commented 4 years ago

For this to work as a block cipher, it needs to be reversible. The xor between the upper and lower bits is reversible. For the prime multiplication, I had to convince myself it was invertible. I knew of the related inverse multiplication trick for regular division (multiply+shift), but I did not know how to actually calculate it. So I borrowed a book on number theory from the work library. This was fun! The resulting algorithm of finding the inversion multiplier is in https://github.com/pauldreik/random_foreach/blob/c7cda2514f593adc5adab50bfe4ccffc6c5e0cc1/MurmurCryptFixed64.h#L109

What remains is to implement the N-bit version and put it in the shootout. Unfortunately I ran out of time now but will be back later.

martinus commented 4 years ago

Nice progress! Although I don't know why you actually need to be able to reverse it?

Also I think it's more accurate to say that the reverse works with odd number. E.g it works with 9, but doesn't with the prime 2. I think most of the time it is enough to use a random odd number for the multiply mixing step.

pauldreik commented 4 years ago

Nice progress! Although I don't know why you actually need to be able to reverse it?

I don't, I just want to prove that it is a block cipher (instead of just a hash). One way of doing that is to find the decryption function!

Also I think it's more accurate to say that the reverse works with odd number. E.g it works with 9, but doesn't with the prime 2. I think most of the time it is enough to use a random odd number for the multiply mixing step.

Yes, any p with gcd(p,2^N)==1 works. Since all odd numbers lack 2 in their factorization and the factors of 2^N are all 2, they share no common factors and the greatest common divisor is 1.

I did not think of this since I was focused on the particular p from murmurhash. It suggests that one can use the multiplication factor as encryption key. I guess the choice of a prime for murmur is not arbritrary, and also that a particular prime has been selected with good mixing properties.

pauldreik commented 4 years ago

Notes to self (I wish I knew about these before I started :-)