6.2.2.1. Fixed or leveled SHE schemes

SHE schemes can only evaluate polynomials of a limited degree; this limit is fixed and cannot be parameterized. They are relatively cheap in terms of time and memory, but are not flexible. These solutions offer a broader range of potential applications than Paillier’s system, for example, but are more costly than the earlier system and present a similar level of rigidity.

Leveled SHE schemes are an alternative that may be used to evaluate a polynomial of limited degree; the upper bound of the degree can be chosen, but must be defined before the application is implemented.

These schemes are more flexible than fixed SHEs; applications may evolve following the initial implementation, as long as the degree of polynomials to evaluate remains below the predefined threshold.

Many examples of this type exist, and while the field was initially subject to much confusion, matters are now much clearer. There are three schemes which appear to be gaining in popularity: BFV (Fan and Vercauteren 2012), CKKS (Cheon et al. 2017, 2018) and TFHE (Chillotti et al. 2016, 2017, 2020). Only the first of these examples will be described in detail here, based on the fact that this approach is the simplest to explain.

BFV is a leveled, almost FHE scheme developed by Fan and Vercauteren (2012), drawing on Brakerski’s initial SHE scheme (Brakerski 2012). Further details can be found in the corresponding articles.

Let q and t be two security parameters (q for key size and t for message size) and let Δ = [q/t]. A distribution χ over the ring R of polynomials is required. The secret key s is an element in . The associated public key requires that we first select an element a from the polynomial ring with a value in and an element e selected according to the distribution χ, before calculating A = [–(as.e)]_q. The couple (A, a) is used as the public key to encrypt a message m. More precisely, for a message in the ring of polynomials with values in , this encryption process involves the following steps:

• – take u uniformly from the ring of polynomials with values in , and take e₁, e₂ according to the distribution χ;
• – calculate and generate the encrypted value c = (c₀, c₁).

Decryption is then carried out by calculating:

This scheme possesses the two necessary homomorphic properties:

• – addition: by simply adding two encrypted values with messages m and respectively, component by component, we obtain a new encrypted value corresponding to the encrypted value of
• – multiplication: this operation is more complicated. Given two encrypted values of messages m and respectively, we can calculate:

However, in this format, the output is not compatible with a new multiplication operation. A relinearization method must then be applied in order to obtain an encrypted value in the initial form, enabling further multiplications in the encrypted domain. This step involves the generation of a relinearization key (k₀, k₁) and the following formulas (where the values d₂[i] correspond to the components of d₂ in a base T associated with relinearization):

The encrypted message then corresponds to an encryption of

6.2.2.2. FHE schemes

FHE schemes have the capacity, in the strict sense, to evaluate polynomials of any degree (to an extent which is limited by computation time constraints and the factors of expansion accepted by the target application). A major advantage of these approaches is that the degree of polynomials does not need to be bounded prior to programming and implementation; however, this flexibility comes at a cost, in terms of both time and memory.

Many leveled approaches can be transformed into FHE approaches using the bootstrapping technique introduced by Gentry (2009), which we shall not describe in detail here. One notable example is the BFV approach presented above. This bootstrapping approach is costly, but a number of techniques have been developed to reduce its impact.

6.3.2.1. Data encoding

There are several ways of encoding plaintext data, depending on the chosen homomorphic scheme. SHE schemes of BFV type (described in section 6.2.2.1) and BGV type (Brakerski et al. 2012) define clear messages as polynomials of a degree less than n (size of the Euclidean lattice) with integer coefficients modulo p (a power of a prime number). Using only the zero-degree coefficient to encode data makes applications easier, as homomorphic operations then correspond to additions and multiplications on scalars modulo p. Boolean circuits can be executed in the case where p = 2. Nevertheless, a number of methods have been proposed in the literature for optimizing this polynomial space. Chen et al. (2018), for example, introduced a method for encoding a number modulo pⁿ in a single encrypted element, while Yasuda et al. (2015) described a way of obtaining the scalar products of two vectors by encoding each vector as a single encrypted element.

The CKKS scheme features an additional operation, division by a constant, which cannot be found in the BFV and BGV schemes. With this operation, fixed-point real numbers can be encoded with a predefined precision. Many more practical applications use arithmetic on real numbers, rather than modulo p arithmetic. SHE schemes using polynomial rings can be used to encode vectors (of size n for BFV/BGV and size n/2 for CKKS) into a single encrypted element. Homomorphic operations become term-to-term operations in this case (the equivalent of the SIMD notion in processors). This technique is called batching and will be discussed briefly in section 6.3.3.

