0. Key Idea

• The noise $e$ is small but makes it computationally hard to recover the exact linear relation
• The scaling factor $\Delta$ ensures that the message $m$ remains distinguishable from the noise

---

1. LWE Problem (Intuition + Structure)

Suppose we have a plaintext number $m$ to encrypt.
The encryption formula is:

\[b = \mathbf{S} \cdot \mathbf{A} + \Delta m + e\]

• $\mathbf{S} \in \mathbb{Z}_q^k$: secret vector (fixed across encryptions)
• $\mathbf{A} \in \mathbb{Z}_q^k$: randomly sampled vector
• $e \in \mathbb{Z}_q$: small noise
• $\Delta$: scaling factor used to separate the plaintext $m$ from the noise $e$
• $q$: modulus defining the ciphertext domain $\mathbb{Z}_q$

1-2. Sampling Process

For each encryption:

• $\mathbf{A}$ is sampled uniformly from $\mathbb{Z}_q^k$
• $e$ is sampled from a small noise distribution over $\mathbb{Z}_q$

The secret vector $\mathbf{S}$ remains fixed.

1-3. Multiple Samples

Given multiple ciphertext pairs:

\[(\mathbf{A}^{(1)}, b^{(1)}), \quad (\mathbf{A}^{(2)}, b^{(2)}), \quad (\mathbf{A}^{(3)}, b^{(3)}), \dots\]

For each $(i = 1, 2, 3, \dots)$,

\[b^{(i)} = \mathbf{S} \cdot \mathbf{A}^{(i)} + \Delta m^{(i)} + e^{(i)}.\]

1-4. Security Intuition

Given many samples $(\mathbf{A}^{(i)}, b^{(i)})$,
recovering the secret $\mathbf{S}$ is computationally hard due to the presence of noise $e^{(i)}$.

This hardness forms the foundation of the Learning with Errors (LWE) problem.

• Search-LWE: Recovering the secret $\mathbf{S}$ is computationally hard

• Decision-LWE: Given samples $(\mathbf{A}^{(i)}, b^{(i)})$, it is hard to distinguish between:
  • $b^{(i)}$ sampled uniformly at random from $\mathbb{Z}_q$, or
  • $b^{(i)} = \mathbf{S} \cdot \mathbf{A}^{(i)} + e^{(i)}$
• These two problems are computationally equivalent

---

2. RLWE Problem (Intuition + Structure)

In RLWE, vectors in LWE are replaced by polynomials over a ring. The key difference is that operations are performed using polynomial multiplication in a ring, rather than vector inner products.

Suppose we have a plaintext polynomial $m(X)$ to encrypt.
The encryption formula is:

\[b(X) = A(X) \cdot S(X) + \Delta m(X) + e(X)\]

• $S(X) \in \mathbb{Z}_q[X]/(X^n + 1)$: secret polynomial (fixed across encryptions)
• $A(X) \in \mathbb{Z}_q[X]/(X^n + 1)$: randomly sampled polynomial
• $e(X) \in \mathbb{Z}_q[X]/(X^n + 1)$: small noise polynomial
• $\Delta$: scaling factor separating message and noise
• $q$: modulus defining the ring $\mathbb{Z}_q[X]/(X^n + 1)$

Here, each polynomial has degree at most $n-1$, meaning the secret consists of $n$ coefficients.

2-1. Sampling Process

For each encryption:

• $A(X)$ is sampled uniformly from $\mathbb{Z}_q[X]/(X^n + 1)$
• $e(X)$ is sampled from a small noise distribution

The secret polynomial $S(X)$ remains fixed.

2-2. Multiple Samples

Given multiple ciphertext pairs:

\[(A^{(1)}(X), b^{(1)}(X)), \quad (A^{(2)}(X), b^{(2)}(X)), \quad (A^{(3)}(X), b^{(3)}(X)), \dots\]

For each $(i = 1, 2, 3, \dots)$,

\[b^{(i)}(X) = A^{(i)}(X) \cdot S(X) + \Delta m^{(i)}(X) + e^{(i)}(X).\]

2-3. Security Intuition

Given many samples $(A^{(i)}(X), b^{(i)}(X))$,
recovering the secret polynomial $S(X)$ is computationally hard.

• Search-RLWE: In particular, this corresponds to finding the $n$ unknown coefficients of $S(X)$.

• Decision-RLWE: It is hard to distinguish between:

  • $b^{(i)}(X)$ sampled uniformly at random, or
  • $b^{(i)}(X) = A^{(i)}(X) \cdot S(X) + e^{(i)}(X)$

RLWE preserves the hardness of LWE while enabling more efficient computation through algebraic structure.

0. Key Idea

• The message is scaled by $\Delta$ to separate it from noise
• The noise occupies the lower bits, while the message stays in the higher bits

---

1. Encryption Structure

The LWE cryptosystem encrypts a message $M^{(i)}$ as:

\[\mathbf{B^{(i)}} = \mathbf{S} \cdot \mathbf{A^{(i)}} + \Delta \cdot \mathbf{M^{(i)}} + \mathbf{E^{(i)}}\]

• $\mathbf{S}$: secret key (unknown to attacker)
• $\mathbf{A}$: public key (random vector)
• $\mathbf{M}$: plaintext
• $\mathbf{E}$: small noise sampled from a distribution
• $\mathbf{B}$: ciphertext
• $\Delta$: scaling factor of the plaintext $\mathbf{M}$

