0
$\begingroup$

I need to parameterize some PRNG, let's assume I need 32-bit numbers. But when numbers doesn't look very random it gives bad results. The creators of SplitMix had similar problem (note that from what I understand they didn't solve it right):

https://www.pcg-random.org/posts/bugs-in-splitmix.html

So I need a function which will transform let's say number 1 into something like 10011110001101110111100110111001. But number 10100111101101010110001111100101 with good algorithmic complexity (I mean Kolmogorov complexity) could stay similarly good (of course don't have to be the same).

So hashing by multiplying: x = x*2654435769 mod 2^32 is not the option, because we can find modular multiplicative inverse, which would give us 1 or something bad anywany. I was trying to use bit mixer from PCG:

uint32_t RXSMXS(uint32_t rxs)
{
    uint8_t r;

    r = rxs >> 28;
    rxs = rxs ^ (rxs >> (4 + r));
    rxs = rxs*277803737;
    return rxs^(rxs >> 22);
}

But it looks like it is also reversible 1 to 1 (the problem is bijection, not reversibility itself). The same murmur32:

uint32_t murmur32(uint32_t z)
{
z ^= (z >> 16);
z *= 0x85ebca6bul;
z ^= (z >> 13);
z *= 0xc2b2ae35ul;
return z ^ (z >> 16);
}

It is reversible and bijetcion, isn't it (so we can find input which give us so bad ouput as we want)?

So, is there a well known, efficient method to do it? I mean - take a number with some low (or high) Kolmogorov complexity and output a number with high Kolmogorov complexity. Of course such a function/mapping would not be bijection, because we just throw away some values. So the different keys/coefficients will sometimes produce the same results.

My idea is to define one half of the number as a constant, for example let most significant bits be: 10011110001101110000000000000000 and then just randomly choose least significant bits (then it could be every 16-bit number). And then put it in the bit mixer like murmur32 or something else. But we have still no guarantee that murmur32 would not transform for example 10011110001101110000000000000011 into 1, 2 or 3. So maybe I will not use a mixer (but such numbers may have the wrong algorithmic entropy in least significant bits).

Do you have any better but efficient ideas?

$\endgroup$

1 Answer 1

1
$\begingroup$

It sounds like you are just asking for a secure hash function.

You explicitly say you want it easy to calculate in one direction and hard to inverse. Which we normally call this requirement preimage resistance. It's hard to find $x$ so that $f(x)=y$.

Of course, if the original value is chosen from a small(low entropy) pool we will still be able to find it via exhaustive search.

Note the number 1 is not low entropy. Entropy is on distributions or collection of values, not single numbers.

$\endgroup$
1
  • $\begingroup$ I think rather about Kolmogorov complexity of binary number known also as algorithmic entropy or algorithmic complexity. I'm not sure if it is similar to binary entropy function (I'm not so into math). And it don't have to be secure. I wrote about inversing thinking about bijection, I meant getting back to input, by using some number. I will change a bit in my question. $\endgroup$
    – Tom
    Apr 10, 2022 at 7:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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