Fast bootstrapping FHE schemes, such as TFHE and FHEW (Ducas and Micciancio 2015; Bonnoron et al. 2018), on the other hand, are a special case in terms of encoding. Their message space is strictly Boolean (only one Boolean value is encoded per element, and there is no notion of batching). However, they natively support more homomorphic operations than SHE schemes. In TFHE and FHEW, more complex generic binary gates (such as thresholds) can be implemented directly. Thus, more complex operations can be performed at the individual gate level than in schemes, which rely on basic logic gates alone; this means that shallower circuits can be used.

The Chimera framework (Boura et al. 2018) introduces a hybrid solution that combines three homomorphic schemes (BFV, TFHE and CKKS) in a single application, in order to enjoy the advantages of each approach, according to the operations to be performed. The authors present a common algebraic structure for the clear message spaces and propose efficient algorithms for passing between these spaces. Chimera allows arithmetic and Boolean computations to be combined in the same homomorphic application, something which is difficult to achieve using a single homomorphic scheme. One example of an application is presented in Carpov et al. (2019). These authors used the TFHE scheme to train a logistic regression model, before using the CKKS scheme to find all of the features in a numerical database, which may be used to improve the quality of the initial model.

6.3.2.2. Circuit optimization

Multiplicative depth is the maximum number of consecutive multiplications in the arithmetic circuit that describes the homomorphic calculation. It is therefore related to the degree of the polynomial corresponding to the calculation to perform. Minimizing this depth is a key aim in improving the performance of fixed or leveled SHE schemes. The size of encrypted elements and the speed of execution of homomorphic operations are highly dependent on this depth, as multiplication has the greatest impact on cost in terms of both time and space. Multiplicative depth minimization can be performed manually when designing homomorphic applications. The design flow that we used to develop a homomorphic application with reduced multiplicative depth is presented in section 6.4.3. Several approaches have been presented in the literature, such as shallow circuits for sorting (Çetin et al. 2015) and Levenshtein distance for genomic similarity (Cheon et al. 2015).

In this context, automatic multiplicative depth optimization of Boolean circuits was first discussed in Carpov et al. (2017) and later in other studies (Aubry et al. 2020; Häner and Soeken 2020; Lee et al. 2020). These works are not limited to Boolean circuits, and the approaches presented can also be used to optimize arithmetic circuits. Several rules are proposed for the local rewriting of Boolean circuits. By applying these rules to critical parts of the circuit (notably the paths of maximum depth), the multiplicative depth can be reduced. The cited works differ in terms of the rewriting rules that they use, and the way in which these rules are applied. With respect to the performance of automatic methods, for example, the method published in Aubry et al. (2020) was able to transform a carry-propagating (128-bit) binary adder (depth 255) into an equivalent carry-forward binary adder with a multiplicative depth of 9.

Operations supported by fast bootstrapping FHE schemes, such as TFHE or FHEW, all have the same computational complexity. Computation time can be reduced by minimizing the number of logic gates to execute in the Boolean circuit. The body of literature on the subject of logical synthesis is vast, and many different optimization methods can be applied directly in order to reduce the size of Boolean circuits.

The optimization methods defined above change the Boolean circuit in order to minimize the complexity and/or number of homomorphic operations to perform. A further complementary approach concerns the optimal scheduling of relinearization (Chen 2017) and bootstrapping operations (Paindavoine and Vialla 2015; Benhamouda et al. 2017). In this case, the aim is to order homomorphic operations (relinearization in SHE schemes, bootstrapping in FHE) in such a way that the total execution time is minimized.

6.3.2.3. Software implementation

At first, implementations of SHE and FHE were not systematically published with each new scheme, but this practice became increasingly regular over time and is now universal. Only public, maintained examples will be cited here. Certain libraries focus on one or two schemes, while others are veritable experimental platforms including multiple schemes.

HElib⁵, launched by Halevi and Shoup in 2014 and maintained by IBM, offers an implementation of BGV (Brakerski et al. 2012) and CKKS (Cheon et al. 2017, 2018). It is intended to provide support for concept proofs rather than for production purposes.

The SEAL library⁶ was launched in 2015 by Laine et al. and is maintained by Microsoft. It currently implements BFV (Fan and Vercauteren 2012) and CKKS, and also targets at production applications.

