CKKS Homomorphic Encryption

A DID scheme based on homomorphic encryption of face features

CKKS algorithm is a fully homomorphic encryption (HE) scheme used for encrypted computation. Its full name is "Cheon-Kim-Kim-Song" and was proposed by Cheon et al. (2017) [3]. The CKKS algorithm can support encrypted computation for complex and real number data, and can achieve relatively high encryption computation accuracy and small ciphertext expansion factors, making it one of the widely used fully homomorphic encryption schemes today.

CKKS plaintext space

Unlike other HE schemes, the CKKS scheme supports approximate arithmetic over complex numbers. More precisely, the plaintext space of the CKKS scheme is $\mathbb{C}^{n/2}$ for some power-of-two integer $n$. To deal with the complex plaintext vector efficiently, Cheon et al. proposed plaintext encoding/decoding methods which exploits a ring isomorphism $\phi: \mathbb{R}[X]/(X^n+1) \rightarrow \mathbb{C}^{n/2}$ .

Encoding method

Given a plaintext vector $\vec z = (z_1,z_2,...,z_{n/2}) \in \mathbb{C}^{n/2}$ and a scaling factor $\Delta > 1$, the plaintext vector is encoded as a polynomial $m(X) \in R:= \mathbb{Z}[X]/(X^n+1)$ by computing $m(X) = \lfloor \Delta \cdot \phi^{-1}(\vec z) \rceil \in R$ where $\lfloor \cdot \rceil$ denotes the coefficient-wise rounding function.

Decoding method

Given a message polynomial $m(X) \in R$ and a scaling factor $\Delta > 1$, the message polynomial is decoded to a complex vector $\vec z \in \mathbb{C}^{n/2}$ by computing $\vec z = \Delta^{-1}\cdot \phi(m(X)) \in \mathbb{C}^{n/2}$.

Here the scaling factor $\Delta > 1$ enables us to control the encoding/decoding error which is occurred by the rounding process. Namely, one can obtain the approximate equation $\text{Dcd}(\text{Ecd}(\vec z; \Delta); \Delta) \approx \vec z$ by controlling $\Delta$ where $\text{Ecd}$ and $\text{Dcd}$ denote the encoding and decoding algorithm, respectively.

From the ring-isomorphic property of the mapping $\phi: \mathbb{R}[X]/(X^n+1) \rightarrow \mathbb{C}^{n/2}$ , for $m_1 = \text{Ecd}(\vec z_1;\Delta)$ and $m_2 = \text{Ecd}(\vec z_2;\Delta)$, the following hold:

• $\text{Dcd}(m_1 + m_2;\Delta) \approx \vec z_1 + \vec z_2$,

• $\text{Dcd}(m_1\cdot m_2;\Delta) \approx \vec z_1 \circ \vec z_2$,

where $\circ$ denotes the [[Hadamard product (matrices)|Hadamard product]] of the same-length vectors. These properties guarantee the approximate correctness of the computations in the encoded state when the scaling factor $\Delta$ is chosen appropriately.

Algorithms

The CKKS scheme basically consists of those algorithms: key Generation, encryption, decryption, homomorphic addition and multiplication, and rescaling. For a positive integer $q$, let $R_q := R/qR$ be the quotient ring of $R$ modulo $q$. Let $\chi_s$, $\chi_r$ and $\chi_e$ be distributions over $R$ which output polynomials with small coefficients. These distributions, the initial modulus $Q$, and the ring dimension $n$ are predetermined before the key generation phase.

Key generation

The key generation algorithm is following:

• Sample a secret polynomial $s \leftarrow \chi_s$.

