from __future__ import annotations
import random
import statistics
import pytest
from inspiring_oracle.lwe import keygen as lwe_keygen
from inspiring_oracle.params import ORACLE_SMALL, ORACLE_TINY
from inspiring_oracle.ring import mul
from inspiring_oracle.rlwe import (
RlweCiphertext,
decrypt,
encrypt,
extract_noise,
keygen,
sample_noise_poly,
s_tilde_from_s,
)
@pytest.fixture
def rng() -> random.Random:
return random.Random(0xCABBA6E)
def rand_message(rng: random.Random, params) -> list[int]:
return [rng.randrange(params.p) for _ in range(params.d)]
class TestSTildeFromS:
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_length_equals_d(self, params, rng) -> None:
s = lwe_keygen(params, rng)
assert len(s_tilde_from_s(s, params)) == params.d
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_positive_values_passed_through(self, params) -> None:
s = [3, 7, 0, 11, 0, 5, 1, 0] + [0] * (params.d - 8)
s = s[: params.d]
assert s_tilde_from_s(s, params) == [v % params.q for v in s]
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_negative_one_maps_to_q_minus_one(self, params) -> None:
s = [-1] * params.d
assert s_tilde_from_s(s, params) == [params.q - 1] * params.d
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_zero_stays_zero(self, params) -> None:
s = [0] * params.d
assert s_tilde_from_s(s, params) == [0] * params.d
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_ternary_secret_canonical_form(self, params, rng) -> None:
s = lwe_keygen(params, rng)
s_tilde = s_tilde_from_s(s, params)
for i, (si, ti) in enumerate(zip(s, s_tilde)):
expected = si % params.q
assert ti == expected, (
f"s_tilde[{i}] = {ti}, expected {expected} from s[{i}] = {si}"
)
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_wrong_length_raises(self, params) -> None:
with pytest.raises(ValueError, match=r"len\(s\) ="):
s_tilde_from_s([0] * (params.d + 1), params)
class TestStructuralDistinction:
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_e_i_basis_vector_passes_through_unchanged(self, params) -> None:
for i in range(params.d):
s = [0] * params.d
s[i] = 1
result = s_tilde_from_s(s, params)
expected = [0] * params.d
expected[i] = 1
assert result == expected, (
f"unit vector e_{i} should map to position {i}, not flipped"
)
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_no_negation_on_indices_above_zero(self, params) -> None:
s = list(range(1, params.d + 1))
s_tilde = s_tilde_from_s(s, params)
for i in range(params.d):
assert s_tilde[i] == (i + 1) % params.q, (
f"s_tilde[{i}] should equal s[{i}] = {i+1}"
)
class TestKeygen:
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_length_equals_d(self, params, rng) -> None:
assert len(keygen(params, rng)) == params.d
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_coefficients_in_canonical_ternary_image(
self, params, rng
) -> None:
for _ in range(50):
s_tilde = keygen(params, rng)
assert all(
v in (0, 1, params.q - 1) for v in s_tilde
), s_tilde
class TestSampleNoisePoly:
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_length_equals_d(self, params, rng) -> None:
e = sample_noise_poly(params, rng)
assert len(e) == params.d
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_coefficient_statistics_match_chi(self, params, rng) -> None:
n = 10_000 // params.d
coefs: list[int] = []
for _ in range(n):
coefs.extend(sample_noise_poly(params, rng))
mean = statistics.fmean(coefs)
std = statistics.stdev(coefs)
assert abs(mean) < 0.1 * params.sigma
assert 0.9 * params.sigma < std < 1.1 * params.sigma
class TestEncryptDecryptRoundtrip:
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_random_messages_roundtrip(self, params, rng) -> None:
for _ in range(500):
s_tilde = keygen(params, rng)
m_bar = rand_message(rng, params)
ct = encrypt(s_tilde, m_bar, params, rng)
assert decrypt(s_tilde, ct, params) == m_bar
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_zero_message_roundtrips(self, params, rng) -> None:
s_tilde = keygen(params, rng)
zero = [0] * params.d
for _ in range(50):
ct = encrypt(s_tilde, zero, params, rng)
assert decrypt(s_tilde, ct, params) == zero
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_max_message_roundtrips(self, params, rng) -> None:
s_tilde = keygen(params, rng)
max_m = [params.p - 1] * params.d
for _ in range(50):
ct = encrypt(s_tilde, max_m, params, rng)
assert decrypt(s_tilde, ct, params) == max_m
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_single_nonzero_coefficient_roundtrips(self, params, rng) -> None:
s_tilde = keygen(params, rng)
for k in range(params.d):
m_bar = [0] * params.d
m_bar[k] = params.p - 1
ct = encrypt(s_tilde, m_bar, params, rng)
assert decrypt(s_tilde, ct, params) == m_bar
class TestSignConventionKAT:
def test_manual_zero_noise_zero_message_at_d8(self) -> None:
params = ORACLE_TINY
s_tilde = [1, params.q - 1, 0, 1, 0, params.q - 1, 1, 0]
c1 = [11, 22, 33, 44, 55, 66, 77, 88]
c1_s = mul(c1, s_tilde, params.q)
c2 = [(-x) % params.q for x in c1_s]
ct = RlweCiphertext(c1=c1, c2=c2)
assert decrypt(s_tilde, ct, params) == [0] * params.d
def test_manual_zero_noise_nonzero_message_at_d8(self) -> None:
params = ORACLE_TINY
s_tilde = [1, params.q - 1, 0, 1, 0, params.q - 1, 1, 0]
c1 = [101, 202, 303, 404, 505, 606, 707, 808]
m_bar = [0, 1, 2, 3, 0, 1, 2, 3]
c1_s = mul(c1, s_tilde, params.q)
delta_m = [(params.delta * mi) % params.q for mi in m_bar]
c2 = [
((-c1s) + dm) % params.q
for c1s, dm in zip(c1_s, delta_m, strict=True)
]
ct = RlweCiphertext(c1=c1, c2=c2)
assert decrypt(s_tilde, ct, params) == m_bar
def test_manual_with_small_noise_decrypts_correctly(self) -> None:
params = ORACLE_TINY
s_tilde = [params.q - 1, 1, 1, 0, params.q - 1, 0, 1, params.q - 1]
c1 = [1234, 5678, 9012, 3456, 7890, 1357, 2468, 9876]
m_bar = [3, 0, 2, 1, 3, 2, 0, 1]
e = [5, -7, 0, 11, -3, 8, -12, 1]
c1_s = mul(c1, s_tilde, params.q)
delta_m = [(params.delta * mi) % params.q for mi in m_bar]
c2 = [
((-c1s) + ei + dm) % params.q
for c1s, ei, dm in zip(c1_s, e, delta_m, strict=True)
]
ct = RlweCiphertext(c1=c1, c2=c2)
assert decrypt(s_tilde, ct, params) == m_bar
def test_extract_noise_recovers_known_noise_polynomial(self) -> None:
params = ORACLE_TINY
s_tilde = [params.q - 1, 1, 0, 1, 0, params.q - 1, 1, 0]
c1 = [11, 22, 33, 44, 55, 66, 77, 88]
m_bar = [1, 2, 3, 0, 1, 2, 3, 0]
e = [4, -6, 0, 9, -2, 7, -11, 1]
c1_s = mul(c1, s_tilde, params.q)
delta_m = [(params.delta * mi) % params.q for mi in m_bar]
c2 = [
((-c1s) + ei + dm) % params.q
for c1s, ei, dm in zip(c1_s, e, delta_m, strict=True)
]
ct = RlweCiphertext(c1=c1, c2=c2)
assert extract_noise(s_tilde, ct, m_bar, params) == e
class TestNoiseBudget:
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_extracted_noise_statistics(self, params, rng) -> None:
s_tilde = keygen(params, rng)
coefs: list[int] = []
n_cts = 2000 // params.d
for _ in range(n_cts):
m_bar = rand_message(rng, params)
ct = encrypt(s_tilde, m_bar, params, rng)
coefs.extend(extract_noise(s_tilde, ct, m_bar, params))
mean = statistics.fmean(coefs)
std = statistics.stdev(coefs)
assert abs(mean) < 0.15 * params.sigma
assert 0.9 * params.sigma < std < 1.1 * params.sigma
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_per_coefficient_within_decryption_budget(
self, params, rng
) -> None:
s_tilde = keygen(params, rng)
max_abs = 0
for _ in range(200):
m_bar = rand_message(rng, params)
ct = encrypt(s_tilde, m_bar, params, rng)
coefs = extract_noise(s_tilde, ct, m_bar, params)
max_abs = max(max_abs, max(abs(c) for c in coefs))
assert max_abs < params.delta // 2
class TestDeterminism:
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_same_seed_same_ciphertext(self, params) -> None:
seed = 0xFEEDFACE
s_tilde = keygen(params, random.Random(seed))
m_bar = [1] * params.d
rng1 = random.Random(seed + 1)
rng2 = random.Random(seed + 1)
ct1 = encrypt(s_tilde, m_bar, params, rng1)
ct2 = encrypt(s_tilde, m_bar, params, rng2)
assert ct1.c1 == ct2.c1
assert ct1.c2 == ct2.c2
class TestInputValidation:
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_message_wrong_length_raises(self, params, rng) -> None:
s_tilde = keygen(params, rng)
with pytest.raises(ValueError, match=r"len\(m_bar\) ="):
encrypt(s_tilde, [0] * (params.d + 1), params, rng)
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_message_coefficient_out_of_range_raises(
self, params, rng
) -> None:
s_tilde = keygen(params, rng)
bad = [0] * params.d
bad[0] = params.p
with pytest.raises(ValueError, match=r"in \[0, p="):
encrypt(s_tilde, bad, params, rng)
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_negative_message_coefficient_raises(self, params, rng) -> None:
s_tilde = keygen(params, rng)
bad = [0] * params.d
bad[3] = -1
with pytest.raises(ValueError, match=r"in \[0, p="):
encrypt(s_tilde, bad, params, rng)