Several implementations of BFV exist, such as FV-NFLlib⁷, which uses the NFLlib library⁸. Further implementations can be found in the PALISADE and CINGULATA libraries.

The TFHE library⁹ was created in 2016, and is run by a group of researchers who were involved in designing the eponymous scheme (Chillotti et al. 2016).

The HEAAN library¹⁰, launched in 2017, offers an implementation of the CKKS scheme, designed for fixed point number encryption.

The PALISADE project¹¹ offers implementations of BGV, BFV, CKKS, FHEW (Ducas and Micciancio 2015) and a variant of TFHE.

The final platform for discussion, launched in 2012, differs from the others in the fact that it includes a compilation and circuit optimization engine, in addition to executing computations. This case is described in greater detail below.

6.3.2.4. Cingulata: a special case

Homomorphic encryption systems allow low-level arithmetic operations (such as addition and multiplication in binary space) to be performed directly on encrypted data. To facilitate the use of these libraries, compilation tools are needed to transform applications written in high-level programming languages into executables using a homomorphic encryption library. Cingulata, formerly known as Armadillo (Aguilar-Melchor et al. 2013; Carpov et al. 2015), is the first compilation and execution tool dedicated to homomorphic encryption. Cingulata combines a compiler chain with an execution environment, allowing developers to write the application and underlying algorithms in C++ without needing to take the inherent homomorphic encryption scheme or homomorphic operations into account. Applications are thus programmed in the same way as for non-encrypted data. Cingulata then couples the program with the chosen encryption scheme, and automatically recodes it to permit execution on encrypted input.

High-level abstractions and tools are provided to facilitate the implementation and execution of privacy-preserving applications. Cingulata is openly distributed as open source and is available from GitHub¹².

Instrumented C++ types, such as the CiInt type for integers and CiBit type for Booleans, are used to denote encrypted (confidential) variables. The Cingulata environment tracks each bit of these variables independently. Operations on integers are performed using Boolean circuits. For example, a carry propagation adder is used to perform addition between two integers. The generation of Boolean circuits corresponding to integer operations is automatic, and two circuit generators are available, allowing users to minimize either the size or the multiplicative depth of the circuit. Users also have the option to implement their own circuit generators or combine existing generators.

Each bit, represented by a CiBit object, may be in a clear or encrypted state. Operations between clear and encrypted elements are optimized automatically. Operations between encrypted bits are executed by an object which implements the IBitExec interface. This object may either encapsulate a homomorphic library, track each bit in the BitTracker application, or carry out clear bit-to-bit execution for debugging purposes.

The use of the BitTracker object makes it possible to construct a representation of the application in the form of a Boolean circuit. The Cingulata chain can then minimize the size or multiplicative depth of the Boolean circuit using specialized optimization modules.

The ABC toolchain¹³, generally used for hardware synthesis, is used to minimize the size of the Boolean circuits, and Cingulata modules implement heuristics to minimize the multiplicative depth of the circuit (Carpov et al. 2017; Aubry et al. 2020).

The optimized Boolean circuit is then executed using the Cingulata parallel execution environment. The execution environment is generic, that is, it uses an object encapsulating a homomorphic library (TfheBitExec, BfvBitExec), to execute the Boolean gates of the circuit. The parallel scheduler is designed to take full advantage of multicore processors. A set of utility applications is provided for parameter generation (with a target security level), key generation, data encryption and decryption. These applications are also generic, in the same way as the runtime environment.

6.3.2.5. Hardware optimization

A first means of speeding up computation time is to deport part of the processing onto suitable hardware implementations. This is particularly critical for schemes using Euclidean networks, which are the most memory intensive and computationally intensive (handling polynomial multipliers of degree n ∈[4,096, 32,768] with coefficients of a size of log₂ q ∈ [125,1,228] bits). One approach, which is relatively economical in terms of investment, is to use GPU cards. Nevertheless, the gains to be made in this case are highly dependent on the homomorphic scheme, since some are less suited to this treatment than others. Much better results can be obtained using specialized hardware components, such as FPGAs or ASICs. However, it is important to understand the expected benefits before implementing these hardware solutions. It is not reasonable to deport everything; a compromise must be found in order to maximize overall gains, offsetting accelerations in terms of calculation time against the time taken to transfer potentially voluminous data. Only the most time-consuming operations, notably multiplications, are deported to hardware.

