# Cryptosystem Conversion, Packing and Matrix Processing of Homomorphically Encrypted Data: Application to IOT Devices

Maxime Pistono, Reda Bellafqira, Gouenou Coatrieux

► To cite this version:

Maxime Pistono, Reda Bellafqira, Gouenou Coatrieux. Cryptosystem Conversion, Packing and Matrix Processing of Homomorphically Encrypted Data: Application to IOT Devices. IEEE Access, 2021, 9, pp.28302 - 28316. 10.1109/access.2021.3058849. hal-05067804

HAL Id: hal-05067804

https://hal.science/hal-05067804v1

Submitted on 14 May 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Received January 13, 2021, accepted February 6, 2021, date of publication February 11, 2021, date of current version February 23, 2021.

Digital Object Identifier 10.1109/ACCESS.2021.3058849

# Cryptosystem Conversion, Packing and Matrix Processing of Homomorphically Encrypted Data: Application to IOT Devices

MAXIME PISTONO<sup>①</sup>, (Member, IEEE), REDA BELLAQIRA<sup>①</sup>, (Member, IEEE), AND GOUENOU COATRIEUX<sup>①</sup>, (Senior Member, IEEE)

Institut Mines-Telecom, IMT Atlantique, Inserm, UMR 1101, 29238 Brest, France

Corresponding author: Maxime Pistono (maxime.pistono@imt-atlantique.fr)

This work was supported in part by the French Government support granted by the National Research Agency in the Investing for the Future Program under Grant ANR-17-RHU-0005-Followknee Project, and in part by the Joint Laboratory SePEMeD.

**ABSTRACT** In this paper, we propose a secure protocol that allows processing encrypted data emitted by an IOT device with low computational capabilities. Its originality is threefold. It first relies on a new fast algorithm which makes possible the conversion of Combined Linear Congruential Generator (CLCG) encrypted IOT data into data homomorphically encrypted with the Damgard-Jurik (D-J) cryptosystem. In second, an original data packing strategy is given so as to reduce communication and computation complexity as well as process several D-J encrypted data at once by means of matrix operations. In third, we introduce a crypto-watermarking based integrity control mechanism. This one combines the lightweight hash function Quark with LSB substitution so as to offer the capability to check the integrity of CLCG encrypted data. We illustrate the deployment of our protocol, in the case an honest-but-curious or malicious third party wants to process encrypted data issued from a real connected knee prosthesis. We theoretically and experimentally demonstrate the performance of our solution. This one can nearly process 500 samples every second. Beyond, our proposal is suited to the general case of IOT.

**INDEX TERMS** Confidentiality, integrity, secure data processing, homomorphic encryption, crypto-watermarking, implemented medical devices.

## I. INTRODUCTION

Nowadays there are billions of IOT (Internet Of Things) devices [1]. In the medical domain they are called to play an important role, offering the capability to better monitor vital signs of patients at the hospital [2] or outside [3]. Among the various type of IOT medical devices [4], [5], connected Implantable Medical Devices (IMDs) constitute a specific class. They include pacemaker, insulin pump, neural implant, prosthesis and so on. If IMDs can have a direct and automatic impact on the patient health (e.g. heart rhythm regulation), they have communication facilities so as to transfer different kind of measurements or for updating purpose (e.g. reconfiguration). In that respect, one IMD has to interact with an external device, this one being a specific terminal [6], [7] or a general public device (e.g. a tablet) [8], providing various functionalities to practitioners like data display and data

The associate editor coordinating the review of this manuscript and approving it for publication was Chao Shen<sup>①</sup>.

processing [2], [9]. Going toward a more general framework (see Fig.1), IMD data can be sent by the external device to a server so as to be mutualized for big health data purposes, for instance [10]. Beyond their innovative character, such IMD collect, transmit and process data that are considered as very sensitive in respect to many international and national regulations (e.g. European General Data Protection Regulation 2016/679 [11], FDA [12]). IMD data are also submitted to various security threats the consequences of which can be dramatic medical adverse events [13]. In such a context, one has to consider the following data security requirements as defined by NIST [14]:

* **Confidentiality:** the property that data or information is not made available or disclosed to unauthorized persons or processes.

* **Integrity:** a property possessed by data items that have not been altered in an unauthorized manner since they were created, transmitted or stored.
<figure><img src="image_2.png" /><figcaption>**FIGURE 1.** Our IMD framework: a connected knee prosthesis (IMD) provides measurements to a Human Machine Interface (HMI) integrated into a mobile device. HMI processes data and acts as a proxy for data transmission to a server.</figcaption></figure>

* **Privacy:** the right of a party to maintain control over and confidentiality of information about itself.

In this work, and as depicted in Fig.1, we are interested in the security in terms of confidentiality and integrity of data emitted by one IMD at destination to a server while leaving toe capacity to a third party, like an external device equipped of a human machine interface (HMI), to process data without endangering IMD data confidentiality and privacy. To the best of our knowledge, this question is still an open issue strengthened by the fact that IMDs are devices with very low memory, battery and computing capabilities.

Different solutions were proposed in order to ensure the confidentiality of IMD data. Among them, the recent Cloakers [7] or IMDguard [6] rely on an external device (ED) for opening a secure communication channel with IMD and jam communications in case of attacks. As EDs are less resource constrained than IMDs, they can use public key encryption such as ElGamal [15] and RSA [16] or symmetric encryption algorithms like AES [17]. A first drawback of these solutions is that ED decrypts IMD data. Thus, if an attacker takes the control of the device, data privacy is endangered. A second is that the symmetric cryptosystems they use do not allow processing data under their encrypted form. In this work we want to go further, with the objective to let HMI securely processes IMD data.

When focusing on secure data processing, whatever the application domain, most solutions make use and of homomorphic encryption (HE) combined or not with secure multiparty computation (SMC). The interest of a HE is that it allows performing operations (e.g. +, ×) over encrypted data with the guarantee that the decrypted result equals to the one carried out onto un-encrypted data. HE is associated with SMC so as to share between different entities the computations HE is not able to conduct (e.g. division, comparison). Note that as the computation complexity and memory needs of HE are much higher than for conventional cryptosystems, they cannot be implemented into IMD. That is not the case of HMI, this one being for instance implemented into a smartphone or in a computer. So, the open issue is how IMD can send encrypted data to HMI in such a way HMI can securely process IMD data.

Regarding the protection of the authenticity and integrity of data, different strategies can be used: message authentication codes (MAC), signature based protocols (SBP),

watermarking and crypto-watermarking. MAC techniques [18] basically compute a cryptographic hash of the data that is next transmitted along with the data. At the reception, any differences between the received and the recomputed hash will indicate a data integrity loss. SBP such as the Digital Signature Algorithm (DSA) [19] can be seen as an extension of the previous strategy. By asymmetrically encrypting a cryptographic hash, they ensure both data integrity and non-repudiation. Differently, the basic idea of watermarking consists in inserting/embedding a data integrity proof like a secret message directly into the data themselves by imperceptibly modifying them [20], [21]. Integrity checking can rely on the verification of the presence of the secret message in the watermarked data. More recently, several crypto-watermarking schemes [22] combining encryption and watermarking have been proposed. Herein, data confidentiality is ensured by encryption while watermarking based security services (e.g. integrity, traceability, ownership protection) can be made available from encrypted and/or decrypted data. One can distinguish these schemes depending on the domain where the watermark can be accessed [23]: *in the clear domain* [24] - usually it is required to decrypt the data before accessing to the watermark; *in the encrypted domain* [25] - most solutions are joint-watermarking encryption schemes that simultaneously conduct encryption and watermarking operations; *in both encrypted and clear domains* [26], [27] - such methods usually take advantage of partial, invariant or homomorphic encryption. In this work, we are interested in integrating a joint crypto-watermarking scheme for verifying the integrity of IMD data without decrypting them.

In this paper, we propose a new protocol that allows an honest but curious and malicious third party (HMI) to securely process data issued from a connected and resource constrained medical implant (IMD). Our contribution are as follow:

1. In order to encrypt data sent by the resource constrained IMD, we use the lightweight stream cipher CLCG. We choose CLCG due to the fact that it is fast in terms of computation and easy to integrate in IMD contrarily to existing lightweight stream cipher algorithms such as Trivium, Grain or MICKEY.

2. In addition, we propose a new cryptosystem conversion, where CLCG encrypted data are transformed into additively homomorphically encrypted data without being decrypted at any moment. By doing so, data confidentiality is ensured without discontinuity, and homomorphically encrypted data can be processed by HMI without endangering privacy. Even though we opted for the Damgard-Jurik (D-J) cryptosystem because of its simplicity and efficiency, our CRC procedure can be generalized to all homomorphic additive cryptosystems under the constraint that the plaintext spaces of CLCG and of the homomorphic cryptosystem are of same dimensions (i.e. they can encrypt messages of same maximum size).
3) Based on the fact the plaintext space of additive homomorphic cryptosystems is usually of very high dimension; e.g. in the case of a public key of 2048 bits, the D-J cryptosystem encrypts messages of 2048 bit long; we introduce an original data packing strategy. On one hand, this one allows securely transmitting several data at once (decreasing communication cost) and, on the other hand, the processing of data in a parallel manner (decreasing computation cost).

4) The previous solutions respond to threats considering HMI is honest but curious. In order to go further in a scenario where a HMI is malicious and changes the way data are processed so as to try to infer medical data from their encrypted form, we propose a zero-knowledge proof of work to detect HMI misbehavior.

5) Finally, another originality of this work stands on the use of a crypto-watermarking based security service [22] any third party can use to check the integrity of CLCG encrypted data without decrypting them. This one relies on the combination of the Quark lightweight hash function [28] with the least significant bit substitution watermarking modulation and CLCG.

The rest of this paper is organized as follows. Section II regroups some preliminaries on different functions and tools on which our protocol relies: the D-J cryptosystem and the CLCG stream cipher. We then depict our approach along with its general framework in Section III. Some theoretical and experimental results are given in Section IV. Before concluding, we discuss of different attacks and analyze the security of our protocol in Section V.

## II. PRELIMINARIES

### A. DAMGARD-JURIK (D-J) HOMOMORPHIC CRYPTO SYSTEM

The Damgard-Jurik cryptosystem [29] is an additively homomorphic cryptosystem with a good trade off in terms of computation complexity and ciphertext expansion (i.e. the ratio between the space dimensions of the plaintext and the ciphertext). It is the generalisation of the Pailler cryptosystem [30] and it is defined as follows. Let $((g, K_p), K_s)$ be the public/private key pair:

$$K_p = pq \quad \text{and} \quad K_s = \text{LCM}((p-1), (q-1)) \quad (1)$$

where: LCM is the least common multiple function; p and q are two large prime integers. $\mathbb{Z}_{K_p^n} = \{0, 1, \dots, K_p^n - 1\}$ and $\mathbb{Z}_{K_p^n}^*$ denotes the integers that have multiplicative inverses modulo $K_p^n$ where n is the D-J exponent, a non-zero positive integer. We choose $g \in \mathbb{Z}_{K_p^{n+1}}^*$ such that $g = (1 + K_p)^j x$ mod $K_p^{n+1}$, where j is a known relatively prime to n and $x \in \{t^{K_p^n} | t \in \mathbb{Z}_{K_p}^*\}$. A fast implementation of this cryptosystem can be achieved without reducing its security by choosing [29]:

