Project · Encrypted computation with a toy scheme

project

hard

module project

Ship something real. Submit your work when you're done.

Brief

Implement a toy additively-homomorphic encryption scheme over integers — similar in spirit to Paillier but stripped down for clarity, not security. Verify on 50 randomly generated test cases that the homomorphic correctness equation $\mathrm{Dec}(\mathrm{Enc}(a) \boxplus \mathrm{Enc}(b)) = a + b \pmod N$ holds. Then measure the ciphertext expansion ratio (bytes per ciphertext divided by bytes per plaintext) and write a paragraph explaining why that ratio is the single number that makes HE expensive to deploy at scale.

Deliverables

A Python file `toy_he.py` exposing `KeyGen`, `Enc`, `Dec`, and `AddCT` with clear type signatures and at least the four algorithms documented in their docstrings.
A test script that generates 50 random plaintext pairs $(a, b)$ in $[0, N)$, encrypts each, adds the ciphertexts, decrypts, and asserts equality with $(a+b) \bmod N$. The script must print each test case and a final pass/fail summary.
A measured ciphertext-expansion report: serialized ciphertext byte length, plaintext byte length, ratio. Run for at least three plaintext sizes ($N = 2^8, 2^{16}, 2^{32}$) and tabulate the results.
A 1-page write-up (PDF or Markdown) explaining (a) why your scheme is additively homomorphic, (b) why it cannot be multiplicatively homomorphic, and (c) why the ciphertext-expansion ratio matters for real HE deployment — link the number to bandwidth, storage, and the noise-budget picture from task 4.

How we grade it

All 50 randomized correctness tests pass, with the random seed printed so the run is reproducible.
The four algorithms are clearly separated and documented — anyone reading `toy_he.py` can map your code to the $(\mathrm{KeyGen}, \mathrm{Enc}, \mathrm{Dec}, \mathrm{Eval})$ definition from task 2.
The ciphertext-expansion ratio is computed correctly (serialized bytes, not in-memory Python object size) and matches the order of magnitude predicted by the parameter sizes.
The write-up names at least one concrete real-world consequence of the expansion ratio (e.g. 'a 30 MB image becomes 30 GB encrypted at $n=2^{14}$, so cellular upload of an inference request takes 5 minutes').
The write-up correctly identifies why multiplication breaks: the cross-term that has no clean homomorphic image under this scheme.

Hints

The simplest correct toy scheme: pick a large modulus

M

(e.g.

M = 2^{64}

) and a plaintext modulus

N

(e.g.

N = 2^{32}

). Let

\mathrm{Enc}(m) = (m + r) \bmod M

where

r

is a random integer in

[0, M)

, but you must also keep

r

around — store the ciphertext as the pair

(b, r)

where

b = (m + r) \bmod M

. Decryption is

(b - r) \bmod M \bmod N

. Addition: componentwise sum mod

M

. (This is not secure —

r

is part of the ciphertext! — but it isolates the homomorphic structure for study. Real Paillier hides

r

inside an exponent.)

For a slightly more honest version, use Paillier proper:

N = pq

\mathrm{Enc}(m) = g^m \cdot r^N \bmod N^2

. This is a 2-3x more complex implementation but actually secure. The Python package has a clean reference implementation if you want to compare.

For ciphertext-expansion measurement, serialize using pickle.dumps or your own int.to_bytes(byte_length, 'big') — do not use sys.getsizeof (that includes Python object overhead and lies).

Use secrets.randbits or random.SystemRandom().getrandbits for the randomness — random.random() is not appropriate even in a toy scheme.

Expected output

A test run should look something like:

random seed: 0xdeadbeef [01/50] a=42, b=99 -> Enc(a)+Enc(b) decrypts to 141 (expected 141) PASS [02/50] a=12345, b=67890 -> Enc(a)+Enc(b) decrypts to 80235 (expected 80235) PASS ... [50/50] a=2147483120, b=128 -> Enc(a)+Enc(b) decrypts to 2147483248 (expected 2147483248) PASS 50/50 tests passed. Ciphertext expansion at three plaintext sizes: N = 2^8 plaintext = 1 byte ciphertext = 16 bytes expansion = 16x N = 2^16 plaintext = 2 bytes ciphertext = 16 bytes expansion = 8x N = 2^32 plaintext = 4 bytes ciphertext = 16 bytes expansion = 4x

…followed by your 1-page analysis. (Real lattice-HE schemes have expansion 1000x–100000x, not 4x — your toy scheme is ridiculously efficient because it's insecure. The write-up should explain why a real HE scheme has to be so much fatter: it has to add cryptographically-meaningful noise sampled from a high-dimensional discrete Gaussian, plus auxiliary key material for relinearization.)

Stretch goals

Replace the toy scheme with an honest Paillier implementation. Re-measure the expansion ratio. Verify additive homomorphism on the same 50 test cases.

Add an AddPlaintextCT operation:

\mathrm{Enc}(a) \boxplus_p b = \mathrm{Enc}(a + b)

— homomorphic addition with a plaintext (no second encryption needed). Show that this is cheaper than ciphertext-ciphertext addition.

Implement MulCTbyPlaintext:

E n c

. Show that this works in your toy scheme. Why does it work for multipliers but not for ciphertext-ciphertext multiplication?