from __future__ import annotations
import random
import pytest
from inspiring_oracle.automorph import G, h, tau, tau_g, tau_g_pow, tau_h
from inspiring_oracle.params import ORACLE_SMALL, ORACLE_TINY
from inspiring_oracle.ring import add, mul
def rand_poly(rng: random.Random, d: int, q: int) -> list[int]:
return [rng.randrange(q) for _ in range(d)]
def x_pow(k: int, d: int) -> list[int]:
out = [0] * d
out[k] = 1
return out
@pytest.fixture
def rng():
return random.Random(0xBEEF)
class TestMonomialKAT_tau_g_d8:
KAT = [
(0, 0, +1),
(1, 5, +1),
(2, 2, -1),
(3, 7, -1),
(4, 4, +1),
(5, 1, -1),
(6, 6, -1),
(7, 3, +1),
]
@pytest.mark.parametrize("i,pos,sign", KAT)
def test_tau_g_on_monomial(self, i: int, pos: int, sign: int) -> None:
d, q = 8, 12289
result = tau_g(x_pow(i, d), q)
expected = [0] * d
expected[pos] = sign % q
assert result == expected, (
f"tau_g(X^{i}): got {result}, expected {expected}"
)
class TestMonomialKAT_tau_h_d8:
@pytest.mark.parametrize("k", list(range(8)))
def test_tau_h_on_monomial(self, k: int) -> None:
d, q = 8, 12289
result = tau_h(x_pow(k, d), q)
expected = [0] * d
if k == 0:
expected[0] = 1
else:
expected[d - k] = q - 1 assert result == expected, (
f"tau_h(X^{k}): got {result}, expected {expected}"
)
class TestOrders:
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_tau_g_iterated_d_over_2_times_is_identity(self, params, rng) -> None:
d, q = params.d, params.q
a = rand_poly(rng, d, q)
b = a
for _ in range(d // 2):
b = tau_g(b, q)
assert b == a
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_tau_g_pow_d_over_2_is_identity(self, params, rng) -> None:
d, q = params.d, params.q
a = rand_poly(rng, d, q)
assert tau_g_pow(a, d // 2, q) == a
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_tau_g_pow_smaller_exponents_are_not_identity(self, params, rng) -> None:
d, q = params.d, params.q
a = rand_poly(rng, d, q)
for j in range(1, d // 2):
assert tau_g_pow(a, j, q) != a, (
f"tau_g^{j} should not be identity but it equals input"
)
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_tau_h_squared_is_identity(self, params, rng) -> None:
d, q = params.d, params.q
a = rand_poly(rng, d, q)
assert tau_h(tau_h(a, q), q) == a
class TestComposition:
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_tau_g_pow_zero_is_identity(self, params, rng) -> None:
d, q = params.d, params.q
a = rand_poly(rng, d, q)
assert tau_g_pow(a, 0, q) == a
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_tau_g_pow_one_equals_tau_g(self, params, rng) -> None:
d, q = params.d, params.q
a = rand_poly(rng, d, q)
assert tau_g_pow(a, 1, q) == tau_g(a, q)
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_tau_g_pow_composes_via_addition_of_exponents(self, params, rng) -> None:
d, q = params.d, params.q
a = rand_poly(rng, d, q)
for i in range(d // 2):
for j in range(d // 2):
lhs = tau_g_pow(tau_g_pow(a, i, q), j, q)
rhs = tau_g_pow(a, (i + j) % (d // 2), q)
assert lhs == rhs, f"tau_g^{i} o tau_g^{j} != tau_g^{(i+j)}"
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_tau_composition_via_index_multiplication(self, params, rng) -> None:
d, q = params.d, params.q
a = rand_poly(rng, d, q)
odd_indices = [g for g in range(1, 2 * d, 2)]
for g1 in odd_indices[:6]:
for g2 in odd_indices[:6]:
lhs = tau(tau(a, g2, q), g1, q)
rhs = tau(a, (g1 * g2) % (2 * d), q)
assert lhs == rhs, (
f"tau_{g1} o tau_{g2} != tau_{(g1*g2) % (2*d)}"
)
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_tau_with_g_one_is_identity(self, params, rng) -> None:
d, q = params.d, params.q
a = rand_poly(rng, d, q)
assert tau(a, 1, q) == a
class TestCommutativity:
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_tau_g_and_tau_h_commute(self, params, rng) -> None:
d, q = params.d, params.q
for _ in range(20):
a = rand_poly(rng, d, q)
assert tau_g(tau_h(a, q), q) == tau_h(tau_g(a, q), q)
class TestRingHomomorphism:
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_tau_g_preserves_addition(self, params, rng) -> None:
d, q = params.d, params.q
for _ in range(20):
a = rand_poly(rng, d, q)
b = rand_poly(rng, d, q)
assert tau_g(add(a, b, q), q) == add(tau_g(a, q), tau_g(b, q), q)
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_tau_g_preserves_multiplication(self, params, rng) -> None:
d, q = params.d, params.q
for _ in range(20):
a = rand_poly(rng, d, q)
b = rand_poly(rng, d, q)
assert tau_g(mul(a, b, q), q) == mul(tau_g(a, q), tau_g(b, q), q)
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_tau_h_preserves_addition(self, params, rng) -> None:
d, q = params.d, params.q
for _ in range(20):
a = rand_poly(rng, d, q)
b = rand_poly(rng, d, q)
assert tau_h(add(a, b, q), q) == add(tau_h(a, q), tau_h(b, q), q)
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_tau_h_preserves_multiplication(self, params, rng) -> None:
d, q = params.d, params.q
for _ in range(20):
a = rand_poly(rng, d, q)
b = rand_poly(rng, d, q)
assert tau_h(mul(a, b, q), q) == mul(tau_h(a, q), tau_h(b, q), q)
class TestSpecialValues:
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_tau_g_fixes_zero(self, params) -> None:
d, q = params.d, params.q
zero = [0] * d
assert tau_g(zero, q) == zero
assert tau_h(zero, q) == zero
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_tau_fixes_constant_polynomial(self, params, rng) -> None:
d, q = params.d, params.q
c = rng.randrange(q)
const = [c] + [0] * (d - 1)
assert tau_g(const, q) == const
assert tau_h(const, q) == const
for j in range(d // 2):
assert tau_g_pow(const, j, q) == const
class TestGaloisGroupStructure:
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_galois_group_has_d_distinct_elements(self, params) -> None:
d = params.d
elements = set()
for j in range(d // 2):
for b in range(2):
g = (pow(G, j, 2 * d) * pow(h(d), b, 2 * d)) % (2 * d)
elements.add(g)
assert len(elements) == d, f"expected d={d} distinct elements, got {len(elements)}"
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_all_galois_group_elements_are_odd(self, params) -> None:
d = params.d
for j in range(d // 2):
for b in range(2):
g = (pow(G, j, 2 * d) * pow(h(d), b, 2 * d)) % (2 * d)
assert g % 2 == 1, f"element {g} is not odd"
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_galois_elements_match_odd_residues_in_2d(self, params) -> None:
d = params.d
generated = set()
for j in range(d // 2):
for b in range(2):
g = (pow(G, j, 2 * d) * pow(h(d), b, 2 * d)) % (2 * d)
generated.add(g)
odd_residues = set(range(1, 2 * d, 2))
assert generated == odd_residues
class TestInverse:
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_tau_g_pow_j_then_d_over_2_minus_j_is_identity(self, params, rng) -> None:
d, q = params.d, params.q
a = rand_poly(rng, d, q)
for j in range(d // 2):
forward = tau_g_pow(a, j, q)
recovered = tau_g_pow(forward, (d // 2) - j, q)
assert recovered == a, (
f"tau_g^{j} composed with tau_g^{(d//2) - j} != identity"
)
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_tau_h_is_self_inverse(self, params, rng) -> None:
d, q = params.d, params.q
a = rand_poly(rng, d, q)
assert tau_h(tau_h(a, q), q) == a