$$g = 1 + K_p \quad (2)$$

Thus, the encryption of a plaintext $m \in \mathbb{Z}_{K_p^n}$ into the ciphertext $c \in \mathbb{Z}_{K_p^{n+1}}^*$ using the public key $K_p^n$ is given by:

$$c = E[m, r] = g^m r^{K_p^n} \mod K_p^{n+1} \quad (3)$$

where $r \in \mathbb{Z}_{K_p}^*$ is a random integer that makes the D-J cryptosystem probabilistic or semantically secure. More clearly, the ciphertext of one plaintext changes depending on the value of r.

To get access to the message m from $c^{K_s}$, the decoder has to calculate $K_s m$. To do so, Damgard and Jurik propose an iterative procedure with as objective to find m from $(1 + K_p)^m \mod K_p^{n+1}$ [31]. This procedure takes advantage of the Binomial theorem and a function $L(\cdot)$ defined such as $L(b) = \frac{b-1}{K_p}$, function that is applied repeatedly as follows. Taking as input the quantity $a = (1 + K_p)^m \mod K_p^{n+1}$ this algorithm first computes $L(a)$ so as to get $m_1 = L(a \mod K_p^2) = m \mod K_p$ (using the Binomial theorem) and then iteratively calculates from $j = 0$ to $n$, $m_j$:

$$L(a \mod K_p^{j+1}) - (C_2^{m_j-1} K_p + \dots + C_j^{m_j-1} K_p^{j-1}) \mod K_p^j \quad (4)$$

The algorithm achieves $m_n = m \mod K_p^n$ where $C_k^j = \frac{j!}{(j-k)!k!}$. This procedure, we note as the function $F(\cdot)$, is given in Algorithm 1.

<caption>**Algorithm 1** Damgard-Jurik Algorithm for the Function $F(\cdot)$</caption>

1: **procedure** F(a)
2:     $m \leftarrow 0$
3:     **for** j $\leftarrow 1, n$ **do**
4:         $t_1 \leftarrow L(a \mod K_p^{j+1})$
5:         $t_2 \leftarrow m$
6:         **for** k $\leftarrow 2, j$ **do**
7:             $m \leftarrow m - 1$
8:             $t_2 \leftarrow t_2 * m \mod K_p^j$
9:             $t_1 \leftarrow t_1 - \frac{t_2 * K_p^{k-1}}{k!} \mod K_p^j \quad t_1 = t_1 - C_k^i K_p^{k-1}$
10:          **end for**
11:      $m \leftarrow t_1$
12:      **end for**
13:      **return** m $\mod K_p^n$
14: **end procedure**

The decryption of the cipher-text $c$ into $m$ is such as:

$$m = F(c^{K_s}) K_s^{-1} \mod K_p^n \quad (5)$$

The D-J cryptosystem has two homomorphic properties. Considering two plaintexts $m_1$ and $m_2$ and two random integers $r_1$ and $r_2$, then:

$$E[m_1, r_1]E[m_2, r_2] = E[m_1 + m_2, r_1 r_2] \quad (6)$$

$$E[m_1, r_1]^{m_2} = E[m_1 m_2, r_1^{m_2}] \quad (7)$$

### B. STREAM CIPHER ENCRYPTION

Stream ciphers are well adapted for encrypting stream of data in environments of limited resources, like IMDs. With such a
scheme, the encryption of one piece of data $d_i$ is the result of the modular sum or XOR in-between $d_i$ and the output $Z_i$ of a stream cipher function: a pseudo random generator initiated with a secret key or seed.

In this work, we opted for the CLCG (Combined Linear Congruential Generator) [32] cryptosystem. CLCG is a fast and easy to implement stream cipher on IMD resource constrained devices. Moreover contrarily to other stream cipher such as Trivium or Grain their exist a technique to convert CLCG encrypted data to additively homomorphic encrypted one.

One output of the CLCG pseudo random generator is the modular sum of the outputs of at least two Linear Congruence Generators (LCGs). The $i^{th}$ output $X_i$ issued by a LCG is defined as:

$$X_i = aX_{i-1} + c \mod m \quad (8)$$

where: a is a multiplier; c is an increment; m is the modulo and $X_0$ is the seed or, equivalently, the secret LCG key. In the case of two LCGs, the CLCG output $Z_i$ is such as:

$$\begin{aligned} Z_i &= X_i + Y_i \mod m \\ &= a_X X_{i-1} + c_X + a_Y Y_{i-1} + c_Y \mod m \end{aligned} \quad (9)$$

The CLCG encryption $c_i$ of the piece of data $d_i$ is given by:

$$c_i = d_i + Z_i \mod m \quad (10)$$

Notice that, as long as seed = {$X_0, Y_0, c_X, c_Y$} remains unknown, the knowledge of the parameters ($a_X, a_Y$) and/or of the modulo m does not endanger the security of this stream cipher (see [33] for more details). From a cryptographic point of view, the security of CLCG is not perfect but, as we will see in Section V, it is sufficient to cover the needs of our application framework.

### III. SECURE PROCESSING FRAMEWORK OF IMD DATA

In this Section, we first position our connected implantable medical device (CIMD) framework along with its security constraints. We then introduce a secure CIMD protocol where IMD sends data, sample by sample, before presenting its extension, i.e. our complete proposal, based on data packing.

#### A. CONNECTED IMPLANTABLE MEDICAL DEVICE (CIMD) FRAMEWORK

The framework we consider is given in Fig.1 where a connected medical implant (IMD) sends data to a human machine interface (HMI) on an external device. HMI serves as a proxy and transfers data to a server (Server) for data storage and future data reuse. We further assume that HMI is capable to process data so as to provide different kind of services to the HMI user (e.g. practitioner, patient). Even though this framework is quite general, it is instantiated as part of the Followknee project<fnref n="1" /> the objective of which is to create

a connected knee prosthesis which collects measures from different biological sensors. Herein, the objective of HMI is to filter such measures and to raise an alarm to alert the patient in case of abnormal results, that is to say when the filter output is above a specific threshold. In that respect, let us consider IMD acquires M samples {$d_i$}$_{i=0,...,M-1}$. Filtering, thresholding and decision of HMI can be summed depending on the sign of the value A defined as:

$$A = \sum_{i} w_{i}d_{i} - s \quad (11)$$

where {$w_i$}$_{i=0,...,M-1}$ denote the HMI filter weight and s the alarm threshold. If A is positive, the filter output is above the threshold and HMI emits an alert. As we will see thereafter, writing will simplify some of our secure processing.

The security hypotheses considered in this scenario are the following ones. All entities: IMD, HMI and Server identify themselves by means of a common dual authentication protocol like AES-XMAC [34]. Because IMD data are medical data, they are confidential and should not be known from HMI. On its side, IMD is assumed to be an honest entity. Being implanted, taking materially the control of it is quite impossible. An original hypothesis considered in our framework is that the filter weights and the threshold are confidential from the HMI point of view. Indeed, one can consider that HMI Company has patented these pieces of information so as to provide an added value service; service it offers through a Service Level Agreement (SLA) stating that HMI and Server will not try to infer processing parameters. As a consequence s and {$w_i$}$_{i=0,...,M-1}$ should not be disclosed to Server; HMI and Server are assumed to be honest but curious adversaries. They will conduct their task appropriately but they may try to infer medical data, filtering and decision parameters, respectively. At the same time, because the HMI device can be hacked or stolen it is considered as an untrusted device. Table 1 resumes what can be known from each entity. Beyond data confidentiality, it is also important that HMI and Server can check if IMD data integrity before processing them. In a second time, we will consider another scenario where HMI becomes malicious aiming at discovering data and parameters.

<table><caption>TABLE 1. Confidentiality issues in our framework; ✓ indicates if the entity can access to a one data in a clear form.</caption><thead><tr><th></th><th>IMD</th><th>HMI</th><th>Server</th></tr></thead><tbody><tr><td>IMD data $d_i$</td><td>✓</td><td></td><td>✓</td></tr><tr><td>Filter weights $w_i$</td><td></td><td>✓</td><td></td></tr><tr><td>Threshold $s$</td><td></td><td>✓</td><td></td></tr><tr><td>Threshold & filter output difference $A$</td><td></td><td></td><td>✓</td></tr><tr><td>Sign of $A$</td><td></td><td>✓</td><td>✓</td></tr></tbody></table>

#### B. SECURE CIMD FRAMEWORK

This first solution, depicted in Fig.2, processes IMD data sample by sample. It relies on several contributions, taking especially into account the fact that IMD is resource constrained.

<footnote n="1">¹Followknee project under reference ANR-17-RHU-0005</footnote>
<figure><img src="image_3.png" /><figcaption>FIGURE 2. Proposed secure CIMD framework without data packing.</figcaption></figure>

In a first time, to ensure data confidentiality, IMD CLCG encrypts its data {$d_i$}$_{i=0,...,M-1}$, before sending them to HMI. As we will see in Section IV, CLCG complexity is low enough to be integrated into a micro-controller unit. In a second time, to make possible the secure processing of IMD data by HMI, we propose an original cryptosystem conversion algorithm (CrC) that allows turning CLCG encrypted data into D-J encrypted data. By doing so, HMI can thus homomorphically process data taking advantage of the mobile device computation power. It is important to notice, that all process in the D-J domain are conducted under the public-key of Server so as to ensure IMD data security. Using the public-key of HMI is a non-sense due to the fact it would be able to decipher data. As third contribution, we suggest a crypto-watermarking tool that gives access to a watermarking based integrity service available from CLCG encrypted data. In the following subsections, we go into the details of each of these contributions. We will see in the Section III-C, how this protocol can be strongly improved in terms of computation and commutation complexities with the help of an original data packing strategy.

1) CRYPTOSYSTEM CONVERSION (CrC)

The idea to convert data encrypted with a non-homomorphic cryptosystem into homomorphically encrypted data is not new. One can for example refer to [35] where AES is evaluated with the BGV cryptosystem [36] with approximately 40 minutes for encrypting an AES block. Reference [37] studies the Salsa20 stream cipher but its authors do not expect its computation in any reasonable amount of time due to the homomorphic cryptosystem they exploit. More recently, [38] proposes to convert TRIVIUM encrypted data into fully homomorphically encrypted data. However, the complexity of this solution remains limited in practice.

In this work, the cryptosystem conversion (CrC) solution we propose turns CLCG encrypted data into D-J encrypted data. It relies on, what we name, a Secure Combined Linear Congruential Generator Cryptosystem (SCLCG) that is the implementation of CLCG cryptosystem into the D-J encrypted domain. To make this possible, the CLCG modulo m in (8) should be equal to the user D-J public key $K_p^n$. Doing

so (9) can then be expressed in the D-J domain as:

$$E[Z_{i+1}, r_{Z,i+1}] = E[X_{i+1}, r_{X,i+1}]E[Y_{i+1}, r_{Y,i+1}] \quad (12)$$

where:

$$ \begin{aligned} E[X_{i+1}, r_{X,i+1}] &= E[X_i, r_{X,i}]^{a_X} E[c_X, r_{c_X}] \\ &= E[a_X X_i + c_X, r_{X,i}^{a_X} r_{c_X}] \end{aligned} \quad (13) $$