2. Why Scaling is Needed

Before encryption, the message is scaled:

\[\Delta M^{(i)}\]

This corresponds to shifting the message by $\log_2 \Delta$ bits to the left.

• This creates space for noise in the lower bits
• Without scaling, noise would corrupt the message

3. Intuition (Bit-Level View)

• $\Delta M^{(i)}$ → occupies higher bits
• $E^{(i)}$ → occupies lower bits

So we get:

\[\Delta M^{(i)} + E^{(i)}\]

• message remains stable
• noise stays small relative to $\Delta M^{(i)}$

4. Encryption

The encryption is defined as:

\[B^{(i)} = S \cdot A^{(i)} + \Delta \cdot M^{(i)} + E^{(i)}\]

• $A^{(i)}$: publicly known random vector
• $B^{(i)}$: ciphertext
• $S$: secret key
• $M^{(i)}$: plaintext
• $E^{(i)}$: noise

Here, $A^{(i)}$ and $B^{(i)}$ are public, while $S$, $M^{(i)}$, and $E^{(i)}$ are unknown.

5. Decryption

To recover the message:

\[\frac{\left\lfloor B^{(i)} - \langle S, A^{(i)} \rangle \right\rceil_{\Delta}}{\Delta} = \frac{\left\lfloor \Delta M^{(i)} + E^{(i)} \right\rceil_{\Delta}}{\Delta} = M^{(i)}, \quad \text{provided that } E^{(i)} < \frac{\Delta}{2}\]

Here, $\left\lfloor \cdot \right\rceil_{\Delta}$ denotes rounding to the nearest multiple of $\Delta$.

For example:

• $\left\lfloor 16 \right\rceil_{10} = 20$
• $\left\lfloor 17 \right\rceil_{8} = 16$

This means that the value is rounded to the closest multiple of $\Delta$.

6. Correctness

To analyze correctness, we start from the decryption step:

\[B^{(i)} - S \cdot A^{(i)} = \Delta M^{(i)} + E^{(i)}\]

This shows that the decrypted value consists of the scaled message plus noise.

Next, we apply rounding:

\[\left\lfloor \Delta M^{(i)} + E^{(i)} \right\rceil_{\Delta}\]

If the noise satisfies:

\[E^{(i)} < \frac{\Delta}{2}\]

then the rounding removes the noise:

\[\left\lfloor \Delta M^{(i)} + E^{(i)}\right\rceil_{\Delta} = \Delta M^{(i)}\]

Finally, dividing by $\Delta$ gives:

\[\frac{\Delta M^{(i)}}{\Delta} = M^{(i)}\]

7. Security

To understand security, consider that an attacker observes many samples:

\[(A^{(i)}, B^{(i)})\]

where:

\[B^{(i)} = S \cdot A^{(i)} + \Delta M^{(i)} + E^{(i)}\]

1) Even with many such samples, recovering the secret key $S$ is computationally hard.

This is because each equation contains a different noise term $E^{(i)}$,
which prevents the system from forming exact linear equations.

2) Even if the same plaintext $M^{(i)}$ is encrypted multiple times:

\[(A^{(1)}, B^{(1)}), \quad (A^{(2)}, B^{(2)}), \quad \dots\]

(each ciphertext is generated independently from the same plaintext, using fresh randomness)

each encryption uses different randomness and noise:

• $A^{(j)}$ is randomly sampled
• $E^{(j)}$ is independently sampled

As a result, the attacker cannot combine these samples to eliminate the noise,
making it difficult to recover the original message.

3) Furthermore, both $A$ and $S$ are high-dimensional vectors. This increases the randomness (entropy) of the system and further strengthens security.

8. Conclusion

Lattice-based cryptography hides a plaintext by combining two key components:

• a linear term $S \cdot A$
• a small random noise $E$

1) During encryption, the message is scaled by $\Delta$ and embedded as:

\[S \cdot A + \Delta M + E\]

2) During decryption:

• The secret key $S$ is used to reconstruct $S \cdot A$ and remove it
• The noise $E$ is eliminated through rounding
• The remaining $\Delta M$ is scaled down to recover $M$

3) This design ensures that:

• The noise hides the underlying structure from attackers
• The rounding process removes the noise for correct decryption
• The scaling factor $\Delta$ separates the message from noise

Thus, lattice-based cryptography achieves both security and correctness through the interplay of noise and scaling.

0. Key Idea

• RLWE extends LWE by replacing vectors with polynomials over a ring.
• This structured representation enables more efficient computation while preserving the hardness of the LWE problem.

---

1. Encryption Structure

The encryption formula is:

\[B^{(i)}(X) = A^{(i)}(X) \cdot S(X) + \Delta M^{(i)}(X) + E^{(i)}(X)\]

• $S(X)$: secret polynomial
• $A^{(i)}(X)$: randomly sampled polynomial
• $M^{(i)}(X)$: plaintext polynomial
• $E^{(i)}(X)$: noise polynomial
• $B^{(i)}(X)$: ciphertext

All operations are performed over:

\[\mathbb{Z}_q[X] / (X^n + 1)\]

2. Key Difference from LWE

• Vector inner product → Polynomial multiplication
• $\mathbb{Z}_q^k$ → $\mathbb{Z}_q[X]/(X^n + 1)$
• Secret becomes $n$ coefficients instead of a vector

3. Summary

RLWE preserves the hardness of LWE while improving efficiency
by operating over polynomial rings instead of vectors.