Source code for fips.FIPS204.sample
from .auxilary import AUXILARY
from .pack import PACK
from .hash import H, G
import math
[docs]
class SAMPLE:
"""
Algorithms for generating algebraic objects pseudorandomly from a seed rho, rho is a byte string whose length varies depending on the algorithm.
"""
def __init__(self, parameter: dict[str, int]):
self.auxilary = AUXILARY(parameter)
self.pack = PACK(parameter)
self.q = parameter["q"]
self.d = parameter["d"]
self.N = parameter["N"]
self.k = parameter["k"]
self.l = parameter["l"]
self.eta = parameter["eta"]
self.gamma1 = parameter["gamma1"]
self.gamma2 = parameter["gamma2"]
self._lambda = parameter["_lambda"] # using _lambda because lambda is not allowed.
self.tau = parameter["tau"]
self.omega = parameter["omega"]
self.beta = self.tau * self.eta
[docs]
def SampleInBall(self, rho: bytes) -> list[int]:
"""
Algorithm 29
Samples a polynomial ``c`` belonging to ``R`` with coefficients from ``{-1, 0, 1}`` and Hamming weight ``tau <= 64``.
Args:
rho (``bytes``): a bytestring of length ``lambda / 4`` bits.
Returns:
c (``list[int]``): a list of integers representing the polynomial.
Raises:
ValueError: if length of ``rho`` is not ``lambda / 4`` bits.
TypeError: if ``rho`` is not a bytestring.
"""
if not isinstance (rho, (bytes, bytearray)):
raise TypeError ("expected a bytestring as input.")
if not (len(rho) == int(self._lambda / 4)):
raise ValueError (f"value of rho must be exatcly {int(self._lambda / 4)} bits")
c = [0 for _ in range(self.N)]
ctx = H() # H.init()
ctx.Absorb(rho) # H.Abosrb(ctx, rho)
search_multiplier = 1
byte_stream = ctx.Squeeze(self.N * search_multiplier)
h = self.auxilary.BytesToBits(byte_stream[:8])
byte_position = 8
for i in range(256 - self.tau, 256):
j = byte_stream[byte_position]
byte_position = byte_position + 1
while j > i:
if byte_position + 1 > len(byte_stream): # to prevent byte_stream from going out of index.
search_multiplier = search_multiplier + 1
byte_stream = ctx.Squeeze(self.N * search_multiplier)
j = byte_stream[byte_position]
byte_position = byte_position + 1
c[i] = c[j]
if int(h[i + self.tau - 256]) == 1: # taking this as equivalent to being (-1)^h[i+tau-256]
c[j] = -1
else:
c[j] = 1
return c
[docs]
def RejNTTPoly (self, rho: bytes) -> list[int]:
"""
Algorithm 30
Samples a polynomial belonging to Tq.
Args:
rho (``bytes``): a bytestring of length 34.
Returns:
polynomial (``list[int]``): a list of integers representing the polynomial.
raises:
TypeError: if ``rho`` is not a ``bytestring``.
ValueError: if length of ``rho`` is not ``34`` bytes.
"""
# input checks.
if not (len(rho) == 34):
raise ValueError ("length of rho must be exatcly 34 bytes.")
# line 1: initialize j = 0 and the polynomial with all 0 coefficients.
j = 0
polynomial = [0 for _ in range (self.N)]
# line 2: initialize shake_128 ; G.init().
ctx = G()
ctx.Absorb(rho)
byte_stream = ctx.Squeeze(894)
byte_position = 0 # temprary variable to keep track of position in byte_stream.
# line 4: main rejection loop.
while j < 256:
if byte_position + 3 > len(byte_stream): # to prevent byte_stream from going out of index.
raise ValueError("ran out of bytes in rejection sampling.")
# line 5: take out next 3 bytes form the hash ; G.squeeze(ctx, 3).
selected_3_bytes = byte_stream[byte_position : byte_position + 3]
byte_position +=3 # update byte position to get next 3 byte on next selection.
# line 6: sample an integer from 3 selected bytes.
sampled_bytes = self.auxilary.CoeffFromThreeBytes(selected_3_bytes[0], selected_3_bytes[1], selected_3_bytes[2])
# line 7 to 9: increment j if sample is accepted.
if sampled_bytes != None:
polynomial[j] = sampled_bytes
j = j + 1
# line 11: return the constructed polynomial.
return polynomial
[docs]
def RejBoundedPoly (self, rho: bytes) -> list[int]:
"""
Algorithm 31
Samples an element a belonging to R with coefficients in [-eta, eta] computed via rejection sampling from rho.
Args:
rho (``bytes``): a bytestring of length ``66``.
Returns:
a (``list``): a list of integers representing the polynomial.
Raises:
TypeError: if ``rho`` is not a ``bytestring``.
"""
# input checks.
if not (len(rho) == 66):
raise ValueError ("length of rho must be exatcly 66 bytes.")
# line 1: initialize j and polynomial a.
j = 0
a = [0 for _ in range(self.N)]
# line 2: initialize shake_256 ; H.init().
ctx = H()
ctx.Absorb(rho)
byte_stream = ctx.Squeeze(481)
byte_position = 0 # temprary variable to keep track of position in byte_stream.
# line 4: main rejection loop.
while j < 256:
if byte_position + 1 > len(byte_stream): # to prevent byte_stream from going out of index.
raise ValueError("Rejection samplaing taking more than intended bytes.")
# line 5: take out next byte form the hash ; H.squeeze(ctx, 1).
z = byte_stream[byte_position]
byte_position += 1 # update byte position go get next byte on next selection.
# line 6: sample a number from z.
z0 = self.auxilary.CoeffFromHalfByte(z & 15)
# line 7: sample a number from z / 16 (floor).
z1 = self.auxilary.CoeffFromHalfByte(math.floor(z >> 4))
# line 8 to 11: rejection checking for z0.
if z0 != None:
a[j] = z0 # accepted.
j = j + 1
# line 12 to 15: rejection checking for z1.
if z1 != None and j < 256:
a[j] = z1 # accepted.
j = j + 1
# line 17: return the polynomial a.
return a
[docs]
def ExpandA (self, rho: bytes) -> list[list[list[int]]]:
"""
Algorithm 32
samples a ``k x l`` matrix of elements of ``Tq``.
Args:
rho (``bytes``): a bytestring of length ``32``.
Returns:
A (list[list[list[int]]]): a ``k x l`` matrix of polynomials.
raises:
ValueError: if length of ``rho`` is not ``32`` bytes.
"""
#input checks.
if not (len(rho) == 32) and not isinstance(rho, bytes):
raise ValueError ("rho must be a 32-bytes bytestring.")
A = [[[0] for _ in range(self.l)] for _ in range(self.k)] # initialize the matrix of polynomials with all 0s.
# line 1 to 2: loop over k and then l.
for r in range(self.k):
for s in range (self.l):
# line 3: concatenate rho with s and r.
rho_prime = rho + self.auxilary.IntegerToBytes(s, 1) + self.auxilary.IntegerToBytes(r, 1)
# line 4: construct a polynomial from rho_prime.
A[r][s] = self.RejNTTPoly(rho_prime)
return A # return the matrix A.
[docs]
def ExpandS (self, rho: bytes) -> tuple[list[list[int]], list[list[int]]]:
"""
Algorithm 33
Samples vector s1 belonging to R^l and s2 belonging to R^k, each with polynomial coordinates whose coefficients are in the interval [-eta, eta].
Args:
rho (``bytes``): a bytestring of length ``64``.
Returns:
s1 (``list``): a ``list`` of ``l`` polynomials representing the vector ``s1``.
s2 (``list``): a ``list`` of ``k`` polynomials representing the vector ``s2``.
Raises:
ValueError: if length of ``rho`` is not ``64`` bytes.
"""
#input checks.
if not (len(rho) == 64):
raise ValueError ("rho must be a 64-bytes bytestring.")
# # initialize and assign both s1 and s2.
s1 = [self.RejBoundedPoly(rho + r.to_bytes(2, "little")) for r in range(self.l)]
s2 = [self.RejBoundedPoly(rho + (s + self.l).to_bytes(2, "little")) for s in range(self.k)]
# line 7: return s1 and s2 polynomail vectors.
return (s1, s2)
[docs]
def ExpandMask(self, rho: bytes, mew: int) -> list[list[int]]:
"""
Algorithm 34
Samples a vector ``y ∈ R^l`` such that each polynomial ``y[r]`` has coefficients between ``-gamma1 + 1`` and ``gamma1``.
Args:
rho (``bytes``): a ``bytestring`` of length ``64``.
mew (``int``): an ``integer`` used in the sampling process.
Returns:
y (``list[list[int]]``): a ``list`` of polynomials representing the vector ``y``.
Raises:
ValueError: if length of ``rho`` is not ``64`` bytes.
TypeError: if ``mew`` is not an integer.
ValueError: if ``mew`` is a negative integer.
"""
if not (len(rho) == 64):
raise ValueError ("rho must be a 64-bytes bytestring.")
if mew < 0:
raise ValueError ("mew must be a non-negative integer.")
if self.gamma1 == (1 << 17):
# bit_count = 18
total_bytes = 576 # (256 * 18) / 8
else:
# bit_count = 20
total_bytes = 640 # (256 * 20) / 8
y = [[0] for _ in range(self.l)]
for r in range (self.l):
rho_prime = rho + self.auxilary.IntegerToBytes(mew + r, 2)
ctx = H()
ctx.Absorb(rho_prime)
v = ctx.Squeeze(total_bytes)
y[r] = self.pack.BitUnpack(v, self.gamma1 - 1, self.gamma1)
return y