# An Efficient Encrypted Floating-Point Representation Using HEAAN and TFHE

Authors: Subin Moon; Younho Lee
Journal: Security and Communication Networks
 (2020)

---

## Abstract

As a method of privacy-preserving data analysis (PPDA), a fully homomorphic encryption (FHE) has been in the spotlight recently. Unfortunately, because many data analysis methods assume that the type of data is of real type, the FHE-based PPDA methods could not support the enough level of accuracy due to the nature of FHE that fixed-point real-number representation is supported easily. In this paper, we propose a new method to represent encrypted floating-point real numbers on top of FHE. The proposed method is designed to have analogous range and accuracy to 32-bit floating-point number in IEEE 754 representation. We propose a method to perform arithmetic operations and size comparison operations. The proposed method is designed using two different FHEs, HEAAN and TFHE. As a result, HEAAN is proven to be very efficient for arithmetic operations and TFHE is efficient in size comparison. This study is expected to contribute to practical use of FHE-based PPDA.


---

## Body

## 1. Introduction

Fully homomorphic encryption (FHE) is a technology that supports computation on ciphertexts without decrypting them. Using these properties, we can process and analyze sensitive medical and financial information without exposing them if we use FHE. Therefore, FHE is expected to be an indispensable core technology for the prevalence of artificial intelligence and data mining, which is the core technology of the 4th industrial revolution [1, 2].Most existing FHEs manage ciphertext on a bit-by-bit basis. Some methods have a number of slots in a ciphertext and support SIMD operations. Even in this case, only one bit of plaintext can be inserted into a single slot. This is because FHE schemes are defined on particular mathematical structures. If multiple bits occupy a slot, it is unclear as to whether or not all efficient computation algorithms can be implemented using the operations provided naturally on the mathematical structures.On the other hand, in the case where only a 1-bit plaintext is inserted in the slot, any efficient algorithm can be implemented with the bitwise-AND and bitwise-XOR operations. Thus, if these operations are implemented with the operations on the mathematical structures, and the ciphertexts are enabled to work with them indefinite number of times, we can say that FHE schemes can implement any efficient algorithm. There are numerous FHE schemes that follow this argument [3–12], including HELib and TFHE.The purpose of this study is to realize representation of encrypted floating-point real number and their operations. Various machine learning algorithms use real numbers to manage their input, output, and intermediate values, as is the case with the recently introduced Deep Neural Network. There have been various attempts to realize these algorithms using FHE and to perform machine learning and classification even when receiving encrypted input values. However, due to the bitwise nature of the plaintexts in most FHE schemes as described above, the existing attempts have treated real numbers with fixed-point representation in most cases. Since using fixed-point numbers in this field causes the degradation of the accuracy and range of the expressed values, it also affects the algorithm performance. For this reason, floating-point representation is preferred in numerical applications [13].Unfortunately, there have been only few attempts to represent floating-point numbers with FHE. A representative study is the HEAAN method [14]. In HEAAN, floating point numbers can be thought of because they have the advantage of keeping the same significant digits regardless of the size of the computed result. However, HEAAN has a few drawbacks. First, it does not provide comparison operations on given numbers. This is a big problem when implementing various applications using HEAAN. Second, HEAAN provides the division operation only within a limited range of realizations. That is, if “a” is the real number contained in a cipher text, then |1−a| ≤ 1/2 should be held. Therefore, in order to use HEAAN for applications, it is necessary to scaling the values.Apart from HEAAN, TFHE was proposed in 2017, which supports very fast bootstrapping [7]. Sadly, because it does not provide floating-point operations, a new method is needed to support the encrypted floating-point representation over TFHE and the operations that can work on top of the representation.Therefore, we propose an encrypted floating-point representation on which it is provided efficient floating-point operations over the encrypted values by the above FHE schemes. In the proposed method, real numbers are expressed with sign, exponent, and mantissa similarly to the conventional IEEE 754 expression. However, it is designed to achieve the efficiency of the entire operations by utilizing the characteristics of each FHE method. Supporting the efficient floating-point operations over the proposed encrypted representation is not an easy task because we have to consider all possible values that ciphertexts of the proposed representation must have when we design the computation circuits to implement the operations.In this paper, we compare the performance of two representations each of which is implemented on top of HEAAN and FHE, respectively. As a result of performance comparison, HEAAN has a computation speed of several tens to hundreds of times faster than that of TFHE-based implementation. In the comparison operation, TFHE has tens to hundreds of times higher performance than HEAAN. In the case of the equality checking operation, we could observe that TFHE case is about 5 times faster than HEAAN. The proposed method is expected to be used for the implementation of the algorithms in privacy-preserving machine learning. In particular, it tells you what type of FHE schemes to use depending on the type of operation being used. Based on this, we hope that it could be widely used in encrypted data processing and analysis applications.This paper is organized as follows. Section2 describes the preliminary to help understanding this study. Section 3 introduces the research motivation and related work. In Section 4, the proposed method is given, which is followed by the performance evaluation of implementation results in Section 5. Section 6 concludes the paper.


## 2. Preliminary

### 2.1. IEEE 754 Floating-Point Representation

The proposed representation is a variant of IEEE 754 standard floating-point representation to support the arithmetic and relational operations efficiently with the underlying FHE schemes. Therefore, to understand the proposed representation easily, we first briefly overview it. In IEEE 754, two types of floating-point representation are defined, single-precision and double-precision, depending on the number of bits assigned for a representation. In this work, we only focus on the single-precision representation as this is only applied for the proposed one.Figure1 shows the IEEE 754 single-precision representation. It is composed of three parts: 1-bit sign, 8-bit exponent, and 23-bit mantissa. The sign bits represent if the value is positive (0) or negative (1). The exponent bits represent the exponent which is in the range between −127 and 127. The “fraction” bits contain the significant bits of the value. In normal mode, Figure 1 represents a real number (−1) (sign) ∗ 1. (FRACTION) (2) ∗ 2(EXPONENT(2)−127), where binary values represent unsigned positive integers.Figure 1
IEEE 754 single-precision floating-point number—bit representation.The arithmetic and relational operations between the numbers expressed in this way can be carried out as follows. In the case of addition and subtraction, the exponents of two operands are made equal. The mantissas of them are adjusted following the changed exponents, respectively. After that, the operation is performed with the adjusted mantissas. In the case of multiplication and division, operations are performed on exponents and mantissas of two operands, respectively. After processing, adjustment is performed on the resultant exponent and mantissa in order to match the expression rules. Please refer to [15] for details.


### 2.2. Fully Homomorphic Encryption (FHE)

FHE is a special cryptosystem that can process encrypted data without decrypting them. This is useful for data delegation or privacy-preserving data processing. Figure2 shows the difference between FHE and a conventional encryption scheme when addition of two encrypted numbers is performed. With the ciphertexts by FHE, addition of their hidden plaintext values is possible without decryption.Figure 2
Adding two plaintexts in ciphertexts: comparison between conventional encryption and homomorphic encryption.An FHE scheme is defined with the following algorithms:ParamGen (1λ, N, L) ⟶ param: this generates a parameter for key generation. It takes the security parameter λ, the number of slots in a ciphertext N, and the possible multiplicative depth of a fresh ciphertext without bootstrapping L.KeyGen (param) ⟶ sk, pk, evk: this is a key generation algorithm, which takes the parameter from the parameter generation algorithm and outputs sk, a secret key for decryption, pk, a public key for encryption, and evk, a set of the evaluation keys with which some computation over the ciphertexts can be done if the ciphertexts are generated with the matched pk.Enc (m⟶, pk) ⟶ C: an encryption algorithm which takes a vector of plaintext message m⟶ of dimension N and a public key and outputs a ciphertext that contains m⟶.Dec (C,sk) ⟶ m⟶ (or ⊥): it takes a ciphertext c and a secret key sk, and outputs a plaintext m⟶ if C is the result of Enc(m⟶, pk) and pk is matched to sk. Otherwise, it outputs ⊥.In addition to the above algorithms, FHE provides computational algorithms between ciphertexts. However, they provide different functions for each FHE scheme. Therefore, they will be described when each FHE scheme is introduced. We introduce two recent FHE schemes, which are used to implement the proposed (encrypted) floating-point representation.


#### 2.2.1. HEAAN

HEAAN’s ciphertext can contain multiple plaintext bits in one slot, unlike the previous FHE methods [14, 16]. Let the corresponding bit length be the word size. HEAAN also supports various operations between the encrypted values of a word size in the ciphertext slots. Unfortunately, they are supported in an approximate fashion. That is, if an operation is performed between encrypted word-sized values, the bit-precision of the result is similar to that of an operand. In the case of multiplication, when the bit length of operands is n, the result’s bit length should be 2n−1 to represent the result correctly. However, in HEAAN, only the most significant n bits of the result are correct. At the expense of this bit accuracy, HEAAN supports very fast arithmetic operations on word-sized encrypted data. This fast computation speed allows HEAAN to be used in many fields such as machine learning and machine control [17, 18]. In addition, unlike TFHE, HEAAN has the advantage of providing a complete SIMD function. That is, there is an advantage that the value can be shifted between slots. The major disadvantage of HEAAN compared to TFHE is that it requires bootstrapping. That is, when performing multiplication operations more than a certain number of times consecutively, that is, when a multiplication circuit having a certain depth or more is performed, bootstrapping should be performed to do further multiplication while preserving the correct computation result. Otherwise, the ciphertext no longer has the correct plaintext.HEAAN_Mult (C0, C1, evk) ⟶ Cmult: this algorithm multiplies the encrypted values stored in each slot of the same position in two ciphers C0, C1 with each other and stores the result in the same slot position of the resultant ciphertext Cmult.HEAAN_Add/Sub (C0, C1, evk) ⟶ Cadd (Csub): this algorithm performs slotwise addition (subtraction) with two ciphertexts C0 and C1 and outputs Cadd (Csub) which has the result of the computation.HEAAN_Bootstrapping (C0, evk) ⟶ cnew: this algorithm takes a ciphertext C0 and returns a new ciphertext Cnew with the same plaintext. We can execute a multiplicative circuit of a certain number of depths with Cnew, where the depth is defined by the parameters.HEEAN_LeftShift (C0, k, evk) ⟶ Cshifted: this algorithm generates a new ciphertext Cshifted by moving the plaintexts in each slot of cipher C0 to the left by k slots. It is a circular shift. Thus, we can shift the values in C0 to the right by k slots by making the values shifted left by N-k slots, where N is the number of total slots.HEAAN supports the following algorithms in addition to the common FHE algorithms described above.


#### 2.2.2. TFHE

TFHE [9, 19] was created in 2017 using the GSW [20] technique. Each slot in the TFHE ciphertext contains a 1-bit plaintext. It supports bitwise AND and bitwise XOR operations on the encrypted plaintext bit in each slot. Based on those operations, it is possible to implement any arbitrary efficient algorithm which can work with encrypted inputs. In addition to the basic algorithms mentioned above, TFHE supports the following algorithms:TFHE_AND (C0, C1, evk) ⟶ cand: a bitwise AND operation is performed on the values of the slot at the same position in the two ciphertexts c0 and c1, and the result is stored in the slot of the same position in the resultant cipher Cand.TFHE_XOR (C0, C1, evk) ⟶ Cxor: it executes the slotwise XOR operations on bit values of the same slot position in c0 and c1. The result is stored in the same slot position of the resultant ciphertext Cxor.One advantage of THE is that it supports very fast bootstrapping. However, it needs bootstrapping at the end of every operation. Thus, we suppose that the bootstrapping is contained in the above bitwise operations.


#### 2.2.3. An Overview for the Ciphertext Structures and Operations

