[docs]
class HINT:
"""
contains power2round, highbits, lowbits, makehint and use hint.
"""
def __init__(self, parameter: dict[str, int]):
self.q = parameter["q"]
self.d = parameter["d"]
self.N = parameter["N"]
self.gamma2 = parameter["gamma2"]
[docs]
def Power2Round(self, r: int) -> tuple[int, int]:
"""
Algorithm 35
Decomposes an integer ``r`` into (r1, r0) such that ::
r ≡ r1 * (2 * d) + r0 (mod q)
Args:
r (``int``): An integer coefficient.
Returns:
tuple (``r₁``, ``r₀``): A tuple containing the ``high bits r₁`` and ``low bits r₀``.
"""
# 1: r⁺ ← r mod q
r_plus = r % self.q
# 2: r₀ ← r⁺ mod± 2ᵈ
mod_val = 2**self.d
r0 = r_plus % mod_val
# Adjust to the centered range [-2^(d-1)+1, 2^(d-1)]
if r0 > mod_val // 2:
r0 -= mod_val
# 3: return ((r⁺ - r₀)/2ᵈ, r₀)
r1 = (r_plus - r0) // mod_val
return (r1, r0)
[docs]
def Power2RoundVector(self, t_vec: list[list[int]]) -> tuple[list[list[int]], list[list[int]]]:
"""
Algorithm 35 modified
Applies ``Power2Round`` component-wise to a ``vector`` of polynomials.
Args:
t_vec (``list[list[int]]``): A vector of polynomials.
Returns:
(tuple(list[list[int]], tuple(list[list[int]]))): ``Tuple(t₁, t₀)`` of two vectors of polynomials, where ``t₁`` contains the ``high bits`` and ``t₀`` contains the ``low bits``.
Raises:
TypeError: If the input is not a ``list`` or ``tuple``, or if any polynomial or coefficient is ``not an integer``.
"""
t1_vec: list[list[int]] = []
t0_vec: list[list[int]] = []
for poly in t_vec:
# print(poly)
poly_t1: list[int] = []
poly_t0: list[int] = []
for coeff in poly:
r1, r0 = self.Power2Round(coeff)
poly_t1.append(r1)
poly_t0.append(r0)
t1_vec.append(poly_t1)
t0_vec.append(poly_t0)
return (t1_vec, t0_vec)
[docs]
def Decompose(self, r: int) -> tuple[int, int]:
"""
Algorithm 36
Decompose ``r`` into ``(r1, r0)`` such that::
r ≡ r1 * (2 * gamma2) + r0 (mod q)
Args:
r (int): Integer in the range ``[0, q - 1]``.
Returns:
- ``r1`` The high bits.
- ``r0`` The low bits in the range
``[-2^(d-1)+1, 2^(d-1)]``.
Raises:
TypeError: If ``r`` is not an integer.
"""
r_plus = r % self.q
mod_val = 2 * self.gamma2
r0 = r_plus % mod_val
# Adjust to the centered range [-2^(d-1)+1, 2^(d-1)]
if r0 > mod_val // 2:
r0 -= mod_val
if (r_plus - r0) == self.q - 1:
r1 = 0
r0 = r0 - 1
else:
r1 = int((r_plus - r0) / (2 * self.gamma2))
return r1, r0
[docs]
def HighBits(self, r:int) -> int:
"""
Algorithm 37
Returns ``r1`` from the output of ``Decompose(r)``.
Args:
r (``int``): An integer in the range ``[0, q-1]``.
Returns:
r1 (``int``): The high bits ``r1``.
Raises:
TypeError: If ``r`` is not an integer.
"""
r1, _ = self.Decompose(r)
return r1
[docs]
def LowBits(self, r:int) -> int:
"""
Algorithm 38
Returns ``r0`` from the output of ``Decompose(r)``.
Args:
r (``int``): An integer in the range ``[0, q-1]``.
Returns:
r0 (``int``): The low bits ``r0``.
Raises:
TypeError: If ``r`` is not an integer.
"""
_, r0 = self.Decompose(r)
return r0
[docs]
def MakeHint(self, z: int, r:int) -> bool:
"""
Algorithm 39
Computes ``hint bit`` indicating whether adding ``z`` to ``r`` alters the ``high bits`` of ``r``.
Args:
z (``int``): An integer in the range ``[0, q-1]``.
r (``int``): An integer in the range ``[0, q-1]``.
Returns:
bool (``bool``): True if the high bits change, False otherwise.
Raises:
TypeError: If ``z`` or ``r`` is not an integer.
"""
r1 = self.HighBits(r)
v1 = self.HighBits(r + z)
return v1 != r1
[docs]
def UseHint(self, h: bool, r:int) -> int:
"""
Algorithm 40
Returns the ``high bits`` of ``r`` adjusted according to ``hint h``.
Args:
h (``bool``): The hint bit.
r (``int``): An integer in the range ``[0, q-1]``.
Returns:
r1 (``int``): The adjusted high bit.
Raises:
TypeError: If ``h`` is ``not a boolean``.
TypeError: If ``r`` is ``not an integer``.
"""
# if not isinstance(h, (int, bool)):
# raise TypeError("Input h must be a boolean or integer(0, 1).")
# if not isinstance(r, int):
# raise TypeError("Input r must be an integer.")
m = int((self.q - 1) / (2 * self.gamma2))
r1, r0 = self.Decompose(r)
if h == 1 and r0 > 0:
return (r1 + 1) % m
if h == 1 and r0 <= 0:
return (r1 - 1) % m
return r1