$$ \begin{aligned} E[Y_{i+1}, r_{Y,i+1}] &= E[Y_i, r_{Y,i}]^{a_Y} E[c_Y, r_{c_Y}] \\ &= E[a_Y Y_i + c_Y, r_{Y,i}^{a_Y} r_{c_Y}] \end{aligned} \quad (14) $$

The secret key of our Secure SCLCG $E[K_c]$ is composed of:

$$ \{E[X_0, r_{X,0}], E[Y_0, r_{Y,0}], E[c_X, r_{c_X}], E[c_Y, r_{c_Y}]\} \quad (15) $$

Notice that because $m = K_p^n$, the CLCG period is extremely long. In the case $K_p^n$ is coded $\lambda = 2048$ bits, the CLCG period is bounded by $K_p^n - 1 \le 2^{2048}$ [39]. Such a period ensures the algorithm security and the unpredictability of CLCG outputs. Coming back to our SCLCG, one can see from (13) and (14) that multipliers $(a_X, a_Y)$ are not encrypted. This does not reduce the SCLCG security as CLCG parameters $(a_X, a_Y)$ are not supposed to be secret [33]. As defined, SCLCG allows thus encrypting/decrypting CLCG data into the D-J domain. Compared to existing approaches, it is of much lower computation and communication complexities and, it relies on an additive HE cryptosystem widely used in practical secure processing [40], [41].

Let us come back to our secure CIMD framework and let us assume IMD uses the CLCG secret key $K_c$. In order, to decipher the $i^{th}$ CLCG encrypted data $c_i = d_i + Z_i \mod m$ in the D-J domain, IMD and HMI conduct the following steps:

1) As part of an initialization step, IMD has sent to HMI the SCLCG secret key $E[K_c]$ and $a_X$ and $a_Y$ in a clear form.

2) Based on the Server D-J public key $K_p^n$, HMI computes the D-J encrypted version of $d_i + Z_i$ with the random value 1: $E[d_i + Z_i, 1] = g^{d_i+Z_i} \mod K_p^{n+1}$.

3) Using SCLCG parameterized with $E[K_c], a_X$ and $a_Y$, HMI computes $E[Z_i, r_{Z,i}]$ using (12).

4) Finally, to get access to the D-J version of $d_i$ HMI computes:

$$ E[d_i, r_{Z,i}^{-1}] = E[d_i + Z_i, 1] \times E[Z_i, r_{Z,i}]^{-1} \quad (16) $$

To sum up, this conversion procedure simply consists in subtracting the CLCG random value $Z_i$ to $d_i + Z_i$ in the D-J domain. It is important to notice that because HMI has no idea about the random value $r_{Z,i}$, it has no clues about $d_i$ from $E[d_i, r_{Z,i}^{-1}]$.

Before detailing how to process these homomorphically encrypted data let us come back on our choice of CLCG and D-J cryptosystems. In a first time, CLCG is of much smaller computation complexity than, for instance, TRIVIUM. It is thus well adapted to our framework where IMD has really limited resources, but is not as secure as TRIVIUM. As we
will see in Section V, its security is however sufficient in our application framework. In second and as demonstrated above, CLCG ciphertext can be converted into additively homomorphic encrypted data whereas the conversion of TRIVIUM ciphertext requires the use of a fully homomorphic cryptosystem as shown in [38]. But, because of the high computation complexity of such fully homomorphic cryptosystems and of their ciphertext expansion, they are not suitable for devices with low computation capacities. In our framework, HMI which should run on a smartphone.

## 2) ANALYZING HOMOMORPHICALLY ENCRYPTED DATA

As stated in Section III-A, the objective is to allow HMI to securely filter IMD data and threshold the filter output so as to raise or not an alarm to the patient. Several well-known issues have to be considered when filtering data in the homomorphic domain [42]: negative numbers, fractional numbers, ... In this section and in order to alleviate the presentation of our proposal, we consider that the IMD data {$d_i$}$_{i=0,...,M-1}$, the threshold s and the HMI filter weights {$w_i$}$_{i=0,...,M-1}$ are integers. One can refer to [42] for a strategy for managing fractional and real numbers. In that respect, once HMI accesses to D-J encrypted data {$E[d_i, r_{Z,i}^{-1}]$}$_{i=0,...,M-1}$ under the Server public key, it computes the secure filtering operation in the D-J domain, that is to say:

$$ 
\begin{aligned}
F &= \prod_{i=0}^{M-1} E[d_i, r_{Z,i}^{-1}]^{w_i} = \prod_{i=0}^{M-1} E[w_i d_i, r_{Z,i}^{-w_i}] \\
&= E[\sum_{i=0}^{M-1} w_i d_i, \prod_{i=0}^{M-1} r_{Z,i}^{-w_i}]
\end{aligned} 
\quad (17) 
$$

By next, HMI needs to make a secure comparison so as to raise an alarm if necessary. The very first solution to the secure comparison problem was developed by Yao using the garbled circuit [43]. Since then various approaches relying on homomorphic encryption such as DGK [44] were proposed. If garbled circuit suffers of very high communication complexity, the drawback of the HE based solutions is their high computation complexity. At present and even though it has been proposed a long time ago, KBH [40] is still one of the best solution for secure comparison due to its simplicity, its low computation and communication complexity thanks to the combination of additive HE [30] and multiplicative data blinding. However, KBH do not perform well in our framework, due to the fact: i) KBH assumes that each party involved in the protocol has access to all encrypted data to compare. This is not our case as we suppose that only HMI has encrypted data; ii) it is based on a HE collaborative decryption procedure to access to the comparison result, where this procedure is not given in the paper. Nevertheless and as we will see in the experimental Section IV, we have compare it to our proposal in term of performance. Anyway, the protocol we propose is depicted in Fig.2 and works as follows:

1) After having converted CLCG data into D-J encrypted data, and conducted the secure filtering operation (17), HMI computes still in the D-J domain the difference between the filtered output and the threshold s.

$$ 
\begin{aligned}
C &= E[\sum_{i} w_i d_i, \prod_{i} r_{Z,i}^{-w_i}] \times E[-s, 1] \\
&= E[\sum_{i} w_i d_i - s, \prod_{i} r_{Z,i}^{-w_i}]
\end{aligned} 
\quad (18) 
$$

2) HMI generates two random values r, r' such that: $r' \ll r$ and applies multiplicative hiding as in [40]:

$$ C^r \times E[-r', 1] = E[r(\sum_{i} w_i d_i - s) - r', (\prod_{i} r_{Z,i}^{-w_i})^r] \quad (19) $$

and sends the result to Server.

3) Server decrypts the message using its D-J private key $K_s$ obtaining:

$$ A = r(\sum_{i} w_i d_i - s) - r' \mod K_p^n \quad (20) $$

Depending on if A is positive or negative, Server sends to HMI 0 or 1, respectively. Due to the fact $r' \ll r$ the sign of (20) is the same as the one of $\sum_i w_i d_i - s$.

As stated in [40], the multiplicative hidden value (20) gives no clues about s, ($w_i$)$_i$ and ($d_i$)$_i$. Ensuring thus that Server cannot infer HMI filter weights and threshold.

This secure analysis procedure ends our secure CIMD protocol. In the next section, we propose to improve it with the help of a crypto-watermarking service for protecting the integrity of CLCG encrypted data.

## 3) CRYPTO-WATERMARKING FOR DATA INTEGRITY PROTECTION

Our basic idea in order to make possible the integrity verification of IMD CLCG encrypted data without decrypting them is to crypto-watermark them with a secret message. Integrity is verified based on the verification of the message.

Let us consider an IMD data sample $d_i$. One bit $b_k$ of a watermark {$b_k$}$_{k=1,...,M}$ is crypto-watermarked by turning $d_i$ into $d_i^w$ so that a secretly selected bit from the cryptographic hash of the CLCG encrypted version of $d_i^w$ equals $b_k$. The hash bit selection depends on a secret watermarking key $K_w$. This insertion procedure can be expressed as follows:

$$ f_{K_w}^e(H(E(d_i^w))) = b_k \quad (21) $$

where: $H(\cdot)$ is a cryptographic hash function; $E(\cdot)$ is the CLCG cryptosystem; $K_w$ is the secret watermarking key; and $f_{K_w}^e(\cdot)$ is the watermark extraction function - based on $K_w$. $f_{K_w}^e(\cdot)$ extracts the value of the bit at a specific position in the binary representation of its input. In this work, due to the limited computation power of the IMD, we opted for the Quark-U hash function [28] and for the least significant bit watermarking modulation. This latter simply consists in flipping some least significant bits (LSBs) of the data to
<figure><img src="image_4.png" /><figcaption>FIGURE 3. Crypto-watermarking for integrity control service.</figcaption></figure>

watermark (i.e. $d_i$ in our case). Algorithm 2 sums up the insertion procedure we propose. As it can be seen, this one is iterative. It flips bits of $d_i^w$ until (21) is verified. At the reading stage, one just as to use $f_{K_w}^e$ to extract $b_k$. Dist represents the maximum number of IMD data sample LSBs that can be modified for message insertion. As defined, our crypto-watermarking procedure is probabilistic and it is possible it fails to watermark $d_i$ so that (21) is satisfied. But, such a situation is unlikely to happen. Indeed, assuming that the hash function is perfect (i.e. output is supposed to be uniformly distributed at random), the probability not being able to insert one bit is upper bounded by $1/2^{2Dist}$.

<caption>**Algorithm 2 Watermarking-Encryption**</caption>

procedure E(d_i^w)
    d_i^w = d_i
    j = 1
    while f_{K_w}^e(H(E(d_i^w))) ≠ b_k and log₂(j) ≤ Dist do
        d_i^w = d_i ⊕ j
        j = j + 1
    end while
    return E(d_i^w)
end procedure

Fig.3 exposes how this crypto-watermarking scheme is used in our framework. As shown, IMD and HMI as well as Server first agree on a watermark {$b_k$}$_{k=1,...,M}$: an integrity control sequence ICS. ICS is integrated into IMD at its initialization step and is crypto-watermarked each time IMD sends data. As IMD may send more data than the ICS length, ICS is repetitively embedded. Based on ICS, $K_w$, $f_{K_w}^e$() HMI and Server will be able to verify the integrity of IMD CLCG data without decrypting them by comparing ICS to the extracted bit sequence ICS$^e$. Any differences will indicate a data integrity loss. Under the hypothesis the cryptographic hash function is perfect, if an attacker modifies data during their transmission, HMI and Server have one chance out of two to detect a data sample (i.e. $d_i$) has been modified. In the case integrity control is conducted at the level of the whole ICS sequence, then the probability of false detection is upper bounded by $1/2^M$.

It is important to notice that the crypto-watermarking scheme we use introduces a definitive information loss on IMD sensor samples. However, being based on the LSB substitution watermarking modulation with a distortion parameter Dist = 1 or 2, the induced distortion is very low and considered as acceptable as discussed in [23], [24], [45]–[47].

One alternative would have been to exploit reversible watermarking [48]. The reversibility property ensures that it is possible to remove the watermark so as to to exactly recover the original data. However, such algorithms imposes many additional computations (e.g., sample prediction, histogram calculation, overflow and underflow management [49]) as well as an increase in terms of memory needs. It is not possible to envision at the moment their integration into a resource constrained device like IMD.

### C. DATA PACKING AND COMMUNICATION COMPLEXITY REDUCTION

