Matrix randomness extractor


Reading time: about 2 minutes

Making a simple randomness extractor using random matrix multiplications.

In [2]:
def make_extractor(in_bytes, out_bytes):
    matr = [os.urandom(1)[0] for _ in range(in_bytes * out_bytes)]
    matr = np.array(matr, dtype=np.ubyte).reshape((in_bytes, out_bytes))
    def extract(buf):
        buf = np.array(list(buf), dtype=np.ubyte)
        res = np.dot(buf, matr)
        return bytes(list(res))
    return extract
In [3]:
output_size = int(256 / 8)

IV = bytes([os.urandom(1)[0] for _ in range(output_size)])

compr = make_extractor(output_size * 2, output_size)

data = b"Waddup my dudes, it's Pickle Rick! No, wait! It's Tiny Rick!"

state = IV
while data:
    block = bytearray(output_size * 2)
    i = 0
    for c in state:
        block[i] = c
        i += 1
    for _ in range(min(len(data), output_size)):
        block[i] = data[0]
        data = data[1:]
        i += 1
    state = compr(block)

print(state.hex())
Out:
b8bafef6b76092ee2241b356f2ad1e03ae69ff4ec65de0e404bec88d976c79ab

The following pages link here

Citation

If you find this work useful, please cite it as:
@article{yaltirakliwikimatrixrandomnessextractor,
  title   = "Matrix randomness extractor",
  author  = "Yaltirakli, Gokberk",
  journal = "gkbrk.com",
  year    = "2024",
  url     = "https://www.gkbrk.com/wiki/matrix-randomness-extractor/"
}
Not using BibTeX? Click here for more citation styles.
IEEE Citation
Gokberk Yaltirakli, "Matrix randomness extractor", October, 2024. [Online]. Available: https://www.gkbrk.com/wiki/matrix-randomness-extractor/. [Accessed Oct. 10, 2024].
APA Style
Yaltirakli, G. (2024, October 10). Matrix randomness extractor. https://www.gkbrk.com/wiki/matrix-randomness-extractor/
Bluebook Style
Gokberk Yaltirakli, Matrix randomness extractor, GKBRK.COM (Oct. 10, 2024), https://www.gkbrk.com/wiki/matrix-randomness-extractor/

Comments

Comment by Guest
2023-11-15 at 22:07
Spam probability: 2.06%

Hey just wondering how do you prove that multiplying a random matrix is an extractor? Leftover hash lemma doesn't seem to work here because of linearity of matrices...

© 2024 Gokberk Yaltirakli