Expandable hash function I have been studying a cryptosystem using Mersenne primes. More specifically, this paper: https://eprint.iacr.org/2017/481.pdf
I have implemented this cryptosystem in python but I am missing the key encapsulation system.
In page 12, they refer to something known as &quot;expandable hash function&quot;. It should take as input a $\lambda$-bit string and output an uniformly random $n$-bit string ($\lambda&lt;&lt;n$) of Hamming weight $h$. This weight $h$ is already determined (actually $h=\lambda$).
I am kind of new to this stuff. Is there a way to implement this hash function in python? Many thanks in advance.
Remember: a random permutation (aka &quot;a hamming-weight-preserving one-way function&quot;) is known in layman's terms as a shuffle; there are trivially correct algorithms to do this; Python itself, though, makes it quite convenient to just leverage its shuffle implementation by subclassing Random with your choice of deterministic CSPRNG:
from Crypto.Hash import SHAKE256
from random import Random


def deterministic_shuffle(seq, key, alg=SHAKE256):
    &quot;&quot;&quot;Applies a hamming-weight-preserving random permutation to seq&quot;&quot;&quot;
    SpongeBasedRandom(key, alg.new).shuffle(seq)


class SpongeBasedRandom(Random):
    def __init__(self, seed, spongefactory):
        super().__init__()
        self._sponge = spongefactory(seed)
    def getrandbits(self, k):
        n = -(-k // 8)
        # FIXME: squeezes-and-then-wastes k % 8 bits -- Is that
        # a security issue?
        # It'd take about +5 or +6 SLOC to patch it, just dunno if
        # it'd be worth it to bother
        return int.from_bytes(self._sponge.read(n), 'little') &amp; (2 ** k - 1)
    def randbytes(self, n):
        return self._sponge.read(n)


k = b'Hyper Secret Input Key'
h = len(k) * 8
n = 4096
assert n &gt; (8 * h)

bitstream = ([1] * h) + ([0] * (n - h))
deterministic_shuffle(bitstream, k)

print(bitstream)