To help the readers understand both FHE methods, we discuss the format of the ciphertext used and more details on them. Let us talk about HEAAN first. Figure3 shows the structure of the HEAAN ciphertext and the operations supported on it. In HEAAN, as shown in the figure below, a limited number of real numbers can be stored in one ciphertext. Arithmetic operations can be performed between those in the same slot as shown in Figure 3(B). In addition to this, as shown in Figure 3(C), it is possible to move the embedded plaintexts between slots. Finally, if there are two ciphertexts where only 0 or 1 are encrypted in each slot, then logical AND/XOR operations between the encrypted values are possible in the same slot position of both ciphertexts. These logical operations can be implemented by arithmetic subtraction, addition, and multiplication using the equations described in Figure 3(D). Unfortunately, there is a disadvantage that a slot can only store a fixed-point real-number plaintext. Also, a certain operation can work only when the stored plaintext value is within a limited range. TFHE has similar ciphertext structure as HEAAN, but each slot can contain only 0 or 1 (1 bit value). Also, slot-shift operation is not supported.Figure 3
Ciphertext structure and operations in HEAAN.


## 2.1. IEEE 754 Floating-Point Representation

The proposed representation is a variant of IEEE 754 standard floating-point representation to support the arithmetic and relational operations efficiently with the underlying FHE schemes. Therefore, to understand the proposed representation easily, we first briefly overview it. In IEEE 754, two types of floating-point representation are defined, single-precision and double-precision, depending on the number of bits assigned for a representation. In this work, we only focus on the single-precision representation as this is only applied for the proposed one.Figure1 shows the IEEE 754 single-precision representation. It is composed of three parts: 1-bit sign, 8-bit exponent, and 23-bit mantissa. The sign bits represent if the value is positive (0) or negative (1). The exponent bits represent the exponent which is in the range between −127 and 127. The “fraction” bits contain the significant bits of the value. In normal mode, Figure 1 represents a real number (−1) (sign) ∗ 1. (FRACTION) (2) ∗ 2(EXPONENT(2)−127), where binary values represent unsigned positive integers.Figure 1
IEEE 754 single-precision floating-point number—bit representation.The arithmetic and relational operations between the numbers expressed in this way can be carried out as follows. In the case of addition and subtraction, the exponents of two operands are made equal. The mantissas of them are adjusted following the changed exponents, respectively. After that, the operation is performed with the adjusted mantissas. In the case of multiplication and division, operations are performed on exponents and mantissas of two operands, respectively. After processing, adjustment is performed on the resultant exponent and mantissa in order to match the expression rules. Please refer to [15] for details.


## 2.2. Fully Homomorphic Encryption (FHE)

FHE is a special cryptosystem that can process encrypted data without decrypting them. This is useful for data delegation or privacy-preserving data processing. Figure2 shows the difference between FHE and a conventional encryption scheme when addition of two encrypted numbers is performed. With the ciphertexts by FHE, addition of their hidden plaintext values is possible without decryption.Figure 2
Adding two plaintexts in ciphertexts: comparison between conventional encryption and homomorphic encryption.An FHE scheme is defined with the following algorithms:ParamGen (1λ, N, L) ⟶ param: this generates a parameter for key generation. It takes the security parameter λ, the number of slots in a ciphertext N, and the possible multiplicative depth of a fresh ciphertext without bootstrapping L.KeyGen (param) ⟶ sk, pk, evk: this is a key generation algorithm, which takes the parameter from the parameter generation algorithm and outputs sk, a secret key for decryption, pk, a public key for encryption, and evk, a set of the evaluation keys with which some computation over the ciphertexts can be done if the ciphertexts are generated with the matched pk.Enc (m⟶, pk) ⟶ C: an encryption algorithm which takes a vector of plaintext message m⟶ of dimension N and a public key and outputs a ciphertext that contains m⟶.Dec (C,sk) ⟶ m⟶ (or ⊥): it takes a ciphertext c and a secret key sk, and outputs a plaintext m⟶ if C is the result of Enc(m⟶, pk) and pk is matched to sk. Otherwise, it outputs ⊥.In addition to the above algorithms, FHE provides computational algorithms between ciphertexts. However, they provide different functions for each FHE scheme. Therefore, they will be described when each FHE scheme is introduced. We introduce two recent FHE schemes, which are used to implement the proposed (encrypted) floating-point representation.


### 2.2.1. HEAAN

HEAAN’s ciphertext can contain multiple plaintext bits in one slot, unlike the previous FHE methods [14, 16]. Let the corresponding bit length be the word size. HEAAN also supports various operations between the encrypted values of a word size in the ciphertext slots. Unfortunately, they are supported in an approximate fashion. That is, if an operation is performed between encrypted word-sized values, the bit-precision of the result is similar to that of an operand. In the case of multiplication, when the bit length of operands is n, the result’s bit length should be 2n−1 to represent the result correctly. However, in HEAAN, only the most significant n bits of the result are correct. At the expense of this bit accuracy, HEAAN supports very fast arithmetic operations on word-sized encrypted data. This fast computation speed allows HEAAN to be used in many fields such as machine learning and machine control [17, 18]. In addition, unlike TFHE, HEAAN has the advantage of providing a complete SIMD function. That is, there is an advantage that the value can be shifted between slots. The major disadvantage of HEAAN compared to TFHE is that it requires bootstrapping. That is, when performing multiplication operations more than a certain number of times consecutively, that is, when a multiplication circuit having a certain depth or more is performed, bootstrapping should be performed to do further multiplication while preserving the correct computation result. Otherwise, the ciphertext no longer has the correct plaintext.HEAAN_Mult (C0, C1, evk) ⟶ Cmult: this algorithm multiplies the encrypted values stored in each slot of the same position in two ciphers C0, C1 with each other and stores the result in the same slot position of the resultant ciphertext Cmult.HEAAN_Add/Sub (C0, C1, evk) ⟶ Cadd (Csub): this algorithm performs slotwise addition (subtraction) with two ciphertexts C0 and C1 and outputs Cadd (Csub) which has the result of the computation.HEAAN_Bootstrapping (C0, evk) ⟶ cnew: this algorithm takes a ciphertext C0 and returns a new ciphertext Cnew with the same plaintext. We can execute a multiplicative circuit of a certain number of depths with Cnew, where the depth is defined by the parameters.HEEAN_LeftShift (C0, k, evk) ⟶ Cshifted: this algorithm generates a new ciphertext Cshifted by moving the plaintexts in each slot of cipher C0 to the left by k slots. It is a circular shift. Thus, we can shift the values in C0 to the right by k slots by making the values shifted left by N-k slots, where N is the number of total slots.HEAAN supports the following algorithms in addition to the common FHE algorithms described above.


### 2.2.2. TFHE

TFHE [9, 19] was created in 2017 using the GSW [20] technique. Each slot in the TFHE ciphertext contains a 1-bit plaintext. It supports bitwise AND and bitwise XOR operations on the encrypted plaintext bit in each slot. Based on those operations, it is possible to implement any arbitrary efficient algorithm which can work with encrypted inputs. In addition to the basic algorithms mentioned above, TFHE supports the following algorithms:TFHE_AND (C0, C1, evk) ⟶ cand: a bitwise AND operation is performed on the values of the slot at the same position in the two ciphertexts c0 and c1, and the result is stored in the slot of the same position in the resultant cipher Cand.TFHE_XOR (C0, C1, evk) ⟶ Cxor: it executes the slotwise XOR operations on bit values of the same slot position in c0 and c1. The result is stored in the same slot position of the resultant ciphertext Cxor.One advantage of THE is that it supports very fast bootstrapping. However, it needs bootstrapping at the end of every operation. Thus, we suppose that the bootstrapping is contained in the above bitwise operations.


### 2.2.3. An Overview for the Ciphertext Structures and Operations

To help the readers understand both FHE methods, we discuss the format of the ciphertext used and more details on them. Let us talk about HEAAN first. Figure3 shows the structure of the HEAAN ciphertext and the operations supported on it. In HEAAN, as shown in the figure below, a limited number of real numbers can be stored in one ciphertext. Arithmetic operations can be performed between those in the same slot as shown in Figure 3(B). In addition to this, as shown in Figure 3(C), it is possible to move the embedded plaintexts between slots. Finally, if there are two ciphertexts where only 0 or 1 are encrypted in each slot, then logical AND/XOR operations between the encrypted values are possible in the same slot position of both ciphertexts. These logical operations can be implemented by arithmetic subtraction, addition, and multiplication using the equations described in Figure 3(D). Unfortunately, there is a disadvantage that a slot can only store a fixed-point real-number plaintext. Also, a certain operation can work only when the stored plaintext value is within a limited range. TFHE has similar ciphertext structure as HEAAN, but each slot can contain only 0 or 1 (1 bit value). Also, slot-shift operation is not supported.Figure 3
Ciphertext structure and operations in HEAAN.


## 2.2.1. HEAAN

HEAAN’s ciphertext can contain multiple plaintext bits in one slot, unlike the previous FHE methods [14, 16]. Let the corresponding bit length be the word size. HEAAN also supports various operations between the encrypted values of a word size in the ciphertext slots. Unfortunately, they are supported in an approximate fashion. That is, if an operation is performed between encrypted word-sized values, the bit-precision of the result is similar to that of an operand. In the case of multiplication, when the bit length of operands is n, the result’s bit length should be 2n−1 to represent the result correctly. However, in HEAAN, only the most significant n bits of the result are correct. At the expense of this bit accuracy, HEAAN supports very fast arithmetic operations on word-sized encrypted data. This fast computation speed allows HEAAN to be used in many fields such as machine learning and machine control [17, 18]. In addition, unlike TFHE, HEAAN has the advantage of providing a complete SIMD function. That is, there is an advantage that the value can be shifted between slots. The major disadvantage of HEAAN compared to TFHE is that it requires bootstrapping. That is, when performing multiplication operations more than a certain number of times consecutively, that is, when a multiplication circuit having a certain depth or more is performed, bootstrapping should be performed to do further multiplication while preserving the correct computation result. Otherwise, the ciphertext no longer has the correct plaintext.HEAAN_Mult (C0, C1, evk) ⟶ Cmult: this algorithm multiplies the encrypted values stored in each slot of the same position in two ciphers C0, C1 with each other and stores the result in the same slot position of the resultant ciphertext Cmult.HEAAN_Add/Sub (C0, C1, evk) ⟶ Cadd (Csub): this algorithm performs slotwise addition (subtraction) with two ciphertexts C0 and C1 and outputs Cadd (Csub) which has the result of the computation.HEAAN_Bootstrapping (C0, evk) ⟶ cnew: this algorithm takes a ciphertext C0 and returns a new ciphertext Cnew with the same plaintext. We can execute a multiplicative circuit of a certain number of depths with Cnew, where the depth is defined by the parameters.HEEAN_LeftShift (C0, k, evk) ⟶ Cshifted: this algorithm generates a new ciphertext Cshifted by moving the plaintexts in each slot of cipher C0 to the left by k slots. It is a circular shift. Thus, we can shift the values in C0 to the right by k slots by making the values shifted left by N-k slots, where N is the number of total slots.HEAAN supports the following algorithms in addition to the common FHE algorithms described above.


## 2.2.2. TFHE

TFHE [9, 19] was created in 2017 using the GSW [20] technique. Each slot in the TFHE ciphertext contains a 1-bit plaintext. It supports bitwise AND and bitwise XOR operations on the encrypted plaintext bit in each slot. Based on those operations, it is possible to implement any arbitrary efficient algorithm which can work with encrypted inputs. In addition to the basic algorithms mentioned above, TFHE supports the following algorithms:TFHE_AND (C0, C1, evk) ⟶ cand: a bitwise AND operation is performed on the values of the slot at the same position in the two ciphertexts c0 and c1, and the result is stored in the slot of the same position in the resultant cipher Cand.TFHE_XOR (C0, C1, evk) ⟶ Cxor: it executes the slotwise XOR operations on bit values of the same slot position in c0 and c1. The result is stored in the same slot position of the resultant ciphertext Cxor.One advantage of THE is that it supports very fast bootstrapping. However, it needs bootstrapping at the end of every operation. Thus, we suppose that the bootstrapping is contained in the above bitwise operations.


## 2.2.3. An Overview for the Ciphertext Structures and Operations