As stated previously, we propose to improve the previous solution in terms of communication and computation complexities with the help of an original data packing strategy. Our basic idea is to CLCG encrypt several IMD pieces of data at once, while giving the capacity to HMI to also process these data at once. Indeed, due to the fact our CrC algorithm imposes the CLCG and D-J cryptosystems to use the same modulo $m = K_p^n$, where $K_p^n$ is the Server D-J public key of size $\lambda$ bits, a CLCG encrypted IMD piece of data is encoded on $\lambda$ bits. $\lambda$ being usually greater than 2048 bits for D-J cryptosystem security (see Section II-A), this induces a large data expansion. Indeed IMD data are encoded with much less bits (e.g. 8, 16, 32 bits). Another consequence of such expansion is a high communication cost as $\lambda$ bits are transmitted for each IMD sample. Our packing strategy organizes IMD data samples into a vector form with the capability for HMI to filter data through matrix operations. As we will see, such strategy drastically reduces the overall communication complexity between entities and of the HMI computation requirements.

#### 1) D-J DATA PACKING AND FILTERING OPERATIONS

Data packing before encrypting data is essentially studied in the case of fully HE, being referred as Single Instruction Multiple Data (SIMD) [50]. Fully HE has interesting bitwise operations that makes possible encrypting several pieces of data at once with the capacity to extract or process them independently. Doing so with partially HE is more difficult. In the context of deep learning, authors of [51] propose to process $N$ $l$-bit messages {$d_j$}$_{j=0,...,N-1}$ concatenated into a vector with $N = \lambda/l$, before partially HE encrypt the resulting integer value $D$:

$$D = d_0 + d_1 2^l + \dots + d_{N-1} 2^{l(N-1)} \quad (22)$$

Under this form, one can process $D$ in a whole but it is not possible to process independently the values {$d_j$}$_{j=0,...,N-1}$ due to the fact additive HE does not allow linearly processing or extracting pieces of data encrypted in a single vector. But if this is impossible, we show in the sequel that one can linearly filter data of same position from different vectors {$D_i$}$_{i=0,...,M-1}$ at once. To achieve this goal, the main question to answer is: “how to organize pieces of data in vector?”.

To simplify the presentation of our packing strategy, let us take into account our applicative framework where IMD will
CLCG encrypts, in a single $\lambda$ bit vector $N$ samples issued from $N$ different sensors for instance. Let us also consider in a first time that samples and filter weights are positive integers. We will depict the general case later on. To process $M$ samples $\{d_{i,j}\}_{i=0,...,M-1}$ from the $j^{th}$ sensor, HMI has to calculate:

$$a_j = \sum_{i=0}^{M-1} w_{i,j} d_{i,j} \quad (23)$$

where $a_j$ is the filter output and $\{w_{i,j}\}_{i=0,...,M-1}$, $\{d_{i,j}\}_{i=0,...,M-1}$ the filter weights. Considering $M$ vectors $\{D_i\}_{i=0,...,M-1}$, (23) can be expressed as a matrices product:

$$A = D^t W \quad (24)$$

Due to some D-J cryptosystem constraints, on which we will come back, it is not possible to apply different filters to each sensors. More clearly, in the D-J encrypted domain, HMI will only be able to apply the same filter to each column with as consequence that $\forall j, w_{i,j} = w_i$. Doing so, (24) is written as:

$$A = \begin{bmatrix} a_0 \\ \vdots \\ a_j \\ \vdots \\ a_{N-1} \end{bmatrix} = \begin{bmatrix} d_{0,0} & \cdots & d_{M-1,0} \\ \vdots & \ddots & \vdots \\ d_{0,N-1} & \cdots & d_{M-1,N-1} \end{bmatrix} \begin{bmatrix} w_0 \\ \vdots \\ w_i \\ \vdots \\ w_{M-1} \end{bmatrix} \quad (25)$$

where: $D$ is a $M \times N$ matrix, $W$ is a $M \times 1$ filter weight vector and $A$ is a $\lambda$-bit vector of size $N \times 1$ containing filter output for each sensor. If one wants to apply different filters, he will have to compute (25) several times in the D-J encrypted domain. This computation complexity increase is nevertheless compensated by the drastic communication complexity reduction.

To make work such linear operations in the D-J domain, the main question is how to organize the sensors' samples into a $\lambda$-bit vector $D_i$ in a specific fashion. Our basic idea is to allocate a set of consecutive bits of $D_i$ to the encoding of one sample $d_{i,j}$ with the guarantee that the filter output $a_j$ stands at the same position than $d_{i,j}$ in the vector $A$. The number of bit $b_j$ to allocate to $d_i$ depends on the process $d_i$ undergone that is to say (23) (with $w_{i,j} = w_i$) a process of $M$ multiplications and $M-1$ summations leading to $a_j$. Knowing that the multiplication or addition of two integers of $l$ bits is encoded on $2^l$ bits, at maximum, the number of bits $b_j$ to allocate to $d_{i,j}$ depends also on the filter weights $\{w_i\}_{i=0,...,M-1}$.

If we consider the packing constants $\{b_j^d, b^w\}$ as the necessary number of bits for the encoding of $\{d_{i,j}\}_{i=0,...,M-1}$ and $\{w_i\}_{i=0,...,M-1}$, respectively:

$$d_{i,j} < 2^{b_j^d} \quad \text{and} \quad w_i < 2^{b^w} \quad \forall i \in [0, M-1] \quad (26)$$

then (23) leads to the following inequality:

$$a_j = \sum_{i=0}^{M-1} w_{i,j} d_{i,j} < 2^{\log_2(M)+b^w+b_j^d} \quad (27)$$

(27) shows that the filter output $a_j$ stands at maximum on the number of bits $b_j$ such as:

$$b_j = \log_2(M) + b^w + b_j^d \quad (28)$$

As a consequence, $d_{i,j}$ has to be packed on $b_j$ bits into $D_i$. Considering all sensors, $D_i$ will then correspond to the integer value:

$$D_i = \sum_{j=0}^{N-1} 2^{\gamma_j} d_{i,j} \quad \text{with} \quad \gamma_j = \sum_{k=0}^{j-1} b_k \quad (29)$$

From here on, (25) can be computed in the encrypted domain. More clearly, let us consider the D-J encrypted versions $\{E[D_i]\}_{i=0,...,M-1}$ of the packed vectors $\{D_i\}_{i=0,...,M-1}$. Notice that, in the rest of this section and for sake of simplicity, we voluntary omit the random value of the D-J cryptosystem in the coming equation writing. So, to calculate (25) in the D-J domain, HMI follows the next steps:

1) It calculates for all $i \in [0, M-1]$, $E[D_i]^{w_i} = E[w_i \sum_{j=0}^{N-1} 2^{\gamma_j} d_{i,j}] = E[\sum_{j=0}^{N-1} 2^{\gamma_j} w_i d_{i,j}]$. Herein, it is important to underline that it is from the way multiplications are conducted in the D-J domain (see (7)) that comes the constraint not being able to process IMD samples in a vectors with different filters at once (see previous comment above and (25)).

2) To get the filters' outputs, it then computes:

$$\begin{aligned} E[A] &= E\left[\sum_{j=0}^{N-1} 2^{\gamma_j} a_j\right] = \prod_{i=0}^{M-1} E[D_i]^{w_i} \\ &= E\left[\sum_{j=0}^{N-1} (2^{\gamma_j} \sum_{i=0}^{M-1} w_i d_{i,j})\right] \end{aligned} \quad (30)$$

In order to unpack $a_j$ from the decrypted integer value $A = \sum_{j=0}^n 2^{\gamma_j} a_j$, we need to extract from $A$ the sequence of bits associated to the power of 2 between $2^{\gamma_j}$ to $2^{\gamma_{j+1}-1}$. This extraction process can be summed up as follows:

$$a_j = \left\lfloor \frac{A}{2^{\gamma_j}} \right\rfloor \mod 2^{b_{j+1}} \quad (31)$$

where $\lfloor \cdot \rfloor$ is the floor function.

Let us now generalize this solution to not only positive integers. From the packing point of view, the computation of the number of bits $b_j$ for the encoding of $d_{i,j}$ works in the same way. It just has to take into account the bit of sign of $\{d_{i,j}\}_{i=0,...,M-1}$ and $\{w_i\}_{i=0,...,M-1}$. Considering that $|d_{i,j}| < 2^{b_j^d}$ and $|w_i| < 2^{b^w}$ and that the filter output can be negative i.e. $|a_j| < 2^{b_j}$, $b_j$ is given by:

$$b_j = \log_2(M) + b^w + b_j^d + 1 \quad (32)$$

On its side, the unpacking procedure has to be modified. This result from the fact that the equivalent operations in the clear domain of the computations conducted in the D-J domain
are modular operations. More clearly, the calculation of (30) corresponds in the clear to the following operation:

$$A = \sum_{j=0}^{N-1} 2^{\gamma_j} a_j \quad \mod K_p^n \text{ with } \gamma_j = \sum_{k=0}^{j-1} b_k \quad (33)$$

where $K_p^n$, is the D-J public key. As a consequence, negative values of A wrap around modulo $K_p^n$, belonging to the range $[\frac{K_p^n+1}{2}, \dots, K_p^n - 1]$, while positive values of A are in the range $[0, \dots, \frac{K_p^n-1}{2}]$.

To detail our unpacking strategy, which is an iterative procedure, let us take an example and first assume that vectors {$D_i$}$_{i=0,...,M-1}$ only contain one piece of data (i.e. $d_{i,0}$). A will thus contain a single filter output value $A = a_0 \mod K_p^n$. If $A \le \frac{K_p^n-1}{2}$ then $a_0 = A$, otherwise $a_0 = A - K_p^n$. Let us now consider that vectors {$D_i$}$_{i=0,...,M-1}$ pack two pieces of data $d_{i,0}$ and $d_{i,1}$ coded onto $b_0$ and $b_1$ bits, respectively. The filters outputs $a_0$ and $a_1$ are consequently packed into A such as $A = a_0 + 2^{b_0}a_1 \mod K_p^n$. As the sign of A is dominated by the one of $a_1$, $a_1$ is extracted first. To do so, in order to remove the modulo $K_p^n$ from (33), if $A > \frac{K_p^n-1}{2}$ then $A' = A - K_p^n$, otherwise $A' = A$. $a_1$ is then extracted by computing $a_1 = \lfloor \frac{A}{2^{b_0}} \rfloor$, where $\lfloor \cdot \rfloor$ is the rounding operator. $a_0$ is accessed by primarily subtracting $2^{b_0}a_1$ to A and by looking the range of values to which it belongs as previously. One can generalize this procedure to the case where N values are packed. To unpack the $a_j$ coefficient from $A = \sum_j 2^{\gamma_j}a_j$, we start by unpacking the $a_{N-1}$ coefficient then we subtract $a_{N-1}2^{\gamma_{N-1}}$ from A so as to unpack $a_{N-2}$, and repeat this procedure until to reach $a_j$. Algorithm 3 sums up this procedure.

**Algorithm 3 Unpacking Algorithm**

if $A > \frac{K_p^n-1}{2}$ then
A $\leftarrow A - K_p^n$

end if

save $\leftarrow 0$

for $j = N-1; j \ge 0; j - \text{do}$