Several approaches have already been explored. Most hardware implementations of multipliers rely on the use of the NTT (Number Theoretic Transform, a Fourier transform on finite fields). This can result in a very significant acceleration, but requires particular parameters, which can sometimes be over-dimensioned. Given that, in this case, n must be a power of 2, if the required value of n exceeds 2^p then n = 2^p+1, which is much larger, must be taken. This means that the body of data will be much larger, and calculations will be more costly. Moreover, the batching techniques that are usually used to reduce data size and parallelize computations are not natively compatible with this approach. Typical examples of NTT use include (Doröz et al. 2013; Pöppelmann et al. 2015; Sinha Roy et al. 2015).

Recent work has focused on designing accelerators for polynomial multiplication for SHEs, working on several RNS channels simultaneously in order to avoid explicit manipulation of large integers (Cathébras et al. 2018). These developments draw on work carried out by the signal processing community on the hardware implementation of the FFT, notably using the Spiral modulo tool for adaptations; in addition to finite field operations, and in contrast with the case of FFT, the coefficients of the transform change constantly. Thus, the development of a hardware module to generate these coefficients on-the-fly, coupled with the circuits produced by the Spiral tool, enables a potential acceleration with a factor of between 5 and 15 for multiplications of encrypted numbers (the main bottleneck in terms of SHE performance).

Another strategy may be used to avoid over-dimensioning parameters and facilitate the natural grouping of data via batching techniques: for example, the Karatsuba algorithm may be used for multiplication, as proposed in Migliore et al. (2017, 2018). Excellent results can be obtained in this case, notably by optimizing the co-design of the remaining software computation and the operations that are deported onto the hardware (Migliore et al. 2018).

Once again, there is a trade-off to be made, guided by the specificities of the target application. Is it better to use an algorithm such as NTT, which provides high acceleration but may use over-dimensioned parameters, or an algorithm such as Karatsuba, which offers lower acceleration for the same parameters but ensures that these parameters will be a better fit (leading to reduced computation cost and smaller encrypted elements)? There is no one-size-fits-all answer in this case, as the solution depends on application-specific constraints in terms of time/memory, parameter size and choice of encryption scheme.

6.3.3.1. Encoding and batching

The first key point is to choose the right encoding approach for the data. Raw data must first be transformed into words in the clear message space of the chosen encryption scheme. In the case of the Paillier scheme, this space is the set of integers modulo n; for schemes based on Euclidean lattice structures, it is a polynomial of degree n (note that the value of n is very different in both cases, and the coefficients of the polynomials belong to large algebraic structures). This encoding can be done in a naive manner, but it is also possible to reduce data size at this stage by grouping several data elements into the same structure. This is only possible for certain algebraic structures, such as polynomials on rings; in this case, several data elements can be encoded in the coefficients of the polynomial, which will constitute the clear message. This technique, called batching, means that multiple data elements can be processed simultaneously. It thus constitutes a form of parallelization applied directly at the data encoding level: several data elements will be processed by processing a single clear message.

6.3.3.2. Transcryption

Another process which is extremely useful for reducing the data load on both client and server is illustrated in Figure 6.3. This process, known as transcryption, was presented in Naehrig et al. (2011). Data are initially encrypted using a classical symmetric encryption system, noted SymEnc, rather than with a homomorphic system, noted HomEnc; thus, the size of the data is not increased. The encrypted data SymEnc_SymKey(m) is sent to the server with no added cost, and will then be transcrypted by the server itself to produce a version as encrypted by the homomorphic system HomEnc(m). Without going into too much detail, note that this transcryption approach is possible for algebraic reasons (homomorphy), and that the key of the symmetric encryption system encrypted using the homomorphic system, that is, HomEnc(SymKey), needs to be sent alongside SymEnc_SymKey(m). Using these two data elements, the server can calculate the HomEnc(m) cipher without passing through m. The whole problem is thus deported onto the server. This comes at a cost, but offers a solution for a large number of otherwise impossible problems. Nevertheless, great care must be taken when choosing the symmetric encryption system, since the transcryption process requires the SymDec process to be evaluated in a homomorphic manner (in the encrypted domain of the homomorphic scheme). We must therefore choose a scheme for which SymDec gives rise to a circuit of which the homomorphic evaluation is as reasonable as possible, notably in terms of multiplicative depth.

