# Expandable hash function

I have been studying a cryptosystem using Mersenne primes. More specifically, this paper.

I have implemented this cryptosystem in Python, but I am missing the key encapsulation system.

On page 12, they refer to something known as an "expandable hash function". It should take as input a $$\lambda$$-bit string and output a uniformly random $$n$$-bit string ($$\lambda<) 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?

• @kelalaka but what about the Hamming weight? May 24 at 20:29
• Hmm, would this just be $H'(m)\leftarrow_\$ S(\text{1}^h\parallel\text{0}^\left(n-h\right))$? All you gotta do is find a way to use$H\$ to uniformly randomly select a permutation of '1' * h + '0' * (n-h). Have you got any candidates for expandable hash functions currently? (This question may prove informative or helpful) May 25 at 17:31
• @JamesTheAwesomeDude no, I have not. How would you implement it in python? May 25 at 18:32
• I was too dumb to properly understand or implement it, but it appears that this paper provides a general method for doing so (or, at least, constructing a function that constructs functions that do so) May 26 at 15:13
• While I haven't yet figured out the permutation generator, It looks like pycryptodome includes a reputable expandable-output hash function: “Are there any variable length hash functions available for Python? May 27 at 4:27

Remember: a random permutation (or, when taken bitwise, "a hamming-weight-preserving one-way function") 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 DRBG:

from Crypto.Hash import SHAKE256
from random import Random
from functools import reduce
from itertools import repeat, islice

def deterministic_shuffle(seq, key, alg=SHAKE256):
"""Applies a pseudorandom permutation from key to seq"""
SpongeBasedRandom(key, alg.new).shuffle(seq)

class SpongeBasedRandom(Random):
def __init__(self, seed, spongefactory, blocksize=1):
sponge = spongefactory(seed)
def getrandbits(self, k):
return _concatbits(islice(self._randbits, k))
# Fix the following functions to prevent implementation-dependency
def randbytes(self, n):
return self.getrandbits(n * 8).to_bytes(n, 'big')
def _randbelow(self, n):
"""Version of Python 3000's Random._randbelow that doesn't waste bits"""
if n <= 1:
return 0
getrandbits = self.getrandbits
k = (n-1).bit_length()
r = getrandbits(k)
while r >= n:
r = getrandbits(k)
return r
def shuffle(self, x):
"""Modern Fisher-Yates shuffle"""
randbelow = self._randbelow
for i in reversed(range(1, len(x))):
j = randbelow(i + 1)
x[i], x[j] = x[j], x[i]

def _ibytestobits(ibytes):
yield from (((i & (0b1 << k)) >> k) for byte in ibytes for i in byte for k in reversed(range(8)))

def _concatbits(x):
return reduce((lambda acc, cur: ((acc << 1) | cur)), x)



SHAKE256 was used in the example code; it should be easily repurposeable to any bit generator. See this answer for some other ideas. To use this in your code would be something like:

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

# An n-element bit sequence of hamming weight h
bitstream = ([1] * h) + ([0] * (n - h))
print(_concatbits(bitstream).to_bytes(n // 8, 'big').hex())

deterministic_shuffle(bitstream, k)
print(_concatbits(bitstream).to_bytes(n // 8, 'big').hex())

• Interestingly, according to some dude on Quora, Fisher-Yates (which Python uses) is "optimal" -- his description of why seems underwhelming, but I don't doubt it per se... Jun 16 at 15:12
• (Admittedly, with the key functions fixed thus, I suppose it doesn't actually need to subclass Random…) Jun 16 at 20:16