• Sample $a$ (resp. $a'$) uniform randomly from $R_Q$ (resp. $R_{PQ}$), and $e,e' \leftarrow \chi_e$.

• Output a secret key $sk \leftarrow (1, s)\in R_Q^2$, a public key $pk \leftarrow (b = -a \cdot s + e, a) \in R_Q^2$, and an evaluation key $evk \leftarrow (b' = -a' \cdot s + e' + P\cdot s^2, a') \in R_{PQ}^2$.

Encryption

The encryption algorithm is following:

• Sample an ephemeral secret polynomial $r \leftarrow \chi_r$.

• For a given message polynomial $m \in R$, output a ciphertext $ct \leftarrow (c_0 = r\cdot b + e_0 + m, c_1 = r\cdot a + e_1) \in R_Q^2$.

Decryption

The decryption algorithm is following:

• For a given ciphertext $ct \in R_q^2$, output a message $m' \leftarrow \langle ct, sk \rangle </math> <math> (\text{mod } q)$.

The decryption outputs an approximate value of the original message, i.e., $\text{Dec}(sk, \text{Enc}(pk, m)) \approx m$, and the approximation error is determined by the choice of distributions $\chi_s, \chi_e, \chi_r$. When considering homomorphic operations, the evaluation errors are also included in the approximation error. Basic homomorphic operations, addition and multiplication, are done as follows.

Homomorphic addition

The homomorphic addition algorithm is following:

• Given two ciphertexts $ct$ and $ct'$ in $R_q^2$, output $ct_{\text{add}} \leftarrow ct + ct' \in R_q^2$.

The correctness holds as $\text{Dec}(sk, ct_\text{add}) \approx \text{Dec}(sk, ct) + \text{Dec}(sk, ct')$.

Homomorphic multiplication

The homomorphic multiplication algorithm is following:

• Given two ciphertext $ct =(c_0, c_1)$ and $ct' =(c_0', c_1')$ in $R_q^2$, compute $(d_0, d_1, d_2) = (c_0c_0', c_0c_1'+c_1c_0', c_1c_1')$ $(\text{mod } q)$. Output $ct_{\text{mult}} \leftarrow (d_0, d_1) + \lfloor P^{-1}\cdot d_2 \cdot evk \rceil \in R_q^2$.

The correctness holds as $\text{Dec}(sk, ct_\text{mult}) \approx \text{Dec}(sk, ct) \cdot \text{Dec}(sk, ct')$.

Note that the approximation error (on the message) exponentially grows up on the number of homomorphic multiplications. To overcome this problem, most of HE schemes usually use a modulus-switching technique which was introduced by Brakerski et al. (2012) [4].

In case of HEAAN, the modulus-switching procedure is called rescaling. The Rescaling algorithm is very simple compared to Brakerski-Gentry-Vaikuntanathan's original algorithm. Applying the rescaling algorithm after a homomomorphic multiplication, the approximation error grows linearly, not exponentially.

Rescaling

The rescaling algorithm is following:

• Given a ciphertext $ct \in R_q^2$ and a new modulus $q'$ output a rescaled ciphertext $ct_{\text{rs}}\leftarrow \lfloor (q'/q)\cdot ct\rceil \in R_{q'}^2$.

The total procedure of the CKKS scheme is as following: Each plaintext vector $\vec z$ which consists of complex (or real) numbers is firstly encoded as a polynomial $m(X) \in R$ by the encoding method, and then encrypted as a ciphertext $ct \in R_q^2$. After several homomorphic operations, the resulting ciphertext is decrypted as a polynomial $m'(X) \in R$ and then decoded as a plaintext vector $\vec z'$ which is the final output.

DID Creation Based on Homomorphic Encrypted Face Features

This scheme uses homomorphic encryption technology to protect users' facial feature data. During user registration, facial features are extracted using liveness verification technology, encrypted using homomorphic encryption technology, and uploaded to the server. The server uses homomorphic encryption technology to compare and generate similarity ciphertext, which will be sent back to the frontend application for decryption and verification. If the user's facial features are not registered, the DID identifier and facial feature ciphertext will be saved in the database to complete the registration.

Homomorphic encryption technology allows calculations to be performed on data in an encrypted state, which can prevent sensitive data from being exposed in plaintext. At the same time, liveness verification technology can prevent malicious users from uploading photos of others to register fake accounts. This scheme provides a secure and reliable method for creating DID identifiers and protecting user privacy.

The creation process is as follows:

1. Generate a public-private key pair on the frontend: Users generate a public-private key pair on the frontend application, where the public key is used to create the DID identifier, and the private key is used for signature.

2. Generate a DID identifier: The DID identifier is generated using the public key, which is used to identify the user's identity.

3. Scan the user's face, perform liveness verification, and extract facial features: The frontend application scans the user's face, uses liveness verification technology to ensure that the face is real, and extracts facial features (faceprint) from it.

4. Homomorphically encrypt the faceprint vector values and upload the facial feature ciphertext to the server: Use homomorphic encryption technology to encrypt the facial features, and upload the encrypted facial feature values to the server.

5. Perform similarity matching based on facial feature ciphertext on the server and obtain the similarity ciphertext: The server uses homomorphic encryption technology to compare the encrypted facial features, and obtains a similarity score ciphertext.

6. Send the similarity ciphertext to the frontend: The server sends the similarity ciphertext to the frontend application.

7. Decrypt the similarity ciphertext on the frontend and determine if the facial features have been registered: The frontend application uses the private key to decrypt the similarity ciphertext to determine whether the facial features have been registered.

8. Register the DID identifier and facial feature ciphertext: If the facial features are not registered, the DID identifier and facial feature ciphertext will be saved to the database to complete the registration process.

References

• Boddeti, Vishnu Naresh. "Secure face matching using fully homomorphic encryption." 2018 IEEE 9th International Conference on Biometrics Theory, Applications and Systems (BTAS). IEEE, 2018.

• Liu, Weiyang, et al. "Sphereface: Deep hypersphere embedding for face recognition." Proceedings of the IEEE conference on computer vision and pattern recognition. 2017.

• Cheon, Jung Hee, et al. "Homomorphic encryption for arithmetic of approximate numbers." Advances in Cryptology–ASIACRYPT 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part I 23. Springer International Publishing, 2017.

• Brakerski, Zvika. "Fully homomorphic encryption without modulus switching from classical GapSVP." Advances in Cryptology–CRYPTO 2012: 32nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012. Proceedings. Springer Berlin Heidelberg, 2012.