I'm searching for way to generate secure pseudo random sequence with a fixed Hamming weight using a seed. I found below code but I need a seed to generate a sequence ... (and need know if is possible add secure property too . i.e one-way)

from random import shuffle

def gen(ham, bits=32):
    # generate a list with the correct number of 1's
    x = [1]*ham+[0]*(bits-ham)
    # convert back to a number
    return int(''.join(map(str,x)),2)

>> print('\n'.join(bin(gen(5,15)) for x in range(10)))
  • $\begingroup$ As it stands this question does not meet my quality expectations for this site. In the future please explain in greater detail what you want (e.g., what your specific requirements are), explain the context/motivation, do some research on your own, and show us what research you have done and what you have tried and where you got stuck. And pick just one question: a block cipher is very different from a PRG. P.S. What you want is obviously impossible if the length of the output is equal to the length of the input, as in your example. $\endgroup$ – D.W. Jun 21 '14 at 2:08
  • $\begingroup$ @D.W. I'm edit my question $\endgroup$ – juaninf Jun 21 '14 at 14:34
  • $\begingroup$ with a fixed Hamming weight I'm guessing fixed to a limit of $l$ to a given string $S$? You can generate a string of numbers of length $l$ and use them as an index of where in $S$ the changes will be made. The Hamming distance on its own (as you seem to use it in code) doesn't mean anything, it is a measure of difference of two strings. Apologies if I've missed something in your source code, I'm not familiar with that language. $\endgroup$ – rath Jun 21 '14 at 16:53
  • $\begingroup$ Use the output of a crypto-quality PRG as your seed. Done. Yes, it'll be secure if the PRG is secure. $\endgroup$ – D.W. Jun 21 '14 at 17:44

Use a crypto-quality pseudorandom generator PRG (e.g., a stream cipher) to stretch a 128-bit random seed (key) into an unlimited stream of pseudorandom bits. Then, you use it to generate a random $n$-bit string with $k$ bits set.

The latter step is relatively easy. Generate a random integer between $1$ and $C(n,k)$ (inclusive), using your stream of pseudorandom bits. If the integer is $\le C(n-1,k-1)$, then output a 1 as the first bit of output, followed by a $n-1$-bit string with $k-1$ bits set; otherwise, output a 0 as the first bit of output, followed by a $n-1$-bit string with $k$ bits set. The "followed by" part can be done using a recursive call.

See also https://stackoverflow.com/q/2060774/781723.

This construction will be as secure as your PRG, so if you use a crypto-strength PRG, it will be secure.


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