Course Notes: Theory and Construction of Fully Homomorphic Encryption – Part One

Introduction: This article is the course notes from the afternoon session of the Fully Homomorphic Encryption summer class. The afternoon course was taught by Professor Xie Xiang, titled “Theory and Construction of Fully Homomorphic Encryption.” Professor Xie is a researcher at Shanghai Qi-Zhi Institute, primarily engaged in the research and implementation of efficient and secure multi-party computation protocols and fully homomorphic encryption algorithms. Professor Xie mainly explained Gentry’s bootstrapping theorem, the construction of three generations of fully homomorphic encryption algorithms, and application-oriented fully homomorphic encryption algorithms.

1

Basic Knowledge

A simple definition of homomorphic encryption algorithms is as follows:

A classic application of homomorphic encryption is outsourced computation (or cloud computing). A client with weak computing capabilities wishes to have a cloud server, which has strong computing capabilities, perform computation tasks without leaking private data. In this case, homomorphic encryption can be considered for encrypted computation. This is a very classic application scenario.

1.1 Security

To ensure stronger security, Goldwasser and Micali proposed probabilistic encryption in 1984, introducing a stronger security goal: semantic security. It has been theoretically proven that semantic security (Semantic Security, SS) is equivalent to ciphertext indistinguishability. Semantic security means that a ciphertext does not leak any plaintext information other than its length. We rarely use the form of semantic security to describe the security of an algorithm because its formal description is relatively obscure. IND-CPA, IND-CCA1, and IND-CCA2 are common definitions for the security of public key encryption. Here we provide a brief introduction to the three. The following link’s article was referenced.

[https://blog.csdn.net/m0_47659650/article/details/125223197]

IND-CPA

IND-CPA is indistinguishability under chosen plaintext attack. The adversary and challenger agree on the target cryptosystem, select the encryption key pk, and then proceed through the following stages:

Search Phase: The adversary selects two plaintexts of equal length,

Guessing Phase: The adversary is informed by the challenger of the encryption result of one plaintext and a random number r, and determines which is which, where b is confidential. If If the adversary’s goal is to guess the value of b with a probability greater than one-half. The adversary’s advantage is defined below. If it can be ignored, then it can be considered indistinguishable.

IND-CCA1

IND-CCA1 is indistinguishability under chosen ciphertext attack. Relative to the previous one, the adversary can call the encryption or decryption capability once before receiving the ciphertext; the specific process is as follows:

Training: The adversary requests the decryption of any ciphertext from the challenger (polynomially bounded times), i.e., selects a ciphertext C for the challenger, and the challenger returns the decryption result to the adversary.

Challenge: The adversary A selects two plaintexts of equal length, , then receives the encrypted ciphertext from the challenger, where b is random;

Guessing: The adversary outputs, if=, then the adversary succeeds.

The adversary’s goal is to guess the value of b with a probability greater than one-half. The adversary’s advantage is defined below:

If can be ignored, then it is considered that this cryptosystem has indistinguishability under non-adaptive chosen ciphertext attack, referred to as IND-CCA1 security.

IND-CCA2

IND-CCA2 is indistinguishability under adaptive chosen ciphertext attack. Relative to the previous one, there is no restriction on the time the adversary can call for decryption. The specific process is as follows:

Training 1: The adversary requests the decryption of any ciphertext from the challenger (polynomially bounded times), i.e., selects a ciphertext C for the challenger, and the challenger returns the decryption result to the adversary.

Challenge: The adversary A selects two plaintexts of equal length, , then receives the encrypted ciphertext from the challenger, where b is random;

Training 2: The adversary continues to request the decryption of any ciphertext from the challenger (polynomially bounded times), i.e., selects a ciphertext C (C cannot be) for the challenger, and the challenger returns the decryption result to the adversary.

Guessing: The adversary outputs, if=, then the adversary succeeds.

Homomorphic algorithms cannot achieve IND-CCA2. IND-CCA1 can be achieved but is relatively complex. In this course, we focus on the level of IND-CPA semantic security.

1.2 From SK-HE to PK-HE

In the notes from the summer class taught by Teacher Yu Yu on homomorphic encryption, we also mentioned that a symmetric homomorphic encryption algorithm can be used to construct an asymmetric homomorphic encryption algorithm. We will briefly review this.

Assume is a symmetric homomorphic encryption algorithm. Define :

where B is the upper limit of the ciphertext size.

Assume we want to encrypt , define Choose , such that .Define . Let

Define

then the obtained is a public key encryption homomorphic encryption algorithm. Therefore, ignoring efficiency, symmetric fully homomorphic algorithms and asymmetric fully homomorphic algorithms are equivalent.

2

Gentry’s Bootstrapping Theory

2.1 Augmented Decryption Circuit

Assume it is an asymmetric homomorphic encryption scheme. We define a Decryption Circuit as follows:

This formula can be understood as decrypting the ciphertext. Here is the input, which is public. If=, then:

Augmented Decryption Circuit:

NAND is a universal circuit, and we can use NAND to construct any logic circuit. NAND can be expressed as follows,

This definition also has a good property, NAND NAND

2.2 Bootstrapping Theorem

For a homomorphic encryption algorithm, if it supports an Augmented Decryption Circuit for ciphertext computation, then it is bootstrappable.

If there exists a bootstrappable public key homomorphic encryption mechanism, then there must exist a fully homomorphic encryption mechanism.

Remark: This is a simplified version of the theorem. The complete version requires additional constraints. However, this does not affect our understanding of the course.

2.3 Gentry’s Construction

Assume it is a bootstrappable homomorphic encryption algorithm. We will construct it according to the following steps.

1 Key Generation

Here a BK is generated, using PK to encrypt SK.

2 Encryption

3 Decryption

4 Eval

The calculation of Eval actually puts the encrypted input into the AGC circuit for computation, resulting in the NAND of the two ciphertexts corresponding to the plaintext. That is, NAND

As shown in the figure, this process can continue indefinitely. Theoretically, this achieves a fully homomorphic algorithm!

Note

1 The plaintext space defined by the previous calculation is, we need to calculate by splitting bits

2 Here, using one’s own public key to encrypt one’s private key, whether this operation is secure is still an open question.

2.4 Leveled FHE

The definition of Leveled FHE scheme: Given an integer, we can perform homomorphic encryption operations on circuits with a depth not exceeding.

Assume it is a bootstrappable homomorphic encryption algorithm. Its construction method is as follows.

1 Key Generation

This scheme first generates public and private keys, and then the generation is different from before. It uses encryption, uses encryption, and so on.

2 Encryption

Note that here it is used for encryption

3 Decryption

4 Eval

For the layer, when performing Eval computation, it will be placed in the ADC circuit, and the result obtained is the encrypted plaintext. Similarly, the layer obtains the ciphertext. And so on, the final ciphertext is obtained.

This scheme can be understood as a chain expansion. Such a chain scheme avoids the issue of using one’s own public key to encrypt the private key.

END

Author’s Introduction:

Zhuang Zhiliang, a graduate student at the School of Big Data and Software of Chongqing University. Main research interests include privacy-preserving machine learning, differential privacy, and federated learning. Zhihu: acai

Previous

Selected

Essays

Paper Notes: Publishing Graph Neural Networks with Differential Privacy Guarantees

BFLC: Blockchain-Based Decentralized Federated Learning Architecture with Committee Mechanism

Differential Privacy from a Statistical Perspective

Frontiers of Federated Learning | Research on Federated Recommendation Systems Based on Graph Neural Networks

Welcome to Submit

Email: [email protected]

To join more discussions, please add the editor’s WeChat to join the discussion group