$a_j \leftarrow \lfloor \frac{A - save}{2^{\gamma_j}} \rfloor$
save $\leftarrow save + a_j 2^{\gamma_j}$

end for

The following theorem generalizes our packing and unpacking proposal.

**Theorem 1 (Packing-Unpacking):** Let {$P_j$}$_{0 \le j \le N-1} \in \mathbb{N}^*$ such that: $P_j < P_{j+1}$ $\forall j \in [0, N-1]$ where $P_N = K_p^n$. Let $A = \sum_{j=0}^{N-1} a_j P_j \mod (K_p^n)$. We can unpack A, i.e extract all values $a_j$ from it, under the condition:

$$\left| \sum_{j=0}^{k} a_j P_j \right| \le \frac{P_{k+1} - 1}{2} \quad \forall k \in [0, N-1] \quad (34)$$

*Proof:* Thanks to the (34) we can write:

$$\left| \sum_{j=0}^{N-1} a_j P_j \right| \le \frac{K_p^n - 1}{2} \quad (35)$$

In order to remove the $K_p^n$ modulo from A, let us consider $A' = A - K_p^n$ if $A > \frac{K_p^n-1}{2}$ or, otherwise, $A' = A$. More clearly, we get:

$$A' = \sum_{j=0}^{N-1} a_j P_j \quad (36)$$