Evidently, the first works focused on existing symmetric encryption schemes, initially on AES, which turned out to be much too costly (Gentry et al. 2012; Cheon et al. 2013; Doröz et al. 2016); the focus then shifted onto lighter encryption schemes such as Simon and Prince, designed for constrained environments, but these also proved to be too costly (Doröz et al. 2014; Lepoint and Naehrig 2014) (the relevant constraints here are not the same as those taken into account when designing these schemes). Given the unsuitable nature of existing schemes, several groups have worked on designing new schemes specific to this context. The first example is Low MC (Albrecht et al. 2015b); the initial version was attacked (Dinur et al. 2015), and then patched (Rechberger 2016). However, these schemes have a flaw linked to their block cipher structure. Canteaut et al. (2016, 2018) proposed a new approach based on stream cipher designs, and this appears to be much better suited to the context in terms of both performance and security. This approach notably allows part of the computation process to be carried out offline, facilitating the later online phase. Efficient solutions to this issue are now available. Two stream cipher schemes have been proposed: Kreyvium (Canteaut et al. 2016, 2018), based on the Trivium scheme, the security of which has been widely tested and recognized over the past decade; and FLIP (Méaux et al. 2016), the security of which is less certain (Duval et al. 2016). These solutions have been implemented and tested experimentally. Another more innovative solution was proposed in (Fouque et al. 2016), but this is less advanced from an experimental perspective.

It should be noted, however, that the transcryption process currently only applies to data transfers from the client to a homomorphic computer, and not to the transfer of computation results to the holder of the secret decryption keys, which are currently transferred in FHE encrypted form. Several solutions to this problem have been explored (Carpov and Sirdey 2016; Kuaté 2018), notably decomposing multislot homomorphic ciphertexts (before computation) and then recomposing them (after computation). However, these solutions are not fully satisfactory, either for performance reasons or because the homomorphic properties of the resulting ciphers are not preserved. Minimizing the bandwidth increase linked to the transfer of homomorphic computations to the client is an important question for current and future research.

6.3.4.1. Schemes based on elliptic curves and pairings

Notable examples of schemes belonging to this category include Paillier (1999), ElGamal (1985) and BGN (Boneh et al. 2005; Herbert et al. 2019). Their theoretical security involves mathematical problems whose difficulty has been extensively studied (calculations of discrete logarithms in large groups, factorization of large integers, etc.). This means that we are on familiar ground, although further developments are possible. This familiarity is a significant advantage; nevertheless, these techniques will cease to be functional with the advent of quantum computers, which have the capacity to solve such problems in an efficient and effective manner. The best way of choosing appropriate parameters is to consult the article presenting the scheme in question in order to identify the mathematical problem, and then consult official documents such as those issued by the ANSSI¹⁵ or listed on the codecolorBlueKrypt¹⁶ website in order to select parameters in accordance with the desired security level.

6.3.4.2. Schemes based on Euclidean networks

The security of schemes based on Euclidean network structures involves different mathematical problems, such as the Bounded Distance Decoding Problem (BDD), the Shortest Vector Problem (SVP) or the resolution of linear systems of equations with errors (learning with errors (LWE)), in its original version or on rings (R-LWE). This family of mathematical problems differs from the previous group (factorization or discrete logarithm calculation) insofar as there are currently no known algorithms with the capacity to solve these problems in a much more efficient way on a quantum computer. For this reason, security schemes using these problems may be referred to as post-quantum: in the current state of the art, they are considered to be as resistant to quantum cryptanalysis as to classical cryptanalysis. This is a significant advantage in the long term, but comes at a high cost in terms of computation and data size, as we have seen.

The sticking point in this case is that these schemes are still relatively new, and the associated problems have received much less attention than their classic counterparts. This implies a less thorough understanding of their security. This consideration is particularly true for concrete security estimations, which go beyond reduction proofs and seek to find the best cryptanalysis strategies. From these cryptanalyses, relations between the parameters and the security level of the scheme can be deduced. This point is crucial, since the desired level of security and the duration of this security must be taken into account when deploying an application. The lack of stability in concrete security analysis also affects the choice of parameters; over-dimensioning is not an option, as the additional costs in terms of calculation and data size are not acceptable. This consideration does not preclude the use of these solutions, but is an important factor to bear in mind. Current research efforts are focused on analyzing the concrete deployment of these schemes, notably on the question of parameter choice and security. Increasing work is also being carried out in the field of cryptanalysis in order to develop understanding. Notable examples include some previous studies (Albrecht et al. 2015a, 2016; Peikert 2016; Bai et al. 2018; Albrecht et al. 2019; Bai et al. 2019; Espitau and Joux 2020) and the Martin Albrecht’s estimator¹⁷, which is updated as new developments occur, and is extremely useful for choosing parameters.

