Expandable hash function

Question

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<<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?

Answer 1

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 well-known correct algorithms to do this — Python itself, for example, makes it quite convenient to just leverage its shuffle implementation by subclassing Random with your choice of DRBG:

from random import Random
from resource import getpagesize as _getpagesize
from functools import reduce as _reduce
from itertools import islice as _islice, repeat as _repeat

from Cryptodome.Hash import SHAKE256


def deterministic_shuffle(seq, seed, sponge=SHAKE256):
    """Applies a pseudorandom permutation from arbitrary bytestring `seed` to mutable sequence `seq`, using SHAKE256 as the DRBG."""
    stream = sponge.new(data=seed)
    random = StreamBasedRandom(stream=stream, blocksize=136)
    random.shuffle(seq)


class StreamBasedRandom(Random):
    def __init__(self, stream, blocksize=_getpagesize()):
        self._randbitgen = _ibytestobits(map(stream.read, _repeat(blocksize)))
    def getrandbits(self, k):
        return _concatbits(_islice(self._randbitgen, 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):
        """Replacement for CPython's Random._randbelow that wastes very few bits"""
        if n <= 1:
            return 0
        getrandbits = self.getrandbits
        k = (n - 1).bit_length()
        a = getrandbits(k)
        b = 2 ** k
        if n == b:
            return a
        while (n * a // b) != (n * (a + 1) // b):
            a = a * 2 | getrandbits(1)
            b *= 2
        return n * a // b
    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):
    """Turns an iterator of bytes into an iterator of its component bits, big-endian"""
    yield from ((i >> k) & 0b1 for b in ibytes for i in b for k in reversed(range(8)))

def _concatbits(bits):
    """Takes a finite iterator of bits and returns their big-endian concatenation as an integer"""
    return _reduce((lambda acc, cur: ((acc << 1) | cur)), bits, 0)

(SHAKE256 was used in this example code; it should be easily repurposeable to any bit generator. See this answer for some other ideas, and the appendix to this answer for a concrete example of how that might be done.)

To use this in your code would be something like this:

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))
deterministic_shuffle(bitstream, k)

print("Shuffled bitstream:", _concatbits(bitstream).to_bytes(n // 8, 'big').hex())

---

Appendix: example usage of another DRBG

# this block of code depends on StreamBasedRandom, defined above
from types import SimpleNamespace as _SimpleNamespace

from Cryptodome.Cipher import AES
from Cryptodome.Hash import SHA256


def deterministic_shuffle(seq, seed, nonce=b''):
    """Applies a pseudorandom permutation from 256-bit (32-byte) `seed` to mutable sequence `seq`, using AES-256-CTR as the DRBG."""
    assert len(seed) == 32, "seed must be 256 bits (32 bytes) long for AES-256."
    cipher = AES.new(key=seed, mode=AES.MODE_CTR, nonce=nonce)
    def randbytes(n):
        return cipher.encrypt(b'\x00' * n)
    stream = _SimpleNamespace(read=randbytes)
    random = StreamBasedRandom(stream=stream, blocksize=cipher.block_size)
    random.shuffle(seq)

def _normalize(data):
    return SHA256.new(data).digest()

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

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

print("AES-shuffled bitstream:", _concatbits(bitstream).to_bytes(n // 8, 'big').hex())