In the bottom of the wikipedia article of LWE (https://en.wikipedia.org/wiki/Learning_with_errors), we can see construction of Public-key cryptosystem based on the LWE.

But, I cannot understand whole thing geometrically.

From a $n$-dimensional vector space (modulo q), we sample a random vector $\mathbf{s} \in \mathbb{Z}^n_q$ which is exactly a secret key. I can easily have geometric understanding of it.

A public key is obtained by choosing $m$ vectors $\mathbf{a}_1,..., \mathbf{a}_m $ where $\mathbf{a}_i \in \mathbb{Z}^n_q$. Then, choose $m$-error offsets $e_1, ..., e_m \in \mathbb{T}$ from normal distribution. The public key is $(\mathbf{a}_i, b_i = \langle \mathbf{a}_i, \mathbf{s}\rangle / q + e_i)^{m}_{i=1}$.

Using the public key, we can encrypt a bit $x\in \{0,1\}$ by choosing a random subset S of $[m]$ and then defining Enc(x) as

$(\mathbf{a}, b) = (\sum_{i\in S} \mathbf{a}_i, \frac{x}{2} + \sum_{i \in S}b_i)$)

The decryption of $Enc(x) = (\mathbf{a}, b)$is 0 if $b - \langle \mathbf{a}, \mathbf{s} \rangle/q$ is closer to 0 than to 1/2, and 1 otherwise.

$\textbf{What I can imagine}:$

  1. There is one secret vector (point) in $n$-dimensional vector space mod q (is $\mathbb{Z}_q^n$ a lattice)?

  2. There are $m$-public vectors (points) in the space.

  3. For each public vector (point), one publicly noisy constant (inner product of the vector and the secret, which is then added to an offset) $\in \mathbb{T}$ is somewhere in between points in $\mathbb{Z}_q^n$).


Q1. What is the geometric interpretation of the public key $(\mathbf{a}_i, b_i) \in (\mathbb{Z}_q^n \times \mathbb{T})^m$? What I can know is we work on $\mathbb{Z}_q^n$ and $\mathbb{T}$. But, where does exactly an element in $\mathbb{T}$ belong along with $\mathbb{Z}_q^n$? From 2 and 3 above, can we say that secret key is blurred?

Q2. What is the geometric interpretation of the ciphertext and its decryption formula? I do not know what's happening by adding public points and adding noisy constants (plus message). I guess the decryption works via inner product of $(\mathbf{a}, b)$ and $(-\mathbf{s}/q, 1) $, but why inner product?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.