6.4.1.1. Principle and system architecture

Consider a case in which an employer wishes to implement a facial recognition authentication system at a company site, alongside the existing badge authentication strategy. To do this, the biometric credentials of a number of employees must be stored (and processed) on a server. Our aim is to reinforce the confidentiality of these credentials using a three-party system architecture: the employer, the employee (using an off-site enrollment procedure) and a third party, responsible for key management. This architecture is interesting in that responsibility for the confidentiality of the credentials is shared between the employer (who holds the encrypted credentials but does not have access to the decryption key) and the third party (who possesses the encryption and decryption keys but does not have access to the encrypted credentials). Evidently, our model is not resistant to collusion between the employer and the third party; nevertheless, it remains relatively acceptable, particularly if the third party is an IS security agency or a provider offering turnkey authentication solutions to multiple companies.

A high-level view of the system architecture is shown in Figure 6.4, with Dilbert and Dogbert in the roles of employee and third party, respectively.

The principle here is to use homomorphic encryption so that the employer’s server can process biometric references directly in the encrypted domain. The architecture guarantees the following properties:

• – the third-party key manager (Dogbert) possesses both the public and secret keys, pk and sk, of the homomorphic encryption system; however, they do not have access to the reference data;
• – the access control devices (Device) know the sk and have access to computation results (a distance to compare to a threshold), but not to the reference data;
• – the employer does not have the sk, and thus cannot access the reference data or the (encrypted) results of computations;
• – the employee (Dilbert) must be confident that the third-party key manager (Dogbert) will not collude with the employer.

6.4.1.2. The face-matching algorithm

The face-matching algorithm used in this case is the OpenIMAJ¹⁸ implementation of the LTP (Local Ternary Patterns) algorithm (Tan and Triggs 2007). OpenIMAJ is one of the reference libraries for multimedia data processing, and the algorithm in question is known to give good results, particularly in suboptimal lighting conditions.

First, enrollment is carried out using one or more photographs of an individual’s face. This phase relies on advanced image processing techniques, and produces a reference made up of 118 distance maps, M⁽⁰⁾, …, M⁽¹¹⁷⁾, each corresponding to an 80 × 80 matrix of values in [0, 1]. The authentication process also requires one or more photographs of the individual, and generates 118 sets of coefficient coordinates S⁽⁰⁾, …, S⁽¹¹⁷⁾. A detailed description of the operation of the algorithm lies outside the scope of this work; instead, we shall focus on the passage into the encrypted domain. Further details can be found in Tan and Triggs (2007).

The matching part of the algorithm is most relevant for our purposes, in terms of execution in the encrypted domain. Matching relies on the following calculation:

[6.2]

Given a threshold T, authentication will be successful if and fail otherwise. Typically, on an empirical base, a threshold value of T = 92 is appropriate.

6.4.1.3. Converting the algorithm to the encrypted domain

With respect to the system architecture presented above, equation [6.2] must be evaluated in the encrypted domain. Helpfully, this can be carried out using an additive encryption system, with the hypothesis that the authentication request (coordinate subsets) is sent in unencrypted form¹⁹.

Table 6.1 presents a summary of the results obtained when the Paillier cryptosystem is used for homomorphic evaluation (using GMP for the modular arithmetic and OpenMP for parallelization). The evaluation step notably takes less than 2 seconds using an 8-core processor, and can easily be shortened to less than 1 second by using a more powerful machine. The online execution time is thus eminently reasonable. Note, too, that similar execution times can be obtained using an SHE such as BGV, optimized for additive function and using batching capacities. Performance is therefore a relatively unimportant factor in the choice of approach.

6.4.2.1. Elementary medical diagnostics

Healthcare data are inherently highly personal in nature. The confidentiality of this data is a priority for both storage and processing solutions. Its sensitive nature means that medical diagnosis is a prime domain for the application of computation techniques using encrypted data. In this section, which draws on the work of (Carpov et al. 2016), we describe a medical diagnosis application used to evaluate an individual’s risk of cardiovascular disease. In this context, homomorphic encryption is used to ensure that the patient’s health data remains confidential.

