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?

  • 2
    $\begingroup$ @kelalaka but what about the Hamming weight? $\endgroup$ May 24 at 20:29
  • $\begingroup$ 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) $\endgroup$ May 25 at 17:31
  • $\begingroup$ @JamesTheAwesomeDude no, I have not. How would you implement it in python? $\endgroup$ May 25 at 18:32
  • $\begingroup$ 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) $\endgroup$ May 26 at 15:13
  • $\begingroup$ 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? $\endgroup$ 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)
        self._randbits = _ibytestobits(map(sponge.read, repeat(blocksize)))
    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())

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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