from __future__ import annotations
import random
import statistics
import pytest
from inspiring_oracle.lwe import (
LweCiphertext,
decrypt,
encrypt,
extract_noise,
keygen,
sample_noise,
)
from inspiring_oracle.params import ORACLE_SMALL, ORACLE_TINY
@pytest.fixture
def rng() -> random.Random:
return random.Random(0xCABBA6E)
class TestKeygen:
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_secret_length_equals_d(self, params, rng) -> None:
s = keygen(params, rng)
assert len(s) == params.d
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_secret_values_are_ternary(self, params, rng) -> None:
for _ in range(50):
s = keygen(params, rng)
assert all(v in (-1, 0, 1) for v in s), s
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_secret_distribution_is_approximately_uniform(
self, params, rng
) -> None:
n = 3000
samples: list[int] = []
for _ in range(n // params.d):
samples.extend(keygen(params, rng))
counts = {v: samples.count(v) for v in (-1, 0, 1)}
expected = len(samples) / 3.0
for v, c in counts.items():
assert abs(c - expected) < 0.2 * expected, (
f"value {v} count {c} far from expected {expected:.0f}"
)
class TestSampleNoise:
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_noise_is_int(self, params, rng) -> None:
for _ in range(20):
assert isinstance(sample_noise(params, rng), int)
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_noise_statistics_match_chi(self, params, rng) -> None:
samples = [sample_noise(params, rng) for _ in range(10_000)]
mean = statistics.fmean(samples)
std = statistics.stdev(samples)
assert abs(mean) < 0.1 * params.sigma, f"mean {mean} too far from 0"
assert 0.9 * params.sigma < std < 1.1 * params.sigma, (
f"std {std:.3f} not within +-10% of sigma={params.sigma}"
)
class TestEncryptDecryptRoundtrip:
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_random_messages_roundtrip(self, params, rng) -> None:
for _ in range(1000):
s = keygen(params, rng)
m = rng.randrange(params.p)
ct = encrypt(s, m, params, rng)
assert decrypt(s, ct, params) == m, (
f"roundtrip failed: m={m}, ct.b={ct.b}, p={params.p}"
)
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_every_message_roundtrips(self, params, rng) -> None:
s = keygen(params, rng)
for m in range(params.p):
for _ in range(50):
ct = encrypt(s, m, params, rng)
assert decrypt(s, ct, params) == m, f"failed for m={m}"
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_zero_message_roundtrips(self, params, rng) -> None:
s = keygen(params, rng)
for _ in range(100):
ct = encrypt(s, 0, params, rng)
assert decrypt(s, ct, params) == 0
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_max_message_roundtrips(self, params, rng) -> None:
s = keygen(params, rng)
m = params.p - 1
for _ in range(100):
ct = encrypt(s, m, params, rng)
assert decrypt(s, ct, params) == m
class TestSignConventionKAT:
def test_manual_zero_noise_zero_message_at_d8(self) -> None:
params = ORACLE_TINY
s = [1, -1, 0, 1, 0, -1, 1, 0]
a = [100, 200, 300, 400, 500, 600, 700, 800]
inner = sum(ai * si for ai, si in zip(a, s))
b = (-inner) % params.q
ct = LweCiphertext(a=a, b=b)
assert decrypt(s, ct, params) == 0
def test_manual_zero_noise_nonzero_message_at_d8(self) -> None:
params = ORACLE_TINY
s = [1, -1, 0, 1, 0, -1, 1, 0]
a = [100, 200, 300, 400, 500, 600, 700, 800]
m = 2
inner = sum(ai * si for ai, si in zip(a, s))
b = (-inner + params.delta * m) % params.q
ct = LweCiphertext(a=a, b=b)
assert decrypt(s, ct, params) == m
def test_manual_with_small_noise_decrypts_correctly(self) -> None:
params = ORACLE_TINY
s = [-1, 1, 1, 0, -1, 0, 1, -1]
a = [1234, 5678, 9012, 3456, 7890, 1357, 2468, 9999]
m = 3
e = 7
inner = sum(ai * si for ai, si in zip(a, s))
b = (-inner + e + params.delta * m) % params.q
ct = LweCiphertext(a=a, b=b)
assert decrypt(s, ct, params) == m
def test_manual_with_negative_small_noise_decrypts_correctly(self) -> None:
params = ORACLE_TINY
s = [-1, 1, 1, 0, -1, 0, 1, -1]
a = [1234, 5678, 9012, 3456, 7890, 1357, 2468, 9999]
m = 0
e = -11
inner = sum(ai * si for ai, si in zip(a, s))
b = (-inner + e + params.delta * m) % params.q
ct = LweCiphertext(a=a, b=b)
assert decrypt(s, ct, params) == m
def test_extract_noise_recovers_known_noise_value(self) -> None:
params = ORACLE_TINY
s = [1, -1, 0, 1, 0, -1, 1, 0]
a = [100, 200, 300, 400, 500, 600, 700, 800]
m = 1
for e in (-15, -3, 0, 5, 12):
inner = sum(ai * si for ai, si in zip(a, s))
b = (-inner + e + params.delta * m) % params.q
ct = LweCiphertext(a=a, b=b)
assert extract_noise(s, ct, m, params) == e
class TestNoiseBudget:
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_extracted_noise_statistics(self, params, rng) -> None:
s = keygen(params, rng)
noises: list[int] = []
for _ in range(2000):
m = rng.randrange(params.p)
ct = encrypt(s, m, params, rng)
noises.append(extract_noise(s, ct, m, params))
mean = statistics.fmean(noises)
std = statistics.stdev(noises)
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_extracted_noise_within_six_sigma(self, params, rng) -> None:
s = keygen(params, rng)
outliers = 0
for _ in range(1000):
m = rng.randrange(params.p)
ct = encrypt(s, m, params, rng)
e = extract_noise(s, ct, m, params)
if abs(e) > 6 * params.sigma:
outliers += 1
assert outliers <= 5, f"got {outliers} > 6-sigma outliers (expected <= 5)"
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_single_lwe_noise_within_decryption_budget(self, params, rng) -> None:
s = keygen(params, rng)
noises: list[int] = []
for _ in range(500):
m = rng.randrange(params.p)
ct = encrypt(s, m, params, rng)
noises.append(extract_noise(s, ct, m, params))
max_abs_noise = max(abs(e) for e in noises)
budget = params.delta // 2
assert max_abs_noise < budget, (
f"noise {max_abs_noise} exceeded budget {budget}"
)
class TestDeterminism:
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_same_seed_same_ciphertext(self, params) -> None:
seed = 0xDEADBEEF
s = keygen(params, random.Random(seed))
rng1 = random.Random(seed + 1)
rng2 = random.Random(seed + 1)
ct1 = encrypt(s, 1, params, rng1)
ct2 = encrypt(s, 1, params, rng2)
assert ct1.a == ct2.a
assert ct1.b == ct2.b
class TestInputValidation:
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_negative_message_rejected(self, params, rng) -> None:
s = keygen(params, rng)
with pytest.raises(ValueError, match="m = -1 not in"):
encrypt(s, -1, params, rng)
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_message_equal_to_p_rejected(self, params, rng) -> None:
s = keygen(params, rng)
with pytest.raises(ValueError, match=r"not in plaintext range"):
encrypt(s, params.p, params, rng)
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_message_above_p_rejected(self, params, rng) -> None:
s = keygen(params, rng)
with pytest.raises(ValueError):
encrypt(s, params.p + 100, params, rng)
class TestCiphertextStructure:
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_a_coefficients_in_z_q(self, params, rng) -> None:
s = keygen(params, rng)
for _ in range(100):
m = rng.randrange(params.p)
ct = encrypt(s, m, params, rng)
assert len(ct.a) == params.d
assert all(0 <= ai < params.q for ai in ct.a)
@pytest.mark.parametrize("params", [ORACLE_TINY, ORACLE_SMALL])
def test_b_in_z_q(self, params, rng) -> None:
s = keygen(params, rng)
for _ in range(100):
m = rng.randrange(params.p)
ct = encrypt(s, m, params, rng)
assert 0 <= ct.b < params.q