Let now consider the quantity $b_{N-i} = \lfloor \frac{A' - \sum_{j=0}^{i-1} b_{N-j} P_{N-j}}{P_{N-i}} \rfloor$.

Our objective is to show that $b_{N-i} = a_{N-i}$, $\forall i \in [1, N]$, providing a way to unpack data. Let us do it by inference.

For $i = 1$ we get:

$$b_{N-1} = \left\lfloor \frac{A'}{P_{N-1}} \right\rfloor \quad (37)$$

Applying (34) we have:

$$\left| \sum_{j=0}^{N-2} a_j P_j \right| \le \frac{P_{N-1} - 1}{2} \quad (38)$$

$$\Leftrightarrow \frac{1}{2P_{N-1}} - \frac{1}{2} \le \frac{\sum_{j=0}^{N-2} a_j P_j}{P_{N-1}} \le \frac{1}{2} - \frac{1}{2P_{N-1}} \quad (39)$$

$$\Leftrightarrow -\frac{1}{2} < \frac{\sum_{j=0}^{N-2} a_j P_j}{P_{N-1}} < \frac{1}{2} \quad (40)$$

Due to the fact that $A' = \sum_{j=0}^{N-1} a_j P_j = \sum_{j=0}^{N-2} a_j P_j + a_{N-1}P_{N-1}$, (37) can be rewritten as:

$$b_{N-1} = \left\lfloor \frac{\sum_{j=0}^{N-2} a_j P_j}{P_{N-1}} + a_{N-1} \right\rfloor = a_{N-1} \quad (41)$$

The inference is thus shown for the rank $i = 1$. To demonstrate it for the $i^{th}$ rank, assuming it is true since the $(i-1)^{th}$, we have:

$$b_{N-i} = \left\lfloor \frac{A' - \sum_{j=0}^{i-1} b_{N-j} P_{N-j}}{P_{N-i}} \right\rfloor = \left\lfloor \frac{\sum_{j=0}^{N-i} a_j P_j}{P_{N-i}} \right\rfloor$$

Next, using (34) and the same reasoning as for $i = 1$ we have:

$$-\frac{1}{2} < \frac{\sum_{j=0}^{N-i-1} a_j P_j}{P_{N-i}} < \frac{1}{2} \quad (42)$$

As a consequence, one can rewrite:

$$b_{N-i} = \left\lfloor \frac{\sum_{j=0}^{N-i-1} a_j P_j}{P_{N-i}} + a_{N-i} \right\rfloor = a_{N-i} \quad (43)$$

This finally proves the inference and the possibility to extract {$a_j$}$_{0 \le j \le N-1}$ from $A = \sum_{j=0}^{N-1} a_j P_j \mod (K_p^n)$. $\square$
## 2) SECURE CIMD FRAMEWORK WITH DATA PACKING

The above packing solution allows processing sets of samples from different sensors with the same filter simultaneously but taking advantage of it in our framework imposes to modify the filter thresholding procedure of our secure CIMD framework (see Section III-B2). Let us recall that in this procedure HMI interacts with Server to decide whether or not the filter output is above a threshold. To do so, HMI computes the difference between the filter output and the threshold, then applies multiplicative blinding using (19) and sends the result under a D-J encrypted form to Server. Server D-J decrypts data and returns to HMI the sign of the multiplicative blinded difference. Due to the fact multiplicative blinding requires to multiply the filter output by a random value and for the same reason it is not possible to multiply packed samples in a vector with different weight values (see Section III-C1), our protocol is modified as follows: we share the multiplicative blinding procedure between IMD and HMI. Here are the steps of this novel procedure:

* Instead of packing {$d_{i,j}$$j=0,...,N-1$ in $D_i$, IMD packs the semi-blinded samples {$d_{i,j}r_j$$j=0,...,N-1$}, where {$r_j$$j=0,...,N-1$ are the multiplicative blinding random values (see (19)). IMD uses the same random values for all CLCG encrypted vectors it will send to HMI.

* Once HMI has received M CLCG encrypted vectors, it converts them into D-J encrypted packed vector and filters them using the same procedure as in Section III-C1. It thus has access to $E[\sum_{j=0}^{N-1} 2^{\gamma_j} r_j \sum_{i=0}^{M-1} w_i d_{i,j}]$. HMI multiplies these results with the D-J encrypted versions of the semi-blinded packed thresholds, i.e. $E[\sum_{j=0}^{N-1} 2^{\gamma_j} r_j s_j] = \prod_{j=0}^{N-1} E[2^{\gamma_j} s_j] r_j$, so as to get $E[\sum_{j=0}^{N-1} 2^{\gamma_j} r_j (\sum_{i=0}^{M-1} w_i d_{i,j} - s_j)]$. To end the multiplicative blinding procedure, HMI computes the random values set {$r'_j$$j=0,...,M-1$ and calculates:

$$ 
\begin{aligned}
E[A] &= E[\sum_{j=0}^{N-1} 2^{\gamma_j} (r_j (\sum_{i=0}^{M-1} w_i d_{i,j} - s_j) - r'_j)] \\
&= E[\sum_{j=0}^{N-1} 2^{\gamma_j} r_j (\sum_{i=0}^{M-1} w_i d_{i,j} - s_j)] E[-\sum_{j=0}^{N-1} 2^{\gamma_j} r'_j]
\end{aligned} 
\quad (44) 
$$

HMI sends the result of this computation to Server. As it can be seen from (44), each filter output is independently multiplicatively blinded at the price however IMD knows the random values {$r_j$$j=0,...,N-1$.

* Server decrypts and unpack the data, analyses the signs of masked filter outputs and sends back a binary vector to HMI for final decision.

From this standpoint, we have to identify the number of bits {$b_j$$j=0,...,N-1$ required for the packing of the sensors' samples {$d_{i,j}$$j=0,...,N-1$ into a vector $D_i$. In addition to the filtering process, one should take in consideration the following operations and variables:

* The subtraction of the threshold $s_j$ to the filter output $a_j$ (see (18)).

* The multiplicative blinding operation and its random values {$r_j$$j=0,...,N-1$ and {$r'_j$$j=0,...,N-1$} knowing that $r'_j \ll r_j$ $\forall j \in [0, N-1]$ (see (19)).

Let us consider the $j^{th}$ sensor. The filtering and thresholding calculations can be summed up as:

$$ a_j = r_j(\sum_i w_i d_{i,j} - s_j) - r'_j \mod K_p^n \quad (45) $$

Let us also assume that $s_j$, $r_j$ and $r'_j$ are positive or negative integers such as: $|s_j| < 2^{b'_s}$, $|r_j| < 2^{b'_r}$ and $|r'_j| < 2^{b'_r}$. From (45), we can write:

$$ a_j < 2^{b'_r} (2^{\log_2(M)} + b^w + b'_d + 2^{b'_s}) \quad (46) $$

It is thus possible to unpack filter output {$a_j$$j=0,...,N-1$ from the vector A, if:

$$ b^j = \max(\log_2(M) + b^w + b'_d, b'_s) + b'_r + 1 \quad (47) $$

Under this constraint, semi-blinded samples {$r_jd_{i,j}$$j=0,...,N-1$ are packed into a vector $D_i$, an integer value defined as:

$$ D_i = \sum_{j=0}^{N-1} 2^{\gamma_j} r_j d_{i,j} \quad \text{with} \quad \gamma_j = \sum_{k=0}^{j-1} b_k \quad (48) $$

Similarly, semi-blinded thresholds {$r_j s_j$$j=0,...,N-1$ and random {$r'_j$$j=0,...,N-1$ are packed such as:

$$ S = \sum_{j=0}^{N-1} 2^{\gamma_j} r_j s_j \quad \text{and} \quad R' = \sum_{j=0}^{N-1} 2^{\gamma_j} r'_j \quad (49) $$

Fig.4 resume our secure CIMD framework with data packing. This one works accordingly the following steps:

1) IMD semi-blinds sensor samples {$d_{i,j}$$j=0,...,N-1$ using {$r_j$$j=0,...,N-1$ and packs {$r_jd_{i,j}$$j=0,...,N-1$ into the vector $D_i = \sum_{j=0}^{N-1} 2^{\gamma_j} r_j d_{i,j}$, using the appropriate number of bits {$b_j$$j=0,...,N-1$}. Then it CLCG encrypts $D_i$ into $D_i + Z_i$ based on the CLCG secret key: $K_c = \{(a_X, a_Y), (X_0, Y_0), (c_X, c_Y)\}$ and sends the results to HMI along with {$r_j$$j=0,...,N-1$.

2) Based on $E[K_c]$, the D-J encrypted version of the CLCG secret key, HMI converts CLCG data into D-J encrypted data: $E[D_i]$. Once it has M encrypted vectors {$E[D_i]$$i=0,...,M-1$}, HMI filters data using (17) and the filter weights {$w_i$$i=0,...,M-1$} getting access to $E[\sum_{j=0}^{N-1} 2^{\gamma_j} r_j (\sum_{i=0}^{M-1} w_i d_{i,j})]$.

3) In order to threshold filters' outputs, HMI and server interacts as follows:

a) HMI masks and packs the thresholds {$s_j$$j=0,...,N-1$ into the vector S using {$r_j$$j=0,...,N-1$ before D-J encrypting it into $E[S] = E[\sum_{j=0}^{N-1} 2^{\gamma_j} r_j s_j]$. it then computes the difference (18) in the D-J domain: $E[R(\sum_i w_i D_i - S)] = E[\sum_{j=0}^{N-1} 2^{\gamma_j} r_j]$.
($\sum_{i=0}^{M-1} w_i d_{i,j} - s_j$)]. To complete the multiplicative blinding it multiplies the previous result by $E[-R'] = E[-\sum_{j=0}^{N-1} 2^{\gamma_j} r'_j]$ to obtain $E[R(\sum_{i=0}^{M-1} w_i D_i - S) - R'] = E[\sum_{j=0}^{N-1} 2^{\gamma_j}(r_j(\sum_{i=0}^{M-1} w_i d_{i,j} - s_j) - r'_j)]$, it sends to Server.

b) Server D-J decrypts data using the D-J secret key $K_s$ and (5) before unpacking using the procedure of Section III-C1. Once it has access to the multiplicatively blinded differences: $\{r_j(\sum_{i=0}^{M-1} w_i d_{i,j} - s_j) - r'_j\}_{j=0,...,N-1}$, it determines their signs and encodes the result into a binary vector Res (a '1' indicates the output is negative) it next sends encrypted to HMI.

c) Once it receives Res, HMI decides to raise or not an alarm.

Notice that, for sake of simplicity, we did not have included the watermarking based integrity control in the presentation of our CIMD framework with data packing. This one works in the same way than in the first solution we presented in Section III-B3 excepting that: i) the above CLCG cryptosystem is replaced by the crypto-watermarking of Section III-B3; ii) one can reduce the watermark distortion and the probability the system fails to watermark a block by guessing the LSB of each packed sample rather than testing Dist LSBs of a single sample. Doing so consists in fixing Dist = 1 for each of the N samples $\{d_{i,j}\}_{j=0,...,N-1}$ in $D_i$ with a probability of crypto-watermarking failure upper bounded by $1 - 1/2^{2N}$. Taking N = 30, the probability of this event is very low, and we believe it will not impact the working of our protocol.

## IV. COMMUNICATION AND COMPUTATION COMPLEXITIES - THEORETICAL AND EXPERIMENTAL RESULTS

The computation and communication complexity for IMD, HMI and Server depends on the number of sensors N and of the filter weight M. Computation complexity is evaluated in terms of modular exponentiation and multiplication operations. These are the most expensive operations. Regarding IMD, it packs $M \times N$ semi-blinded samples into M vectors before CLCG encrypting them. The corresponding computation complexity is thus $M(N + 1)$ modular multiplications. The communication complexity associated to the transmission of the packed vectors and of the random values $\{r_j\}_{j=0,...,N-1}$ is of $M\log_2(K_p^n) + N\log_2(r_j)$. On its side, HMI first applies CrC conversion to M packed-CLCG encrypted vectors and filters data according to (17). Then it packs thresholds using (49), makes secure thresholds' subtraction (18) and ends multiplicative blinding. These operations correspond to a computation complexity of $3M + 2$ modular exponentiation plus $4M + 3N - 1$ modular multiplications. The communication cost between HMI and Servers to complete the thresholding operation is of $\log_2(K_p^{n+1})$. The calculation complexity of Server corresponds to the D-J

<table><caption>TABLE 2. Computation complexity of KBH and of our proposal. E denotes modular exponentiation and M modular multiplication.</caption><thead><tr><th></th><th>Proposed solution</th><th>KBH</th></tr></thead><tbody><tr><td>IMD</td><td>M(N+1)M</td><td>4E + 2M</td></tr><tr><td>HMI</td><td>(3M+2)E + (4M+3N-1)M</td><td>5E + (4+n(n-1))M</td></tr><tr><td>Server</td><td>1E + (3N+n(n-1)+1)M</td><td>4E + (4+n(n-1))M</td></tr><tr><td>Processed data</td><td>MN</td><td>2</td></tr></tbody></table>

<table><caption>TABLE 3. Communication complexity of KBH and of proposal.</caption><thead><tr><th></th><th>Proposed solution</th><th>KBH</th></tr></thead><tbody><tr><td>IMD</td><td>Mlog<sub>2</sub>(K<sub>p</sub><sup>n</sup>) + Nlog<sub>2</sub>(r<sub>j</sub>)</td><td>2log<sub>2</sub>(K<sub>p</sub><sup>n+1</sup>)</td></tr><tr><td>HMI</td><td>log<sub>2</sub>(K<sub>p</sub><sup>n+1</sup>)</td><td>3log<sub>2</sub>(K<sub>p</sub><sup>n+1</sup>)</td></tr><tr><td>Server</td><td>N</td><td>3log<sub>2</sub>(K<sub>p</sub><sup>n+1</sup>)</td></tr><tr><td>Processed data</td><td>MN</td><td>2</td></tr></tbody></table>

<table><caption>TABLE 4. Computation times of our protocol compared to the KBH based protocol, considering 340 samples and that all entities are implemented on the equivalent of an IPhone 5.</caption><thead><tr><th></th><th>Proposed solution</th><th>KBH</th></tr></thead><tbody><tr><td>IMD</td><td>1.7ms</td><td>10671ms</td></tr><tr><td>HMI</td><td>648.8ms</td><td>10700ms</td></tr><tr><td>Server</td><td>32.4ms</td><td>10570ms</td></tr><tr><td>Total</td><td>682.9ms</td><td>31941ms</td></tr></tbody></table>

decryption and data unpacking. It is thus of 1 modular exponentiation and $3N + n(n-1) + 1$ modular multiplications, where n is the D-J exponent (see Section II-A). As Server only sends to HMI a binary vector, the communication cost is N.

Table 2 and Table 3 provide the computational and communicational costs of our solution compared to the same framework deployed with KBH. We recall that KBH is one of the most efficient scheme for securely comparing two numbers. As it can be seen, thanks to our packing strategy, our solution achieves much better performance, especially for IMD.

To go further, IMD CLCG encryption was implemented on an ultra-low-power micro-controller based on the Arm Cortex-M4 32-bit RISC core (80 MHz, 1 Mbyte memory, 320 Kbyte of SRAM) considering the D-J following parameters: $n = 1$, $\lambda = 2048$ (see Section II-A), The micro-controller was able to output a CLCG every 9ms demonstrating that our protocol is thus compatible with low power IMD devices. For practical reasons, it was not possible to integrate KBH into the micro-controller. So, for fair comparison, we implemented our IMD packing solution and the KBH based IMD into the equivalent of an IPhone 5 equipped of a 1.3 GHz CPU and 1GB memory. The computation times given in Table 4 correspond to the processing of 340 samples divided in 10 packed vector (i.e. $M = 10$ and $N = 34$). As shown, our solution can nearly process 500 samples in 1 seconds whereas the KBH comparison protocol only treats 94 samples at same time.

## V. SECURITY ANALYSIS

Before entering into the details, let us recall that our scheme is a tripartite protocol where:
<figure><img src="image_5.png" /><figcaption>FIGURE 4. Proposed secure CIMD framework with data packing.</figcaption></figure>

1) IMD sends semi-blinded packed CLCG encrypted data to HMI.

2) HMI, after encryption conversion, processes semi-blinded packed in the D-J domain (filtering, threshold subtraction) and to take a decision about raising or not an alarm, it interacts with Server.

3) HMI forwards data it receives from IMD to Server for storage and data reuse purposes.

As stated in Section III-A, our scheme has been developed considering that IMD is honest while HMI and Server are honest-but curious adversaries. HMI should not be able to infer information about patient data and Server should not discover HMI filter weights and thresholds. As defined in [44], the security of a protocol in the presence of static semi-honest adversaries is proved if its correctness and privacy are demonstrated. Lindell proposed in [52] the following definitions under normal conditions of use:

* Correctness means that the output of the parties is correct.

* Privacy means that nothing but the output is learned.

## A. CORRECTNESS

In our context, the correctness of our protocol is demonstrated if the correctness of its three entities is ensured.

1) IMD CLCG encrypts packed medical data {$D_i$}$_i$ where $i$ belongs to $[0, M-1]$ using the CLCG secret seed $K_c$. As CLCG is a deterministic function, by giving $K_c$ and $D_i$ to IMD, this one correctly outputs $D_i + Z_i$.

2) It is the same for HMI. The 5 operations it has to conduct (encryption conversion, filtering, thresholding's encryption, secure thresholding and multiplicative blinding) are deterministic, so the proof of its correctness is immediate.

3) Regarding Server we have to show that the vector $Res$ equals 0 (resp. 1) at the index $j$ if the $j^{th}$ unpacked value is positive (resp. negative). As defined in Section III-C, $a_j$ is the result of the secure processing operation (45). Due to the fact we packed our data accordingly to Theorem 1, then if $A > \frac{K_p^n-1}{2}$ we subtract $K_p^n$ to A in

order to obtain:

$$A = [r_0(\sum_{i=0}^{M-1} w_i d_{i,0} - s_0 - s_0) - r'_0] + \dots + 2^{\gamma N-1}(r_{N-1}(\sum_{i=0}^{M-1} w_i d_{i,N-1} - s_{N-1}) - r'_{N-1})$$

Using our unpacking Algorithm 3 Server accesses to the values {$r_j(\sum_{i=0}^{M-1} w_i d_{i,j} - s_j) - r'_j$}$_{j=0,...,N-1}$. It conclude the quantity $r_j(\sum_{i=0}^{M-1} w_i d_{i,j} - s_j) - r'_j$ is positive (resp. negative) if and only if $\sum_{i=0}^{M-1} w_i d_{i,j} - s_j$ is positive (resp. negative). Consequently, the $j^{th}$ value of $Res$ is equal to 0 (resp. 1) if and only if the filter output $a_j$ is above (resp. under) the $j^{th}$ threshold, proving thus the Server correctness. To sum-up, the correctness of our protocol is demonstrated.

## B. PRIVACY

Based on the above definition, privacy is ensured in our framework if: i) HMI learns the signs of the differences between thresholds and filter outputs but not the IMD samples; ii) Server learns the multiplicatively blinded differences but not HMI filter weights and thresholds.

Before entering into the details of our proof, let us recall that in our protocol: i) data are CLCG encrypted on IMD side ii) CLCG encrypted data are next securely converted into D-J homomorphically encrypted data using the CrC protocol; iii) HMI processes the data and interacts with Server; Server that can securely recover the sign of the secure processing through the use of blinding as explained in Section II-B.

Now let us prove the privacy of this protocol in a more formal way as given in [44]. Let us first assume HMI tries to infer the samples {$d_{i,j}$}$_{i=0,...,M-1}$$_{; j=0,...,N-1}$ HMI knows the following inputs and parameters: the IMD CLCG data {$D_i + Z_i$}$_{i=0,...,M-1}$, {$r_j$}$_{j=0,...,N-1}$, the SCLCG key $E[K_c]$ and Server binary sign vector $Res = \{\text{sign}(r_j(\sum_{i=0}^{M-1} w_i d_{i,j} - s_j) - r'_j)\}$_{j=0,...,N-1}$, the Server D-J public key $K_p^n$, the thresholds {$s_j$}$_{j=0,...,N-1}$ and the packing constants {$b'_r, b^j$}$_{j=0,...,N-1}$. In order to prove that HMI learns no additional information
than Res, we should show that one can simulate inputs of HMI without HMI being able to distinguish simulated data from data in a real run of the protocol. The input of HMI can be trivially simulated as follows: 1) as CLCG is based on a pseudorandom number generator M IMD CLCG packed vectors from IMD can be simulated by M random numbers from $\mathbb{Z}_{K_p^n}$ - HMI will not see the difference with real data; 2) the secret SCLCG secret key $E[K_c]$, which is the D-J encryption of the CLCG secret key, can be simulated by D-J encrypting random numbers from $\mathbb{Z}_{K_p^n}$ - because of semantic security property of the D-J cryptosystem, HMI will not distinguish these fake data; 3) IMD random numbers $\{r_j\}_{j=0,...,N-1}$ can be simulated taking N random from $\llbracket 0, 2^{b_j} - 1 \rrbracket$ again HMI will see no differences; 4) The value of the server output Res, HMI receives, depends on the data of HMI. As one value of Res can be obtained from many different HMI data, HMI cannot get information from Res. This proves the HMI privacy.

The analysis of privacy is similar for Server. Server receives from HMI: $E[A] = E[\sum_{j=0}^{N-1} 2^{2^j}(r_j(\sum_{i=0}^{M-1} w_i d_{i,j} - s_j) - r'_j)]$ it decrypts/unpacks to get access to $\{a_j = r_j(\sum_{i=0}^{M-1} w_i d_{i,j}) - r'_j \mod K_p^n\}_{j=0,...,N-1}$. Remembering the representation of negative numbers in the clear domain of the D-J cryptosystem (see Section III-B2), Server can be simulated by generating the following uniform random values $\{\bar{a}_j\}_{j=0,...,N-1}$:

$$ \bar{a}_j \in \llbracket 0, 2^{b_j} - 1 \rrbracket \text{ if } a_j \ge 0 \text{ and } \bar{a}_j \in \llbracket -2^{b_j} + 1, -1 \rrbracket \text{ otherwise} \quad (50) $$

Because of multiplicative blinding $a_j$ is uniformly distributed over the range $\llbracket -2^{b_j} + 1, 2^{b_j} - 1 \rrbracket$. As a consequence, it is impossible to distinguish between $a_j$ and $\bar{a}_j$. $a_j$ and $\bar{a}_j$ having the same sign, it is impossible to distinguish Server output. Regarding Server' inputs, because the D-J cryptosystem is semantically secure, Server will not make the difference between D-J encrypted real values and D-J encrypted random ones. Thus, the privacy of Server as well as of our protocol are proved.

In terms of cryptography security, the one of D-J cryptosystem has been demonstrated in [29]. Regarding the CLCG algorithm, let us first recall that this one is a combination of several LCGs. In [53], [54], it has been shown that, under some hypothesis, such a combination can be approximated by a single LCG. The LCG security analysis has been conducted in terms of randomness tests in [55] and attacks in [56]. Looking at [55] when LCG or CLCG parameters are big such as a modulo $m = 2^{61} - 1$, a multiplier $a = 2^{30} - 2^{20}$ and an increment $c = 0$ the number of failed tests is relatively low. In our case and as explained in Section III-B1, the CLCG parameters depend on D-J public key. Therefore, the size of our CLCG output is coded on 2048 bits, which is definitively more robust [55]. On its side, [56] depicts several attacks that take as input some LCG outputs $\{X_i\}_i$ so as to find the LCG parameters and consequently the whole LCG sequence. Let us come back to our framework and consider that a LCG is used instead of a CLCG. Even though the attacker does not

have access to LCG outputs $\{X_i\}_i$, as these ones are generated in IMD, one may questioned about if it is possible to retrieve some $X_i$ values from LCG encrypted IMD data that is to say $c_i = d_i + X_i \mod m$, where m is the D-J public key. To the best of our knowledge, two possible strategies can be followed: i) an exhaustive search making varying $d_i$ and for each $d_i$, applying the attack of [56] testing the corresponding values $X_i = c_i - d_i \mod m$; ii) a dictionary attack [57], where the attacker search's for most likely data $d_i$ in order to infer $X_i$. The dictionary attack is of much smaller complexity but remains hard to apply in our case for the following reasons:

1) due to the fact that the CLCG modulo is equal to the D-J public key and because of our packing strategy the attacker has to guess not only one sample but all the concatenated ones in order to apply the dictionary attack. More clearly, in the case of 8 bit encoded samples and a public key of 2048 bits, 128 samples are packed and CLCG encrypted at once. If the attacker has a dictionary containing $2^4$ of 8 bit encoded values; values that medical samples can take; he will have to compute $2^{4*128}$ guess in order to recover only one value $X_i$. Such a complexity is extremely high.

2) in addition, as in our protocol sample values $d_i$ are multiplicatively blinded before being encrypted (see Section III-C2), guessing $d_i$ is equivalent to a brute-force attack on a 2048 bits vector which is unfeasible ($2^{2048}$ guess in order to recover only one $X_i$).

To sum up, an attacker cannot recover $X_i$ output and break LCG security and by next CLCG ones.

### C. MALICIOUS HMI SCENARIO

Contrarily to the static semi-honest adversary, in the case an entity in a protocol is assumed to be a malicious adversary, this one will not process data has established by the protocol. In our case, only HMI could try to infer patient data it receives thanks to a dichotomy attack. To illustrate this attack, and for sake of simplicity, let us consider the non-packed version of our protocol. In addition, let us consider the attack where HMI wants to know one element of the CLCG secret key $K_c$; secret key HMI only accesses under a D-J encrypted form (i.e. $E[K_c] = \{E[X_0], E[Y_0], E[c_X], E[c_Y]\}$). So, rather than sending the value $A = R(\sum_i w_i D_i - S) - R' \mod K_p^n$ (see (44)) to Server for sign computation, HMI sends $E[X_0 - X']$ with $X' = 2^{\lambda/2}$ where $\lambda$ is the D-J security parameter. HMI can compute $E[X_0 - X']$ thanks to the D-J cryptosystem and the Server public key. On its side, Server decrypts $E[X_0 - X']$ using its private key and sends back to HMI the sign of the difference. Applying the dichotomy principle, HMI re-iterates the operation modifying $X'$ such as $X' = X'/2$ in case the difference sign is negative, or such as $X' = 3 \times X'/2$, otherwise. This attack is logarithmic which means that HMI needs to do $\lambda$ times this exchange with the server in order to find $X_0$. Thanks to this attack HMI can find $K_c$ and CLCG decrypt data received from the HMI. This attack also works for our packed protocol.
In order to prevent such an attack, our scheme includes a zero-knowledge proof sub protocol the purpose of which is to test if HMI is trying to infer information without following the rules. The basic idea of this sub protocol is that Server asks HMI to process data HMI has already processed. In our case, the detection of a HMI misbehavior is conducted by comparing the signs of the differences between the filter outputs and thresholds of already processed data and with those of reprocessed ones. Any dissimilarities will alert Server that HMI is cheating. It is important to note that, due to the fact the D-J cryptosystem is semantically secure, HMI cannot infer the data that are reprocessed.

## VI. CONCLUSION

In this paper, we have presented a complete novel secure framework for connected implanted medical device (IMD) where semi-honest third parties (HMIs) can process IMD data while preserving patient privacy as well as the confidentiality of the HMI process parameters. It relies on two main original contributions: i) a cryptosystem conversion that allows converting stream ciphered CLCG data into Damgard-Jurik encrypted data; ii) a data packing method which makes possible the processing of batch of data. Those two techniques reduce computation and communication complexity over entities and especially on IMD resource constraint device. We further have proposed a sub-protocol in order to counteract a malicious adversary HMI that tries to infer patient data by means of a dichotomy attack. It also includes a crypto-watermarking service that allows parties to verify the integrity of data without decrypting them. Computation and communication complexities have been established theoretically and validated experimentally. Compared to KBH our solution is 45 times more efficient. On the basis on a HMI and IMD implemented on a device equivalent to IPhone 5, it is possible to process nearly 500 samples/s. Our solution can thus be used in real life applications.

