2
$\begingroup$

Would there be an efficient way to implement a function with the following signature:

unsigned long long int random_word(size_t n, size_t m)

that would generate a random machine word (64 bits here) such that exactly m bits over the n least significant ones at set to 1. For example: random_word(10, 3) would generate a 64-bit random number such that 3 bits over the 10 LSBs are set to 1. For a given n and m every possible output should have equal probability (uniform distribution of possible permutations).

If assembly bit twiddling hacks to do that are known, great, if not, I am looking for references and research directions.

$\endgroup$

closed as off-topic by puzzlepalace, AleksanderRas, kelalaka, Luis Casillas, forest Aug 21 at 5:48

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Programming questions are off-topic even if you are writing or debugging cryptographic code. Unless your question is specifically about how the cryptographic algorithm, protocol or side-channel (mitigation) works, you should look into asking on Stack Overflow instead." – puzzlepalace, AleksanderRas, kelalaka, Luis Casillas, forest
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ If the percentage of samples that match the requirement from the full range of numbers isn't too small, then rejection sampling should work (only needs to be done on those n bits, the prefix can be randomized once and then you rejection sample the n bits) $\endgroup$ – Natanael Aug 20 at 19:20
  • 5
    $\begingroup$ Seems more like a programming challenge than crypto-related. Define "efficient":. Code size? Minimal number of uniformlly random bit used? Is that on average, for the first call, or..? Speed: for the first call, for a million calls with the same n,m..? Is the time to generate uniform random bits counted in the performance? $\endgroup$ – fgrieu Aug 20 at 19:20
  • $\begingroup$ Why do you need this in cryptography? $\endgroup$ – Conrado Aug 20 at 19:25
  • 1
    $\begingroup$ There's actually a second way that's likely more efficient (at least when m is far from n/2). Generate 64 minus n bits of random bits for the prefix, then simply generate a bitstring of m 1's and n-m 0's, and then you perform a randomized bitwise sort (with some random sort algorithms with a sufficiently small bias, using a unique random seed), and concatenate the two strings. $\endgroup$ – Natanael Aug 20 at 19:44
  • 1
    $\begingroup$ Drawing an error vector of a prescribed length and Hamming weight is one of the steps in the McEliece cryptosystem. $\endgroup$ – Squeamish Ossifrage Aug 21 at 16:57
2
$\begingroup$

I'd guess that you can simply split this into two problems:

  1. create 64 - n random bits, call this R
  2. shuffle n bits where m bits (at any location) are set to 1, call this P

Finally you can simply perform R | P (presuming big endian notation).

Shuffling lists of elements is an operation present in almost any language. If there is any inefficiency it would be in the shuffling algorithm (although Fisher-Yates is optimal, so you'd expect some form of that algorithm, possibly the inefficiency is getting values in a range...).

$\endgroup$
  • $\begingroup$ I'm thinking that you could also just generate a value x within of 0..n - i where i goes from 0 to m, where you set the x'th bit that is not set. That would be equivalent and easier to implement. $\endgroup$ – Maarten Bodewes Aug 20 at 23:39
  • $\begingroup$ Actually, I've proven both experimentally and theoretically that the method in the above comment should not introduce bias (this is easy enough to prove). $\endgroup$ – Maarten Bodewes Aug 23 at 5:38
1
$\begingroup$

The problem for choosing $k$ bits from $64$ ultimately comes down to computing a uniformly random integer $r$ with $0 \leq r < \frac{64!}{k!(64-k)!}$ then decoding it to determine which bits. The $k!$ in the denominator is annoying, but we can ignore it, because we can just allow our algorithm to have $k!$ random numbers that map to the same output (setting bit 0 then bit 4 is the same as setting bit 4 then bit 0). Now we just have multiplying a decreasing sequence starting from $64$: with $k=4$ this equals $64 * 63 * 62 * 61$.

So for efficiency, you select a random number in $0 \le r_0 < 64$, then another $0 \le r_1 < 63$ ... through $0 \le r_{k-1} < 64-(k-1)$ each time using $r_n$ to select among the remaining unset bits.

I threw the following Python code together showing the idea, though it's not fast or anything:

# b = size of integer type
# n = number of set bits
# random_limited(x) is some function returning [0, x) sufficiently uniformly
def random_n_set_bits(b, n):
    assert b > 0
    assert n >= 0 and n <= b
    result = 0
    available = list(range(b))
    for i in range(n):
        index = random_limited(len(available))
        bit = available[index]
        available = available[:index] + available[index + 1:]
        result |= (1 << bit)
    return result
$\endgroup$

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