from __future__ import annotations
import math
import random
import pytest
from inspiring_oracle import key_switching, rlwe
from inspiring_oracle.automorph import G, h, tau
from inspiring_oracle.collapse import collapse_half
from inspiring_oracle.params import ORACLE_SMALL, ORACLE_TINY, RlweParams
from inspiring_oracle.ring import mul as ring_mul
from inspiring_oracle.ring import sub as ring_sub
from inspiring_oracle.wide_helpers import (
build_wide_ciphertext,
decrypt_wide,
extract_wide_noise,
)
PARAMS = [ORACLE_TINY, ORACLE_SMALL]
def _s_hat_left(s_tilde: list[int], params: RlweParams) -> list[list[int]]:
d, q = params.d, params.q
two_d = 2 * d
return [tau(s_tilde, pow(G, j, two_d), q) for j in range(d // 2)]
def _s_hat_right(s_tilde: list[int], params: RlweParams) -> list[list[int]]:
d, q = params.d, params.q
two_d = 2 * d
h_d = h(d)
return [
tau(s_tilde, (pow(G, j, two_d) * h_d) % two_d, q)
for j in range(d // 2)
]
def _per_step_ks_noise_sigma_bound(params: RlweParams) -> float:
return math.sqrt(params.ell * params.d / 4.0) * params.z * params.sigma
def _half_noise_sigma_bound(params: RlweParams) -> float:
return math.sqrt(params.d // 2 - 1) * _per_step_ks_noise_sigma_bound(params)
class TestInputValidation:
@pytest.mark.parametrize("params", PARAMS)
def test_rejects_wrong_a_length(self, params: RlweParams) -> None:
rng = random.Random(0xC11_01)
s_tilde = rlwe.keygen(params, rng)
K_g = key_switching.setup(
tau(s_tilde, G, params.q), s_tilde, params, rng
)
a = [[0] * params.d for _ in range(params.d // 2 + 1)] b = [0] * params.d
with pytest.raises(ValueError, match="d/2"):
collapse_half(a, b, K_g, "identity", params)
@pytest.mark.parametrize("params", PARAMS)
def test_rejects_invalid_rho(self, params: RlweParams) -> None:
rng = random.Random(0xC11_02)
s_tilde = rlwe.keygen(params, rng)
K_g = key_switching.setup(
tau(s_tilde, G, params.q), s_tilde, params, rng
)
a = [[0] * params.d for _ in range(params.d // 2)]
b = [0] * params.d
with pytest.raises(ValueError, match="rho"):
collapse_half(a, b, K_g, "invalid", params)
class TestOutputShape:
@pytest.mark.parametrize("params", PARAMS)
@pytest.mark.parametrize("rho", ["identity", "tau_h"])
def test_output_is_single_polynomial_pair(
self, params: RlweParams, rho: str
) -> None:
rng = random.Random(0xC11_10)
s_tilde = rlwe.keygen(params, rng)
K_g = key_switching.setup(
tau(s_tilde, G, params.q), s_tilde, params, rng
)
s_wide = (
_s_hat_left(s_tilde, params)
if rho == "identity"
else _s_hat_right(s_tilde, params)
)
m_bar = [0] * params.d
a, b, _ = build_wide_ciphertext(s_wide, m_bar, params, rng)
a_out, b_out = collapse_half(a, b, K_g, rho, params) assert isinstance(a_out, list)
assert len(a_out) == params.d
assert all(0 <= c < params.q for c in a_out)
assert isinstance(b_out, list)
assert len(b_out) == params.d
assert all(0 <= c < params.q for c in b_out)
class TestCorrectnessLeftHalf:
@pytest.mark.parametrize("params", PARAMS)
def test_random_messages(self, params: RlweParams) -> None:
rng = random.Random(0xC11_20)
s_tilde = rlwe.keygen(params, rng)
s_hat_left = _s_hat_left(s_tilde, params)
K_g = key_switching.setup(
tau(s_tilde, G, params.q), s_tilde, params, rng
)
for _ in range(20):
m_bar = [rng.randrange(params.p) for _ in range(params.d)]
a, b, _ = build_wide_ciphertext(s_hat_left, m_bar, params, rng)
a_out, b_out = collapse_half(a, b, K_g, "identity", params)
recovered = decrypt_wide([a_out], b_out, [s_tilde], params)
assert recovered == m_bar
class TestCorrectnessRightHalf:
@pytest.mark.parametrize("params", PARAMS)
def test_random_messages(self, params: RlweParams) -> None:
rng = random.Random(0xC11_30)
s_tilde = rlwe.keygen(params, rng)
s_hat_right = _s_hat_right(s_tilde, params)
K_g = key_switching.setup(
tau(s_tilde, G, params.q), s_tilde, params, rng
)
s_target = tau(s_tilde, h(params.d), params.q)
for _ in range(20):
m_bar = [rng.randrange(params.p) for _ in range(params.d)]
a, b, _ = build_wide_ciphertext(s_hat_right, m_bar, params, rng)
a_out, b_out = collapse_half(a, b, K_g, "tau_h", params)
recovered = decrypt_wide([a_out], b_out, [s_target], params)
assert recovered == m_bar
class TestSwitchCallCount:
@pytest.mark.parametrize("params", PARAMS)
@pytest.mark.parametrize("rho", ["identity", "tau_h"])
def test_exact_count(self, params: RlweParams, rho: str) -> None:
rng = random.Random(0xC11_40)
s_tilde = rlwe.keygen(params, rng)
K_g = key_switching.setup(
tau(s_tilde, G, params.q), s_tilde, params, rng
)
s_wide = (
_s_hat_left(s_tilde, params)
if rho == "identity"
else _s_hat_right(s_tilde, params)
)
a, b, _ = build_wide_ciphertext(s_wide, [0] * params.d, params, rng)
key_switching.reset_switch_counter()
collapse_half(a, b, K_g, rho, params) assert key_switching.switch_call_count() == params.d // 2 - 1
class TestRandomComponentInvariant:
@pytest.mark.parametrize("params", PARAMS)
@pytest.mark.parametrize("rho", ["identity", "tau_h"])
def test_varying_b_does_not_change_a_out(
self, params: RlweParams, rho: str
) -> None:
rng = random.Random(0xC11_50)
s_tilde = rlwe.keygen(params, rng)
K_g = key_switching.setup(
tau(s_tilde, G, params.q), s_tilde, params, rng
)
a = [
[rng.randrange(params.q) for _ in range(params.d)]
for _ in range(params.d // 2)
]
b1 = [rng.randrange(params.q) for _ in range(params.d)]
b2 = [rng.randrange(params.q) for _ in range(params.d)]
a_out_1, _ = collapse_half(a, b1, K_g, rho, params) a_out_2, _ = collapse_half(a, b2, K_g, rho, params) assert a_out_1 == a_out_2
class TestNoiseGrowthBounded:
@pytest.mark.parametrize("params", PARAMS)
@pytest.mark.parametrize("rho", ["identity", "tau_h"])
def test_noise_under_decryption_budget(
self, params: RlweParams, rho: str
) -> None:
rng = random.Random(0xC11_60)
s_tilde = rlwe.keygen(params, rng)
K_g = key_switching.setup(
tau(s_tilde, G, params.q), s_tilde, params, rng
)
s_wide = (
_s_hat_left(s_tilde, params)
if rho == "identity"
else _s_hat_right(s_tilde, params)
)
s_target = (
s_tilde if rho == "identity"
else tau(s_tilde, h(params.d), params.q)
)
budget = params.delta // 2
for _ in range(20):
m_bar = [rng.randrange(params.p) for _ in range(params.d)]
a, b, _ = build_wide_ciphertext(s_wide, m_bar, params, rng)
a_out, b_out = collapse_half(a, b, K_g, rho, params) e = extract_wide_noise([a_out], b_out, [s_target], m_bar, params)
max_abs = max(abs(c) for c in e)
assert max_abs < budget, (
f"noise overflowed Delta/2 = {budget}: max |e| = {max_abs}"
)
@pytest.mark.parametrize("params", PARAMS)
def test_ks_noise_below_subgaussian_bound(self, params: RlweParams) -> None:
rng = random.Random(0xC11_61)
s_tilde = rlwe.keygen(params, rng)
s_hat_left = _s_hat_left(s_tilde, params)
K_g = key_switching.setup(
tau(s_tilde, G, params.q), s_tilde, params, rng
)
d, q = params.d, params.q
a = [
[rng.randrange(q) for _ in range(d)]
for _ in range(d // 2)
]
b = [0] * d
for i in range(d // 2):
b = ring_sub(b, ring_mul(a[i], s_hat_left[i], q), q)
a_out, b_out = collapse_half(a, b, K_g, "identity", params)
e = extract_wide_noise([a_out], b_out, [s_tilde], [0] * d, params)
max_abs = max(abs(c) for c in e)
bound = 6 * _half_noise_sigma_bound(params)
assert max_abs < bound, (
f"max |e_half| = {max_abs} > 6 * sigma_half = {bound:.0f}"
)
class TestDeterminism:
@pytest.mark.parametrize("params", PARAMS)
@pytest.mark.parametrize("rho", ["identity", "tau_h"])
def test_same_inputs_same_output(
self, params: RlweParams, rho: str
) -> None:
rng = random.Random(0xC11_70)
s_tilde = rlwe.keygen(params, rng)
K_g = key_switching.setup(
tau(s_tilde, G, params.q), s_tilde, params, rng
)
s_wide = (
_s_hat_left(s_tilde, params)
if rho == "identity"
else _s_hat_right(s_tilde, params)
)
m_bar = [rng.randrange(params.p) for _ in range(params.d)]
a, b, _ = build_wide_ciphertext(s_wide, m_bar, params, rng)
out1 = collapse_half(a, b, K_g, rho, params) out2 = collapse_half(a, b, K_g, rho, params) assert out1 == out2
class TestEdgeCases:
@pytest.mark.parametrize("params", PARAMS)
@pytest.mark.parametrize("rho", ["identity", "tau_h"])
def test_all_zero_message(self, params: RlweParams, rho: str) -> None:
rng = random.Random(0xC11_80)
s_tilde = rlwe.keygen(params, rng)
K_g = key_switching.setup(
tau(s_tilde, G, params.q), s_tilde, params, rng
)
s_wide = (
_s_hat_left(s_tilde, params)
if rho == "identity"
else _s_hat_right(s_tilde, params)
)
s_target = (
s_tilde if rho == "identity"
else tau(s_tilde, h(params.d), params.q)
)
m_bar = [0] * params.d
a, b, _ = build_wide_ciphertext(s_wide, m_bar, params, rng)
a_out, b_out = collapse_half(a, b, K_g, rho, params) assert decrypt_wide([a_out], b_out, [s_target], params) == m_bar
@pytest.mark.parametrize("params", PARAMS)
@pytest.mark.parametrize("rho", ["identity", "tau_h"])
def test_all_max_message(self, params: RlweParams, rho: str) -> None:
rng = random.Random(0xC11_81)
s_tilde = rlwe.keygen(params, rng)
K_g = key_switching.setup(
tau(s_tilde, G, params.q), s_tilde, params, rng
)
s_wide = (
_s_hat_left(s_tilde, params)
if rho == "identity"
else _s_hat_right(s_tilde, params)
)
s_target = (
s_tilde if rho == "identity"
else tau(s_tilde, h(params.d), params.q)
)
m_bar = [params.p - 1] * params.d
a, b, _ = build_wide_ciphertext(s_wide, m_bar, params, rng)
a_out, b_out = collapse_half(a, b, K_g, rho, params) assert decrypt_wide([a_out], b_out, [s_target], params) == m_bar