Regev Encryption — the LWE public-key scheme, and why recovering the secret is game over

Regev's original LWE-based public-key scheme: it encrypts one bit at a time as (u, v), and once you recover the LWE secret s, decryption is a one-line inner product — no further cryptanalysis needed.

The signal that gives it away

A challenge is doing Regev encryption (or a close variant) when you see:

- Per-bit ciphertexts: the plaintext is split into individual bits, each encrypted separately into its own (u, v) pair — not a single ciphertext for the whole message. - A matrix public key: (A, b) with b = A·s + e (or the transposed form b = sᵀ·A + e), i.e. the public key already *is* an LWE instance. - A `q/2` (or `⌊q/2⌋`) offset in the ciphertext — the unmistakable tell. It's the encoding trick that turns a bit into "far from 0" vs "far from q/2" after decryption. - Subset-sum-of-rows structure at encryption time: the ciphertext u is built by summing a random subset (or a random 0/1-weighted combination) of the rows of A, and v sums the corresponding entries of b plus the bit·⌊q/2⌋ term. - Decryption described as an inner product with a secret vector followed by rounding — v - <u, s> compared against 0 vs q/2.

If instead the ciphertext is one big vector/polynomial with no per-bit q/2 offsets, you're more likely looking at Ring-LWE — recognizing polynomial-ring LWE and reducing it to plain LWE or a different LWE-based scheme (e.g. a KEM), not textbook Regev.

How to exploit it

The scheme, concretely:

- Keygen: secret s ∈ Z_q^n; public A (an N×n, or m×n, matrix over Z_q) and b = A·s + e for small noise e — this pair *is* an LWE sample set, and is exactly what LWE Fundamentals — recognizing and breaking noisy linear equations mod q describes. - Encrypt one bit m ∈ {0,1}: pick a random binary vector r ∈ {0,1}^N (equivalently, a random subset of the rows of A/b), and output: - u = Aᵀ·r (sum of a random subset of the rows of A) - v = bᵀ·r + ⌊q/2⌋·m - Decrypt: compute d = (v - <u, s>) mod q. The result is ≈0 if m=0 and ≈q/2 if m=1 (the residual noise from r's combination of e stays small, |noise| ≪ q/4, so the two cases don't overlap). Round to the nearest of {0, q/2}:

```python def decrypt_bit(u, v, s, q): d = (v - u.dot_product(s)) % q return 1 if abs(d - q//2) < q//4 else 0 # nearest of {0, q/2}

msg_bits = [decrypt_bit(u, v, s, q) for (u, v) in ciphertexts] ```

The entire game is therefore recover `s`, then decrypt is free. To recover s, treat (A, b) as a plain LWE instance and attack it the way LWE Fundamentals — recognizing and breaking noisy linear equations mod q describes: embed into a lattice (Kannan embedding) and run LLL Reduction — the polynomial-time workhorse behind almost every lattice attack (or BKZ for larger instances) to pull out the short error vector, then solve A·s = b - e linearly.

CTF-realistic shortcuts that skip a full lattice attack, in order of how often they show up:

- Noise too small / structured: if the error is tiny enough (or the low bits of b are noise-free), you can sometimes solve A·s ≈ b directly with linear algebra over a truncated system — no LLL needed. Always check this first; it's much faster than reaching for reduction. - Reused randomness across ciphertexts: if the same r (or overlapping subsets) is reused to encrypt multiple bits, the system of equations across ciphertexts becomes overdetermined and easier to attack, or leaks relations between plaintext bits directly. - Low-dimension secret: small n (toy/demo parameters) makes s brute-forceable directly, especially if entries are binary or ternary — check the dimension before setting up a lattice attack. - Degenerate `r`: if r isn't uniformly random over {0,1}^N (e.g. always low Hamming weight, or a fixed/predictable pattern), the effective noise in u/v shrinks or becomes biased, which can make direct solving or a smaller lattice basis sufficient.

Once s is known, every ciphertext under that public key decrypts instantly — this is why isolating "how do I recover s" (small n, low noise, structural leaks) matters more than optimizing the decryption formula itself.

What does NOT work

- Trying to invert the `⌊q/2⌋` rounding without `s`: v alone tells you nothing about m; the offset only becomes meaningful relative to <u, s>. Don't waste time reasoning about v's raw value in isolation. - Treating each bit-ciphertext as an independent unrelated cryptosystem: they all share the same (A, s). Recovering s from *one* set of LWE samples (the public key itself, which is already N samples) breaks *every* ciphertext ever produced under it — don't try to attack each (u, v) pair separately as its own hard problem. - Running LLL/BKZ blindly on a huge, correctly-parameterized instance: production-grade LWE parameters (large n, sufficiently large Gaussian noise) resist off-the-shelf lattice reduction; a CTF Regev instance that's actually secure at those parameters will not fall to a quick LLL call. If reduction doesn't terminate quickly or the resulting basis has no unusually short vector, look for a parameter weakness (small n, small modulus, tiny noise, reused randomness) instead of throwing more BKZ blocksize at it — that's usually the intended path, not brute lattice strength. - Assuming the `q/2` threshold check has to be exact equality: decryption is a *rounding* operation with a slack of q/4 on either side; if your recovered s is only approximately correct, some bits may still decrypt correctly while others flip — don't discard a "close" secret candidate as wrong just because a few bits look off, and don't assume a scheme is broken (padding/format oracle needed) just because a handful of bits are noisy.

Related

LWE Fundamentals — recognizing and breaking noisy linear equations mod q Lattice Fundamentals — encoding a bounded unknown as a short vector LLL Reduction — the polynomial-time workhorse behind almost every lattice attack Ring-LWE — recognizing polynomial-ring LWE and reducing it to plain LWE