To help the readers understand both FHE methods, we discuss the format of the ciphertext used and more details on them. Let us talk about HEAAN first. Figure3 shows the structure of the HEAAN ciphertext and the operations supported on it. In HEAAN, as shown in the figure below, a limited number of real numbers can be stored in one ciphertext. Arithmetic operations can be performed between those in the same slot as shown in Figure 3(B). In addition to this, as shown in Figure 3(C), it is possible to move the embedded plaintexts between slots. Finally, if there are two ciphertexts where only 0 or 1 are encrypted in each slot, then logical AND/XOR operations between the encrypted values are possible in the same slot position of both ciphertexts. These logical operations can be implemented by arithmetic subtraction, addition, and multiplication using the equations described in Figure 3(D). Unfortunately, there is a disadvantage that a slot can only store a fixed-point real-number plaintext. Also, a certain operation can work only when the stored plaintext value is within a limited range. TFHE has similar ciphertext structure as HEAAN, but each slot can contain only 0 or 1 (1 bit value). Also, slot-shift operation is not supported.Figure 3
Ciphertext structure and operations in HEAAN.


## 3. Related Work and System Model

### 3.1. Related Work

There have been some attempts to represent encrypted floating-point real numbers before this study. Arita and Nakasato [21] proposed the FHE4FX method that can perform addition and multiplication between encrypted floating-point numbers without decryption based on the FV FHE method [22]. It generates an encrypted floating-point representation by encrypting each sign, exponent, and mantissa part of a real number in separate ciphertexts. For the multiplication and addition operations between encrypted values, it first determines the type of FHE operations to be performed on the sign, exponent, and mantissa parts based on the comparison result of values of each part of the ciphertext. Unfortunately, there is some limitation in this approach that it is necessary to use the decryption key for computation and it does not support operations other than addition and multiplication.Zhu et al. [23] proposed a method to represent floating-point numbers as Double List Tree format and provide the encryption function for them with Paillier cryptosystem [24]. Their work utilizes hashtag (#) to represent the location of the decimal points of encrypted numbers. However, in this method, the digits of the real number can be inferred through the position of the hashtag used for performing the operation of each digit. Furthermore, their arithmetic operations use the size comparison operation. However, they did not show how to implement the size comparison operation.In the method of Jaschke and Armknecht [25], when an operation is performed on encrypted rational numbers, they are multiplied by an exponent of 2 to move the decimal place values to an integer position. After this, rounding is performed to remove the decimal point value, and the main operation is performed with only the integer parts of two operands. After that, the desired result is obtained by adjusting the digits. This process has the disadvantage that the precision of the operation is reduced because the calculation is performed after some bit values of input rational numbers are removed.There are other methods such as those of Seiko and Nakasato [26] and Dowlin et al. [27]. However, they require a very large computation for floating-point operations. Also, as we mentioned in the previous section, HEAAN [14, 16] has some limitation on representing encrypted floating-point numbers. Also, there has been no approach to represent encrypted floating-point numbers on top of TFHE [9, 19].In conclusion, there is no way to represent encrypted floating-point real numbers with similar level of accuracy and efficiency to the floating-point representation used in common computing environment, even if there are so many methods using existing FHE methods. In this paper, we aim to solve this problem and make it possible to represent encrypted floating-point numbers and to perform computation with them efficiently. In other words, this research is the first study to propose and implement a size comparison operation and arithmetic operations over encrypted floating-point real-number representation efficiently using FHE.


### 3.2. System Model

The system model assumed in this study is as follows. The client translates the plaintext representation of the floating-point real numbers into the encrypted one using the proposed method and delivers it to the central server. The central server then performs an algorithm that can be performed on the encrypted input and returns the results back to the client. The client can decode the result to get the result. In this model, the client and server shares their public keys with each other.The security model we assume is the general Honest-But-Curious (HBC) model. The central server performs predefined protocols, but it tries to obtain useful information of the clients while running the protocol. The clients are those who own their data, including both input and result of the protocol, and want it to be protected from the central server. Please check Figure4 above for the detailed description of the system and security model.Figure 4
System and security model.


## 3.1. Related Work

There have been some attempts to represent encrypted floating-point real numbers before this study. Arita and Nakasato [21] proposed the FHE4FX method that can perform addition and multiplication between encrypted floating-point numbers without decryption based on the FV FHE method [22]. It generates an encrypted floating-point representation by encrypting each sign, exponent, and mantissa part of a real number in separate ciphertexts. For the multiplication and addition operations between encrypted values, it first determines the type of FHE operations to be performed on the sign, exponent, and mantissa parts based on the comparison result of values of each part of the ciphertext. Unfortunately, there is some limitation in this approach that it is necessary to use the decryption key for computation and it does not support operations other than addition and multiplication.Zhu et al. [23] proposed a method to represent floating-point numbers as Double List Tree format and provide the encryption function for them with Paillier cryptosystem [24]. Their work utilizes hashtag (#) to represent the location of the decimal points of encrypted numbers. However, in this method, the digits of the real number can be inferred through the position of the hashtag used for performing the operation of each digit. Furthermore, their arithmetic operations use the size comparison operation. However, they did not show how to implement the size comparison operation.In the method of Jaschke and Armknecht [25], when an operation is performed on encrypted rational numbers, they are multiplied by an exponent of 2 to move the decimal place values to an integer position. After this, rounding is performed to remove the decimal point value, and the main operation is performed with only the integer parts of two operands. After that, the desired result is obtained by adjusting the digits. This process has the disadvantage that the precision of the operation is reduced because the calculation is performed after some bit values of input rational numbers are removed.There are other methods such as those of Seiko and Nakasato [26] and Dowlin et al. [27]. However, they require a very large computation for floating-point operations. Also, as we mentioned in the previous section, HEAAN [14, 16] has some limitation on representing encrypted floating-point numbers. Also, there has been no approach to represent encrypted floating-point numbers on top of TFHE [9, 19].In conclusion, there is no way to represent encrypted floating-point real numbers with similar level of accuracy and efficiency to the floating-point representation used in common computing environment, even if there are so many methods using existing FHE methods. In this paper, we aim to solve this problem and make it possible to represent encrypted floating-point numbers and to perform computation with them efficiently. In other words, this research is the first study to propose and implement a size comparison operation and arithmetic operations over encrypted floating-point real-number representation efficiently using FHE.


## 3.2. System Model

The system model assumed in this study is as follows. The client translates the plaintext representation of the floating-point real numbers into the encrypted one using the proposed method and delivers it to the central server. The central server then performs an algorithm that can be performed on the encrypted input and returns the results back to the client. The client can decode the result to get the result. In this model, the client and server shares their public keys with each other.The security model we assume is the general Honest-But-Curious (HBC) model. The central server performs predefined protocols, but it tries to obtain useful information of the clients while running the protocol. The clients are those who own their data, including both input and result of the protocol, and want it to be protected from the central server. Please check Figure4 above for the detailed description of the system and security model.Figure 4
System and security model.


## 4. Proposed Approach

In this section, we propose a new scheme to represent encrypted floating-point numbers using two methods, HEAAN and TFHE, respectively. Our proposal includes the methods to support the arithmetic and the relation operations over the encrypted numbers represented by the proposed methods. Before explaining each method, we first introduce the tools used to implement the proposed methods and then proceed to the description of the proposed one. We omit showing the evaluation key (evk) when we present the proposed methods because any calculation involving the proposed encrypted representation needs evk.


### 4.1. Building Blocks

#### 4.1.1. Kogge–Stone Adder (KSA)

The authors in [28] implemented the Kogge–Stone Adder [29], which performs addition on two input numbers, using FHE to have it work on encrypted input numbers. In [28], it is assumed that each slot of a ciphertext stores only one bit value, and all the slots are used to represent one number. Therefore, we can use [28] to implement the Kogge–Stone Adder over encrypted inputs using either TFHE or HEAAN, if we put only one-bit plaintext in each slot of ciphertext. Using this, it is possible to implement the adder using a circuit with log n multiplication depth when inputs are of n bits. Figure 5(A) shows the encrypted KSA (E-KSA) in [12]. Two ciphertexts are output of the adder where the first has the sum where all n slots are filled with outputs, whereas only one slot is used in the other ciphertext to represent the carry of the addition.Figure 5
Building blocks: encrypted Kogge–Stone Adder and comparator circuit.


#### 4.1.2. Comparator (COMP) Module

It compares the size of two ciphertexts and returns a ciphertext containing the result. For example, if there are two ciphers C1 and C2, and each represents a binary number using the bit values of all of its slots, this module returns a ciphertext of 1 when C1 > C2 and returns 0 otherwise (if the resultant ciphertext has many slots, it outputs the ciphertext containing 1 in every slot; this also holds in the case where the resultant ciphertext contains 0). It can be implemented as shown in Figure 5(B) using E-KSA module. The reason why this works is illustrated in Figure 5(C). For example, if C1 contains an encryption of 1100(2) (4 bits) and C2 contains 1010(2), we can see that a carry is generated as a result of adding the 1’s complements of C1 and C2. Based on this, we can confirm that C1 > C2.When using such a COMP circuit, if two ciphertexts C1 and C2 are input, we can make a circuit that outputs a ciphertext CB containing the larger plaintext and another ciphertext CS which contains the smaller plaintext among the plaintexts encrypted in C1 and C2, respectively. If we assume the result of executing the COMP module with input C1 and C2 as COMP (C1, C2), CB can be derived by calculating C1 ∗ COMP(C1, C2) + C2 ∗ (1c—COMP (C1, C2)). Similarly, CS ⟵ C1 ∗ (1c—COMP (C1, C2)) + C2 ∗ COMP (C1, C2). 1c means an encoding of 1 where calculation is possible with other ciphertexts. If the ciphertext has many slots, 1c is an encoding of 1 in every slot. One caveat is that you cannot know whether CB and CS come from either C1 or C2, respectively, because the above formulas’ calculation results depend on the results of COMP() circuit whose output is encrypted; thus, it cannot be known without decryption. We can define the above two circuits as MinMax() as follows:(1)Cb,Cs⟵MinMaxC1,C2.


### 4.2. HEAAN-Based Method

The HEAAN-based method uses three ciphertexts to represent a single real number. The first ciphertext represents the sign of the real number, the second ciphertext stores the exponent value, and the last ciphertext stores the mantissa. The sign and exponent are expressed as bit values like IEEE 754 standard. However, when expressing a mantissa, the corresponding number is not stored as a multibit value. Instead, it is encrypted to a HEAAN ciphertext directly. One significant difference of this approach from IEEE 754 is that the value of the mantissa is assumed to be in the range [0, 1). This is because the HEAAN operation works better when the hidden plaintext in the ciphertext in [0, 1) than [1, 2).Figure6 shows the procedure on how a single floating-point number is encrypted using three ciphertexts. cresult [] is an array containing ciphertexts. It is assumed that the value assigned to the ciphertext cresult [] is encrypted and stored in the corresponding ciphertext. Figure 7 shows an example of converting a real number into the proposed encrypted representation.Figure 6
Procedure of generating a set of ciphertexts containing a single floating-point number.Figure 7
An example of representing 30.3 with the HEAAN-based proposed scheme. The exponent is converted to binary representation. Then, it is encrypted to C[expo]. Each encrypted bit is stored in each slot. On the other hand, the fraction is stored as it is in a HEAAN ciphertext.


#### 4.2.1. Addition/Subtraction

The HEAAN-based addition method is implemented as shown in Figure8. In this method, two operands are classified to a smaller number and the other bigger number first. Then, the exponent value of the smaller number is increased to be matched to that of the bigger number. The increase of the value of the smaller number, which results from the increasing the exponent, is cancelled by dividing the mantissa part. After that, two mantissa parts are added to complete the addition.Figure 8
Overview of addition operation in the HEAAN-based method.The details of addition operation is as follows. We suppose two operands to be added as C1 = (C1[SIGN], C1[EXPO], C1[FRAC]), C2 = (C2[SIGN], C2[EXPO], C2[FRAC]). The function ReArrange (), which returns a larger value in cB and a small value in cS among the input C1 and C2, can be implemented as shown in Figure 9. C1 and C2 are compared based on their exponent values.Figure 9
Rearrange() function.We suppose the result of Rearrange (C1, C2, EXPO) is CS and CB. We run the following addition code with CS and CB in Figure 10. The output of the code is Cout. We discuss how the following code works. Because CS[EXPO] < CB[EXPO] and CS[FRAC], CB[EXPO] in [0, 1), the sign of the addition result is CB[SIGN]. Also, to perform calculation, the code increases CS[EXPO] to make it the same as CB[EXPO]. To keep the original value of CS after increasing CS[EXPO], the code decreases CS[FRAC] accordingly. After that, it returns the result of CB[FRAC] + CS[FRAC] when both CB and CS have the same sign or CB[FRAC] − CS[FRAC] if the signs are different. To keep the result’s fraction is in [0, 1), the exponent is increased by 1 and the fraction is divided by 2.Figure 10
Addition method in HEAAN-based approach.Because the maximum binary string that CB[EXPO] and CS[EXPO] can have is 11111111(2), Ceqcc is an encryption of 1 only once in the loop. In this case, CB[FRAC] + CS[FRAC] ∗ (1 − 2 ∗ Csign) is given to Cout[FRAC], where Csign is the result of checking if CB[SIGN] and CS[SIGN] are the same: if so, it has the encryption of 0, and 1 otherwise. In Step 3, EQCC (CB[EXPO], CS[EXPO]) executes HEAAN_XNOR(CB[EXPO], CS[EXPO]) from inside to perform XNOR operation between the bit values in the same slot of CB[EXPO] and CS[EXPO], respectively. After that, we multiply all the bit values in each slot of XNOR result to create Ccomp. Ccomp becomes 1 if CB[EXPO] and CS[EXPO] have exactly the same bit value in all of their slots; otherwise, it becomes 0.To perform subtraction, the sign of the number to be subtracted is inverted using HEAAN_XNOR, and then the addition operation is performed instead.


#### 4.2.2. Multiplication

Multiplication is easier to implement than addition. First, the sign of the result value is equal to the value obtained by XORing the sign of two input numbers, and the result of the exponent part can be obtained by adding the exponents of the two inputs. E-KSA can be used to calculate it. Also, the mantissa can be obtained by multiplying the mantissas of two input numbers. In this case, the result of multiplying mantissa is still in [0, 1). Thus, we have nothing to do further. Figure11 shows the process of multiplying two encrypted floating-point real numbers C1 and C2 in the proposed method.Figure 11
Multiplication with HEAAN-based representation.


#### 4.2.3. Comparison

In the HEAAN-based approach, COMPHEAAN() function is used as a tool to perform the size comparison operation of the encrypted floating-point values. COMPHEAAN () takes two HEAAN ciphertexts and the computation key evk of the ciphertext and performs the following operation [30]:(2)COMPHEAANC1HEAAN,C2HEAAN,evk⟶1ifC1HEAAN>C2HEAANelse 0.Using the above circuit, we can compare the size of two encrypted floating-point numbers C1 = (C1[SIGN], C1[EXPO], C1[FRAC]) and C2 = (C2[SIGN], C2[EXPO], C2[FRAC]) using the code written in Figure 12. If the code outputs an encryption of 1, it says C1’s absolute value is greater than C2’s and it returns an encryption of 0 otherwise. Step 2 in Figure 12 is described in Figure 13 in detail.Figure 12
Absolute value comparison circuit with HEAAN-based representation.Figure 13
Details in Step 2 of the absolute value comparison circuit.A circuit for determining if two encrypted representations are equal can be implemented similar to addition/subtraction circuit: it can be easily obtained by calculating whether the FRAC part and the SIGN part of both floating-point numbers to be compared are the same using COMPHEAAN() after equalizing their EXPO parts.


#### 4.2.4. Division

The division operation is similar to the multiplication operation except that the exponent part of the divisor is subtracted from the exponent of the dividend, and the inverse of the mantissa of the divisor is calculated using the inverse function and then it is multiplied by the mantissa of the dividend. In this case, if we do nothing further, the mantissa of the resultant value may be greater than 1. To deal with this, before performing the multiplication operations in the fraction part, the mantissa of the dividend is corrected so that it is smaller than the mantissa of the divisor. However, it is greater if the mantissa of the dividend is doubled. The process can be described as follows.Step 1 in Figure14 can be specified in detail as follows in Figure 15.Figure 14
Division operation in HEAAN-based representation.Figure 15
Details of Step 1 of the division operation.


### 4.3. TFHE-Based Method

The TFHE-based expression follows the standard IEEE 754 exactly. For example, to represent 30.3 with the TFHE-based representation, we first translate this as 1.1110010011001100110 × 23(2). Then we add 127 to the exponent to represent the exponent bits. The fraction part stores all the fraction bits except the first “1” at the left of the decimal point. In this approach, sign, exponents, and mantissa are encrypted by separate ciphertexts. The number of ciphertexts in C[SIGN] is 1, C[EXPO] is 8, and C[FRAC] is 23 when the encrypted floating-point number is represented as C = (C [SIGN], C [EXPO], C[FRAC]). Also, for ease of expression, TFHE_XOR () operation is written as ⊕, and TFHE_AND () operation is indicated by. Figure 16 explains the procedure of making a TFHE-based encrypted floating-point number representation with an example of 30.3.Figure 16
Creating a ciphertext of a floating-point number with TFHE.To explain the methods clearly, we are going to use the following notations. An array of ciphertexts C[] = c0||c1||…||cn−1 can be described as C[0] = c0, C[1] = c1,… , C[n−1] = cn−1, where ci (i ∈ [0, n−1]) refers to an encryption of a single bit value. If we describe C[] = (cn−1 cn−2 … c2c1c0) (2), as a binary integer representation, then C[0] = c0, C[1] = c1,… , C[n−1] = cn−1, too. If there are two array of ciphertexs A[] and C[], where both are represented as binary integers and they are added using E-KSA circuit, then the result CR[] is 2n−1 (cn−1 + an−1) + 2n−2 (cn−2 + an−2)+ … + 21(c1 + a1) + c0+a0. Also, you have to keep in mind that c ⊕ (c0||c1||…||cn−1) = (c ⊕ c0||c ⊕ c1…||c ⊕ cn-1) and (ca0||ca1||…||can) ⊕ (cb0||cb1||…||cbn) = (ca0 ⊕ cb0||ca1 ⊕ cb1||…||can ⊕ cbn). The concatenation of two ciphertext arrays A[] and B[] can be described as A[]||B[], and it generates a new array of ciphertexts. Finally, C[] = C[] >> 1 means C[i + 1] = C[i] for all i = 0, …, len(C[])−2 and C[0] = 0.


#### 4.3.1. Addition/Subtraction

The addition algorithm is constructed in a manner as similar as the HEAAN-based method. However, in this TFHE based method, arrays of ciphertexts are used to represent the components of the representation and each ciphertext has one bit value, which complicates the process as shown in Figure17. We use E-KSA as building block. The input of E-KSA, however, is arrays of ciphertexts instead of ciphertexts of multiple slots. Our implementation of E-KSA considered that. Figure 18 shows an implementation of Equality Comparison Circuit (TFHE_EQCC()) for TFHE representation, which is also a building block for addition operation. We also introduce the negate function (Negate()) which flips the bits in the input set of ciphertexts in Figure 19.Figure 17
Overview of addition operation in TFHE-based method.Figure 18
Equality comparison circuit for TFHE-based representation (TFHE_EQCC).Figure 19
Negate() function used in TFHE-based representation.Figure20 shows the procedure of addition operation with TFHE-based representation. For subtraction, the addition operation can be used after modifying the sign of the value to be subtracted.Figure 20
The addition algorithm for the TFHE-based representation. It takes CB, CS and outputs Cout.


#### 4.3.2. Multiplication

The multiplication operation proceeds as follows. First, a basic operation is performed in which an XOR operation is performed on sign portions and the addition is performed on exponent portions. Then, the result of the multiplication operation of the fraction parts is applied. When adding the exponent parts, 127 is subtracted from the addition result to get the correct result. This is because the exponent part is basically expressed by adding 127 so that a negative number can be expressed with unsigned bit-strings. The overall multiplication process is shown in Figure21 below.Figure 21
Multiplication in TFHE-based representation.Among the three operations in Figure21, (1) and (2) are easy to implement, so we focus on (3). To perform (3), the numbers actually represented by C1[FRAC] and C2[FRAC] must be restored. The bits in C1[FRAC] and C2[FRAC] mean the values to the right of the decimal point in the two numbers’ fraction parts, and the leading “1” to the left of the decimal point is omitted as specified by the standard. Therefore, the multiplication calculation should be performed after recovering the “1”. Therefore, the multiplication is performed by attaching an encoding of “1” to the most significant digit, which is just left to the decimal point. In this case, the multiplication result cannot exceed 4, so the result is a 46-bit value with two bits to the left of the decimal point and the remaining 44 bits to the right.After calculating Cm[], the final step is to check whether the value in the ciphertext Cm[0], which represents the most significant bit of the multiplication result and 1 bit left away from the decimal point, is 1. If Cm[0] is 1, the fraction part of the multiplication result is Cm [1] ∼ Cm [22], and the exponent value should be incremented by one. If Cm[0] is 0, that means Cm [1] is 1, so the exponent does not increase and the fraction part of the result is Cm [2]∼Cm [24]. The method that reflects this is shown in Figure 22 below.Figure 22
Details of calculating the exponent and fraction in multiplication in TFHE-based representation.


#### 4.3.3. Division

The division operation is similar to the multiplication operation. That is, to calculate the exponent part, the exponent value of the denominator is subtracted from the numerator, and division operation is performed between the fraction parts of them. Since the exponent should be added to 127 (=2((length of exponent bits)−1) − 1) to represent the negative exponent, 127 should be added to the resultant exponent after the subtraction. An overview of division operation to calculate the resultant exponent and fraction is shown in Figures 23 and 24, respectively.Figure 23
Exponent calculation module in the division operation of TFHE-based method.Figure 24
Fraction calculation module in the division operation of TFHE-based method.After calculating the exponent and the fraction, we need to correct them because the range of the result of calculating the fraction part is (0.5, 2). Thus, if the fraction part’s result is less than 1, 1 must be subtracted from the exponent and the bit position of the resultant fraction must be shifted to left by 1 bit. The sign is determined by XORing the signs of the numerator and denominator. Figure25 shows the operations to be performed for division. Cout[EXPO] and Cout[FRAC] are the result values, C1 = (C1[SIGN], C1[EXPO], C1[FRAC]) is the numerator, and C2 = (C2[SIGN], C2[EXPO], C2[FRAC]) is the denominator.Figure 25
An overview of the division operation in TFHE-based representation.As with multiplication, the most important and difficult process is (3). We use the nonrestoring division [31] method, which uses the divide-and-conquer to implement (3). This is known to be more efficient than the well-known methods such as those of Newton-Rapth [32] and Burnikel and Ziegler [33]. Figure 26 shows the result of implementing the nonrestoring division algorithm [15] to make it work on ciphertext input. This algorithm assumes that the highest-order bits are stored in index 0 of each input array, and the lower-order bits are stored as the index becomes larger. The bit length of both dividend and divisor is 24 bits each.Figure 26
Restoring division algorithm (R_DIV()).We deal with how to calculate (3) specifically. Since the mantissa is represented by omitting 1 immediately to the left of the decimal point which is the largest digit, in order to perform division correctly, the omitted bits should be restored before starting the division operation. To do this, the size of the ciphertext arrays indicating both the dividend and divisor is increased by one each, and we place an encoding of 1 to the highest position (i.e., the zeroth index). Then, division is performed through R_DIV (). The result is a 25-bit quotient. In this case, if the bit value of the highest position is 1, the next 23 bits are stored in the resultant fraction. Otherwise, the value of the second digit is 1 because the division quotient range is (0.5, 2). Therefore, the subsequent 23 bits are stored in the fraction part. If so, the value of exponent must be decreased by one. Figure27 shows an example of the case where the left part of the decimal point becomes zero in the fraction part of the division result. The steps to be performed is shown in the figure. The details of (3) is shown in Figure 28.Figure 27
An example of normalizing the fraction part in the division result.Figure 28
Procedure for calculating Cout[FRAC] with updating Cout[EXPO] in division.


#### 4.3.4. Comparison and Equality Check

The comparison operation can be done using the COMP() circuit described in Figure5(B), using the bitwise concatenation results of all of the sign, exponent, and fraction ciphertext arrays in both values to be compared as inputs. IEEE 754 standard exactly uses the same approach to compare the floating-point numbers. The process of comparing two numbers can be expressed as shown in Figure 29.Figure 29
Comparison operation on TFHE-based representation.The equality can be easily checked as they are represented using bits. Two values are treated the same only if they have the same bits.


### 4.4. Discussion on the Differences between the Implementation of Two Methods

The differences between the implementation of the two methods can be summarized as follows. First, in the operation with exponent values, the HEAAN-based method can reduce the number of operations by using the SIMD operation, but the TFHE-based method must perform operations in bit units, which requires large number of TFHE operations.Second, the HEAAN-based implementation can implement the operations for dealing with the mantissa part with a small number of HEAAN operations using arithmetic operation provided by HEAAN, but in TFHE-based method, the operation must be processed for each bit of mantissa, which also requires a large number of TFHE operations.In the above two cases, the HEAAN-based method seems to be dominant, but HEAAN requires bootstrapping when it needs complex arithmetic with their floating point representations: especially when it needs calculation of more than a predetermined multiplication depth. In this case, HEAAN needs a lot of computation resources. Thus, it will be much slower than the TFHE-based method.


## 4.1. Building Blocks

### 4.1.1. Kogge–Stone Adder (KSA)

The authors in [28] implemented the Kogge–Stone Adder [29], which performs addition on two input numbers, using FHE to have it work on encrypted input numbers. In [28], it is assumed that each slot of a ciphertext stores only one bit value, and all the slots are used to represent one number. Therefore, we can use [28] to implement the Kogge–Stone Adder over encrypted inputs using either TFHE or HEAAN, if we put only one-bit plaintext in each slot of ciphertext. Using this, it is possible to implement the adder using a circuit with log n multiplication depth when inputs are of n bits. Figure 5(A) shows the encrypted KSA (E-KSA) in [12]. Two ciphertexts are output of the adder where the first has the sum where all n slots are filled with outputs, whereas only one slot is used in the other ciphertext to represent the carry of the addition.Figure 5
Building blocks: encrypted Kogge–Stone Adder and comparator circuit.


### 4.1.2. Comparator (COMP) Module

It compares the size of two ciphertexts and returns a ciphertext containing the result. For example, if there are two ciphers C1 and C2, and each represents a binary number using the bit values of all of its slots, this module returns a ciphertext of 1 when C1 > C2 and returns 0 otherwise (if the resultant ciphertext has many slots, it outputs the ciphertext containing 1 in every slot; this also holds in the case where the resultant ciphertext contains 0). It can be implemented as shown in Figure 5(B) using E-KSA module. The reason why this works is illustrated in Figure 5(C). For example, if C1 contains an encryption of 1100(2) (4 bits) and C2 contains 1010(2), we can see that a carry is generated as a result of adding the 1’s complements of C1 and C2. Based on this, we can confirm that C1 > C2.When using such a COMP circuit, if two ciphertexts C1 and C2 are input, we can make a circuit that outputs a ciphertext CB containing the larger plaintext and another ciphertext CS which contains the smaller plaintext among the plaintexts encrypted in C1 and C2, respectively. If we assume the result of executing the COMP module with input C1 and C2 as COMP (C1, C2), CB can be derived by calculating C1 ∗ COMP(C1, C2) + C2 ∗ (1c—COMP (C1, C2)). Similarly, CS ⟵ C1 ∗ (1c—COMP (C1, C2)) + C2 ∗ COMP (C1, C2). 1c means an encoding of 1 where calculation is possible with other ciphertexts. If the ciphertext has many slots, 1c is an encoding of 1 in every slot. One caveat is that you cannot know whether CB and CS come from either C1 or C2, respectively, because the above formulas’ calculation results depend on the results of COMP() circuit whose output is encrypted; thus, it cannot be known without decryption. We can define the above two circuits as MinMax() as follows:(1)Cb,Cs⟵MinMaxC1,C2.


## 4.1.1. Kogge–Stone Adder (KSA)

The authors in [28] implemented the Kogge–Stone Adder [29], which performs addition on two input numbers, using FHE to have it work on encrypted input numbers. In [28], it is assumed that each slot of a ciphertext stores only one bit value, and all the slots are used to represent one number. Therefore, we can use [28] to implement the Kogge–Stone Adder over encrypted inputs using either TFHE or HEAAN, if we put only one-bit plaintext in each slot of ciphertext. Using this, it is possible to implement the adder using a circuit with log n multiplication depth when inputs are of n bits. Figure 5(A) shows the encrypted KSA (E-KSA) in [12]. Two ciphertexts are output of the adder where the first has the sum where all n slots are filled with outputs, whereas only one slot is used in the other ciphertext to represent the carry of the addition.Figure 5
Building blocks: encrypted Kogge–Stone Adder and comparator circuit.


## 4.1.2. Comparator (COMP) Module

It compares the size of two ciphertexts and returns a ciphertext containing the result. For example, if there are two ciphers C1 and C2, and each represents a binary number using the bit values of all of its slots, this module returns a ciphertext of 1 when C1 > C2 and returns 0 otherwise (if the resultant ciphertext has many slots, it outputs the ciphertext containing 1 in every slot; this also holds in the case where the resultant ciphertext contains 0). It can be implemented as shown in Figure 5(B) using E-KSA module. The reason why this works is illustrated in Figure 5(C). For example, if C1 contains an encryption of 1100(2) (4 bits) and C2 contains 1010(2), we can see that a carry is generated as a result of adding the 1’s complements of C1 and C2. Based on this, we can confirm that C1 > C2.When using such a COMP circuit, if two ciphertexts C1 and C2 are input, we can make a circuit that outputs a ciphertext CB containing the larger plaintext and another ciphertext CS which contains the smaller plaintext among the plaintexts encrypted in C1 and C2, respectively. If we assume the result of executing the COMP module with input C1 and C2 as COMP (C1, C2), CB can be derived by calculating C1 ∗ COMP(C1, C2) + C2 ∗ (1c—COMP (C1, C2)). Similarly, CS ⟵ C1 ∗ (1c—COMP (C1, C2)) + C2 ∗ COMP (C1, C2). 1c means an encoding of 1 where calculation is possible with other ciphertexts. If the ciphertext has many slots, 1c is an encoding of 1 in every slot. One caveat is that you cannot know whether CB and CS come from either C1 or C2, respectively, because the above formulas’ calculation results depend on the results of COMP() circuit whose output is encrypted; thus, it cannot be known without decryption. We can define the above two circuits as MinMax() as follows:(1)Cb,Cs⟵MinMaxC1,C2.


## 4.2. HEAAN-Based Method

The HEAAN-based method uses three ciphertexts to represent a single real number. The first ciphertext represents the sign of the real number, the second ciphertext stores the exponent value, and the last ciphertext stores the mantissa. The sign and exponent are expressed as bit values like IEEE 754 standard. However, when expressing a mantissa, the corresponding number is not stored as a multibit value. Instead, it is encrypted to a HEAAN ciphertext directly. One significant difference of this approach from IEEE 754 is that the value of the mantissa is assumed to be in the range [0, 1). This is because the HEAAN operation works better when the hidden plaintext in the ciphertext in [0, 1) than [1, 2).Figure6 shows the procedure on how a single floating-point number is encrypted using three ciphertexts. cresult [] is an array containing ciphertexts. It is assumed that the value assigned to the ciphertext cresult [] is encrypted and stored in the corresponding ciphertext. Figure 7 shows an example of converting a real number into the proposed encrypted representation.Figure 6
Procedure of generating a set of ciphertexts containing a single floating-point number.Figure 7
An example of representing 30.3 with the HEAAN-based proposed scheme. The exponent is converted to binary representation. Then, it is encrypted to C[expo]. Each encrypted bit is stored in each slot. On the other hand, the fraction is stored as it is in a HEAAN ciphertext.


### 4.2.1. Addition/Subtraction

The HEAAN-based addition method is implemented as shown in Figure8. In this method, two operands are classified to a smaller number and the other bigger number first. Then, the exponent value of the smaller number is increased to be matched to that of the bigger number. The increase of the value of the smaller number, which results from the increasing the exponent, is cancelled by dividing the mantissa part. After that, two mantissa parts are added to complete the addition.Figure 8
Overview of addition operation in the HEAAN-based method.The details of addition operation is as follows. We suppose two operands to be added as C1 = (C1[SIGN], C1[EXPO], C1[FRAC]), C2 = (C2[SIGN], C2[EXPO], C2[FRAC]). The function ReArrange (), which returns a larger value in cB and a small value in cS among the input C1 and C2, can be implemented as shown in Figure 9. C1 and C2 are compared based on their exponent values.Figure 9
Rearrange() function.We suppose the result of Rearrange (C1, C2, EXPO) is CS and CB. We run the following addition code with CS and CB in Figure 10. The output of the code is Cout. We discuss how the following code works. Because CS[EXPO] < CB[EXPO] and CS[FRAC], CB[EXPO] in [0, 1), the sign of the addition result is CB[SIGN]. Also, to perform calculation, the code increases CS[EXPO] to make it the same as CB[EXPO]. To keep the original value of CS after increasing CS[EXPO], the code decreases CS[FRAC] accordingly. After that, it returns the result of CB[FRAC] + CS[FRAC] when both CB and CS have the same sign or CB[FRAC] − CS[FRAC] if the signs are different. To keep the result’s fraction is in [0, 1), the exponent is increased by 1 and the fraction is divided by 2.Figure 10
Addition method in HEAAN-based approach.Because the maximum binary string that CB[EXPO] and CS[EXPO] can have is 11111111(2), Ceqcc is an encryption of 1 only once in the loop. In this case, CB[FRAC] + CS[FRAC] ∗ (1 − 2 ∗ Csign) is given to Cout[FRAC], where Csign is the result of checking if CB[SIGN] and CS[SIGN] are the same: if so, it has the encryption of 0, and 1 otherwise. In Step 3, EQCC (CB[EXPO], CS[EXPO]) executes HEAAN_XNOR(CB[EXPO], CS[EXPO]) from inside to perform XNOR operation between the bit values in the same slot of CB[EXPO] and CS[EXPO], respectively. After that, we multiply all the bit values in each slot of XNOR result to create Ccomp. Ccomp becomes 1 if CB[EXPO] and CS[EXPO] have exactly the same bit value in all of their slots; otherwise, it becomes 0.To perform subtraction, the sign of the number to be subtracted is inverted using HEAAN_XNOR, and then the addition operation is performed instead.


### 4.2.2. Multiplication

Multiplication is easier to implement than addition. First, the sign of the result value is equal to the value obtained by XORing the sign of two input numbers, and the result of the exponent part can be obtained by adding the exponents of the two inputs. E-KSA can be used to calculate it. Also, the mantissa can be obtained by multiplying the mantissas of two input numbers. In this case, the result of multiplying mantissa is still in [0, 1). Thus, we have nothing to do further. Figure11 shows the process of multiplying two encrypted floating-point real numbers C1 and C2 in the proposed method.Figure 11
Multiplication with HEAAN-based representation.


### 4.2.3. Comparison

In the HEAAN-based approach, COMPHEAAN() function is used as a tool to perform the size comparison operation of the encrypted floating-point values. COMPHEAAN () takes two HEAAN ciphertexts and the computation key evk of the ciphertext and performs the following operation [30]:(2)COMPHEAANC1HEAAN,C2HEAAN,evk⟶1ifC1HEAAN>C2HEAANelse 0.Using the above circuit, we can compare the size of two encrypted floating-point numbers C1 = (C1[SIGN], C1[EXPO], C1[FRAC]) and C2 = (C2[SIGN], C2[EXPO], C2[FRAC]) using the code written in Figure 12. If the code outputs an encryption of 1, it says C1’s absolute value is greater than C2’s and it returns an encryption of 0 otherwise. Step 2 in Figure 12 is described in Figure 13 in detail.Figure 12
Absolute value comparison circuit with HEAAN-based representation.Figure 13
Details in Step 2 of the absolute value comparison circuit.A circuit for determining if two encrypted representations are equal can be implemented similar to addition/subtraction circuit: it can be easily obtained by calculating whether the FRAC part and the SIGN part of both floating-point numbers to be compared are the same using COMPHEAAN() after equalizing their EXPO parts.


### 4.2.4. Division

The division operation is similar to the multiplication operation except that the exponent part of the divisor is subtracted from the exponent of the dividend, and the inverse of the mantissa of the divisor is calculated using the inverse function and then it is multiplied by the mantissa of the dividend. In this case, if we do nothing further, the mantissa of the resultant value may be greater than 1. To deal with this, before performing the multiplication operations in the fraction part, the mantissa of the dividend is corrected so that it is smaller than the mantissa of the divisor. However, it is greater if the mantissa of the dividend is doubled. The process can be described as follows.Step 1 in Figure14 can be specified in detail as follows in Figure 15.Figure 14
Division operation in HEAAN-based representation.Figure 15
Details of Step 1 of the division operation.


## 4.2.1. Addition/Subtraction

The HEAAN-based addition method is implemented as shown in Figure8. In this method, two operands are classified to a smaller number and the other bigger number first. Then, the exponent value of the smaller number is increased to be matched to that of the bigger number. The increase of the value of the smaller number, which results from the increasing the exponent, is cancelled by dividing the mantissa part. After that, two mantissa parts are added to complete the addition.Figure 8
Overview of addition operation in the HEAAN-based method.The details of addition operation is as follows. We suppose two operands to be added as C1 = (C1[SIGN], C1[EXPO], C1[FRAC]), C2 = (C2[SIGN], C2[EXPO], C2[FRAC]). The function ReArrange (), which returns a larger value in cB and a small value in cS among the input C1 and C2, can be implemented as shown in Figure 9. C1 and C2 are compared based on their exponent values.Figure 9
Rearrange() function.We suppose the result of Rearrange (C1, C2, EXPO) is CS and CB. We run the following addition code with CS and CB in Figure 10. The output of the code is Cout. We discuss how the following code works. Because CS[EXPO] < CB[EXPO] and CS[FRAC], CB[EXPO] in [0, 1), the sign of the addition result is CB[SIGN]. Also, to perform calculation, the code increases CS[EXPO] to make it the same as CB[EXPO]. To keep the original value of CS after increasing CS[EXPO], the code decreases CS[FRAC] accordingly. After that, it returns the result of CB[FRAC] + CS[FRAC] when both CB and CS have the same sign or CB[FRAC] − CS[FRAC] if the signs are different. To keep the result’s fraction is in [0, 1), the exponent is increased by 1 and the fraction is divided by 2.Figure 10
Addition method in HEAAN-based approach.Because the maximum binary string that CB[EXPO] and CS[EXPO] can have is 11111111(2), Ceqcc is an encryption of 1 only once in the loop. In this case, CB[FRAC] + CS[FRAC] ∗ (1 − 2 ∗ Csign) is given to Cout[FRAC], where Csign is the result of checking if CB[SIGN] and CS[SIGN] are the same: if so, it has the encryption of 0, and 1 otherwise. In Step 3, EQCC (CB[EXPO], CS[EXPO]) executes HEAAN_XNOR(CB[EXPO], CS[EXPO]) from inside to perform XNOR operation between the bit values in the same slot of CB[EXPO] and CS[EXPO], respectively. After that, we multiply all the bit values in each slot of XNOR result to create Ccomp. Ccomp becomes 1 if CB[EXPO] and CS[EXPO] have exactly the same bit value in all of their slots; otherwise, it becomes 0.To perform subtraction, the sign of the number to be subtracted is inverted using HEAAN_XNOR, and then the addition operation is performed instead.


## 4.2.2. Multiplication

Multiplication is easier to implement than addition. First, the sign of the result value is equal to the value obtained by XORing the sign of two input numbers, and the result of the exponent part can be obtained by adding the exponents of the two inputs. E-KSA can be used to calculate it. Also, the mantissa can be obtained by multiplying the mantissas of two input numbers. In this case, the result of multiplying mantissa is still in [0, 1). Thus, we have nothing to do further. Figure11 shows the process of multiplying two encrypted floating-point real numbers C1 and C2 in the proposed method.Figure 11
Multiplication with HEAAN-based representation.


## 4.2.3. Comparison

In the HEAAN-based approach, COMPHEAAN() function is used as a tool to perform the size comparison operation of the encrypted floating-point values. COMPHEAAN () takes two HEAAN ciphertexts and the computation key evk of the ciphertext and performs the following operation [30]:(2)COMPHEAANC1HEAAN,C2HEAAN,evk⟶1ifC1HEAAN>C2HEAANelse 0.Using the above circuit, we can compare the size of two encrypted floating-point numbers C1 = (C1[SIGN], C1[EXPO], C1[FRAC]) and C2 = (C2[SIGN], C2[EXPO], C2[FRAC]) using the code written in Figure 12. If the code outputs an encryption of 1, it says C1’s absolute value is greater than C2’s and it returns an encryption of 0 otherwise. Step 2 in Figure 12 is described in Figure 13 in detail.Figure 12
Absolute value comparison circuit with HEAAN-based representation.Figure 13
Details in Step 2 of the absolute value comparison circuit.A circuit for determining if two encrypted representations are equal can be implemented similar to addition/subtraction circuit: it can be easily obtained by calculating whether the FRAC part and the SIGN part of both floating-point numbers to be compared are the same using COMPHEAAN() after equalizing their EXPO parts.


## 4.2.4. Division

The division operation is similar to the multiplication operation except that the exponent part of the divisor is subtracted from the exponent of the dividend, and the inverse of the mantissa of the divisor is calculated using the inverse function and then it is multiplied by the mantissa of the dividend. In this case, if we do nothing further, the mantissa of the resultant value may be greater than 1. To deal with this, before performing the multiplication operations in the fraction part, the mantissa of the dividend is corrected so that it is smaller than the mantissa of the divisor. However, it is greater if the mantissa of the dividend is doubled. The process can be described as follows.Step 1 in Figure14 can be specified in detail as follows in Figure 15.Figure 14
Division operation in HEAAN-based representation.Figure 15
Details of Step 1 of the division operation.


## 4.3. TFHE-Based Method

The TFHE-based expression follows the standard IEEE 754 exactly. For example, to represent 30.3 with the TFHE-based representation, we first translate this as 1.1110010011001100110 × 23(2). Then we add 127 to the exponent to represent the exponent bits. The fraction part stores all the fraction bits except the first “1” at the left of the decimal point. In this approach, sign, exponents, and mantissa are encrypted by separate ciphertexts. The number of ciphertexts in C[SIGN] is 1, C[EXPO] is 8, and C[FRAC] is 23 when the encrypted floating-point number is represented as C = (C [SIGN], C [EXPO], C[FRAC]). Also, for ease of expression, TFHE_XOR () operation is written as ⊕, and TFHE_AND () operation is indicated by. Figure 16 explains the procedure of making a TFHE-based encrypted floating-point number representation with an example of 30.3.Figure 16
Creating a ciphertext of a floating-point number with TFHE.To explain the methods clearly, we are going to use the following notations. An array of ciphertexts C[] = c0||c1||…||cn−1 can be described as C[0] = c0, C[1] = c1,… , C[n−1] = cn−1, where ci (i ∈ [0, n−1]) refers to an encryption of a single bit value. If we describe C[] = (cn−1 cn−2 … c2c1c0) (2), as a binary integer representation, then C[0] = c0, C[1] = c1,… , C[n−1] = cn−1, too. If there are two array of ciphertexs A[] and C[], where both are represented as binary integers and they are added using E-KSA circuit, then the result CR[] is 2n−1 (cn−1 + an−1) + 2n−2 (cn−2 + an−2)+ … + 21(c1 + a1) + c0+a0. Also, you have to keep in mind that c ⊕ (c0||c1||…||cn−1) = (c ⊕ c0||c ⊕ c1…||c ⊕ cn-1) and (ca0||ca1||…||can) ⊕ (cb0||cb1||…||cbn) = (ca0 ⊕ cb0||ca1 ⊕ cb1||…||can ⊕ cbn). The concatenation of two ciphertext arrays A[] and B[] can be described as A[]||B[], and it generates a new array of ciphertexts. Finally, C[] = C[] >> 1 means C[i + 1] = C[i] for all i = 0, …, len(C[])−2 and C[0] = 0.


### 4.3.1. Addition/Subtraction

The addition algorithm is constructed in a manner as similar as the HEAAN-based method. However, in this TFHE based method, arrays of ciphertexts are used to represent the components of the representation and each ciphertext has one bit value, which complicates the process as shown in Figure17. We use E-KSA as building block. The input of E-KSA, however, is arrays of ciphertexts instead of ciphertexts of multiple slots. Our implementation of E-KSA considered that. Figure 18 shows an implementation of Equality Comparison Circuit (TFHE_EQCC()) for TFHE representation, which is also a building block for addition operation. We also introduce the negate function (Negate()) which flips the bits in the input set of ciphertexts in Figure 19.Figure 17
Overview of addition operation in TFHE-based method.Figure 18
Equality comparison circuit for TFHE-based representation (TFHE_EQCC).Figure 19
Negate() function used in TFHE-based representation.Figure20 shows the procedure of addition operation with TFHE-based representation. For subtraction, the addition operation can be used after modifying the sign of the value to be subtracted.Figure 20
The addition algorithm for the TFHE-based representation. It takes CB, CS and outputs Cout.


### 4.3.2. Multiplication

The multiplication operation proceeds as follows. First, a basic operation is performed in which an XOR operation is performed on sign portions and the addition is performed on exponent portions. Then, the result of the multiplication operation of the fraction parts is applied. When adding the exponent parts, 127 is subtracted from the addition result to get the correct result. This is because the exponent part is basically expressed by adding 127 so that a negative number can be expressed with unsigned bit-strings. The overall multiplication process is shown in Figure21 below.Figure 21
Multiplication in TFHE-based representation.Among the three operations in Figure21, (1) and (2) are easy to implement, so we focus on (3). To perform (3), the numbers actually represented by C1[FRAC] and C2[FRAC] must be restored. The bits in C1[FRAC] and C2[FRAC] mean the values to the right of the decimal point in the two numbers’ fraction parts, and the leading “1” to the left of the decimal point is omitted as specified by the standard. Therefore, the multiplication calculation should be performed after recovering the “1”. Therefore, the multiplication is performed by attaching an encoding of “1” to the most significant digit, which is just left to the decimal point. In this case, the multiplication result cannot exceed 4, so the result is a 46-bit value with two bits to the left of the decimal point and the remaining 44 bits to the right.After calculating Cm[], the final step is to check whether the value in the ciphertext Cm[0], which represents the most significant bit of the multiplication result and 1 bit left away from the decimal point, is 1. If Cm[0] is 1, the fraction part of the multiplication result is Cm [1] ∼ Cm [22], and the exponent value should be incremented by one. If Cm[0] is 0, that means Cm [1] is 1, so the exponent does not increase and the fraction part of the result is Cm [2]∼Cm [24]. The method that reflects this is shown in Figure 22 below.Figure 22
Details of calculating the exponent and fraction in multiplication in TFHE-based representation.


### 4.3.3. Division

The division operation is similar to the multiplication operation. That is, to calculate the exponent part, the exponent value of the denominator is subtracted from the numerator, and division operation is performed between the fraction parts of them. Since the exponent should be added to 127 (=2((length of exponent bits)−1) − 1) to represent the negative exponent, 127 should be added to the resultant exponent after the subtraction. An overview of division operation to calculate the resultant exponent and fraction is shown in Figures 23 and 24, respectively.Figure 23
Exponent calculation module in the division operation of TFHE-based method.Figure 24
Fraction calculation module in the division operation of TFHE-based method.After calculating the exponent and the fraction, we need to correct them because the range of the result of calculating the fraction part is (0.5, 2). Thus, if the fraction part’s result is less than 1, 1 must be subtracted from the exponent and the bit position of the resultant fraction must be shifted to left by 1 bit. The sign is determined by XORing the signs of the numerator and denominator. Figure25 shows the operations to be performed for division. Cout[EXPO] and Cout[FRAC] are the result values, C1 = (C1[SIGN], C1[EXPO], C1[FRAC]) is the numerator, and C2 = (C2[SIGN], C2[EXPO], C2[FRAC]) is the denominator.Figure 25
An overview of the division operation in TFHE-based representation.As with multiplication, the most important and difficult process is (3). We use the nonrestoring division [31] method, which uses the divide-and-conquer to implement (3). This is known to be more efficient than the well-known methods such as those of Newton-Rapth [32] and Burnikel and Ziegler [33]. Figure 26 shows the result of implementing the nonrestoring division algorithm [15] to make it work on ciphertext input. This algorithm assumes that the highest-order bits are stored in index 0 of each input array, and the lower-order bits are stored as the index becomes larger. The bit length of both dividend and divisor is 24 bits each.Figure 26
Restoring division algorithm (R_DIV()).We deal with how to calculate (3) specifically. Since the mantissa is represented by omitting 1 immediately to the left of the decimal point which is the largest digit, in order to perform division correctly, the omitted bits should be restored before starting the division operation. To do this, the size of the ciphertext arrays indicating both the dividend and divisor is increased by one each, and we place an encoding of 1 to the highest position (i.e., the zeroth index). Then, division is performed through R_DIV (). The result is a 25-bit quotient. In this case, if the bit value of the highest position is 1, the next 23 bits are stored in the resultant fraction. Otherwise, the value of the second digit is 1 because the division quotient range is (0.5, 2). Therefore, the subsequent 23 bits are stored in the fraction part. If so, the value of exponent must be decreased by one. Figure27 shows an example of the case where the left part of the decimal point becomes zero in the fraction part of the division result. The steps to be performed is shown in the figure. The details of (3) is shown in Figure 28.Figure 27
An example of normalizing the fraction part in the division result.Figure 28
Procedure for calculating Cout[FRAC] with updating Cout[EXPO] in division.


### 4.3.4. Comparison and Equality Check

The comparison operation can be done using the COMP() circuit described in Figure5(B), using the bitwise concatenation results of all of the sign, exponent, and fraction ciphertext arrays in both values to be compared as inputs. IEEE 754 standard exactly uses the same approach to compare the floating-point numbers. The process of comparing two numbers can be expressed as shown in Figure 29.Figure 29
Comparison operation on TFHE-based representation.The equality can be easily checked as they are represented using bits. Two values are treated the same only if they have the same bits.


## 4.3.1. Addition/Subtraction

The addition algorithm is constructed in a manner as similar as the HEAAN-based method. However, in this TFHE based method, arrays of ciphertexts are used to represent the components of the representation and each ciphertext has one bit value, which complicates the process as shown in Figure17. We use E-KSA as building block. The input of E-KSA, however, is arrays of ciphertexts instead of ciphertexts of multiple slots. Our implementation of E-KSA considered that. Figure 18 shows an implementation of Equality Comparison Circuit (TFHE_EQCC()) for TFHE representation, which is also a building block for addition operation. We also introduce the negate function (Negate()) which flips the bits in the input set of ciphertexts in Figure 19.Figure 17
Overview of addition operation in TFHE-based method.Figure 18
Equality comparison circuit for TFHE-based representation (TFHE_EQCC).Figure 19
Negate() function used in TFHE-based representation.Figure20 shows the procedure of addition operation with TFHE-based representation. For subtraction, the addition operation can be used after modifying the sign of the value to be subtracted.Figure 20
The addition algorithm for the TFHE-based representation. It takes CB, CS and outputs Cout.


## 4.3.2. Multiplication

The multiplication operation proceeds as follows. First, a basic operation is performed in which an XOR operation is performed on sign portions and the addition is performed on exponent portions. Then, the result of the multiplication operation of the fraction parts is applied. When adding the exponent parts, 127 is subtracted from the addition result to get the correct result. This is because the exponent part is basically expressed by adding 127 so that a negative number can be expressed with unsigned bit-strings. The overall multiplication process is shown in Figure21 below.Figure 21
Multiplication in TFHE-based representation.Among the three operations in Figure21, (1) and (2) are easy to implement, so we focus on (3). To perform (3), the numbers actually represented by C1[FRAC] and C2[FRAC] must be restored. The bits in C1[FRAC] and C2[FRAC] mean the values to the right of the decimal point in the two numbers’ fraction parts, and the leading “1” to the left of the decimal point is omitted as specified by the standard. Therefore, the multiplication calculation should be performed after recovering the “1”. Therefore, the multiplication is performed by attaching an encoding of “1” to the most significant digit, which is just left to the decimal point. In this case, the multiplication result cannot exceed 4, so the result is a 46-bit value with two bits to the left of the decimal point and the remaining 44 bits to the right.After calculating Cm[], the final step is to check whether the value in the ciphertext Cm[0], which represents the most significant bit of the multiplication result and 1 bit left away from the decimal point, is 1. If Cm[0] is 1, the fraction part of the multiplication result is Cm [1] ∼ Cm [22], and the exponent value should be incremented by one. If Cm[0] is 0, that means Cm [1] is 1, so the exponent does not increase and the fraction part of the result is Cm [2]∼Cm [24]. The method that reflects this is shown in Figure 22 below.Figure 22
Details of calculating the exponent and fraction in multiplication in TFHE-based representation.


## 4.3.3. Division

The division operation is similar to the multiplication operation. That is, to calculate the exponent part, the exponent value of the denominator is subtracted from the numerator, and division operation is performed between the fraction parts of them. Since the exponent should be added to 127 (=2((length of exponent bits)−1) − 1) to represent the negative exponent, 127 should be added to the resultant exponent after the subtraction. An overview of division operation to calculate the resultant exponent and fraction is shown in Figures 23 and 24, respectively.Figure 23
Exponent calculation module in the division operation of TFHE-based method.Figure 24
Fraction calculation module in the division operation of TFHE-based method.After calculating the exponent and the fraction, we need to correct them because the range of the result of calculating the fraction part is (0.5, 2). Thus, if the fraction part’s result is less than 1, 1 must be subtracted from the exponent and the bit position of the resultant fraction must be shifted to left by 1 bit. The sign is determined by XORing the signs of the numerator and denominator. Figure25 shows the operations to be performed for division. Cout[EXPO] and Cout[FRAC] are the result values, C1 = (C1[SIGN], C1[EXPO], C1[FRAC]) is the numerator, and C2 = (C2[SIGN], C2[EXPO], C2[FRAC]) is the denominator.Figure 25
An overview of the division operation in TFHE-based representation.As with multiplication, the most important and difficult process is (3). We use the nonrestoring division [31] method, which uses the divide-and-conquer to implement (3). This is known to be more efficient than the well-known methods such as those of Newton-Rapth [32] and Burnikel and Ziegler [33]. Figure 26 shows the result of implementing the nonrestoring division algorithm [15] to make it work on ciphertext input. This algorithm assumes that the highest-order bits are stored in index 0 of each input array, and the lower-order bits are stored as the index becomes larger. The bit length of both dividend and divisor is 24 bits each.Figure 26
Restoring division algorithm (R_DIV()).We deal with how to calculate (3) specifically. Since the mantissa is represented by omitting 1 immediately to the left of the decimal point which is the largest digit, in order to perform division correctly, the omitted bits should be restored before starting the division operation. To do this, the size of the ciphertext arrays indicating both the dividend and divisor is increased by one each, and we place an encoding of 1 to the highest position (i.e., the zeroth index). Then, division is performed through R_DIV (). The result is a 25-bit quotient. In this case, if the bit value of the highest position is 1, the next 23 bits are stored in the resultant fraction. Otherwise, the value of the second digit is 1 because the division quotient range is (0.5, 2). Therefore, the subsequent 23 bits are stored in the fraction part. If so, the value of exponent must be decreased by one. Figure27 shows an example of the case where the left part of the decimal point becomes zero in the fraction part of the division result. The steps to be performed is shown in the figure. The details of (3) is shown in Figure 28.Figure 27
An example of normalizing the fraction part in the division result.Figure 28
Procedure for calculating Cout[FRAC] with updating Cout[EXPO] in division.


## 4.3.4. Comparison and Equality Check

The comparison operation can be done using the COMP() circuit described in Figure5(B), using the bitwise concatenation results of all of the sign, exponent, and fraction ciphertext arrays in both values to be compared as inputs. IEEE 754 standard exactly uses the same approach to compare the floating-point numbers. The process of comparing two numbers can be expressed as shown in Figure 29.Figure 29
Comparison operation on TFHE-based representation.The equality can be easily checked as they are represented using bits. Two values are treated the same only if they have the same bits.


## 4.4. Discussion on the Differences between the Implementation of Two Methods

The differences between the implementation of the two methods can be summarized as follows. First, in the operation with exponent values, the HEAAN-based method can reduce the number of operations by using the SIMD operation, but the TFHE-based method must perform operations in bit units, which requires large number of TFHE operations.Second, the HEAAN-based implementation can implement the operations for dealing with the mantissa part with a small number of HEAAN operations using arithmetic operation provided by HEAAN, but in TFHE-based method, the operation must be processed for each bit of mantissa, which also requires a large number of TFHE operations.In the above two cases, the HEAAN-based method seems to be dominant, but HEAAN requires bootstrapping when it needs complex arithmetic with their floating point representations: especially when it needs calculation of more than a predetermined multiplication depth. In this case, HEAAN needs a lot of computation resources. Thus, it will be much slower than the TFHE-based method.


## 5. Performance Evaluation

In this section, we compare the performance of the two encrypted floating-point values’ representations proposed in this paper. The first subsection deals with the performance on various exponent bits. Then, we discuss the effect of the length of mantissa bits in the next subsection. Before showing the details of experiments, we provide the complexity analysis result of the operations in terms of the required multiplication operation on each FHE in Table1. Because of the SIMD operation supported, HEAAN requires less number of multiplication operations. However, some operations which require heavy multiplication depth such as division need bootstrapping operation in HEAAN, which causes heavy delay.Table 1
Computational complexity analysis on the operations in terms of the number of FHE multiplication operations required.
Operations
TFHE
HEAAN
Addition
O
2
e
m
+
e
log
m
+
e
O
2
e
log
e
Multiplication
O
m
2
+
e
log
e
O
2
e
e
Division
O
m
2
+
m
e
+
e
log
e
O
m
log
e + 2 bootstraps
Comparison
O
m
+
e
log
m
+
e
O
log
e
m: bit length of mantissa, e: bit length of exponent.


### 5.1. Experiment on Various Exponent Bits

We measured the execution time of the operations on both methods on various exponent bits. The environment used is as shown in Table2. The performance of the E-KSA(), COMP(), and MinMax() modules used to implement the operations in each representation is compared in Figure 30. Since HEAAN uses them only to deal with the exponent bits, we measure the execution time of the modules in processing only exponent bits in the TFHE case, for fair comparison. In order to show the performance change according to the bit length of the exponent, we measure the execution time with the exponent bit lengths of 2, 4, and 8 cases, respectively. The results are shown in the figure below. As shown in the figure, when bitwise operation is implemented in HEEAN, it takes more time than TFHE because it requires to perform interslot calculation. However, in the case of TFHE, the longer the bit length, the longer the execution time, but HEAAN is not.Table 2
Experiment environment for the experiments in Section5.1
TFHE
HEAAN
Parameters
Lambda = 128
log N = 15, log p = 23, log q = 29, log Q = 620, log T = 2
Experiment environment
Intel i7-6700, 3.40 GHz, 16.0 GB RAM, Ubuntu 14.04LTSFigure 30
Performance comparison of building blocks.Next, we compare the performance of arithmetic operations. Figure31 shows the comparison of execution time of arithmetic operations. We can say the HEAAN-based method is superior to the TFHE-based one in terms of the speed of the arithmetic operations because the operations that should be done between the fraction parts of both operands can be executed more efficiently than the TFHE. One peculiar point is that the addition/subtraction operation is the slowest. This is due to the nature of the FHE operation. In the case of addition, the addition operation of the fraction part must be performed after the exponent has been adjusted. However, in the case of operations on data encrypted with FHE, since the exponent parts are also encrypted, we cannot make both encrypted operands have the same exponents. Therefore, the actual operation is performed by performing the operation of the fraction part for all possible exponent values and selecting the result only when the exponent values of the two operands match. Therefore, since the number of combinations of all possible exponents of both operands is large, the addition/subtraction operation takes the longest.Figure 31
Performance on arithmetic operations.Figure32 compares the performance of size comparison and equivalence operations. Since the comparison operation takes too long when the exponent is 8 bits, the experiment is performed only on 2-bit and 4-bit exponents. In this case, the HEAAN-based method consumes too many multiply operation depths for comparison operations, resulting in poor performance due to the large number of bootstrapping. Finally, we compare the execution time of the equality check operation. We can confirm that TFHE is five times faster because of the inefficiency of the equality check operation between HEAAN ciphertexts.Figure 32
Performance comparisons on comparison and equality-check operations on various exponent bits.


### 5.2. Experiments on Various Mantissa Bits

Experiments with various mantissa bit lengths are presented in this subsection. The experimental environment is shown in Table3. According to the developers of the libraries, both libraries offer 128-bit security in this setting. The experimental results are shown in Table 4 below. In order to provide mantissas of various bit lengths in the HEAAN-based method, we adjusted the “quantize-bit” parameter value in HEAAN. In each slot of the HEAAN ciphertext, there is a plaintext value and the noise which is attached to the plaintext value during encryption or arithmetic operations. The quantize-bit defines the bit length of those combined values. Since the bit length of noise added during encryption is at most five with a very high probability, which is around (1 − 3 ∗ 10−7) (this refers to Pr[μ-5σ<X<μ+5σ], where X is a random variable of standard normal distribution with parameter (μ , σ); the σ value used in HEAAN is 3.2), we set the quantize bit as the bit length of the mantissa bit plus five. The quantize bit values used are shown as p-bit in Table 4.Table 3
Experiment environment for the experiments in Section5.2.
TFHE
HEAAN
Parameters
Lambda = 128
log N = 15, logp = (Vary. See Table 4), log Q = 1446, log T = 2
Experiment environment
Intel i9-9900K, 3.6 GHz, 64.0 GB RAM, Ubuntu 18.04 LTSTable 4
Experiment results on various mantissa bit lengths when the bit length of exponent is fixed to four (in seconds).
Fraction bit length
TFHE
HEAAN
Logp (p-bit)
ADD
MULT
DIV
COMP
ADD
MULT
DIV
COMP
23
489.613
162.195
686.513
5.70388
185.735
10.735
417.938
171.706
28
33
1351.28
446.062
2275.67
12.0943
166.174
10.783
716.644
152.721
38
43
1167.55
571.274
2950.23
12.6297
583.492
10.659
1066.72
531.607
48
52
1207.52
686.463
3559.19
13.0962
1110.84
10.449
2162.76
941.9
57From Table4, we can see that the comparison operation is much faster in the TFHE-based method than in the HEAAN-based implementation. However, in the multiplication operation, HEAAN-based method is better than TFHE in terms of the required time. Regarding the other operations, HEAAN seems better. However, as the exponent bit length is longer, the gap of the performance will be reduced because more multiplication depth is necessary, so bootstrapping may be needed in the HEAAN-based implementation. Thus, it is estimated that TFHE-based method might be better if the exponent bit is above a certain threshold.


### 5.3. Experiment on Precision in the HEAAN-Based Method

To verify the precision of the HEAAN-based method, we conducted the following experiment. After selecting two random float-type values, they were multiplied by each other, and then another random float-type number was selected and multiplied by the previous result of multiplication. This process was repeated 10 times. We performed this process using only plaintext and performed the same process with the encrypted values generated with HEAAN-based method. We decrypt the result of multiplication in each step and compare it with the result of multiplication with the plaintexts. To measure the error of calculation, we used the following formula: |(multiplication result with plaintexts)−(multiplication result with HEAAN ciphertexts)| |(multiplication result with plaintexts)|. It means the relative error of calculation. The measurement results are shown in Table5 below. Since 2−23 is around 1.192E-7, we can say the error generated by the multiplication on two HEAAN-based encrypted floating-point representations is small enough compared to the errors generated by the multiplication on float-type values.Table 5
Relative errors between the multiplication result with ciphertexts and that with plaintexts.
Multiplication round
1
2
3
4
5
6
7
8
9
10
Relative error
1.21E − 7
6.92E − 8
7.91E − 8
9.04E − 8
1.03E − 7
0
6.75E − 8
1.54E − 7
0
0


## 5.1. Experiment on Various Exponent Bits

We measured the execution time of the operations on both methods on various exponent bits. The environment used is as shown in Table2. The performance of the E-KSA(), COMP(), and MinMax() modules used to implement the operations in each representation is compared in Figure 30. Since HEAAN uses them only to deal with the exponent bits, we measure the execution time of the modules in processing only exponent bits in the TFHE case, for fair comparison. In order to show the performance change according to the bit length of the exponent, we measure the execution time with the exponent bit lengths of 2, 4, and 8 cases, respectively. The results are shown in the figure below. As shown in the figure, when bitwise operation is implemented in HEEAN, it takes more time than TFHE because it requires to perform interslot calculation. However, in the case of TFHE, the longer the bit length, the longer the execution time, but HEAAN is not.Table 2
Experiment environment for the experiments in Section5.1
TFHE
HEAAN
Parameters
Lambda = 128
log N = 15, log p = 23, log q = 29, log Q = 620, log T = 2
Experiment environment
Intel i7-6700, 3.40 GHz, 16.0 GB RAM, Ubuntu 14.04LTSFigure 30
Performance comparison of building blocks.Next, we compare the performance of arithmetic operations. Figure31 shows the comparison of execution time of arithmetic operations. We can say the HEAAN-based method is superior to the TFHE-based one in terms of the speed of the arithmetic operations because the operations that should be done between the fraction parts of both operands can be executed more efficiently than the TFHE. One peculiar point is that the addition/subtraction operation is the slowest. This is due to the nature of the FHE operation. In the case of addition, the addition operation of the fraction part must be performed after the exponent has been adjusted. However, in the case of operations on data encrypted with FHE, since the exponent parts are also encrypted, we cannot make both encrypted operands have the same exponents. Therefore, the actual operation is performed by performing the operation of the fraction part for all possible exponent values and selecting the result only when the exponent values of the two operands match. Therefore, since the number of combinations of all possible exponents of both operands is large, the addition/subtraction operation takes the longest.Figure 31
Performance on arithmetic operations.Figure32 compares the performance of size comparison and equivalence operations. Since the comparison operation takes too long when the exponent is 8 bits, the experiment is performed only on 2-bit and 4-bit exponents. In this case, the HEAAN-based method consumes too many multiply operation depths for comparison operations, resulting in poor performance due to the large number of bootstrapping. Finally, we compare the execution time of the equality check operation. We can confirm that TFHE is five times faster because of the inefficiency of the equality check operation between HEAAN ciphertexts.Figure 32
Performance comparisons on comparison and equality-check operations on various exponent bits.


## 5.2. Experiments on Various Mantissa Bits

Experiments with various mantissa bit lengths are presented in this subsection. The experimental environment is shown in Table3. According to the developers of the libraries, both libraries offer 128-bit security in this setting. The experimental results are shown in Table 4 below. In order to provide mantissas of various bit lengths in the HEAAN-based method, we adjusted the “quantize-bit” parameter value in HEAAN. In each slot of the HEAAN ciphertext, there is a plaintext value and the noise which is attached to the plaintext value during encryption or arithmetic operations. The quantize-bit defines the bit length of those combined values. Since the bit length of noise added during encryption is at most five with a very high probability, which is around (1 − 3 ∗ 10−7) (this refers to Pr[μ-5σ<X<μ+5σ], where X is a random variable of standard normal distribution with parameter (μ , σ); the σ value used in HEAAN is 3.2), we set the quantize bit as the bit length of the mantissa bit plus five. The quantize bit values used are shown as p-bit in Table 4.Table 3
Experiment environment for the experiments in Section5.2.
TFHE
HEAAN
Parameters
Lambda = 128
log N = 15, logp = (Vary. See Table 4), log Q = 1446, log T = 2
Experiment environment
Intel i9-9900K, 3.6 GHz, 64.0 GB RAM, Ubuntu 18.04 LTSTable 4
Experiment results on various mantissa bit lengths when the bit length of exponent is fixed to four (in seconds).
Fraction bit length
TFHE
HEAAN
Logp (p-bit)
ADD
MULT
DIV
COMP
ADD
MULT
DIV
COMP
23
489.613
162.195
686.513
5.70388
185.735
10.735
417.938
171.706
28
33
1351.28
446.062
2275.67
12.0943
166.174
10.783
716.644
152.721
38
43
1167.55
571.274
2950.23
12.6297
583.492
10.659
1066.72
531.607
48
52
1207.52
686.463
3559.19
13.0962
1110.84
10.449
2162.76
941.9
57From Table4, we can see that the comparison operation is much faster in the TFHE-based method than in the HEAAN-based implementation. However, in the multiplication operation, HEAAN-based method is better than TFHE in terms of the required time. Regarding the other operations, HEAAN seems better. However, as the exponent bit length is longer, the gap of the performance will be reduced because more multiplication depth is necessary, so bootstrapping may be needed in the HEAAN-based implementation. Thus, it is estimated that TFHE-based method might be better if the exponent bit is above a certain threshold.


## 5.3. Experiment on Precision in the HEAAN-Based Method

To verify the precision of the HEAAN-based method, we conducted the following experiment. After selecting two random float-type values, they were multiplied by each other, and then another random float-type number was selected and multiplied by the previous result of multiplication. This process was repeated 10 times. We performed this process using only plaintext and performed the same process with the encrypted values generated with HEAAN-based method. We decrypt the result of multiplication in each step and compare it with the result of multiplication with the plaintexts. To measure the error of calculation, we used the following formula: |(multiplication result with plaintexts)−(multiplication result with HEAAN ciphertexts)| |(multiplication result with plaintexts)|. It means the relative error of calculation. The measurement results are shown in Table5 below. Since 2−23 is around 1.192E-7, we can say the error generated by the multiplication on two HEAAN-based encrypted floating-point representations is small enough compared to the errors generated by the multiplication on float-type values.Table 5
Relative errors between the multiplication result with ciphertexts and that with plaintexts.
Multiplication round
1
2
3
4
5
6
7
8
9
10
Relative error
1.21E − 7
6.92E − 8
7.91E − 8
9.04E − 8
1.03E − 7
0
6.75E − 8
1.54E − 7
0
0


## 6. Conclusion

In this paper, we have proposed a new encrypted floating-point number representation method that supports full arithmetic and comparison operations and is able to represent a real number whose range is very similar to that supported by the IEEE 754 standard. Our representation has been implemented on two recent FHE schemes, HEAAN and TFHE, to demonstrate the feasibility of the proposed method. We hope the proposed representation will be applied to the privacy-preserving applications where the floating point numbers are used in common, such as the machine learning with private data.



---

*Source: 1250295-2020-03-02.xml*