## REFERENCES

[1] J. Gubbi, R. Buyya, S. Marusic, and M. Palaniswami, "Internet of Things (IoT): A vision, architectural elements, and future directions," *Future Gener. Comput. Syst.*, vol. 29, no. 7, pp. 1645-1660, Sep. 2013.

[2] A. M. Ghosh, D. Halder, and S. K. A. Hossain, "Remote health monitoring system through IoT," in *Proc. 5th Int. Conf. Informat., Electron. Vis. (ICIEV)*, May 2016, pp. 921-926.

[3] R. Zgheib, E. Conchon, and R. Bastide, "Engineering IoT healthcare applications: Towards a semantic data driven sustainable architecture," in *Proc. E-Health*, 2017, pp. 407-418.

[4] B. Latré, B. Braem, I. Moerman, C. Blondia, and P. Demeester, "A survey on wireless body area networks," *Wireless Netw.*, vol. 17, no. 1, pp. 1-18, Jan. 2011.

[5] M. Rushanan, A. D. Rubin, D. F. Kune, and C. M. Swanson, "SoK: Security and privacy in implantable medical devices and body area networks," in *Proc. IEEE Symp. Secur. Privacy*, May 2014, pp. 524-539.

[6] F. Xu, Z. Qin, C. C. Tan, B. Wang, and Q. Li, "IMDGuard: Securing implantable medical devices with the external wearable guardian," in *Proc. IEEE INFOCOM*, Apr. 2011, pp. 1862-1870.

[7] T. Denning, K. Fu, and T. Kohno, "Absence makes the heart grow fonder: New directions for implantable medical device security," in *Proc. 3rd Conf. Hot Topics Secur.*, 2008, pp. 1-7, Art. no. 5. [Online]. Available: https://dl.acm.org/doi/10.5555/1496671.1496676

[8] D. Thilakanathan, S. Chen, S. Nepal, R. Calvo, and L. Alem, "A platform for secure monitoring and sharing of generic health data in the cloud," *Future Gener. Comput. Syst.*, vol. 35, pp. 102-113, Jun. 2014.

[9] M. Pistono, R. Bellafqira, and G. Coatrieks, "Secure processing of stream cipher encrypted data issued from IOT: Application to a connected knee prosthesis," in *Proc. 41st Annu. Int. Conf. IEEE Eng. Med. Biol. Soc. (EMBC)*, Jul. 2019, pp. 6494-6497.

[10] G. Bouzillé, "Sharing health big data for research—A design by use cases: The INSHARE platform approach," in *Proc. 16th World Congr. Med. Health Informat.*, 2017, p. 245.

[11] P. Voigt and A. V. D. Bussche, *The EU General Data Protection Regulation (GDPR): A Practical Guide*. Springer, 2017.

[12] Content of Premarket Submissions for Management of Cybersecurity in Medical Devices, U.S. Department of Health and Human Services, Washington, DC, USA, Oct. 2018.

[13] H. Rathore, A. Mohamed, A. Al-Ali, X. Du, and M. Guizani, "A review of security challenges, attacks and resolutions for wireless medical devices," in *Proc. 13th Int. Wireless Commun. Mobile Comput. Conf. (IWCMC)*, Jun. 2017, pp. 1495-1501.

[14] R. Ron, P. Victoria, D. Kelley, R. Mark, and G. Gary, "Protecting controlled unclassified information in nonfederal systems and organizations," in *Proc. NIST*, Feb. 2020, pp. 52-55.

[15] T. Elgamal, "A public key cryptosystem and a signature scheme based on discrete logarithms," *IEEE Trans. Inf. Theory*, vol. IT-31, no. 4, pp. 469-472, Jul. 1985.

[16] R. L. Rivest, A. Shamir, and L. Adleman, "A method for obtaining digital signatures and public-key cryptosystems," *Commun. ACM*, vol. 26, no. 1, pp. 96-99, Jan. 1983.

[17] J. Daemen and V. Rijmen, "Reijndael: The advanced encryption standard," *J. Softw. Tools Prof. Programme*, vol. 26, no. 3, pp. 137-139, 2001.

