Optimizing the communication cost when using homomorphic encryption

Scenario

In typical applications of homomorphic encryption, one of the first steps consists for a user, let's call her Alice, to encrypt her data $m$ under a public key $\textsf{pk}$ and send the ciphertext $c = \textrm{Enc}(\textsf{pk}, m)$ to someone else, e.g. to the Cloud (see Fig. 1).

Fig. 1. Alice sends her data $m$ encrypted to the Cloud, which publicly performs an operation $f$ on it.

The Cloud then performs publicly a function $f$ on the data, and sends back the result to Alice. Unfortunately, even the most recent homomorphic encryption schemes (e.g. BGV or GSW) are such that the size of the ciphertext $c = \textrm{Enc}(\textsf{pk}, m)$ is much larger than the size of $m$. Typically, to encrypt a 4MB image, the ciphertext will end up being at least 1 GB long!

Using an Hybrid Approach

In 2012, Michael Naehrig, Kristin Lauter and Vinod Vaikuntanathan suggested to use the following hybrid approach: encrypt the message $m$ under a scheme with no ciphertext expansion (i.e. the ciphertext will have the same size as $m$), e.g. under the Advanced Encryption Standard $\hat c = \textsf{AES}_k(m)$ for a key $k$, and send to the Cloud $(\textsf{Enc}(\textsf{pk}, k), \hat c)$. Now, the communication cost becomes the cost of sending $\hat c$ (same size as $m$) and sending only once $\textsf{Enc}(\textsf{pk}, k)$, which is independent of the data $m$, i.e. is quasi-optimal.

The Cloud has now to perform the $f\circ \textsf{AES}^{-1}_k$ instead of $f$ to publicly compute the expected result as in Fig. 1.

This solution was first implemented by Craig Gentry, Shai Halevi and Nigel Smart in 2012 (Nigel Smart is a member of the HEAT project). Recent timings (from early 2015) demonstrates the possibility to evaluate only $\textsf{AES}^{-1}_k$ (i.e. taking parameters to evaluate the latter function but nothing else) in less than 7 minutes on a classical laptop.

However, this approach has several drawbacks. First, AES was not at all designed in a context of homomorphic cryptography: the operations are not easily parallelizable, the multiplicative depth is large: AES does not appear to be particularly well suited for homomorphic evaluations. Second drawback, the latency of the homomorphic evaluation of $\textsf{AES}^{-1}_k$ is added to the latency of the homomorphic evaluation of $f$: in other words, the data will be homomorphically processed upon after being homomorphically decrypted (i.e. 7 minutes later!).

Block Ciphers for Homomorphic Evaluations

The first drawback has been investigated in a series of work (LN14, DSES14...), trying to replace AES by lighter primitives such as SIMON or PRINCE: the resulting homomorphic evaluations have a much smaller latency. Au EUROCRYPT 2015, Martin Albrecht, Christian Rechberger, Thomas Schneider, Tyge Tiessen and Michael Zohner presented a new family of block cipher especially designed for homomorphic encryption called LowMC (see also our blog article about EUROCRYPT). Designed to have a shallow decryption circuit (multiplicative depth of 11), they performed much better than previous approaches. Unfortunately, LowMC was broken soon after its publication because of weaknesses inherent in its low multiplicative complexity.

Revisiting the Whole Hybrid System

In 2015, partly founded by the HEAT project, Tancrède Lepoint and Pascal Paillier from CryptoExperts together with Anne Canteaut, Sergiu Carpov, Caroline Fontaine, María Naya-Plasencia and Renaud Sirdey proposed to revisit the hybrid system entirely to tackle both drawbacks mentioned earlier in an article available on the Eprint archive. The key idea is to identify that the homomorphic "decompression" phase is subject to an offline phase and an online phase. The offline phase is plaintext-independent and therefore can be performed in advance, whereas the online phase completes decompression upon reception of the plaintext-dependent part of the compressed ciphertext. 

Using the notation of above, the offline phase consists in sending $\textsf{Enc}(\textsf{pk}, k)$ because this value does not depend on the data. And the online phase consists in sending the data $m$ encrypted under the key $k$.