The implemented algorithm evaluates a set of rules which, when activated, correspond to cardiovascular risk factors. The set of 11 rules is shown in Figure 6.5. The result of the algorithm is an integer between 0 and 9; a higher value denotes a higher risk of cardiovascular disease. The algorithm was implemented in C++ and compiled using the Cingulata compilation chain (see section 6.3.2.4). The highlighted terms in Figure 6.5 were processed in encrypted form. Although the algorithm is relatively simple in terms of computation requirements, it represents a certain reality in the context of online medical diagnostics, as an example of a relatively simple algorithm handling intrinsically personal, sensitive data.

Figure 6.6 gives a schematic overview of this application in a cloud implementation. The patient fills out a form (using an Android tablet), providing their medical data, and the cardiovascular risk assessment application is executed in the cloud. Transcryption is used in order to limit the volume of transmitted data (see section 6.3.3.2), and Kreyvium symmetric stream cipher is used to encrypt medical data sent to the cloud. The Kreyvium encryption key, SymKey, is in the tablet.

It is interesting to note that the transcryption key HomEnc(SymKey) is only sent to the cloud once, when the user registers. A public initialization vector IV, common to both parties, is used to synchronize the two streams in the transcryption process. The homomorphic execution of Kreyvium decryption, used to prepare the stream used for the transcryption operation, can be carried out offline by the cloud, in advance of the transaction itself, to minimize transaction length. This is one of the main advantages of this stream cipher-based transcryption solution.

Now, consider what happens online at the moment of transaction. Once the user’s data, encrypted using Kreyvium, is received by the cloud, the homomorphically encrypted Kreyvium stream (prepared in advance offline) is used for transcryption (a simple additive operation). In this way, the Cloud obtains the user’s medical data in a homomorphically encrypted form. The data then serve as input for the cardiovascular risk calculation algorithm, executed by the Cingulata environment in homomorphic form. The result of the calculation (the risk factor) is represented by four homomorphic numbers, one for each bit of the result. These ciphertexts are grouped into a single ciphertext using batching. The resulting ciphertext is sent back to the user’s tablet, which decrypts it using the secret key of the homomorphic scheme sk; the risk factor is then reconstructed from its binary form and displayed on the patient’s tablet.

6.4.2.1.2. Implementation and performance

The Android application on the patient side was developed in Java. Figure 6.7 shows a screenshot from the application, specifically the form into which the patient inserts their data. The BFV homomorphic encryption scheme (Fan and Vercauteren 2012), parameterized using 128 security bits, was used for homomorphic computations. The Kreyvium cryptosystem used in transcryption has a key length of 128 bits. Thus, in this configuration, the cloud diagnosis service offers end-to-end security of 128 bits. In terms of multiplicative depth, the Kreyvium algorithm has a depth of 12 and the risk calculation algorithm has a depth of 8. The leveled SHE library used here was then dimensioned to take a total multiplicative depth of 20 into account, in order to ensure error-free execution. Each homomorphic ciphertext has a size of around 250 kb.

During the first interaction between the patient and the cloud, the patient sends the transcryption key HomEnc(SymKey). This corresponds to 128 homomorphic ciphertexts (one per bit in the Kreyvium key). Hence, a total of ~32 Mb are sent to the cloud during this phase.

Since Kreyvium is used to send medical data to the cloud, the size of the encrypted payload transmitted over the network to the server is the same as that of the clear payload. The only additional element is the symmetric key encrypted using the homomorphic system: this is relatively small. Once the homomorphic calculation has been carried out, the patient or doctor receives a single ciphertext (~250 Kb) containing the encrypted result of the calculation. The total response time between the moment when the tablet sends the data and the moment the result of the calculation is received is less than 4 seconds, of which ~3.2 seconds are taken up by the homomorphic execution of the diagnostic algorithm.. The homomorphic execution of the Kreyvium decryption algorithm prior to transcryption takes around 8 minutes: this is why this step should be carried out in advance, offline.

6.4.2.2. Medical diagnostics using artificial neural networks

Cardiac arrhythmia corresponds to a set of conditions which causes an irregular heartbeat. While some of these conditions are relatively benign, others cause more or less problematic symptoms. For certain chronic patients, electrocardiogram (EKG) monitoring is crucial for identifying arrhythmia as soon as it occurs to prevent their state from worsening.