from __future__ import annotations
import math
import random
import pytest
from inspiring_oracle import key_switching, lwe, rlwe
from inspiring_oracle.automorph import G, h, tau
from inspiring_oracle.collapse import collapse
from inspiring_oracle.intermediate import IRCtx, aggregate, transform
from inspiring_oracle.params import ORACLE_SMALL, ORACLE_TINY, RlweParams
PARAMS = [ORACLE_TINY, ORACLE_SMALL]
def _build_pipeline(
params: RlweParams, rng: random.Random
) -> tuple[
list[int], list[int], key_switching.KeySwitchingMatrix, key_switching.KeySwitchingMatrix, ]:
s = lwe.keygen(params, rng)
s_tilde = rlwe.s_tilde_from_s(s, params)
tau_g_s = tau(s_tilde, G, params.q)
tau_h_s = tau(s_tilde, h(params.d), params.q)
K_g = key_switching.setup(tau_g_s, s_tilde, params, rng)
K_h = key_switching.setup(tau_h_s, s_tilde, params, rng)
return s, s_tilde, K_g, K_h
def _aggregate_d_messages(
s: list[int],
messages: list[int],
params: RlweParams,
rng: random.Random,
) -> IRCtx:
cts = [lwe.encrypt(s, m, params, rng) for m in messages]
irctxs = [transform(ct, params) for ct in cts]
return aggregate(irctxs, params)
def _theorem2_sigma_pack(params: RlweParams) -> float:
return (
math.sqrt(params.ell * params.d * params.d / 4.0)
* params.z
* params.sigma
)
class TestOutputType:
@pytest.mark.parametrize("params", PARAMS)
def test_returns_rlwe_ciphertext(self, params: RlweParams) -> None:
rng = random.Random(0xC12_01)
s, _s_tilde, K_g, K_h = _build_pipeline(params, rng)
messages = [0] * params.d
ictx_agg = _aggregate_d_messages(s, messages, params, rng)
ct = collapse(ictx_agg, K_g, K_h, params)
assert isinstance(ct, rlwe.RlweCiphertext)
assert len(ct.c1) == params.d
assert len(ct.c2) == params.d
assert all(0 <= c < params.q for c in ct.c1)
assert all(0 <= c < params.q for c in ct.c2)
class TestSwitchCallCountInvariant:
@pytest.mark.parametrize("params", PARAMS)
def test_exactly_d_minus_1_switch_calls(self, params: RlweParams) -> None:
rng = random.Random(0xC12_10)
s, _s_tilde, K_g, K_h = _build_pipeline(params, rng)
messages = [rng.randrange(params.p) for _ in range(params.d)]
ictx_agg = _aggregate_d_messages(s, messages, params, rng)
key_switching.reset_switch_counter()
collapse(ictx_agg, K_g, K_h, params)
assert key_switching.switch_call_count() == params.d - 1
@pytest.mark.parametrize("params", PARAMS)
def test_count_is_invariant_across_inputs(
self, params: RlweParams
) -> None:
rng = random.Random(0xC12_11)
s, _s_tilde, K_g, K_h = _build_pipeline(params, rng)
for trial in range(5):
messages = [rng.randrange(params.p) for _ in range(params.d)]
ictx_agg = _aggregate_d_messages(s, messages, params, rng)
key_switching.reset_switch_counter()
collapse(ictx_agg, K_g, K_h, params)
assert key_switching.switch_call_count() == params.d - 1, (
f"trial {trial}: {key_switching.switch_call_count()} != {params.d - 1}"
)
class TestCorrectnessRoundtrip:
@pytest.mark.parametrize("params", PARAMS)
def test_random_messages(self, params: RlweParams) -> None:
rng = random.Random(0xC12_20)
s, s_tilde, K_g, K_h = _build_pipeline(params, rng)
for _ in range(20):
messages = [rng.randrange(params.p) for _ in range(params.d)]
ictx_agg = _aggregate_d_messages(s, messages, params, rng)
ct = collapse(ictx_agg, K_g, K_h, params)
recovered = rlwe.decrypt(s_tilde, ct, params)
assert recovered == messages
class TestNoiseGrowthBounded:
@pytest.mark.parametrize("params", PARAMS)
def test_noise_under_decryption_budget(self, params: RlweParams) -> None:
rng = random.Random(0xC12_30)
s, s_tilde, K_g, K_h = _build_pipeline(params, rng)
budget = params.delta // 2
for _ in range(20):
messages = [rng.randrange(params.p) for _ in range(params.d)]
ictx_agg = _aggregate_d_messages(s, messages, params, rng)
ct = collapse(ictx_agg, K_g, K_h, params)
e = rlwe.extract_noise(s_tilde, ct, messages, 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_noise_under_6_sigma_pack(self, params: RlweParams) -> None:
rng = random.Random(0xC12_31)
s, s_tilde, K_g, K_h = _build_pipeline(params, rng)
sigma_pack = _theorem2_sigma_pack(params)
bound = 6.0 * sigma_pack
for _ in range(3):
messages = [rng.randrange(params.p) for _ in range(params.d)]
ictx_agg = _aggregate_d_messages(s, messages, params, rng)
ct = collapse(ictx_agg, K_g, K_h, params)
e = rlwe.extract_noise(s_tilde, ct, messages, params)
max_abs = max(abs(c) for c in e)
assert max_abs < bound, (
f"max |e_pack| = {max_abs} > 6 * sigma_pack = {bound:.0f}"
)
class TestRandomComponentInvariant:
@pytest.mark.parametrize("params", PARAMS)
def test_varying_b_tilde_does_not_change_c1(
self, params: RlweParams
) -> None:
rng = random.Random(0xC12_40)
_s, _s_tilde, K_g, K_h = _build_pipeline(params, rng)
a_hat = [
[rng.randrange(params.q) for _ in range(params.d)]
for _ in range(params.d)
]
b_tilde_1 = [rng.randrange(params.q) for _ in range(params.d)]
b_tilde_2 = [rng.randrange(params.q) for _ in range(params.d)]
ct_1 = collapse(IRCtx(a_hat=a_hat, b_tilde=b_tilde_1), K_g, K_h, params)
ct_2 = collapse(IRCtx(a_hat=a_hat, b_tilde=b_tilde_2), K_g, K_h, params)
assert ct_1.c1 == ct_2.c1
assert ct_1.c2 != ct_2.c2
class TestDeterminism:
@pytest.mark.parametrize("params", PARAMS)
def test_same_inputs_same_output(self, params: RlweParams) -> None:
rng = random.Random(0xC12_50)
s, _s_tilde, K_g, K_h = _build_pipeline(params, rng)
messages = [rng.randrange(params.p) for _ in range(params.d)]
ictx_agg = _aggregate_d_messages(s, messages, params, rng)
ct1 = collapse(ictx_agg, K_g, K_h, params)
ct2 = collapse(ictx_agg, K_g, K_h, params)
assert ct1 == ct2
class TestEdgeCases:
@pytest.mark.parametrize("params", PARAMS)
def test_all_zero_messages(self, params: RlweParams) -> None:
rng = random.Random(0xC12_60)
s, s_tilde, K_g, K_h = _build_pipeline(params, rng)
messages = [0] * params.d
ictx_agg = _aggregate_d_messages(s, messages, params, rng)
ct = collapse(ictx_agg, K_g, K_h, params)
assert rlwe.decrypt(s_tilde, ct, params) == messages
@pytest.mark.parametrize("params", PARAMS)
def test_all_max_messages(self, params: RlweParams) -> None:
rng = random.Random(0xC12_61)
s, s_tilde, K_g, K_h = _build_pipeline(params, rng)
messages = [params.p - 1] * params.d
ictx_agg = _aggregate_d_messages(s, messages, params, rng)
ct = collapse(ictx_agg, K_g, K_h, params)
assert rlwe.decrypt(s_tilde, ct, params) == messages