The second drawback presented earlier is that the online phase has a long latency. Making the online phase as quick as technically doable leads us to choose an additive IV-based stream cipher instead of AES. Therefore the system performs as in Fig. 2.

Fig. 2. When receiving the encryption $\textsf{Enc}(\textsf{pk}, k)$ of the symmetric key $k$, the Cloud can perform during the offline phase (i.e. before getting any data $m$) the generation of the keystream using a stream cipher adapted to current homomorphic encryption constraints. Therefore the latency of the online phase is minimal: when receiving the one-time padded message $m\oplus\textsf{keystream}$, the Cloud can homomorphically and very efficiently evaluate the XOR to obtain $\textsf{Enc}(\textsf{pk}, m)$.

To accelerate the offline phase (and tackle the first drawback), we propose our own stream cipher candidates adapted to homomophic encryption : the keystream generator Trivium, which belongs to the eSTREAM portfolio of recommended stream ciphers, and a new proposal called Kreyvium, which shares the same internal structure. The main advantage of Kreyvium over Trivium is that it provides 128-bit security (instead of 80-bit) with the same multiplicative depth, and inherits the same security arguments. 

Finally, we show that the promising performances obtained by LowMC can also be achieved with Trivium, a well-known primitive whose security has been thoroughly analyzed, and by Kreyvium. The 10-year analysis effort from the whole community, initiated by the eSTREAM competition, enables us to gain confidence in its security. Also our variant Kreyvium, with a 128-bit security, benefits from the same analysis since the core of the cipher is essentially the same. Also the Cloud can also exploits the highly parallel structure of Trivium and Kreyvium to speed up the homomorphic evaluation.

Ring-GSW

This post is about a ring variant of the GSW FHE scheme, which has been dubbed SHIELD by its authors. The original paper SHIELD is available here.   What is interesting about the SHIELD scheme is that noise increases less than in other schemes if you multiply a number of fresh ciphertexts together in sequence. In addition there is no $p$ and $q$, but only a single modulus $q$. The plaintext space is the ring $R_q={\mathbb F}_q[X]/\Phi_m(X)$ for some cyclotomic polynomial $\Phi_m(X)$.

However, there are a number of drawbacks which include the fact that the ciphertext consists of many elements of $R_q$ and that whilst messages from the whole of $R_q$ maybe encrypted operating on such messages can be a problem. For example scalar multiplying a ciphertext by an element in $R_q$ will make it undecryptable, or homomorphicallhy operating on encryptions of "non-small" elements of $R_q$ will result in decryption not working due to excessive noise growth. These problems do not occur in systems which have a plaintext modulus $p$ which is much smaller than $q$, such as BGV or YASHE.

As usual we define a secret key as a small element $t$ in the ring $R_q$, and the public key is given by a Ring-LWE tuple with respect to this secret, i.e. a pair $(a,b)$ where $a$ is chosen uniformly at random from $R_q$ and $b=a \cdot t+e$ for some small element $e$ in $R_q$. 

To encrypt we form an $N \times 2$ matrix where $N=2\cdot \log_2 q =2 \cdot \ell$. We pick two matrices consisting of small elements in $R_q$, one $R$ is of dimension $N \times 1$ whilst the other $E$ is of size $N \times 2$. A plaintext $m \in R_q$ is then encrypted via the equation

$$ C =m \cdot B + R \cdot (b,a) + E$$

where $B$ is the $N \times 2$ matrix which is zero everywhere, but has the element $2^i$ in location $(i,1)$ and $(i+\ell,2)$ for $i=0,\ldots,\ell-1$.

