Score:0

Mapping number into number with big algorithmic entropy - how to do it?

tf flag
Tom

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?

Score:1
in flag

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.

Tom avatar
tf flag
Tom
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.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.