[18] R. C. H. Krawczyk and M. Bellare, "HMAC: Keyed-hashing for message authentication," Tech. Rep. RFC 2104, Feb. 1997. [Online]. Available: https://www.hjp.at/doc/rfc/rfc2104.html

[19] Digital signature standard (DSS), National Institute of Standards and Technology, Gaithersburg, MD, USA, Jul. 2013.

[20] V. M. Potdar, S. Han, and E. Chang, "A survey of digital image watermarking techniques," in *Proc. 3rd IEEE Int. Conf. Ind. Informat.*, Aug. 2005, pp. 709-716.

[21] A. Cheddad, J. Condell, K. Curran, and P. Mc Kevitt, "Digital image steganography: Survey and analysis of current methods," *Signal Process.*, vol. 90, no. 3, pp. 727-752, Mar. 2010.

[22] D. Bouslimi, G. Coatrieks, M. Cozic, and C. Roux, "A joint encryption/watermarking system for verifying the reliability of medical images," *IEEE Trans. Inf. Technol. Biomed.*, vol. 16, no. 5, pp. 891-899, Sep. 2012.

[23] S. Haddad, G. Coatrieks, A. Moreau-Gaudry, and M. Cozic, "Joint Watermarking-Encryption-JPEG-LS for medical image reliability control in encrypted and compressed domains," *IEEE Trans. Inf. Forensics Security*, vol. 15, pp. 2556-2569, 2020.

[24] D. Bouslimi and G. Coatrieks, "A crypto-watermarking system for ensuring reliability control and traceability of medical images," *Signal Process., Image Commun.*, vol. 47, pp. 160-169, Sep. 2016.

[25] C. V. Kumar, V. Natarajan, K. Nirmala, T. Balasubramanian, K. R. Rao, and S. Krishnan, "Encrypted separable reversible watermarking with authentication and error correction," *Multimedia Tools Appl.*, vol. 78, no. 6, pp. 7005-7027, Mar. 2019.

[26] R. Schmitz, S. Li, C. Grecos, and X. Zhang, "A new approach to com-mutative watermarking-encryption," in *Proc. IFIP Int. Conf. Commun. Multimedia Secur.*, 2012, pp. 117-130.

[27] D. Bouslimi, G. Coatrieks, M. Cozic, and C. Roux, "Data hiding in encrypted images based on predefined watermark embedding before encryption process," *Signal Process., Image Commun.*, vol. 47, pp. 263-270, Sep. 2016.

[28] J.-P. Aumasson, L. Henzen, W. Meier, and M. Naya-Plasencia, "Quark: A lightweight hash," *J. Cryptol.*, vol. 26, no. 2, pp. 313-339, Apr. 2013.

[29] I. B. Damgrd and M. J. Jurik, "A length-flexible threshold cryptosystem with applications," *BRICS Rep. Ser.*, vol. 10, no. 16, p. 350, Mar. 2003.

[30] P. Paillier, "Public-key cryptosystems based on composite degree residue-osity classes," in *Proc. Int. Conf. Theory Appl. Cryptograph. Techn.*, 1999, pp. 223-238.

[31] M. J. Jurik, *Extensions to the Paillier Cryptosystem with Applications to Cryptological Protocols*. Citeseer, Princeton, NJ, USA, 2003.

[32] B. A. Wichmann and I. D. Hill, "Algorithm AS 183: An efficient and portable pseudo-random number generator," *Appl. Statist.*, vol. 31, no. 2, p. 188, 1982.
[33] P. L'Ecuyer, "Tables of linear congruential generators of different sizes and good lattice structure," *Math. Comput.*, vol. 68, no. 225, pp. 249–261, Jan. 1999.

[34] S. Frankel and H. Herbert, "The AES-XCBC-MAC-96 algorithm and its use with IPsec," Tech. Rep. RFC 3566, Sep. 2003. [Online]. Available: https://www.hjp.at/doc/rfc/rfc3566.html

[35] C. Gentry, S. Halevi, and N. P. Smart, "Homomorphic evaluation of the AES circuit," in *Proc. Adv. Cryptol. Conf.*, 2012, pp. 850–867.

[36] Z. Brakerski, C. Gentry, and V. Vaikuntanathan, "(Leveled) fully homomorphic encryption without bootstrapping," *ACM Trans. Comput. Theory*, vol. 6, pp. 1–36, Jul. 2014.

[37] S. Mella and R. Susella, "On the homomorphic computation of symmetric cryptographic primitives," in *Proc. Cryptogr. Coding Conf.*, 2013, pp. 28–44.

[38] A. Canteaut, S. Carpov, C. Fontaine, T. Lepoint, M. Naya-Plasencia, P. Paillier, and R. Sirdey, "Stream ciphers: A practical solution for efficient homomorphic-ciphertext compression," *J. Cryptol.*, vol. 31, no. 3, pp. 885–916, 2018.

[39] P. L'Ecuyer, R. Simard, E. J. Chen, and W. D. Kelton, "An object-oriented random-number package with many long streams and substreams," *Oper. Res.*, vol. 50, no. 6, pp. 1073–1075, 2002.

[40] F. Kerschbaum, D. Biswas, and S. D. Hoogh, "Performance comparison of secure comparison protocols," in *Proc. 20th Int. Workshop Database Expert Syst. Appl.*, 2009, pp. 133–136.

[41] M. Tebaa, S. El Hajji, and A. El Ghazi, "Homomorphic encryption applied to the cloud computing security," in *Proc. World Congr. Eng.*, 2012, pp. 4–6.

[42] R. Bellafqira, G. Coatrieux, E. Genin, and M. Cozic, "Secure multilayer perceptron based on homomorphic encryption," in *Proc. Int. Workshop Digit. Watermarking*, 2019, pp. 322–336.

[43] A. C. C. Yao, "How to generate and exchange secrets," in *Proc. 27th Annu. Symp. Found. Comput. Sci. (SFCS)*, Oct. 1986, pp. 162–167.

[44] I. Damgård, M. Geisler, and M. Krøgaard, "Efficient and secure comparison for on-line auctions," in *Proc. Australas. Conf. Inf. Secur. Privacy*, 2007, pp. 416–430.

[45] A. Nait-Ali and C. Cavaro-Ménard, *Compression of Biomedical Images and Signals*. Hoboken, NJ, USA: Wiley, 2008.

[46] A. Tiwari and T. H. Falk, "Lossless electrocardiogram signal compression: A review of existing methods," *Biomed. Signal Process. Control*, vol. 51, pp. 338–346, May 2019.

[47] D. Koff, P. Bak, P. Brownrigg, D. Hosseinzadeh, A. Khademi, A. Kiss, L. Lepanto, T. Michalak, H. Shulman, and A. Volkening, "Pan-Canadian evaluation of irreversible compression ratios ('lossy' compression) for development of national guidelines," *J. Digit. Imag.*, vol. 22, no. 6, p. 569, 2009.

[48] A. Khan, A. Siddiqa, S. Munib, and S. A. Malik, "A recent survey of reversible watermarking techniques," *Inf. Sci.*, vol. 279, pp. 251–272, Sep. 2014.

[49] G. Coatrieux, W. Pan, N. Cuppens-Boulahia, F. Cuppens, and C. Roux, "Reversible watermarking based on invariant image classification and dynamic histogram shifting," *IEEE Trans. Inf. Forensics Security*, vol. 8, no. 1, pp. 111–120, Jan. 2013.

[50] N. P. Smart and F. Vercauteren, "Fully homomorphic SIMD operations," *Des., Codes Cryptogr.*, vol. 71, no. 1, pp. 57–81, 2014.

[51] L. Trieu Phong, Y. Aono, T. Hayashi, L. Wang, and S. Moriai, "Privacy-preserving deep learning via additively homomorphic encryption," *IEEE Trans. Inf. Forensics Security*, vol. 13, no. 5, pp. 1333–1345, May 2018.

[52] Y. Lindell, *How to Simulate it—A Tutorial on the Simulation Proof Technique*. Springer, 2017, pp. 277–346.

[53] P. L'Ecuyer and S. Tezuka, "Structural properties for two classes of combined random number generators," *Math. Comput.*, vol. 57, no. 196, pp. 735–746, 1991.

[54] P. L'Ecuyer, "Combined multiple recursive random number generators," *Oper. Res.*, vol. 44, no. 5, pp. 816–822, 1996.

[55] P. L'Ecuyer and R. Simard, "Testu01: A library for empirical testing of random number generators," *ACM Trans. Math. Softw.*, vol. 15, pp. 1–40, Aug. 2007.

[56] H. Krawczyk, "How to predict congruential generators," *J. Algorithms*, vol. 13, no. 4, pp. 527–545, 1992.

[57] C. Li and B. Sun, "Using linear congruential generators for cryptographic purposes," in *Proc. 20th Int. Conf. Comput. Appl.*, May 2005, pp. 13–19.

<figure><img src="image_6.png" /></figure>

**MAXIME PISTONO** (Member, IEEE) received the B.Sc. degree in mathematics and the M.Sc. degree in mathematics and application from Aix-Marseille University, France, in 2015 and 2017, respectively, and the M.Sc. degree in information security and cryptography from the University of Limoges, Limoges, France, in 2018. He is currently pursuing the Ph.D. degree with the IMT Atlantique in Laboratory of Medical Information Processing, INSERM U1101, Brest, France,

focusing on compression, processing, and security using different cryptographic mechanisms, including homomorphic encryption, stream cipher, and watermarking.

His research interests include data processing and compression in a secure way.

<figure><img src="image_7.png" /></figure>

**REDA BELLAFQIRA** (Member, IEEE) received the M.Sc. degree in information security and cryptography from the University of Limoges, Limoges, France, in 2014, and the Ph.D. degree from the IMT Atlantique Bretagne-Pays de la Loire, Brest, France, in 2017.

Since 2018, he has been a Postdoctoral Researcher with the Laboratory of Medical Information Processing, Inserm UMR 1101. He is currently an Associate Professor with the Department

of Information and Image Processing, IMT Atlantique, and conducts his search activities within the Laboratory of Medical Information Processing, Inserm UMR 1101, and the Joint Laboratory SePEMeD (Security and Processing of Externalized Medical Image Data). His research interests include data security, with a particular interest for protecting medical images and database from malicious entities and service providers using cryptographic and watermarking tools.

<figure><img src="image_8.png" /></figure>

**GOUENOU COATRIEUX** (Senior Member, IEEE) is currently a Full Professor with IMT Atlantique, Brest, France, and conducts his research in the Laboratory of Medical Information Processing, Inserm UMR 1101, Brest, where he leads the research axis Multimedia Medical Information Analysis, Protection and Secondary Use. He is also the Head of the Joint Laboratory SePEMeD (Security and Processing of Externalized Medical Image Data). His research interests include

watermarking, crypto-watermarking, secure processing of data, and digital forensics. He is also a member of the International Federation for Medical and Biological Engineering "Global Citizen Safety and Security Working Group" and the European Federation for Medical Informatics "Security, Safety, and Ethics Working Group," and has contributed to the Technical Committee of "Information Technology for Health" of the IEEE EMB Society. He is also an Associate Editor of the *Innovation and Research in Biomedical* and a Past Associate Editor of Engineering and the IEEE JOURNAL ON BIOMEDICAL AND HEALTH INFORMATICS and *Digital Signal Processing*.