To decrypt we multiply $C$ by the vector $(1,-t)^T$ so as to obtain an $N$ dimensional column vector which has $m \cdot 2^i + \mathsf{error}$ in position $i$ and $m \cdot 2^i \cdot t + \mathsf{error}$ in position $i+\ell$. The message $m$  can then be recovered by solving this `trivial' variant of the hidden number problem (an exercise for the reader).

To homomorphically add two ciphertexts we simply add the associated matrices together. To homomorphically multiply ciphertexts $C_1$ and $C_2$ we take $C_1$ and apply a bit-decomposition method to it, the resulting matrix is then multiplied into $C_2$ on the left.  We need to keyswitching etc, so multiplicaton is involved but relatively simple. 

The noise growth for homomorphic addition behaves additively. But the noise growth for homomorphic multiplication behaves as $B_1 \cdot || m_2||_1 + B_2 \cdot n \cdot \log q$ where $B_i$ is a noise bound for ciphertext $C_i$ and $m_2$ is the plaintext underlying $C_2$.  This gives very good noise growth if the messages which are encrypted are very small, e.g.bits, but it is less useful when the messages are from all of $R_q$. Thus whilst we can encrypt messages in the whole of $R_q$, we are unable to perform homomorphic operations on such ciphertexts. Making the benefit of Ring-GSW less than one would immediately expect.

 

Hardness of the LWE problem

One of the goals of the HEAT project is to better understand the hardness of the computational problems that underly SHE. One of those problems, the Learning with Errors problem, has been investigated repeatedly, but until now, there was no consistent way to specify security parameters. In order to resolve this and increase interest in LWE-based cryptosystems, we built an efficient online security estimation tool, available to anyone and straightforward to use.

The LWE problem has three parameters: a dimension n, a Gaussian width parameter s and a modulus q. In order to implement the complexity of attacks against LWE as a function of these parameters, we combined results from the literature of the last couple of years, with a main focus on the Bounded Distance Decoding attack and the Blum-Kalai-Wasserman (BKW) algorithm. 

Our webtool implements the following three attacks:

- The SIS-based attack is an attack against the LWE decision problem, as described by Micciancio and Regev. Given a pair (A,t), one searches a vector v orthogonal to the rows of A (mod q) and checks whether the inner product <v,t> is small. 

- The Bounded distance decoding (BDD) attack is a combination of lattice basis reduction and the nearest planes algorithm of Lindner and Peikert. It attempts to solve the LWE search problem by searching a lattice point close to t.

- The BKW (Blum-Kalai-Wasserman) algorithm approaches the LWE search problem as a noisy linear system and uses a blocked version of Gaussian elimination with back substitution. This method was recently optimised by Duc, Tramèr and Vaudenay. 

Designers of cryptosystems are no longer restricted to parameters proposed in papers, but can use this tool to query the security estimates of any set of LWE parameters. Finally, in order to further simplify the process of choosing LWE parameters, we also implemented the search for a suitable modulus q. A user can input parameters n and s and a security level sec to obtain the approximate value of log_2(q) that results in sec bits of security.

 

Lauren De Meyer

Satellite Case Study for Homomorphic Encryption

Satellite Case Study for Homomorphic Encryption

The satellite industry is strategically important for Europe, and generates significant revenue as well as employing many tens of thousands of people in Europe. A particular issue facing European satellite providers is shared use and reconfigurability of infrastructure. Flexibility and configurability, and particularly shared use of satellites and their infrastructure, is essential to enable affordable use of satellites. The costs of launching and managing a single use satellite are prohibitive for many organisations. The ability to share this cost over multiple customers would expand the commercial reach of European satellite providers.

Shared infrastructure would ideally cover the satellites themselves, communication links to the ground, and the ground infrastructure which collates, processes and otherwise manages data received from the satellites. However, it brings with it security concerns due to the differing commercial and national sensitivities of the applications and data. In the HEAT project, we are looking at how Homomorphic Encryption could allow encryption to be used to provide the required security separation on such shared infrastructure, while still allowing essential and value-add processing of data to take place. It could also allow more cost-effective outsourcing of data processing and storage to Cloud Computing providers.

Potential applications areas are:

•  Commercial domain: the ground segment for the European Space Agency (ESA) Copernicus programme. Access to the Sentinel satellites’ Earth-observation data and generated products is restricted for commercial reasons. These missions will require increased processing capacity and would benefit from Cloud solutions.
• Scientific domain: the future Euclid ground segment. Scientific data for missions such as Euclid are confidential as access needs to be restricted to institutes, universities, etc. contributing to the mission, in order to ensure that they will publish the first papers and have the benefit of any discoveries. The confidentiality of scientific data is not uniquely defined. Therefore, solutions that allow flexibility in the security separation required (i.e. are not tied to the infrastructure) and allow outsourcing of the processing and storage would be of significant benefit.
• Dual domain (civilian & military): ESA’s Space Surveillance Awareness programme, and in particular the Space Surveillance and Tracking centre. Examples of sensitive data include sensor data, operational information (e.g. precise orbit information or existence of a satellite) and tactical information (e.g. object detached from a satellite).

For more than 40 years now, Thales Alenia Space has designed, integrated, tested, operated and delivered innovative space systems. Thales Alenia Space’s satellites and payloads are recognized worldwide as benchmarks in delivering communications and navigation services, monitoring our environment and the oceans, better understanding climate change and supporting scientific research. Thales Alenia Space is a leader in Earth observation, based on its high or very-high resolution optical and radar payloads. The appropriate handling of such sensitive data, using techniques such as homomorphic encryption, is a challenge, which the results of the HEAT project will help to address.

Homomorphic Encryption At EUROCRYPT 2015

This is a blog post from the Eurocrypt 2015 conference held in Sofia, Bulgaria, this week. There were a number of talks which were related to homomorphic encryption; which we discuss below.

Kristen Lauter: Practical Applications of Homomorphic Encryption

Kristen gave one of the three invited talks, and she focused on topics which are closely related to the HEAT project. She first described the Secure Genome Analysis competition run last month, which was sponsored by the United States' NIH funding agency. The idea behind the competition was to encourage research on practical computations on encrypted genomic data. The competition involved both FHE and MPC technology, and attracted eleven submissions. The submissions related to FHE from Kristen's group at Microsoft as well as submissions from IBM, Stanford/MIT, UCI and Tsukuba.

The competition raised a lot of excitement in the bioinformatics community and in popular science journals. The reason for this excitement is the confluence of interest in both privact protection and genome research data, which on its own poses a significant risk in relation to personal data. The competition also encouraged interdisciplinary work between Computer Science, Mathematics,
Bioinformatics and Policy.

The spur in research in the area has resulted from the drop in the cost of sequencing a human genome. This was estimated to cost 3 billion US dollars in 2000 per person, but now costs around 1000 USD per person. This drop in cost opens up new applications in personalized medicine, forensic work, ancestry, anthropology and other areas. Yet, it brings to the fore the need for  LARGE
SCALE PRIVACY PRESERVING analysis. Since the privacy risks are not only for the people being sequenced but also their families.  

Kristen went onto discuss the various Secure GWAS (Genome Wide Association Scenarios) that the competition covered. The two main areas were where there was a single data owner (e.g. one patient and one hospital) versus multiple data owners (which are mututally distrusting).  The talk focused on the single data owner case, as the other case is really more suited to MPC than FHE.

There were two challenges in the single data owner case. The first challenge was related to large scale statistical studies. Two hundred cases were taken from the PGP (Personal Genome Project) from Harvard Medical School, as well as 200 randomized controls and various statistical operations were performed. It turned out that the required computation could be done by only the additively homomorphic Paillier system. However, the somewhat homomorphic LWE based system had faster evaluation time than the Paillier scheme, and was hence relatively competitive.

In the second challenge two individuals were randomly selected from the PGP and 5000, 10000 and 100000 locations in the genome sequence were also selected. The competitors task was to compute the edit distance and Hamming Weight on the two sequences at the given locations. Despite the complexity of the task (the edit distance has a relatively deep circuit), the processing times for the LWE based schemes was measured in seconds as opposed to minutes.

It turned out that much of the work in these challenges was not directly cryptographically related. There were issues related to cleaning of the data, how data was encoded, time vs memory trade-offs in the algorithms used, as well as parameter selection (related to function and data size as opposed to
security).
   
Kristen then discussed another example, which was demonstrated at a recent American Assoication for the Advancement of Science (AAAS) meeting. In this application encrypted measurements of an individuals weight, age, height, blood pressure etc were transmitted to the cloud, and then the cloud produced an encryption of the likelihood of the individual having a heart attack. The overall computation took less than 0.2 of a second on the cloud, however the cost of sending the ciphertext to the cloud was far more due to the large ciphertext sizes.  In some sense this was a silly example as the function could be computed by the individual themselves. However there are scenarios where the function is private, thus this example demonstrates that something can be done in such situations.

Kristen ended with a number of research open problems which included that of reduced the storage and transmission costs, which often dominated the computation in the examples considered in the talk, the problem of analyzing the new hard problems such as RLWE upon which most schemes depend, as well as moving the computations to those of real life in scale by (for example) considering larger amounts of data or deeper circuits.

Ciphers for MPC and FHE:  Martin Albrecht, Christian Rechberger, Thomas Schneider, Tyge Tiessen and Michael Zohner

Earlier in the conference this paper was presented which tries to reduce the storage requirements by using a hybrid FHE scheme $HE_{pk}(k), Enc_k(m)$. The key problem being to define a symmetric encryption scheme $Enc_k$ which is easy to homomorphically evaluate using a homomorphic encryption scheme. This is a new design requirement for such symmetric primitives. The main difference between standard ciphers is that in the homomorphic environment XOR gates are cheaper than AND gates (a situation which holds also in MPC applications as well as FHE ones). Usually cipher designers assume the two costs are equivalent. Thus the question arises as to what would an efficient cipher look like if such linear operations are for free.

The paper considered a number of possible metrics for such ciphers for example i) the number of ANDs per bit of encrypted text, ii) the multiplicative depth, or iii) the total number of ANDs per encryption. Existing schemes such as Noekeon, Fantomas, and Robin meet these design criteria; but they were introduced for side-channel resistance. For FHE applications we need something more extreme.

The authors decided to pick an SPN design with very small S-Boxes. However, not all S-Boxes where used in each substitution later. The parameters of the scheme are the block size n, the number of S-Boxes used in the substitution layer m, the key size k, and the data complexity d (effort required to break the cipher). From these values they estimate the required number of rounds r.

For the S-Boxes the authors selected a 3-bit to 3-bit S-box consisting of three AND gates and having multiplicative depth one. The affine layers are selected by choosing a uniform random binary matrix and vector and computing  

$$ Ax+b. $$ 

To produce a NUMS (Nothing Up My Sleeve) matrix the Grain LFSR is used to generate the matrix.
 

The talk went on to discuss security against differential, algebraic and other forms of cryptanalysis. Coming up with example parameters of $n=256$, $m=63$, $r=12$ and $d=2^{128}$ with a total AND depth of twelve (compared to $40$ for AES).
 

Fully Homomorphic Encryption over the Integers Revisited: Jung He Cheon and Damien Stehle

This paper examined the security of integer based FHE/SHE schemes. These are derived from the original DGHV scheme and their security is based on the AGCD problem. There are two key issues with schemes based on AGCD; first there is no known reduction to a classical lattice problem (unlike the LWE based schemes) and the schemes need an additional sparse subset sum problem for
bootstrapping.

This talk solved both of these problems. It showed a reduction from LWE to AGCD, and hence AGCD is no easier than worst case lattice problem. It then showed that the cost estimate of various previous orthogonal lattice attacks on these schemes was overly pessimistic. Finally it gave an integer based scheme which was as secure as LWE, had smaller ciphertexts than previous schemes and
which did not require an additional assumption for bootstrapping.

The new scheme was similar to previous schemes in that encryption involved sampling a subset of encryptions of zero and then adding these onto the message. The message itself was embedded in the upper bits of the ciphertext (as in usual scale invariant schemes). Finally multiplication was performed using the usual trick of BitDecomp and PowerOfTwo used in other schemes.

Leo Ducas and Daniele Micciancio: FHEW: Bootstrapping in less than a second.

Whilst HELib (see below) can do bootstrapping in about 6 mins, and this is amortized over many ciphertexts using SIMD operations, this work refreshes one ciphertext, with no amortization, in 0.61 seconds on a 3GHz machine.

The key idea is to provide a new cheap NAND gate and then a simpler refreshing procedure using the ring structure. The cost of the Homomorphic NAND operation is relatively very small.  This was then combined with the general bootstrapping  approach using the ring variant of GSW scheme and using the approach of Alperin-Sheriff and Peikert from last year.  Implementing mod q arithmetic "in
the exponent".   The decryption circuit itself is implemented as an accumulator; which is very well suited to the GSW scheme.  To do reduction mod q we embed the group $(Z_q,+)$ into the $q$th roots of unity.

For sample parameters the authors have a bootstrapping key size of 1.3 GB. The main issue is computing fast fourier transforms (for which they used the FFTW library).

Bootstrapping for HELib: Shai Halevi and Victor Shoup.

The talk started by discussing the three generations of FHE schemes (as typified by the original Gentry scheme, the BGV scheme and the GSW scheme). The slow noise growth in third generation schemes such as GSW is however incompatible  with ciphertext packing.  Thus in terms of efficiency there is a fork in current schemes. One either uses packing and large noise (as in BGV style schemes) or small noise and no packing (as in GSW style schemes). The purpose of this talk was to focus on schemes which support packing.

There are very few bootstrapping implementations; and none (up to now) utilize packing. The paper starts by utilizing the techniques of GHS12 (The "Better Bootstrapping" paper), which focuses on $p=2$ and $q=2^e+1$. The technique requires one to encrypt the secret key modulo the plaintext
space $2^{e+1}$. Then we need to extract the most significant bit; this is the non-linear part of the procedure.

The problem in GHS12 was applying the procedure to packed ciphertexts. This is a linear operation. Then we do the above non-linear step. Then reverse the linear step. Alperin-Sheriff and Peikert showed how to perform these linear steps more efficiently.  This paper generalises GHS12 technique to arbitrary $p$, and not just $p=2$ and then specializes the AP linear techniques to make them more efficient. 

Computationally the hard bit is the non-linear step, the hardest to implement is however the linear parts.  The authors presented a technique to implement matrix-vector multiplicatin in a SIMD manner. This method uses a arotation methodology (slow but adds little noise) and multiplication by constants (fast but adds lot of noise). To get the algebra to work they needed to impose constraints on m and p (dimension and plaintext modulus).

For small $p$ bootstrapping takes 12 levels, for larger $p$ can go to 24 (or even 48 levels). Can put extension field elements in the slots, and not just integers.  Single thread performance between 5 mins and 5 hours. For AES style parameters have a depth 24 evaluation of which 11 are for bootstrapping,
allowing enough for a round of AES to be done.  Now AES with bootstrapping allows much smaller parameters, without need bigger parameters. The new implementation without bootstrapping can evaluate 120 blocks in 245 secs, whilst the method with bootstrapping can evaluate 180 blocks in 1050 seconds

A short history of lattice reduction in cryptography: from direct applications to FHE.

After the discovery of the LLL lattice reduction algorithm in 1982, it quickly became an handy tool for cryptanalysts. In particular, it was used as a weapon of choice against knapsack-based cryptosystems. More generally, at that time, lattice reduction was mostly used to find linear relations between integers or vectors of integers. This is a very direct application but it already showed the power of the LLL algorithm as a cryptographic tool. Interestingly, in order to analyze the performance of lattice reduction in this context, it was pretty standard to assume that a lattice reduction oracle was available and to prove that a given system could broken with such an oracle. The underlying heuristic assumption was that in practice, the behavior of LLL closely approximated the reduction oracle. This heuristic was motivated by the fact that for the lattice dimensions that were tractable at that time, the result of LLL was usually good enough to make attacks developped in the reduction oracle setting pratical.

In 1996, the discovery of Coppersmith's small root algorithms was a major change that greatly renewed the interest of cryptanalysts in lattice reductions. After this breakthrough, the technique was used in a variety of cryptanalyses, allowing to break some special, speed-optimized, constructions of RSA keys or to leverage side-channel techniques leaking partial information on keys into full-fledged attacks. More surprisingly, it was also used constructively as a tool to understand the security of RSA-OAEP. A very strong property of Coppersmith's small root algorithms it that it is no longer necessary to assume the existence of a reduction oracle and that LLL itself can provably be used in the method.

Droping the reduction oracle is a very important progress. Indeed, around the same time, it became clear that lattice reduction remains a difficult problem. From a complexity theoretic viewpoint, Ajtai showed that the problem of finding a shortest non-zero lattice vector is NP-hard for randomized reduction. From a constructive cryptographic viewpoint, the first cryptosystems based on the hardness of lattice related problems started to appear. Since then lattice-based cryptography underwent steady progress. A major success of the field was the discovery by Gentry of the first fully homomorphic encryption scheme based on ideal lattices.

Case Study: Automated Detection of Organized Crime

Automated Detection of Organized Crime (ADOC)

Europol’s 2013 Organised Crime Threat Assessment (OCTA), published April 2013, reveals that organised crime is becoming increasingly diverse in its methods, group structures, and impact on society. A new criminal landscape is emerging, marked increasingly by highly mobile and flexible groups operating in multiple jurisdictions and criminal sectors.

Organised crime is a multi–billion euro business in Europe and it is growing. The ex- pansion of Internet and mobile technologies, the proliferation of illicit trafficking routes as well as opportunities offered by the global economic crisis, have all contributed to the development of a more potent threat from organised crime 

says Rob Wainwright, Director of Europol.

Tools supporting the systematic environmental scanning for weak signals, searching / fusing / interpreting data from different sources such as databases with personal information and public web sites exist and are increasingly being used by intelligence services. Such systems typically have access to many large personal databases.

EU Data Protection

The most important instruments governing data privacy in Europe (which the HEAT architecture will fully comply with) include

- the Council of Europe (CoE) Convention on Human Rights and Fundamental Freedom (ECHR) – namely art. 8;

- the Charter of Fundamental Rights of the European Union (CFREU) – namely art. 7 and 8;

- the CoE Convention No. 108 on the protection of individuals with regard to automatic processing

of personal data (Convention No. 108) and;

- the Recommendation No. R (87) 15 of the committee of ministers to member states regulating the use of personal data in the police sector.

On one side, the disrespect of these constraints not only exposes police investigators and other OC fighter to legal sanctions and understandable public protest, but also may jeopardise legal cases against members of OC, who often benefit from excellent legal assistance.

On the other side, law enforcement forces need the detection of weak OC signals resulting from environmental scanning to effectively fight existing and emerging OC.

Therefore the abovementioned legal instruments protecting data privacy severely handicap investigators in their attempt to anticipate, detect and fight OC, which in affects threatens personal freedom. The protection of citizen rights makes it more difficult to protect citizen rights.

Solving the Problem with an FHE-based Architecture

The basic principle consists in using FHE/SHE to encrypt databases while enabling data aggrega- tion in the Cloud for authorized users. Authorized users of the ADOC system are law enforcement entities (EU police forces, financial/tax authorities, etc.). A trusted authority (a.k.a a ”judge”) owns a master private key sk and performs on-demand decryptions. The architecture supports the following high-level functionalities:

Database enrollment. a user detaining a number of databases containing personal data encrypts these databases under a system-wide FHE public key pk and publishes the encrypted databases in the Cloud.

Data aggregation. a user performs a data aggregation algorithm homomorphically, possibly across multiple encrypted databases, and gets an encrypted result.

Authorized decryptions. the trusted authority is sollicited by the user to decrypt the aggregation result. Prior to decryption, evidence is provided by the user that the performed aggregation is authorized, e.g. by providing a verifiable transcript of the computation. The trusted authority may provide the necessary material for the user to verify that the decryption was performed correctly.