Public Key Encryption

The encryption scheme in §B-4.2 assumes that it is the secret key owner who encrypts each plaintext. In this section, we explain a public key encryption scheme in which we create a public key counterpart of the secret key. Anyone who knows the public key can encrypt the plaintext in such a way that only the secret key owner can decrypt it. The high-level idea is that a portion of the components to be used in the encryption stage is pre-computed at the setup stage and published as a public key. At the actual encryption stage, the public key is multiplied by an additional randomness (

U

) and added to additional noise (

E_{1}, {\vec{E}}_{2}

) to create unpredictable randomness for each encrypted ciphertext. The actual scheme is as follows:

$⟨$ Summary B-4.5 $⟩$ GLWE Public Key Encryption

Initial Setup:

The scaling factor $Δ = ⌊ \frac{q}{t} ⌋$
The secret key $\vec{S} = {S_{i}}_{i = 0}^{k - 1} \leftarrow_{}^{$} R_{⟨ n, 𝑡𝑒𝑟𝑛 ⟩}^{k}$
The public key pair $({𝑃𝐾}_{1}, {\vec{𝑃𝐾}}_{2}) \in R_{⟨ n, q ⟩}^{k + 1}$ is generated as follows:
$\vec{A} = {A_{i}}_{i = 0}^{k - 1} \leftarrow_{}^{$} R_{⟨ n, q ⟩}^{k}$ , $E \leftarrow_{}^{χ_{σ}} R_{⟨ n, q ⟩}$
${𝑃𝐾}_{1} = \vec{A} \cdot \vec{S} + E \in R_{⟨ n, q ⟩}$
${\vec{𝑃𝐾}}_{2} = \vec{A} \in R_{⟨ n, q ⟩}^{k}$

Encryption Input: $M \in R_{⟨ n, t ⟩}$ , $U \leftarrow_{}^{$} R_{⟨ n, 𝑡𝑒𝑟𝑛 ⟩}, E_{1} \leftarrow_{}^{χ_{σ}} R_{⟨ n, q ⟩}, {\vec{E}}_{2} \leftarrow_{}^{χ_{σ}} R_{⟨ n, q ⟩}^{k}$

1.

Scale up

M \to Δ M \in R_{⟨ n, q ⟩}

2.

Compute the following:

$B = {𝑃𝐾}_{1} \cdot U + Δ M + E_{1} \in R_{⟨ n, q ⟩}$

$\vec{D} = {\vec{𝑃𝐾}}_{2} \cdot U + {\vec{E}}_{2} \in R_{⟨ n, q ⟩}^{k}$ $▹$ ${\vec{𝑃𝐾}}_{2} \cdot U$ multiplies each element of ${\vec{𝑃𝐾}}_{2}$ by $U$

3.

{𝖦𝖫𝖶𝖤}_{S, σ} (Δ M + E_{𝑎𝑙𝑙}) = (\vec{D}, B) \in R_{⟨ n, q ⟩}^{k + 1}

▹

where

E_{𝑎𝑙𝑙} = E \cdot U + E_{1} - {\vec{E}}_{2} \cdot \vec{S}

Decryption Input: $𝖼𝗍 = (\vec{D}, B) \in R_{⟨ n, q ⟩}^{k + 1}$

1.: ${𝖦𝖫𝖶𝖤}_{S, σ}^{- 1} (𝖼𝗍) = B - \vec{D} \cdot \vec{S} = Δ M + E_{𝑎𝑙𝑙} \in R_{⟨ n, q ⟩}$
2.: Scale down $⌈ \frac{Δ M + E_{𝑎𝑙𝑙}}{Δ} ⌋ = M \in R_{⟨ n, t ⟩}$

For correct decryption, every noise coefficient $e_{i}$ of polynomial $E_{𝑎𝑙𝑙}$ should be: $| e_{i} | < \frac{Δ}{2}$ .

{𝖦𝖫𝖶𝖤}_{S, σ}^{- 1} (𝖼𝗍 = (\vec{D}, B)) = B - \vec{D} \cdot \vec{S}

= ({𝑃𝐾}_{1} \cdot U + Δ M + E_{1}) - ({\vec{𝑃𝐾}}_{2} \cdot U + {\vec{E}}_{2}) \cdot \vec{S}

= (\vec{A} \cdot \vec{S} + E) \cdot U + Δ M + E_{1} - (\vec{A} \cdot U) \cdot \vec{S} - {\vec{E}}_{2} \cdot \vec{S}

= (U \cdot \vec{A}) \cdot \vec{S} + E \cdot U + Δ M + E_{1} - (U \cdot \vec{A}) \cdot \vec{S} - {\vec{E}}_{2} \cdot \vec{S}

= Δ M + E_{𝑎𝑙𝑙}

▹

where

E_{𝑎𝑙𝑙} = E \cdot U + E_{1} - {\vec{E}}_{2} \cdot \vec{S}

Security: The GLWE encryption scheme’s encryption formula (Summary B-4.2 in §B-4.2) is as follows:

{𝖦𝖫𝖶𝖤}_{S, σ} (Δ M + E) = (\vec{A}, B = \vec{A} \cdot \vec{S} + Δ M + E)

, where the hardness of the LWE and RLWE problems guarantees that guessing

\vec{S}

is difficult given

\vec{A}

and

E

are randomly picked at each encryption. On the other hand, the public key encryption scheme is as follows:

{𝖦𝖫𝖶𝖤}_{S, σ} (Δ M + E_{𝑎𝑙𝑙}) = (\vec{D} = {\vec{𝑃𝐾}}_{2} \cdot U + {\vec{E}}_{2}, B = {𝑃𝐾}_{1} \cdot U + Δ M + E_{1})

, where

{𝑃𝐾}_{1}

{\vec{𝑃𝐾}}_{2}

are fixed and

U

E_{1}

{\vec{E}}_{2}

are randomly picked at each encryption. Given the polynomial degree

n

is large, both schemes provide the equivalent level of hardness to solve the problem.

B-4.5 Public Key Encryption