from __future__ import annotations
import random
import pytest
from inspiring_oracle import lwe, rlwe
from inspiring_oracle.decrypt_under_s_hat import (
decrypt_polynomial_under_s_hat,
decrypt_under_s_hat,
extract_noise_under_s_hat,
s_hat_from_s_tilde,
)
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_zero_irctx(params: RlweParams) -> IRCtx:
return IRCtx(
a_hat=[[0] * params.d for _ in range(params.d)],
b_tilde=[0] * params.d,
)
def _encrypt_d_messages(
s: list[int],
messages: list[int],
params: RlweParams,
rng: random.Random,
) -> tuple[list[lwe.LweCiphertext], list[int]]:
cts = [lwe.encrypt(s, m, params, rng) for m in messages]
noises = [
lwe.extract_noise(s, ct, m, params)
for ct, m in zip(cts, messages, strict=True)
]
return cts, noises
class TestInputValidation:
@pytest.mark.parametrize("params", PARAMS)
def test_rejects_too_few(self, params: RlweParams) -> None:
irctxs = [_build_zero_irctx(params) for _ in range(params.d - 1)]
with pytest.raises(ValueError, match="exactly d"):
aggregate(irctxs, params)
@pytest.mark.parametrize("params", PARAMS)
def test_rejects_too_many(self, params: RlweParams) -> None:
irctxs = [_build_zero_irctx(params) for _ in range(params.d + 1)]
with pytest.raises(ValueError, match="exactly d"):
aggregate(irctxs, params)
@pytest.mark.parametrize("params", PARAMS)
def test_empty_list_raises(self, params: RlweParams) -> None:
with pytest.raises(ValueError, match="exactly d"):
aggregate([], params)
class TestOutputShape:
@pytest.mark.parametrize("params", PARAMS)
def test_shapes_and_ranges(self, params: RlweParams) -> None:
rng = random.Random(0xA66_01)
s = lwe.keygen(params, rng)
irctxs = [
transform(lwe.encrypt(s, rng.randrange(params.p), params, rng), params)
for _ in range(params.d)
]
agg = aggregate(irctxs, params)
assert len(agg.a_hat) == params.d
for poly in agg.a_hat:
assert len(poly) == params.d
assert all(0 <= c < params.q for c in poly)
assert len(agg.b_tilde) == params.d
assert all(0 <= c < params.q for c in agg.b_tilde)
class TestBTildeIsLiteralBValues:
@pytest.mark.parametrize("params", PARAMS)
def test_b_tilde_agg_equals_b_vector(self, params: RlweParams) -> None:
rng = random.Random(0xA66_02)
s = lwe.keygen(params, rng)
cts = [
lwe.encrypt(s, rng.randrange(params.p), params, rng)
for _ in range(params.d)
]
irctxs = [transform(ct, params) for ct in cts]
agg = aggregate(irctxs, params)
assert agg.b_tilde == [ct.b % params.q for ct in cts]
class TestDecryptionRoundtrip:
@pytest.mark.parametrize("params", PARAMS)
def test_random_messages(self, params: RlweParams) -> None:
rng = random.Random(0xA66_10)
s = lwe.keygen(params, rng)
s_tilde = rlwe.s_tilde_from_s(s, params)
s_hat = s_hat_from_s_tilde(s_tilde, params)
for _ in range(20):
messages = [rng.randrange(params.p) for _ in range(params.d)]
cts, _ = _encrypt_d_messages(s, messages, params, rng)
irctxs = [transform(ct, params) for ct in cts]
agg = aggregate(irctxs, params)
recovered = decrypt_under_s_hat(agg, s_hat, params)
assert recovered == messages
@pytest.mark.parametrize("params", PARAMS)
def test_all_zero_messages(self, params: RlweParams) -> None:
rng = random.Random(0xA66_11)
s = lwe.keygen(params, rng)
s_tilde = rlwe.s_tilde_from_s(s, params)
s_hat = s_hat_from_s_tilde(s_tilde, params)
messages = [0] * params.d
cts, _ = _encrypt_d_messages(s, messages, params, rng)
irctxs = [transform(ct, params) for ct in cts]
agg = aggregate(irctxs, params)
assert decrypt_under_s_hat(agg, s_hat, params) == messages
@pytest.mark.parametrize("params", PARAMS)
def test_all_max_messages(self, params: RlweParams) -> None:
rng = random.Random(0xA66_12)
s = lwe.keygen(params, rng)
s_tilde = rlwe.s_tilde_from_s(s, params)
s_hat = s_hat_from_s_tilde(s_tilde, params)
messages = [params.p - 1] * params.d
cts, _ = _encrypt_d_messages(s, messages, params, rng)
irctxs = [transform(ct, params) for ct in cts]
agg = aggregate(irctxs, params)
assert decrypt_under_s_hat(agg, s_hat, params) == messages
@pytest.mark.parametrize("params", PARAMS)
def test_alternating_messages(self, params: RlweParams) -> None:
rng = random.Random(0xA66_13)
s = lwe.keygen(params, rng)
s_tilde = rlwe.s_tilde_from_s(s, params)
s_hat = s_hat_from_s_tilde(s_tilde, params)
messages = [params.p - 1 if k % 2 == 0 else 0 for k in range(params.d)]
cts, _ = _encrypt_d_messages(s, messages, params, rng)
irctxs = [transform(ct, params) for ct in cts]
agg = aggregate(irctxs, params)
assert decrypt_under_s_hat(agg, s_hat, params) == messages
class TestNoiseRoutingPerSlot:
@pytest.mark.parametrize("params", PARAMS)
def test_per_slot_noise_matches_per_input_lwe_noise(
self, params: RlweParams
) -> None:
rng = random.Random(0xA66_20)
s = lwe.keygen(params, rng)
s_tilde = rlwe.s_tilde_from_s(s, params)
s_hat = s_hat_from_s_tilde(s_tilde, params)
messages = [rng.randrange(params.p) for _ in range(params.d)]
cts, lwe_noises = _encrypt_d_messages(s, messages, params, rng)
irctxs = [transform(ct, params) for ct in cts]
agg = aggregate(irctxs, params)
agg_noise = extract_noise_under_s_hat(agg, s_hat, messages, params)
assert agg_noise == lwe_noises
class TestAHatAggIndependentOfBs:
@pytest.mark.parametrize("params", PARAMS)
def test_random_b_vectors_do_not_change_a_hat(
self, params: RlweParams
) -> None:
rng = random.Random(0xA66_30)
a_vecs = [
[rng.randrange(params.q) for _ in range(params.d)]
for _ in range(params.d)
]
b1_vec = [rng.randrange(params.q) for _ in range(params.d)]
b2_vec = [rng.randrange(params.q) for _ in range(params.d)]
irctxs1 = [
transform(lwe.LweCiphertext(a=a, b=b), params)
for a, b in zip(a_vecs, b1_vec, strict=True)
]
irctxs2 = [
transform(lwe.LweCiphertext(a=a, b=b), params)
for a, b in zip(a_vecs, b2_vec, strict=True)
]
agg1 = aggregate(irctxs1, params)
agg2 = aggregate(irctxs2, params)
assert agg1.a_hat == agg2.a_hat
assert agg1.b_tilde == [b % params.q for b in b1_vec]
assert agg2.b_tilde == [b % params.q for b in b2_vec]
class TestZeroIRCtxsAggregateToZero:
@pytest.mark.parametrize("params", PARAMS)
def test_d_zero_irctxs(self, params: RlweParams) -> None:
irctxs = [_build_zero_irctx(params) for _ in range(params.d)]
agg = aggregate(irctxs, params)
zero_a_hat = [[0] * params.d for _ in range(params.d)]
assert agg.a_hat == zero_a_hat
assert agg.b_tilde == [0] * params.d
class TestSingleNonzeroSlot:
@pytest.mark.parametrize("params", PARAMS)
@pytest.mark.parametrize("nonzero_slot", [0, 1, 3])
def test_only_slot_k_is_nonzero(
self, params: RlweParams, nonzero_slot: int
) -> None:
nonzero_slot = nonzero_slot % params.d
rng = random.Random(0xA66_40 + nonzero_slot)
s = lwe.keygen(params, rng)
s_tilde = rlwe.s_tilde_from_s(s, params)
s_hat = s_hat_from_s_tilde(s_tilde, params)
messages = [0] * params.d
messages[nonzero_slot] = params.p - 1
cts, _ = _encrypt_d_messages(s, messages, params, rng)
irctxs = [transform(ct, params) for ct in cts]
agg = aggregate(irctxs, params)
recovered = decrypt_under_s_hat(agg, s_hat, params)
assert recovered[nonzero_slot] == params.p - 1
for k in range(params.d):
if k != nonzero_slot:
assert recovered[k] == 0
class TestDeterminism:
@pytest.mark.parametrize("params", PARAMS)
def test_same_inputs_same_output(self, params: RlweParams) -> None:
rng = random.Random(0xA66_50)
s = lwe.keygen(params, rng)
cts = [
lwe.encrypt(s, rng.randrange(params.p), params, rng)
for _ in range(params.d)
]
irctxs = [transform(ct, params) for ct in cts]
a = aggregate(irctxs, params)
b = aggregate(irctxs, params)
assert a == b
class TestRecoveredPolynomialMatchesPerSlotMessageAndNoise:
@pytest.mark.parametrize("params", PARAMS)
def test_centered_per_slot_decomposition(self, params: RlweParams) -> None:
rng = random.Random(0xA66_60)
s = lwe.keygen(params, rng)
s_tilde = rlwe.s_tilde_from_s(s, params)
s_hat = s_hat_from_s_tilde(s_tilde, params)
messages = [rng.randrange(params.p) for _ in range(params.d)]
cts, lwe_noises = _encrypt_d_messages(s, messages, params, rng)
irctxs = [transform(ct, params) for ct in cts]
agg = aggregate(irctxs, params)
raw = decrypt_polynomial_under_s_hat(agg, s_hat, params)
for k in range(params.d):
residual_modq = (raw[k] - params.delta * messages[k]) % params.q
residual = (
residual_modq if residual_modq <= params.q // 2
else residual_modq - params.q
)
assert residual == lwe_noises[k], (
f"slot {k}: residual {residual} != lwe noise {lwe_noises[k]}"
)