Antoine Guellier
email: antoine.guellier@supelec.fr

Can Homomorphic Cryptography ensure Privacy?

Keywords: privacy, anonymity, anonymous, PETs, homomorphic, cryptography, fully homomorphic cryptography vie privée, anonymat, PETs, homomorphe, homomorphisme, cryptographie, chiffrement homomorphe

The advent of information technology, the dramatic increase of computational and storage capacities along with the development of worldwide communications promise very personalized, well designed and convenient services. However, although privacy is an important right in our societies, these services often neglect and abuse their consumers' privacy, by collecting sensible data notably. This work focuses on the protection of privacy in information systems. For this, it is known that traditional cryptography (e.g. encryption or signature schemes) is necessary, for instance to ensure confidentiality, but it is not sufficient. To enable usability and privacy at the same time, stronger tools are required. Homomorphic cryptography is a possible and promising candidate for this purpose. This technology allows manipulating encrypted data and performing logical operations on it without actually accessing the data in the clear. In particular, homomorphic cryptography is envisioned as the perfect technology for secure computation (or storage) delegation in the cloud. This work investigates how homomorphic cryptography can enable privacy, by first giving a deep insight of the field of privacy in computer science (systems of interest, tools, main goals, ...) and then presenting homomorphic cryptography and more specifically (fully) homomorphic encryption, aggregating the work done in this branch of cryptography in the last 30 years. At last, this work gives clues to answer the main question can homomorphic cryptography ensure privacy?, and interesting leads currently investigated or yet to be considered.

La cryptographie homomorphe peut-elle assurer la vie privée ?

Introduction

Context In modern societies, the notion of privacy and the question of its protection has been growing along with the development of individual liberties. Several events in the 2 nd millennium can attest of this momentum: the Age of Enlightenment and its writings, the French, British and American revolutions/declarations of independence, the Declaration of the Rights of Man and of the Citizen, and very recently, the Arab Spring in Tunisia, Egypt, Libya, Syria and other countries of the Arab world. All these events have in common to increase the importance the individual in society. Still today, achieving adequate balance between individual liberties and life in community is a dominating issue in the public place organization.

As described in the 1948 Universal Declaration of Human Right of the United Nations, privacy is a right of every individual. The first appearance of privacy as a right dates from the late XIX th century, shortly after the invention and development of photography. According to Warren and Brandeis, it is the continuation of the right of property [START_REF] Samuel | The right of privacy[END_REF].

Because it stems from social considerations, the perimeter of privacy depends on cultures, habits, local history and individual sensitivities. Delimiting privacy is far from trivial, especially because this notion is in constant evolution in the public opinion. As the EDWIGE (in France) or PRISM (mainly in USA) scandals in recent history attest, delimitation of privacy is performed in an ad-hoc manner, i.e. by fails and retries. Note that these "scandals" also show an opposition between national security and privacy. Once defined, privacy is neither easy to enforce, even with legal, technological and economical resources. Furthermore, gaps between reality and the proposed legal or technological theorization are always possible.

Issues

The advent of information technologies in the second part of the XX th century vastly modified and extended the shape of privacy. In 1890, Warren and Brandeis [START_REF] Samuel | The right of privacy[END_REF] were already concerned that the growing easiness to take pictures would put everyone under constant surveillance and make true the prediction "what is whispered in the closet shall be proclaimed from the house-tops". We are now far further from this truth, mostly due to the development of Internet along with computational and storage capacities. We are now able to automatically and systematically collect, store, transform, share and duplicate information at will. Furthermore, information can be stored for decades, centuries, or even hundred of centuries. While this is a great advance for information processing, and may help in decision making or facilitate the duty of remembrance, it turns out that one of the most valuable type of information are the individuals' personal ones. This is where individuals privacy is endangered.

As the public rejoices in the new possibilities offered by technology advances, it is also concerned by the privacy loss incurred (when aware of it). Unfortunately, it is easy to see that the most known and used internet systems (e-commerce, social networks, web search engines, ...) are not privacy-friendly. We could even say they benefit from the privacy losses of their clients, to a certain extent. It falls down to the information technologist and the legislator to inform individuals on the dangers they are exposed to, and to provide protection of their privacy in information system. Although we will only consider the information technologist and not the legislator in this document, these two actors have to work in pair and in parallel to enforce the protections.

Note that there is an important difference between privacy and information security. Security is based on 3 pillars: confidentiality, integrity and authenticity of data. The last two are orthogonal to privacy (although not incompatible), and confidentiality, as it is now widely known, is not enough to ensure privacy. In other words, even though confidentiality is necessary for privacy, it is not sufficient on its own. For instance, in network communications, even if the payload (i.e. the message) is encrypted, an entity observing the network can easily see who communicates with whom. That is a problem when, for instance, an individual accesses a sensible website, such as aa.org or wikileaks.org. solution(s) will be more easily be accepted and used by individuals if the need of privacy is high or critical.

Organization of the document

The rest of this document is organized as follows. In chapter 1, we detail the multiple facets of numerical privacy. We propose a synthetic view of privacy solutions in information systems, and review the fields of computer science where privacy is relevant. In chapter 2, we move on to the presentation of homomorphic cryptography. More specifically, we focus on homomorphic encryption schemes: we categorize them according to their homomorphic capacities, describe each class, and review the schemes they are composed of. Both chapters are concluded by discussions and openings. In particular, we question the need for privacy and we present other homomorphic tools than encryption (e.g. signatures). In our conclusion, we re-unite privacy and homomorphic cryptography: we give clues as of the way to use the latter in order to protect the former.

Chapter 1 Privacy

This first chapter draws a view of the notion of privacy in computer science in general before taking a closer look at privacy from a technical and technological point of view. Although it takes into account the social dimension of privacy, this chapter leaves aside all social reflexions and does not form a general, complete definition of privacy as understood in a very broad sense: we mainly focus on privacy in the digital world and numerical privacy in the rest of this document. This chapter notably reviews the different approaches to privacy and sectors in which privacy is considered desirable or necessary, along with the technical tools provided to the computer scientist willing to take privacy in consideration inside information systems. The last section discusses the facts and results introduced in the chapter and explains the why of privacy.

Proposed definitions

The term "privacy" has been used to refer to multiple notions and concepts, even within the field of computer science alone, and has not always been clearly defined by those using it. We first give attention to the general meanings and acceptations of the term, focusing on numerical privacy, i.e. privacy in the digital world. After drawing several overlapping but different definitions for this notion, we give a practical way to consider privacy in a composed but synthetic view.

Several meanings

In a first approach, the notion of privacy can be defined aside from any technical considerations: its meaning is intuitive, known to anyone and appears in every day life. Indeed, each individual is most likely to be willing to keep some information about himself or his (past) actions private to himself or a set of adaptively chosen persons. One may want to hide information from journalists, co-workers or the general public, conceal the contents of a communication, or even the very fact that he communicated with a specific entity. For some, privacy can also mean spending time alone or with chosen company to dedicate to certain tasks such as (self-)reflexion or hobbies. Others mean by privacy the possibility to take actions without having to justify them. The concept, even though it seems at first glance intuitive and well understandable, has many facets when considering the plethora of contexts in which privacy is crucial, along with the means employed to ensure it. In particular, in the digital and ubiquitous computing world, where individuals do not have access or do not have the proper knowledge to understand complex systems, the concept of privacy is not trivial and comprises many dimensions. Several authors tried to give a definition for privacy in general, which are often partial or far from the above naive and intuitive definition.

Already in 1967, Allan Westin was worried about privacy in the emerging computer society, when electronic devices were becoming more and more accessible. In its seminal book, Privacy and Freedom [START_REF] Westin | Privacy and Freedom[END_REF], he lays the first elements of reflexion on the conflict between surveillance and privacy: he forms the idea that massive data collection and development of surveillance devices may harm individuals' privacy. To his mind, although privacy was (and is) an essential and necessary notion for the individuals' autonomy and liberty, it had never been well defined in social theory, and most studies on the subject were vague and confused. His proposed definition reduces privacy to a right and is centered on information flow control : "Privacy is the claim of individuals, groups, or institutions to determine for themselves when, how, and to what extent information about them is communicated to others." This very general definition has been widely used as a starting point, but as we can see it does not encompass all the examples listed above. Another approach, by Sara Baase [START_REF] Baase | A Gift of Fire: Social, legal, and ethical issues for computers and the Internet[END_REF], defines 3 guarantees that the notion of privacy should imply: (i) freedom from intrusion, (ii) ability to control information dissemination, and (iii) freedom from surveillance, i.e. from being tracked, followed, watched. This definition is more complete as it does not totally reduces to information flow management. However, we can see points (ii) and (iii) as one and the same (i.e. freedom from surveillance is, in definitive, the ability to avoid unwanted information disclosure), and they are more or less equivalent to Westin's definition. The new element here is the freedom from intrusion in the sense of being "left alone" when desired. The definition of privacy is thus augmented compared to Westin's but also more complex. Both definitions are however very abstract and uneasy to work with.

In the field of computer science, privacy needs a practical definition that can be expressed as a formal goal. Following Pfitzmann et al. [START_REF] Pfitzmann | Anonymity, unobservability, and pseudonymity -a proposal for terminology[END_REF], privacy is defined by anonymity, the state for an individual of being not identifiable within a set of individuals (the anonymity set), and/or the property of unlinkability between an individual and its actions or among the actions of a same individual. They are notions specific to computer science, and we can see they differ from Westin and Baase's definitions (although they are not conflicting) as they are much more concrete. The danger using such specific terms is to forget a large portion of what "privacy" means: Pfitzmann's terminology might not embrace all the meanings of privacy.

As we can see, definitions of privacy are either very abstract and unusable, or very specific and possibly incomplete. One of the most relevant and complete definition of privacy, to our knowledge, is depicted in the taxonomy of Daniel Solove [START_REF] Daniel | A taxonomy of privacy[END_REF], which is also a reflexion on the social meaning of privacy: "Privacy is the relief from a range of kinds of social friction, [...] it is protection from a cluster of related activities that impinge upon people in related ways." "Privacy is too complicated a concept to be boiled down to a single essence. Attempts to find such an essence often end up being too broad and vague, with little usefulness in addressing concrete issues." Solove's point of view is, unlike ours, mainly social, and his taxonomy lists the possible privacy harms an individual might suffer in society. He clears out 4 main categories that encompass many (all ?) social meanings of privacy: information collection, information processing, information dissemination and invasion. This categorization, depicted in Fig. 1.1, is still driven by information flow control, but in the details it takes into account the social context (a context Inria that might be very different from one country/culture to another) to create a more complete map of (social) privacy, close to what anyone can experiment by himself. In this document, Solove also insists on the fact that privacy is a complicated concept that refers "to a wide and disparate group of related things", and underlines the fact that using such a broad term must be done with caution in order to avoid confusion and distraction from real issues. Indeed, privacy is very often confused and reduced with a fraction of what the word refers to. In many occasions in computer science, for instance, authors of works on the anonymization of databases containing sensible information (e.g. medical databases) use the general word to name their field of work, "privacy", instead of using the more specific field name, e.g. "database anonymization". Figure 1.1: Solove's taxonomy of privacy torts from a social point a view Solove puts in light the composed nature of privacy, and the need for a careful approach of the field. If privacy is summed up in one phrase, the better it can achieve is to give a very "high level" and abstract definition, which will always be subject to interpretation and largely differ in meaning depending on the reader. On the contrary, a practical and formal definition easily reduces privacy to a fraction of what it refers to. We intend to proceed analogously to Solove when describing the field of numerical privacy and trying to obtain a synthetic and complete view of it. We need a way to explicit the many facets of privacy in computer science in order to avoid simplifications. In the subsequent sections we try to sketch a more systematic and concrete way to embrace the notion of privacy.

Multiple dimensions

As we can see, the notion of privacy is composed, we can put forward several definitions for the word, and it is easy to leave aside and "forget" a whole part of the field it represents. To be convinced of this, one simply needs to read from different sources: although most of the literature in privacy use the same word and follow the same abstract goal, the meaning of the term will largely differ when looking closely at the implicit hypothesis made.

We begin by giving here elements that can be used to characterize privacy-enhancing systems or "privacy solutions", or more generally all works in numerical privacy. The motivation for this list is to have a better view on how and by what privacy works differs. We do not mean to clear out a new definition of privacy, as we saw the notion is too complex to be reduced to a few phrases, but rather to draw a synthetic and concrete view of it. More generally, the below list gives the different dimensions of privacy, aims to be sufficient to fully characterize a large portion of works in this field, and will be used in the following section to divide the field of privacy in several classes.

Approach

We claim that the most important and the first characteristic of a work in privacy is the chosen approach, that is, the general angle under which we consider privacy.

In other words, the approach is the first implicit choice we make when designing a privacy solution, and will be omnipresent in every following choices. For instance, when defining privacy as a right and trying to ensure it by laws, one uses a legal approach, whereas managing numerical data and designing information flow control system takes place in a technological approach. More concrete examples are given in the next section.

Sector The second most important characteristic of a privacy system is the sector it addresses, i.e. what "real-life" privacy problem it considers and tries to solve. Examples of sectors include geolocation, authentication, social networks, or data mining.

Privacy Goals Given the approach and the sector, privacy solutions will then differ by their goals in term of privacy. This characteristic put in light what privacy properties the solution will provide, and possibly details how much privacy is guaranteed (i.e. gives a quantification for the privacy properties).

Tools Another important feature to characterize and classify a privacy work is the tools it uses to achieve the given privacy goals. Tools largely depend on the chosen approach and sector: one may use cryptographic and mathematical theories when working in computer science, as in the legal approach it would not make sense.

Assumptions and Models Although these are not always explicit in the literature, all solutions make assumptions on the context or on the parties, and use more or less formal models. This is a characteristic in the sense that when searching for privacy solution for a given problem, one must be cautious of the assumptions made by the authors of the system in order to avoid incompatibilities between the authors' intention and the real usage.

Efficiency When choosing a privacy solution, and when all other characteristics are equal, the most efficient will often be the most suitable. Thus efficiency is an important characteristic. Note that here efficiency does not necessarily mean fast computability, and we use this term with a broader sense. As the evaluation of the efficiency largely depends on the chosen approach (e.g. efficiency relates to easy applicability in the legal approach), what is meant by this term is to be defined when designing the privacy solution.

This list could go deeper in the details, for example taking into account the number and nature of the entities interacting in the system and what protection each of them is guaranteed, but we claim that with the above-listed elements, privacy solutions and privacy-enhancing systems are sufficiently characterized. We go even further, claiming that with only the first two items of the list, we have enough information to obtain a detailed and synthetic view of the term "privacy". The next section develops this idea.

Trial for a synthetic view of privacy: Approach × Sector

From the list above we have at our disposal (almost) all the information needed to characterize a privacy solution. We could use those criteria, possibly with additional ones in special cases, to categorize and create a detailed taxonomy of privacy solutions. However, this is not our intention Inria here. We neither intend to deliver a definition for the word "privacy", as many have already been proposed and are sufficient for a high level view of privacy. Instead the aim of this section is to clear out a way to embrace the field of privacy in one unified view that would be practical and usable, as a roadmap for categorizing privacy works. This categorization is important to obtain a clear view of the field of privacy, to be able to efficiently choose a privacy solution for a specific application, and lastly to avoid comparing privacy systems that are not comparable (e.g. comparing a technology for anonymous internet communications and a law enforcing the notion of consent is absurd).

In our criteria list, we already pointed out that some criteria are correlated and that relations between them exist. One of the most obvious relation is the dependence between the approach and the used tools: using a technological tool in a legal approach does not makes sense, just like law theory does not have its place in a technological solution, although there are links between the two and they must be considered altogether 1 . The definition and quantification of efficiency also depends on the chosen approach: an efficient law will be an easy to apply and easy to enforce one, but a efficient technical solution will be a fast computable one (for instance). Another example is the choice of the privacy goals, that are largely correlated with the chosen sector: if the sector is a privacy-preserving geolocation, the goal may be to hide the user's location among a group of individuals, which does not makes sense as a goal in private biometric authentication.

In the light of previous paragraphs, we argue that some criteria are more important than others, and a small subset of criteria determines the others. We would like to find a minimal number of criteria that are sufficient to determine all the others, and to create classes from this minimal set. Solving this problem would require to acquire knowledge of all works on privacy and characterize them precisely and without mistake. As we do not have this knowledge at hand and because the time necessary to obtain it is way too large, the best we can do is to draw an approximate answer from a non-negligible (hopefully) representative subset of privacy works. Thus we pick few criteria that seem to determine others according to our knowledge, which is mainly driven by computer security considerations. The set we propose to consider is { approach, sector }.

First, to justify the number of criteria in our selection, we argue that to perform a trade-off between ease-of-use and accuracy of our categorization, it is necessary to select only a few criteria (e.g. 2 or 3). Indeed, consider for instance using some criterion crit 1 to categorize all privacy works in the set Ω. If N val crit1 is the number of possible values for the criterion crit 1 , then the space is divided in N val crit1 classes of size ≈ |Ω|/N val crit1 2 . And if N val crit1 is small we obtain a few large classes, which allows a simple and fast prune when searching for a privacy solution for a specific application, or when "inserting" a new privacy work in the categorization. Then, to continue the example, if we use a second criterion crit 2 , we obtain N val crit1 .N val crit2 classes of size ≈ |Ω|/(N val crit1 .N val crit2 ): the "pruning" is more effective, however the number of classes grows and so does the complexity of the categorization. With more criteria, we obtain better pruning but more classes and a more complex categorization. We prefer using a moderate number of (large) classes, as it eases the categorizations of privacy works each in its right place, without error. Indeed, many classes means many details to investigate in each privacy work, thus many factors of errors.

Then, the choice of the specific criteria is very important and mainly depends on what information is needed: when searching for any efficient privacy solution, of course, a categorization with the efficiency criterion is most suited. However, this example is not likely to be realistic. Rather, one will often or always have an approach and a sector in mind when searching for or designing a privacy solution. This is a first element that designates these two criteria over the others. Also, as another element in favor of this choice, we showed (but did not prove) earlier in this section that the couple (approach, sector) almost completely determines the other criteria of our list. Then, depending on the need, one can for instance append as third criterion the tools, when the desired tool for a particular application is chosen beforehand. Furthermore, for the sake of consistency and coherence, we would like that privacy works within a same class share similar characteristics so as to be able to compare them to each other. Precisely, most of the privacy systems within the same (approach, sector) class are comparable without introducing absurd comparisons. On the contrary, when considering systems from different approaches or from different sectors, there is a great risk of incompatibilities preventing comparisons. Lastly, we will see in section 1.2 that the number of approaches is limited, i.e. N val approach is very small), yielding a small number of large classes. The number of sectors being moderately large, we achieve a trade-off between number of classes and accuracy. This explains our specific choice for these criteria.

Using the couple (approach, sector) we can divide privacy works in wide classes. Although those still contain a lot of diversity, it is a first sorting that allows to immediately have a synthetic view of the field of privacy. This result is of course not exact and questionable (see section 1.5.1 for a discussion on this matter), but we find it appropriate for an efficient categorization. It can be considered as a trade-off between a complete and accurate but very complex and heavy categorization that puts every privacy system in its own class, and a partial but efficient one (as for the exactness, both categorizations may be flawed independently).

The next two sections give a better insight of our proposed view of privacy by listing the possible approaches and existing sectors.

Different approaches to privacy

By approach to privacy, we mean the highest level angle under which privacy is considered, or more exactly under which the field of numerical privacy is considered. When designing a privacy solution, this aspect immediately implicitly chosen. In some cases the approach need not to be made explicit and is well understood, but in many occasions, authors use the word "privacy" with a specific approach in mind, assuming the reader will be in the same state of mind, which is not necessarily the case. Thus clearing out the different approaches is crucial, and in order to avoid confusion, one should always specify which approach is considered when speaking about "privacy".

Note that enumeration in this section is inevitably tainted by the computer science oriented background of the authors and may not reflect the true nature of each approach.

The legal approach

Already mentioned several times, the legal approach is the easiest to picture. In this context, privacy is considered as a right and legal practitioners intend to ensure individuals' or entities' privacy using legal means. This can take the form of laws created by governments of course, but many other tools are widely used, such as directives (e.g. EU directives 95/46/CE [PtC95] and 2002/58/EC [PtC02]), federal laws in the US (e.g. Privacy [oE95] HIPA [UC96] Acts), international agreements (OCDE guidelines [START_REF]The Organization for Economic Co-Operation and Development[END_REF] or UN resolutions [START_REF]Guidelines for the regulation of computerized data file[END_REF]), and governmental institutions (e.g. Federal Trade Commission in the US and its Fair Information Practice Principles [START_REF]Privacy online: Fair information practices in the electronic marketplace: A federal trade commission report to congress[END_REF], or the CNIL in France).

Inria

We give here a very brief overview of the legal approach of privacy in the sector of computer science and information processing, as it is the one we are interested in. We leave aside all discussions about private property and "non-numerical privacy". In modern society, the fact that privacy is a fundamental right of every individual is widely admitted. It is written in the Universal Declaration of Human Right of the United Nations of 1948, the right to privacy has been present in most national legislations since the XVIII th century [START_REF] Piolle | Agents utilisateurs pour la protection des données personnelles : modélisation logique et outils informatiquesdeswar[END_REF], and it was adapted along the years to the evolution of information processing. Very broadly speaking, in the numerical privacy sector, modern laws mainly focus on the notion of personal information (e.g. the term used in US law is "Personally identifiable information"), and do not include (so far, and to the best of our knowledge) more complex privacy notions such as hiding the fact that Alice communicated with Bob on date d or who are Alice's friends for instance. Generally, laws define what is and what is not considered as personal information and try to prevent or reprimand disclosure of individuals' personal information [START_REF] Ohm | Broken promises of privacy: Responding to the surprising failure of anonymization[END_REF]. Other points of interest in legal considerations include [START_REF] Piolle | Agents utilisateurs pour la protection des données personnelles : modélisation logique et outils informatiquesdeswar[END_REF]: the information of service users (e.g. user needs to be informed on what and how data is collected), the consent of the user (e.g. explicitly ask the user for some permission before performing an action), and the right of the user to access and rectify its information. They also regulate the duration of data holding by the service provider, the communication of these information to third parties, and the motive for collecting and manipulating specific data. All those enumerated points can be summed up in two main principles: sovereignty of the user over its data, and minimization of the collection of data. However, these laws are always mitigated by others allowing the disclosure of such information for judicial or "national security" reasons.

It is important to note that the blazing fast evolution of technology during the past decade has left the legislation behind: laws are not always adapted to the reality of information processing. Notably, many flaws allow information broker to collect and sell particular data without real legal framework. Indeed, some data are (rightfully) considered by the law as personal to the individual because they allow to directly identify him but recent works in privacy showed that almost any information can be used to indirectly identify an individual, such as the history of one's web searches [START_REF] Castelluccia | Private information disclosure from web searches[END_REF] or movie ratings [START_REF] Narayanan | Robust de-anonymization of large sparse datasets[END_REF], and laws need time to take these results into account.

For a more complete history of the privacy laws in the United States, the reader might refer to a reflexion about law on personal information and database anonymization by Paul Ohm [START_REF] Ohm | Broken promises of privacy: Responding to the surprising failure of anonymization[END_REF]. Concerning the European Union and more specifically France, see section 1.1.2 of Guillaume Piolle's thesis [START_REF] Piolle | Agents utilisateurs pour la protection des données personnelles : modélisation logique et outils informatiquesdeswar[END_REF].

The policy approach

This second approach is quite close to the previous one and both are often presented as one. Actually, in a sense the policy approach is the continuation of the legal approach: it formalizes legal (or more generally, human-readable) statements and transform them into machine-understandable requirements. The goal in this approach is to ensure that some properties, expressed via policy statements, are observed by systems, and optionally to build tools that take human expressed properties as input and formalize them in applicable properties for information systems. This approach is thus also close to a technical approach in the sense that it uses computer technologies to enforce policies. However, in what we call the policy approach, pure technological solutions may be used, but not invented. Actually, when a framework for describing privacy policies is designed, how to enforce the policy with technological tools is not always considered, but comes at the end of the reflexion, sometimes as an optional step, to transform policies from simple "information" on how to handle data, into verifiable system properties. Although the policy approach is in between two other approaches, it is considered here on its own because this step is necessary for building a bridge between law and technology. Moreover, the complexity of designing and composing policies being great enough, it deserves a special category.

When defining a policy or a "law to policy translator", several challenges arise, mainly from the fact that the requirements and privacy properties aren't expressed by computer experts but by legal ones. Indeed, those requirements must be transformed into machine-understandable properties without loosing their original meaning, which is far from trivial. Some research focus specifically on that issue [ABSB + 11, PD11], using deontic logic to express privacy requirements. Another common issue is the management of conflicting privacy rules or requirements [START_REF] Hu | Detecting and resolving privacy conflicts for collaborative data sharing in online social networks[END_REF] within a set of policies applied to a system. For instance, in a social networks where each user would be given the possibility to express privacy rules for its own data, when Alice publishes a picture depicting Bob and Charlie, how does the system handles the publication when Alice wants to make the picture public, Bob wants to disclose it only to his close friends, and Charlie demands this specific picture to be hidden.

In practice, in the particular sector of web applications, expression of privacy policies is done with the now widely used P3P (Platform for Privacy Preferences Project) standard from the World Wide Web Consortium [START_REF]Platform for privacy preferences specification 1[END_REF]. This standard allows web site to specify their data processing and collection policies in XML, via a P3P policy accessible through a simple URL, so that it can be read and interpreted by web browsers. The policy is then presented to the user or even automatically compared to its privacy preferences. Another well know tool available in the policy approach and for various sectors are the sticky policies [START_REF] Karjoth | A privacy policy model for enterprises[END_REF], which are integrated in pieces of information as meta data and specify the allowed uses of the information.

However, none of the two technologies ensure the policy is respected: P3P standard does not check the enforcement of the policy server-side, and sticky policies are just information on how the data should be used. In both cases, there is a need for a mean to enforce the observation of policies. The basic solution is to suppose that the client trusts the server to do what as it says it will do, and a more complex is to perform an audit by trusted experts such as government institutions. In all cases, the means to enforce the policy lie in the technological approach.

The technological approach

The angle to approach privacy we are focusing on in this document is the technological one, where privacy researchers try to enforce privacy via pure technological means, often with cryptographic, mathematical or hardware-based tools. We do not extensively describe this approach here, as the next sections and this whole chapter are dedicated to this purpose. Section 1.3 describes existing sectors and general tools of this approach.

However, we detail here two ideas belonging to the technological approach. First, describe what seems to be the modus operandi of every privacy work in this approach (it can possibly be adapted to other approaches). Indeed, it seem that most of the works in privacy are constructed in 4 main steps:

1. Choose a pre-existing system that seems to "need" privacy, and study it;

2.

Investigate and decide what should be "private" or not;

3. Modelize and formalize these requirements into properties of the system; 4. Enforce these properties by technological means (e.g. adapt the infractrusture or the protocole, use cryptography or a trusted third party, ...)

We will roughly follow the same procedure in our constructions. Secondly, we would like to point out here two "sub-approaches" that specify a bit more where, how, and to what purpose technology is used. Note that the separation between the two sub-Inria approaches is not always clearly defined, and they can be seen as a high level characteristic of (technological) privacy solutions.

Service-centric approach

In this case, privacy technologies are used to enable privacy in existing services, with as less impact on the service provider as possible. For example, designing privacy-preserving targeted advertising or geolocation-based services are within this scope. This approach often takes an existing service, and slightly modifies its implementation to take clients' privacy into account, without substantially modifying the functionality or questioning it. In this case, modifications are often needed on client and service side.

User-centric approach

On the contrary, in this case the user's privacy is the first and primary goal. No specific service is considered, and the aim is to fully protect the user and give him control over his "privacy". The only assumptions are that the user do not wish to give away (any) information or more generally compromise his privacy, and is even willing to refuse some services if their privacy terms do not match his requirements. If possible, in this approach, only the client-side is modified and only the user needs to take action, so that his protection only depends on his choices and the technology used, and not on the services accessed. The philosophy of this approach is to allow the user to have "unconditional privacy", i.e. to provide the user means to protect his privacy independently of the entity it is in contact with (e.g. a service, a system, ...). In other words, "unconditional privacy" refers to the ability of the user to protect its privacy even if no measures have been taken service-side. Achieving this kind of privacy is not always easy, and achieving it with only client-side modifications is almost impossible (there is often the need to make adjustments to the environment, if not the service). Of course, a trivial solution is for the user avoid any interaction with any entity, but we reject this solution as we want the user to still interact with the world and perform meaningful actions.

The economics approach

Finally, we argue there exists a fourth approach to privacy, the one called economics. As the name suggests, this approach is actually mainly business-oriented and uses market laws to characterise privacy 'transactions". Its starting point is the emerging business model where users do not directly pay for a service, but the service provider collects and analyses their personal information. At first, it seems like a nice solution for the user as the cost of the service is reduced, and for the organisation as it still creates wealth. Society would also benefit from it (in the contemporary economic paradigm), under the form of increased growth and wealth. In the economics approach, works start from these observations, try to keep in mind that users might not actually want that business model if their privacy is endangered, and investigate to what extent the market is efficient to ensure user's privacy. Indeed, the main assumption here is that users manage their privacy the same way they would manage their physical goods and money: individuals choose to trade (or not) private information or a fragment of their privacy against advantages of other nature. Following the definition of Acquisti et al. [START_REF] Acquisti | Privacy and rationality in individual decision making[END_REF]: "According to that view, individuals are forward-looking, utility-maximizing Bayesian updaters who are fully informed or base their decisions on probabilities coming from known random distributions."

The "utility-maximizing" term means that the user intends to maximize its total benefits, defined via criteria left to his choice. For instance, if, in the opinion of some individual, privacy prevails over (small) financial advantages, he should choose to refuse a fidelity card in a shopping center, a card that often mentions name and address of the bearer and tracks his purchases, but also proposes reductions and special offers on shopping items. "Forward-looking" implies that individuals try to maximize their "utility" in the medium or long term. The notion "Bayesian updater" models an individual that is able to make rational decisions based on a priori beliefs, and to improve his beliefs at each new event (here, an event is a transaction). In practice, this means an individual makes rational decisions on how to handle a specific privacy transaction based on his expectations of the outcome of the transaction and his past experiences. The last part of the definition supposes the individuals are fully informed, in particular on the consequences on the transaction for all parties, or at least have access to knowledge common to all parties.

Privacy solutions in the economics approach may propose ways to correct the aforementioned business model or the individuals' behavior model, mitigate users' privacy loss and try to achieve balance between individuals and data holders, notably via law and technology. Typical questions raised in this approach are for instance "Who owns the data: the user or the collector ?", "Have the user consented, and do we need explicit consent ?", "Do we really need regulation through legal means, or is the market efficient to achieve balance in the case of privacy ?".

One of the main points of interest is the validation (and correction if necessary) of the "Bayesian updaters" model for individuals described above. Several works question the model and suspect it does not match reality [START_REF] Acquisti | Privacy and rationality in individual decision making[END_REF][START_REF] Grossklags | When 25 cents is too much: An experiment on willingness-to-sell and willingness-to-protect personal information[END_REF][START_REF] Conti | An honest man has nothing to fear: user perceptions on web-based information disclosure[END_REF]. Notably because of information asymmetry between users and service providers, but also because individuals are rarely aware of privacy risks and technological possibilities to prevent them. Other factors [START_REF] Acquisti | Privacy and rationality in individual decision making[END_REF] include the humans' bounded rationality which limits his ability to acquire and use information, and "psychological deviations from rationality" inherent to human nature (that for instance imply time-inconsistent decisions where a lesser immediate good is chosen over a greater good further in time). Some reflexions also speak of a "market failure" in the context of privacy [START_REF] Acquisti | Privacy and market failures: Three reasons for concern, and three reasons for hope[END_REF], that is to say they wonder if the market laws are applicable directly, and if the market model is valid in this context. On this matter, Acquisti gives some reasons for "hope" and other reasons for "concern" [START_REF] Acquisti | Privacy and market failures: Three reasons for concern, and three reasons for hope[END_REF]. Briefly, reasons to be concerned by the ability of the market to regulate privacy transactions are: the unprecedented easy access for third parties to a large number of individual's personal life aspects (often without the person knowing it), partly because of the development of communication technologies; and the fact that giving more control to the users as it is often recommended by privacy advocates would be a false solution because users are unaware of the value of their information (it even sometimes leads to less privacy [WCS + 13]). Reasons to hope are that human seems to naturally need publicity and privacy, and this tendency should appear in the long term; research on behavior in economics of privacy put in light psychological bias, but can actually help erasing those bias by informing individuals about underlying psychological processes and contradictions; and finally hope lies in technological advancements and "privacy enhancing technologies".

Different sectors of privacy in computer science

After exposing the main angles under which it is possible to consider numerical privacy, we continue by enumerating the possible sectors, in order to complete our Approach × Sector view. However, we will see that giving an exhaustive list of sectors in numerical privacy is pointless, as one can envision privacy in all aspects of computer science and all systems are subject to ameliorations in term of privacy. However, there are some that are more relevant than others, Inria and more significant. We try, in this section, to lay out a succinct hierarchy and list of sectors in which privacy is relevant and those that research already took hold of.

For a more complete list of existing privacy issues in society and the digital age, see the list from the Privacy Rights Clearinghouse [START_REF]Privacy today: A review of current issues[END_REF].

Identity management and authentication

Authentication is necessary in many systems where there is a personalized user space or where actions of the user must be imputable to the individual owning the identity. In numerical privacy, we are interested in allowing a user to be anonymous and authenticate at the same time. Indeed, in many contexts the true identity of a user does not need to be known and systems merely need to distinguish him uniquely in the set of individuals using the service. Sometimes, an even weaker form of authentication is sufficient, for instance when the user and the service only need to recognize each other for a temporary session and the service does not need to "remember" the session. In this case the user can use a different identity (or pseudonym) for each session, and he can use the service without the service provider being able to link the different sessions to him. On the contrary, the service provider might specifically want to impute malicious actions to a user in order to ban him from the service. In this case we speak of accountability of the user toward its actions. As an extreme example, we can imagine a user undertaking criminal actions while being anonymous: accountability is necessary in order to find the individual responsible for the actions and to prevent anonymity abuse. Although they seem like orthogonal requirements, accountability and anonymity can be guaranteed at the same time, e.g. via revocable anonymity [START_REF] Köpsell | Revocable anonymity[END_REF].

All the cases informally described above can be expressed with the notion of linkability: linkability between a user and its actions, and between actions of a same user in a system. The notion (un)linkability is crucial, and it is a widely accepted term used to define and quantify privacy properties. It has been defined by Pfitzmann et al. [START_REF] Pfitzmann | Anonymity, unobservability, and pseudonymity -a proposal for terminology[END_REF], along with the terms anonymity, pseudonymity and unobservability, all of which are relevant to formalize privacy properties: Anonymity is the state of being not identifiable within a set of individuals or users, the anonymity set.

Pseudonymity is the use of pseudonyms as identities. Pseudonymity can be seen as anonymity with accountability: users do not use their real identifier to perform actions, but a pseudonym that may have a known connection with a real identifier. There are several degrees of pseudonymity (see below).

Unlinkability of two items (e.g. users, actions, messages, events, ...) in a system means that within this system, these items are no more and no less related after a "run" of the system than they are related with respect to the a priori knowledge of an observer. Note that anonymity is the unlinkability between an action and a specific identity, and stronger unlinkability leads to stronger anonymity.

Unobservability is the property of a system to produce unobservable events, i.e. events either undistinguishable from any other event, or events undetectable by an observer.

Unobservability being a very strong notion, difficult to achieve because often implying very inefficient constructions in practice, we do not consider it in this section. As anonymity and pseudonymity can be defined in terms of unlinkability, we mainly focus on the unlinkability. Thus we can restate the main objective of privacy-enhanced identity management in terms of unlinkiability: the goal is to reconcile authentication, accountability and unlinkability.

We distinguish here two main kinds of unlinkability: unlinkability between the user and its actions, which is equivalent to anonymity, and unlinkability between actions of the same user (without knowing which user performed them). In many occasions, the two kinds of unlinkability are necessary because from a "sufficient" number of actions known to be related to a specific user, it is possible to infer the identity of the user. The main known method to ensure both types of unlinkability is using different virtual identities, i.e. pseudonyms. Depending on the necessary level of unlinkability, a user is provided with different types and numbers of pseudonyms [START_REF] Pfitzmann | Anonymity, unobservability, and pseudonymity -a proposal for terminology[END_REF]. The knowledge of the linking between a pseudonym and the identity of the user using it determines the degree of unlinkability between a user and its actions: a public linking leads to total linkability, a linking known by some specific entities (such as trusted third parties) can lead to revocable anonymity, and a linking known to the user only gives total unlinkability. Then, how and how many times a pseudonym is used determines the linkability between several actions performed by the same user: providing one unique pseudonym for one user leads to total linkability, providing as many one-time pseudonyms as the number of action of a user leads to total unlinkability. In between are 3 alternative solutions: one pseudonym for each role the user assumes in the system, one pseudonym for each entity the user is in contact with, or one pseudonym per role and entity. The favored approach is to give knowledge of the linking between pseudonym(s) and identity of the user to some trusted third parties so as to enable revocable anonymity. As for the number of pseudonyms and their usage, the choice depends on the available resources and the privacy goals.

It is important to note that the notions of unlinkability, pseudonymity and unobservability are relevant in many other contexts than identity management. In fact, Pfitzmann et al. [START_REF] Pfitzmann | Anonymity, unobservability, and pseudonymity -a proposal for terminology[END_REF] proposed this terminology for network communications (see section 1.3.3). In the rest of the chapter, unless specified otherwise, we refer to these notions as defined above.

Example: Biometric authentication We can illustrate identity management systems with the case of biometric authentication. Biometric data such as DNA or iris pattern are very sensitive data, but they are also very reliable for strong authentication as they are often very hard to counterfeit or steal. Thus, we would like to find a privacy-preserving way to perform biometric authentication. In this setting, typically, a user interacts with a secure device which has access to stored biometric profiles, and has the capacity to capture the biometric profile of the user. Authentication succeeds if the captured profile matches a profile in the database. Systems have been designed so that the biometric profile of individuals stored in a database are comparable with captured profiles, but the owner of the database can not link a stored profile to an individual's identity (e.g. name and address). Other useful properties include the unlinkability between several authentications of the same user. Some solutions proposed applying distortions the profile using a one way function that will preserve the similarities between the stored and captured profiles [START_REF] Ratha | Enhancing security and privacy in biometrics-based authentication systems[END_REF], others use fuzzy commitments and error-correcting codes [START_REF] Zhou | Quantifying privacy and security of biometric fuzzy commitment[END_REF].

Personal information and data management

As it appears in the previous sections and in this whole chapter, the first, largest and most known sector is the one dealing with personal information management. Most of the works in (numerical) privacy consider this sector, and it is indeed an important one because of its broad sense. Indeed, personal data are everywhere and when interacting with systems, individuals inevitably leave numerical traces, either under a digital form (e.g. IP address or email) or "real world" information such as age, country, habits or name of friends. In many occasions, numerical privacy is (but should not be) reduced to personal data management, because of the predominance of the sector.

Inria

Even though it is possible to outline multiple sub-sectors of personal information management, there exists general principles that apply to the whole sector, principles that were partly exposed in section 1.2.1, as they are extracted from social and legal reflexions. Sovereignty of the individual over its personal data: those data belong to him, and he should be able to access, rectify them and to accurately control how, when and who holds and processes them. Among other requirements, this principle implies the right to be forgotten, i.e. the possibility for the individual to erase all or a part of its numerical traces. When the data is on a distant server not controlled by the user, or in ubiquitous computing, this principle is very difficult to enforce.

Minimization of personal data: the individual should disclose only the information necessary to fulfill a given goal. For instance, for an individual to prove that he is adult he does not need to give his age or date of birth, but the only information he should disclose is "my age is above 18 " (or 21).

Consent of the individual on its personal information collection, processing and dissemination. An explicit consent is preferred over an implicit, opt-out one.

Information and transparency: the individual should be able to accurately know what is done with his information.

Security against unauthorized access, modification or use is the responsibility of the data holder (and not the data owner, the individual).

Those principles should be enforced by technical means, and are often the starting points of new systems' privacy goals of the "personal information management" sector. In the following sub-sections, we list some of its most representative sub-sectors, along with short descriptions.

Statistical databases and Big Data

This sub-sector has been given so much attention it could be a sector on its own. However, we argue it is only a small part of numerical privacy. By statistical databases, we mean databases containing demographic information and/or names of many individuals, along with sensible information, such as political opinion, religious orientation or health details. The typical model supposes one entry per individual in the database, composed of several fields for demographical and identification information, and other fields storing the sensible information. The typical example is a hospital database, where people are fully identified and a diagnostic is appended in a last field. These database are called "statistical" because of their main use: computing statistics on populations, and inferring relations between demographic parameters and some properties or events (e.g. correlating a specific location and an epidemic). "Big Data" refers to the management of very large statistical databases: as information storage and collection becomes easier every year, we are now in presence of extremely large databases and challenges arise in terms of processing, search, sharing and visualisation. We are not interested in these challenges, and we will consider Big Data and mere statistical databases as the same concept. We are only interested in the process of "curating" those objects in order to ensure the privacy of individuals in the database. Basically, this consists in perturbing or removing a (significant) part of the information contained in the database so that identifying individuals in the database is impossible. The challenge is to do so while leaving enough information in order for statisticians to be able to extract relevant knowledge from the database.

The extensive study of database curation dates from the 80s [START_REF] Kims | A method for limiting disclosure in microdata based on random noise and transformation[END_REF] and can be explained by the need for companies, organisations and institutions to publish or share the data they collect on individuals. The collection is (as for now) legal, but the publication isn't if the data can be linked to the individuals it relates to. The publication or sharing of data is often motivated by the need to extract statistics and tendencies from them. It can be for public interests (e.g. analysing medical databases can predict epidemics) or for private profits (e.g. analyse implicit feedback from service users in order to improve the service). There are also companies that transform their data collection into profit by selling them, for instance to advertisers, for whom this information is crucial to offer better, targeted advertising.

We can distinguish two types of database curation: until beginning of 2000s was the era of database anonymization and sanitization, an approach that has been shown flawed, and since 2006, the technique called differential privacy has been the leading solution. To understand the "failure" of database anonymization, the reader may refer to Paul Ohm's 2009 article [START_REF] Ohm | Broken promises of privacy: Responding to the surprising failure of anonymization[END_REF] which describes very accurately anonymization techniques and why this approach is now considered obsolete. Here, we outline very briefly the ideas of the two techniques, and explain why differential privacy is favored over anonymization.

The basic idea behind database anonymization, or database sanitization is to remove from the database the information that could identify the individuals it contains. Several ways of doing so have been proposed, such as suppression of some database entries, randomization and perturbation, or query limitation (in nature or number). But the most known and widely used technique is called k-anonymization, invented by Sweeney in 2002 [START_REF] Sweeney | k-anonymity: A model for protecting privacy[END_REF]. The basic idea behind k-anonymity, besides removing individuals' names, is to generalize the values of some well chosen attributes, called quasi-identifiers. Each entry of the database is processed so that for every individual contained in the database, there are at least k -1 other individuals that share exactly the same values of quasi-identifiers. Before modifying the data, the database owner must choose the appropriate set of quasi-identifiers (e.g. demographic attributes such as age of ZIP code). These attributes should be those that can indirectly identify individuals. The database attributes are thus partitioned in 3 categories: the name of individuals (i.e. information that directly identify individuals), the quasi-identifiers, and the rest of the attributes. Those last attributes are called sensible information and may correspond for instance to the diagnostic in a medical database. Then the database owner removes the names of the individuals, and generalizes the quasi-identifiers in order to obtain a database partitioned in classes, each of them containing k entries sharing the same, generalized, quasi-identifiers before publishing it. Figure 1.2 shows a database ensuring the k-anonymity property. As it turns out, k-anonymity is not sufficient to avoid re-identification (i.e. linking a particular entry of the database to an identifier, thus to an individual). Two complementary variants have been proposed to cope with the flaws of kanonymity, l-diversity [START_REF] Machanavajjhala | L-diversity: Privacy beyond k-anonymity[END_REF] (ensures a minimum diversity of the sensible attributes in each class of k entries) and t-closeness [START_REF] Li | t-closeness: Privacy beyond k-anonymity and l-diversity[END_REF] (ensures that the distribution of sensible attributes in each class is close to the global database distribution), but presented the same shortcomings in definitive. See Paul Ohm's reflexion for more information [START_REF] Ohm | Broken promises of privacy: Responding to the surprising failure of anonymization[END_REF].

In 2006, Dwork proved what was beginning to be admitted by the whole community: the assumption of the existence of quasi-identifiers was erroneous, in the sense that finding the correct set of attributes to play the role of quasi-identifier is not possible. In fact, several reidentifications, or inference attacks, such as Sweeney's works [START_REF] Sweeney | Uniqueness of simple demographics in the[END_REF][START_REF] Sweeney | Privacy-enhanced linking[END_REF] and the Netflix prize competition [START_REF] Narayanan | Robust de-anonymization of large sparse datasets[END_REF], led researchers to believe that any information is a quasi-identifier. This fact is particularly obvious with the Netflix inference attack [START_REF] Narayanan | Robust de-anonymization of large sparse datasets[END_REF], where, with only benign data such as users' movie ratings, researchers were able to re-identify individuals. The key of these attacks is the side-knowledge of the attacker, which, combined with the anonymized dataset, leads to re-identification: for instance, combining voters list or public records with a medical database [START_REF] Sweeney | Uniqueness of simple demographics in the[END_REF][START_REF] Sweeney | Privacy-enhanced linking[END_REF] or Netflix database with IMDb's. The issue raised by Dwork [START_REF] Dwork | Differential privacy[END_REF] is that it is not possible to predict the attacker's side-knowledge, thus it is impossible to chose the proper quasi-identifiers. To be more accurate, Dwork's proof shows it is not possible, with the "anonymize and publish" approach described previously, to obtain anonymity and utility, where utility is a quantifiable parameter specifying the quantity of useful information extractable from the database. Indeed, utility is maximal and anonymity minimal when the database is released as is, and conversely if the database is completely emptied before release. The two notions thus seem antagonist.

But in 2006, Dwork proposed a new technique that reconciled anonymity and utility, differential privacy [Dwo06, Dwo08, DMNS06], which has been adapted to other context than statistical databases after its creation [START_REF] Alaggan | Blip: Noninteractive differentially-private similarity computation on bloom filters[END_REF]. In few words, the concept of differential privacy requires that, for a privacy-preserving mechanism M Q with Q the query to the database issued by the analyst, the probability distributions of M Q 's output on database DB 1 and DB 2 are statistically close, where DB 2 is DB 1 stripped from 1 entry only. Dwork instantiates such a mechanisms by setting M Q (DB) = Q(DB) + ∆(Sensitivity(Q)): the mechanisms gives the exact answer for the query Q(DB), masked using a Laplacian noise ∆ calibrated following the sensitivity of the query Q3 computed on the database. As the mechanism is tailored to a specific query which need to be known prior to the computation of the output, this mechanism is said interactive as the analyst must provide the query and wait for the answer. The key aspect of differential privacy which makes the difference with sanitization techniques, is that the utility is know prior to the database transformation, i.e. the query Q is known before the release of the answer, contrary to the "anonymize and publish" paradigm. When the utility is known, it is easier to robustly anonymize the database in a way preserving the desired utility, but only this particular utility, specified via the query Q. More details are provided in section 1.4.3.

Online

Online privacy also give rise to a lot of interest in numerical privacy research, as web applications are multiplying and growing in importance. Basically, online privacy works try to enable anonymous online service access on internet. Those services include:

Targeted advertising where the goal is to offer tailored adverts to the user, without the advertiser knowing who (which IP address) requested a specific ad, thus preventing profiling from the advertiser.

e-Commerce where the user might want to prevent the merchant from knowing its true identity.

Web searches and history as it has been shown that web searches reveal a lot of information on users [START_REF] Castelluccia | Private information disclosure from web searches[END_REF].

Anonymous service access can easily be implemented using anonymous proxies that strip all identifying information from the service request issued by the individual [START_REF] Deswarte | Current and future privacy enhancing technologies for the internet[END_REF], but this simple solution only moves the trust from the service provider to the proxy owner.

Other points of interest in online privacy include avoiding web tracking of users by websites, especially third party website that try to follow every movements of users in order to infer its habits and/or identity. Also, (online) social networks are a problematic topic, as their very definition is an infringement to the sovereignty and minimization principles (see section 1.3.2 ). Goals of researchers in this context is to re-enforce the control of the user over its data, and to investigate re-identification through social graph reconstruction [START_REF] Zheleva | To join or not to join: the illusion of privacy in social networks with mixed public and private user profiles[END_REF].

Authentication, authorizations and anonymous service access

We complete here section 1.3.1 on identity management with some considerations on authorizations and authentication. Indeed, in this section we left aside cases where the system or service provider does not need to associate any identity at all to the user in order to deliver the service, but it only needs to check some specific properties of the individual such as his age, his affiliation to a certain group, or other specific properties.

In this context, anonymous credentials [START_REF] Deswarte | Current and future privacy enhancing technologies for the internet[END_REF] play a large role: those constructions, typically based on zero-knowledge proofs [Gol01, Chapter 4] or group signature [START_REF] Chaum | Group signatures[END_REF], allow an individual to prove specific attributes that are certified by an authority recognized by both the service provider and the individual. Only the authority can make the link between an authorization and an individual. After a short protocol, the service provider is assured that the individual fulfils the necessary requirements, but does not know who he is. The requirements can take the form of attribute testing (e.g. is age above some threshold ?) or authorizations (e.g. a signed, anonymous piece of paper granting access some building).

IBM developed the idemix (Identity Mixer) system [START_REF] Camenisch | A formal model of identity mixer[END_REF], implementing anonymous credentials and blind verification principles. The implementation involves extensive use of zeroknowledge proofs and group signatures and ensures unlinkability between an individual's actions. If necessary, anonymity is revocable: the issuer of the credentials (i.e. the trusted third party) can make the link between a specific use of the identity mixer and an individual.

Anonymous credentials are also used in a proposal for an privacy-preserving digital identity card [START_REF] Deswarte | The challenges raised by the privacypreserving identity card[END_REF]. Basically, this card is meant to communicate with a secure device allowed to ask one specific binary question, that can be a boolean expression composed of several questions, such as "are you over 18 AND are you French ?". The device must possess and show a credential issued by the certification authority (e.g. the government) for each question it is allowed to ask. Anonymous credentials are then used by the card to answer the questions, and certify those answers. Other challenges in designing a privacy-preserving identity card are notably ensuring the non-transferability (impossibility to lend one's card), correctness (impossibility for the individual to cheat/lie) and unforgeability (impossibility to counterfeit a card) properties. The use of tamper-proof smartcards and biometric authentication embedded in the card helps achieving these goals.

Geolocation

Many services based on location are emerging since the advent of mobile phones and GPS devices, and require the user to share its geographic position with the service provider and/or third parties. The social network Four Square is a famous example, but many more systems are geolocated: Inria a city bus card records users' entry and exit points in and out the network, cellular phones are always (approximately) geolocated using relay antennas, ip addresses give away information on the region of the computer using it, and of course GPS systems communicate very precise location information. In general, geolocation mechanisms always associates a spatial location with a specific device (e.g. GPS, card, phone), often itself linked to one individual.

However, location and mobility patterns are very sensible data and should be considered similarly to personal data, as several studies show [START_REF] Gambs | Show me how you move and i will tell you who you are[END_REF][START_REF] Golle | On the anonymity of home/work location pairs[END_REF]. In fact, from mobility traces, it is possible to infer points of interest such as working place (most stable place in the trace during the day) and home (the last stop of the day), to predict the individual's moves, and even approximate his habits, social relations and income (based on the places visited). Even if the mobility traces are anonymous, studies show it is possible to de-anonymize them using side-information such as social graph [START_REF] Srivatsa | Deanonymizing mobility traces: Using social network as a side-channel[END_REF][START_REF] Ma | Privacy vulnerability of published anonymous mobility traces[END_REF].

Solutions are needed to protect individuals from disclosure of their location, while still enabling the use of location-based services. Some solutions are adapted from other contexts such as k-anonymity [START_REF] Gruteser | Anonymous usage of location-based services through spatial and temporal cloaking[END_REF] (called spatial cloaking), mix-zones [START_REF] Beresford | Location privacy in pervasive computing[END_REF] (inspired from Chaum's mixnets 1.3.3), and perturbation techniques such as randomization [START_REF] Armstrong | Geographically masking health data to preserve confidentiality[END_REF], insertion of dummies, or suppression or swapping of parts of the traces.

Cloud

The emerging concept called cloud computing refers to a powerful computational resource composed of a large distributed network of machines easily accessible via a unified, virtualized interface. It encompasses several services: infrastructure, platform and software as a service, respectively denoted IaS, PaS and SaS. Basically, a cloud provider grants computing resources to clients (expressed in terms of software, CPU frequency, storage size, ...), and manages all details concerning hardware, computing power, installation, administration, etc. This is especially convenient for companies willing to easily obtain computing resources without having to administrate a complex and expensive installation. The cloud provider makes extensive use of virtual machines and virtualization in order to abstract from hardware considerations. The challenge is then to design a smart, dynamic, on demand allocation of computing resources depending on the clients needs. This is the role of the hypervisor, a software that manages the virtual machines. Large cloud providers often control several pools of hypervisors.

In the cloud, resources are shared among several clients, and a resource belonging to Alice may pass onto Bob the minute after. This raises concerns in terms of security and privacy for individuals or companies hosting their data in the cloud. In particular, the data owner must be assured of the proper use of its data, of the non-transferability of the data's ownership and of adequate access control management in the cloud. Privacy researches in this sector try to enable the use of the cloud's large computing power, while hiding the actual data manipulated from the cloud provider. Zhang et al. proposed [ZYZ + 12] a taxonomy of key privacy issues in cloud computing and lay the foundations for future researches in cloud security. In particular, they divide researches on the client from those on the cloud provider side. On the provider side, they also subdivide points of interest following the levels of abstraction in the cloud: the platform, virtual machine and hardware levels.

In higher levels of abstraction, i.e. at the application level, privacy solutions mainly involve cryptographic primitives. However, these solutions can not rely on cryptography alone to achieve privacy. Indeed, the impossibility result of van Dijk et al. [START_REF] Van Dijk | On the impossibility of cryptography alone for privacy-preserving cloud computing[END_REF] states that software alone can not guarantee privacy in the context of several clients mixing their data in an off-line multiparty computation [START_REF] Goldreich | The Foundations of Cryptography -Basic Applications[END_REF] setting (e.g. for similarity computations of profiles in social networks). They prove that others tools are necessary, and propose the use of trusted hardware to circum-vent these shortcomings. Another possibility is to ask for clients involved in the computation to cooperate at some point in the protocol, but this requires dropping the off-line property of the protocol. Proposals for privacy-preserving cloud applications involve multiparty computation and homomorphic cryptography [LATV12, AJLA + 12] (see also Chapter 2). In those solutions, computations performed by the cloud can be made off-line, but clients need to be online and cooperate at the decryption phase. Thus they do not allow complete off-line multiparty computation.

Misc.

There exist many more sub-sectors within the "personal data management" sector, however we do not provide a complete list here. Other points of interest include:

Mobiles phones Leakage of personal information through mobile OSs and applications, often without the user's consent, poses serious threats: mobile phones are very personal devices, aware of many personal information and details and it is able to monitor a large portion of its bearer's actions. The Inria project "Mobilitics" [ABC + 13] investigates these issues.

Radio Frequency Identification RFID tags are small wireless devices used to identify objects or persons. They can notably be used for physical tracking and localization. For instance, stores and malls may track their customers in order to construct profiles and clear out buying habits. Tracking is also possible city-wise, to monitor road traffic and vehicules. It is a major threat to individual's privacy, as RFID tags can identity and locate individuals. The security and privacy of this technology is investigated [START_REF] Juels | Rfid security and privacy: a research survey. Selected Areas in Communications[END_REF], as the practical threats and attacks are still unclear.

CCTV and video surveillance

Along the same lines, surveillance via video cameras poses serious threats as the cost of these devices drops and automated facial recognition technologies progress.

Internet of things

With the dropping cost of electronic devices, the emergence of IPv6 (and its very large addressing space) and the easiness of internet access, it is reasonable to assert that in a few years, all objects surrounding human beings will embed computational power and have internet access. In particular, the domestic devices in a house will form an "ambient intelligence" that should facilitate everyday life. These devices, however, form a privileged access inside one person's sanctuary of privacy, his home. In this context, Oleshchuk [START_REF] Oleshchuk | Internet of things and privacy preserving technologies[END_REF] proposes solutions based on secure multiparty computation to protect the data collected by these devices.

Digital Rights Management

The very design of DRMs is an infringement to privacy, as the goals is to trace ownership of digital items in case of fraud or misuse. DRMs and broadcast encryption infrastructures can lead to consumers tracing and profiling by content distributors (e.g. by monitoring who watches which movie). Researches try to reconcile "traitor" (or misbehavior) tracing, while ensuring anonymity, possibly using revocable anonymity [CKSJ03, GPY + 04].

Anonymous communications and traffic analysis

Although close to anonymous service access or identity management, traffic analysis prevention actually forms a well separated sector. It comprises notions absent in both sectors, notably hiding communication patterns and who communicates with who. Indeed, aside from confidentiality, Inria integrity and authenticity of the content of the exchanged messages, which are easily enforceable with encryption and signature, the communication link between two parties (or more) itself can also need to be confidential. This problem was introduced by David Chaum in 1981 [START_REF] David | Untraceable electronic mail, return addresses, and digital pseudonyms[END_REF] in the context of electronic mail, under the name "traffic analysis information" and described as "the problem of keeping confidential who converses with whom, and when they converse". This work is motivated by the fact that traffic analysis poses an important threat against privacy, since the simple observation of source and destination identities (e.g. IP addresses) can reveal sensible information. For instance, observing an IP packet incoming from an identified individual towards a sensitive web page (e.g. www.aa.org) reveals private information on the individual. Or, more serious, a totalitarian government could easily eavesdrop outgoing communications from the country and detect dissidents willing to engage in illegal communications with external parties.

Definition

In this context, the notions of unlinkability, unobservability and pseudonymity (see section 1.3.1) are also relevant, as they were actually invented for this context [START_REF] Pfitzmann | Anonymity, unobservability, and pseudonymity -a proposal for terminology[END_REF]. Here, we are interested in the (un)linkability between network nodes (e.g. source and destination) and between network nodes and messages. More precisely, we consider the notions listed below. In the following definitions, according to the definition of unlinkability, by "impossible to know" we mean that the two items (e.g. a node and a message) are no more and no less related compared to the situation before the event (e.g. message sending).

Source/Message unlinkability: given a message and the identity of a potential source, it is impossible to know if the source is the actual issuer of the message;

Destination/Message unlinkability: similar to Source/message unlinkability;

Source/Destination unlinkability: given two nodes, it is impossible to know whether they communicate together or not (this notion is composed source/message and destination/message unlinkability for the same message4 );

Relay/Message unlinkability:

given a message and a potential relay node in the network, it is impossible to know if the message passed though the relay node;

Node anonymity: all or a subset of nodes in the network stay anonymous, i.e. their identities are never disclosed;

Message unobservability: it is impossible for some observer to know whether or not a message is issued, received or relayed in the network. Note: this property typically implies very inefficient solutions and is not considered in the rest of the section.

These definitions implicitly suppose the existence of an "observer" or and "attacker", a malicious entity willing to learn as much as possible about the network, network nodes and communication patterns for its own profit. In a military network deployment, this entity can be the opponent army for instance. It is crucial to define the capacities of this observer or attacker in order to evaluate the above properties: a system might provide source/message unlinkability against an attacker X, but not against a more powerful attacker Y . The main models for network attackers are: active or passive, global or local, and external or internal to the network. In some cases, the location or role of the attacker in the network is also important (e.g. the attacker can be on a message's route or not, impacting its capacities). For more information, [GBP13, Section 3.2] provide a detailed definition of these models.

There exist interactions between the different privacy properties. For instance, if a system provides source unlinkability, but no destination unlinkability, when Alice sends a message to multiple recipients, who all answer back to Alice, an observer will notice a sudden increase in the amount of messages received by Alice and can infer Alice was the sender of the original messages. In other words, source unlinkability without destination unlinkability might result in neither source or destination unlinkability. Thus, the consistency and compatibility of a system's privacy properties must be thoroughly analyzed. Also, it is important to note that, even though all the above properties are enforced in the system, confidentiality and integrity of application-level messages are not implied. Adequate encryption and signature techniques must be applied if those are necessary. Conversely, encryption and signature do not provide anonymous communications. Also, it is important to note that providing anonymous communications and confidentiality/integrity is not enough to obtain anonymous access to a service: the two sectors are correlated but not equivalent, and if the application-level messages sent to the service provider contains identifying information, the anonymity provided by the network is vain (see section 1.3.2). However, confidentiality, integrity and more generally the contents of application-level message are not considered in anonymous communication solutions: in this sector, we focus on routing and traffic analysis.

MIX-nets

In its seminal work on traffic analysis and untraceable communications [START_REF] David | Untraceable electronic mail, return addresses, and digital pseudonyms[END_REF], Chaum presented a protocol using particular routers, which he called MIXes. These MIXes have been the building blocks for many of the solutions proposed to provide anonymous communications. Basically, a MIX router hides the link between incoming and outgoing messages, using techniques tampering with time, ordering and appearance of messages. An adversary observing a specific MIX router may try to re-link messages in two main ways. First, following the assumption that an incoming message and an outgoing message have a higher probability to be linked when the time elapsed between the incoming message reception and the outgoing message emission is shorter. To prevent this kind of attack, two types of MIXes exist: continuous MIXes introduce a random delay between reception and forwarding (the protection they provide is efficient when traffic is dense, else, timing attacks are still feasible). The alternative is using Pool MIXes that function in batches: it waits for n messages to be received before forwarding them, in an order different from the order of arrival. Secondly, using size and/or appearance of message, attacker can very easily trace traffic. MIXes thus use padding techniques and fixed-size packets, along with decryption/re-encryption techniques (using pre-distributed, publicly known keys for instance). In a network, several MIX routers are often used in chain, so that unlinkability properties Inria are ensured even if all routers are compromised but one. Indeed, when there is only one MIX on the route, this MIX knows the sender and the receiver, thus neither the source/message, destination/message nor the source/destination unlinkability properties are observed. When two MIXes are used one mix can make the source-message link, the other can link message and destination, but none of the two MIXes can break source/destination unlinkability. The risk is that they collude to pool their knowledge and try to re-link source, destination and messages together. Therefore, the more MIXes, the better the unlinkability, but the slower the communication. In standard solutions, the first MIX can link a message and its source, and the last MIX can link the message and its destination [START_REF] Dingledine | Tor: The secondgeneration onion router[END_REF], but this can be avoided (e.g. via anonymous authentication between the source and the first MIX) [START_REF] Zhang | Mask: anonymous on-demand routing in mobile ad hoc networks[END_REF]. Moreover, note that an external observer can always trivially detect message emission (or reception) by a particular node, and therefore link a message to a sender (or a destination). This inherent characteristic of network communications is particularly uneasy to circumvent. The main way to get around it is for the network to ensure unobservability. For this, Chaum proposes the introduction of dummy messages, which is very costly in terms of bandwidth.

In order to distribute trust among many nodes, solutions like Tarzan [START_REF] Michael | Tarzan: A peer-to-peer anonymizing network layer[END_REF] and Morphmix [START_REF] Rennhard | Introducing morphmix: Peer-to-peer based anonymous internet usage with collusion detection[END_REF] propose to build a peer to peer network where any node can be a MIX router. Those are called MIX networks. Generally, routes and MIX routers are chosen randomly and adaptively, either by the source or dynamically by the MIXes en route.

High-latency/Low-latency networks

When implementing a MIX router, choices and trade-offs have to be made between delay and unlinkability (or more generally, privacy): while continuous MIXes introduce less delay, anonymity is low when traffic load is low, as pool MIXes may introduce large delay, but ensure high anonymity. Note that the chosen cryptographic primitives can induce more or less delay as well (e.g. asymmetric encryption is generally slower than symmetric encryption). In the literature, MIXing solutions are divided between high-latency and low-latency ones. The first category are dedicated to latency-insensitive applications with little interaction such as email and are able to resist a global eavesdropper. Low-latency MIXes support more dynamic applications such as web browsing, or SSH and TCP sessions, but are more vulnerable.

As an example, Mixminion [DDM03] is a high-latency network assuming the loss of efficiency in order to obtain strong anonymity properties. On the contrary, the basic Onion Routing protocol [START_REF] Goldschlag | Onion routing[END_REF] is designed for low-latency networks, and in the presence of low traffic, MIXes must continue forwarding traffic, even if gives a significant advantage to the attacker. The second generation of Onion Routing (Tor) [START_REF] Dingledine | Tor: The secondgeneration onion router[END_REF] goes even further in to reduce latency, as it no longer uses MIXing techniques. Indeed, the authors consider that the benefits in terms of privacy are too low (and not formally proved) and that the overhead they imply too large to justify their use. In practice, Tor no longer re-order message in batches, but still adds padding after decryption of a layer. The result is an efficient low-latency network, however vulnerable to a global attacker.

Cryptographic constructions and protocols

The last sector we put forward deals with cryptographic schemes and protocols. Although mentioning cryptography as a sector instead of a tool can be somewhat surprising, we argue cryptography is both. Indeed, as we can see, cryptography is extensively employed to enable confidentiality, anonymity and privacy in the technological approach. However, cryptographic constructions themselves can also benefit from privacy properties. One may take as a starting point an existing cryptographic construction as a public key scheme, and try to define, design and incorporate properties that preserve "anonymity" within the construction. What is meant by "anonymity" in this case is to be defined depending on the cryptographic system considered, and the unlinkability-based definitions from sections 1.3.1 and 1.3.3 are also relevant here.

A simple example consists in modifying a public key scheme such that it ensures "key privacy", a property preventing an adversary from distinguishing, given a ciphertext and a set of public keys, which key was used to encrypt the message. Indeed, messages intended to Alice are encrypted with Alice's public key (which is often publicly known), and if, given a ciphertext, it is possible to reveal the key used for encryption, the link between the message and Alice is trivial. It is proven that key privacy is possible in several schemes such as El Gamal or Cramer-Shoup, but not for RSA for instance [START_REF] Bellare | Keyprivacy in public-key encryption[END_REF].

Key exchange and cryptographic authentication are also systems that can integrate anonymity properties [START_REF] Viet | Anonymous password-based authenticated key exchange[END_REF][START_REF] Gambs | Prover anonymous and deniable distance-bounding authentication[END_REF]. As outlined in section 1.3.1 authentication and anonymity seem orthogonal objectives, but the cryptographic tools used in authentication can incorporate privacy properties. The solution is to authenticate users, not as individuals, but as legitimate members of a trusted group. For instance, using group signature, a user proves he has the knowledge of a secret common to a known group, and thus authenticates himself as member of the group, but it is impossible to uncover the signer's identity from the signature. Another way of doing so is to use a certificating trusted third party: this entity delivers certificates that the user can show to prove himself to other entities (who can verify the certificate publicly). The drawback of this approach is that the third party knows the link between anonymous certificates and the users.

In functional encryption, where secret keys' special construction allows decryption and computation of a certain function f at the same time, Boneh et al. [START_REF] Boneh | Function-private identity-based encryption: Hiding the function in functional encryption[END_REF] propose the notion of functional privacy. Typically, in basic functional encryption, an entity is given a secret key sk f that can be used to compute Dec(sk f , Enc(pk, m)) = f (m), and security requirements ask that nothing except f (m) leaks about the underlying message. However, nothing is said concerning f , and the computed function can be known and/or learned. Boneh and al. go further, and require that f stays secret, so that only f (m) is computed without revealing neither f nor m. This requirement is useful in a context of computation delegation: for instance, a user might need to delegate email sorting between "urgent" and "other" mails to a proxy, without revealing the contents of its mails nor the "urgent" selection criteria. In practice, authors give a solution for identity-based encryption (a simpler variant of functional encryption where f is a simple predicate checking the identity embedded in a ciphertext) based on the assumption that identities that correspond to a given secret key are sampled from distributions with a certain amount of min-entropy. This result does not provide a strong functional privacy as one would expect, but this work lays the foundations for future developments.

Measuring privacy in computer science

In order to be able to compare privacy solutions, given a sector in the technological approach, there is a need for a privacy metric. In other words, it is necessary to measure and quantify privacy precisely. An impartial, objective measure is the only way to obtain certainty of the privacy properties ensured by a system, and to unambiguously compare privacy solutions.

Several ways of measuring privacy have been proposed and used. Some metrics are formally defined, others are more intuitive and easy to use but less accurate. What they measure needs to be specified, as they are generic tools. Depending on what is considered private or not and on the endorsed vision of privacy, the measures must focus on different objects. Indeed, although the metrics are well defined as theories, the intended objects of measurement are not included in their definitions. As a result, there is no precise framework for the measurement of privacy.

Inria

This often results in incomparable solutions and measurements, which is exactly the opposite of privacy metrics' primary goal.

However, privacy metrics are necessary, and while this field needs formalization and is quite recent, efforts in this direction can only be beneficial. In this section, we sketch a few privacy measurement tools and illustrate their use in privacy works. Note that, although we listed cryptography as a privacy sector, we do not present measurements of privacy properties in cryptographic schemes: in this particular context, proofs of privacy properties are analogous to those of traditional security properties, and this field of information security uses its own, very strict and formal, mathematical tools.

Information theory

The main privacy measurement tool, the most well defined and the most used is information theory. Invented by Shanon in 1949 [Sha49] to be applied to signal processing measurements, this method of information quantification has been widely used in computer science.

The key component of information theory is entropy, which measures the quantity of information (often in bits) needed to represent an object. For instance, as there are nearly 2 33 ≈ 7 billions human beings on earth, 33 bits of information are needed to represent a person. Another way to see entropy is as a quantifier of the uncertainty of a random variable. In our example, if the random variable X is defined by a uniform law and takes as value 1 human being on earth, the entropy of X is 33. Remark that when the entropy is high, the value of the random variable is very uncertain, i.e. it can take many values, each with the approximatively same probability (X is close to uniform). When it is very low, the random variable is almost determined, in the sense that there is 1 value with high probability, and a few other very improbable outcomes. The exact formula used to measure the entropy of a random variable X is:

H(X) = - a|P r[x=a]>0 P r[X = a].log 2 (P r[X = a])
This formula computes the expected value of the logarithm of the probabilities, and thus the average number of bits needed to represent X. Indeed, as X can be described by -log 2 (P r[X = a]) bits with probability P r[X = a]5 , the average number of bits to represent X is E[-log 2 (P r[X = a])]. We reformulate the above explanation with the value H(X): when H(X) ≈ 0, uncertainty of X is very low and ≈ 0 bits are needed to represent X, thus we can consider X is determined. On the contrary, if H(X) is high, the outcome of X is very uncertain and a lot of information is needed to figure out the outcome of X.

A useful derivative of entropy is the conditional entropy H(X|Y ) which computes the uncertainty of X provided Y is known:

H(X|Y ) = - a,b|P r[X=a|Y =b]>0 P r[X = a ∧ Y = b].log 2 (P r[X = a|Y = b])
This formula quantifies the average quantity of information needed to know the outcome of an event X when the outcome of the event Y is known. For instance, it is useful in cryptography to express a perfect cryptosystem: the phrase "knowledge of the ciphertext does not change uncertainty of the plaintext, and knowledge of the plaintext does not change uncertainty of the ciphertext"can be expressed as H(P ) = H(P |C) and H(C) = H(C|P ), where H(P ) is the entropy of the plaintext and H(C) the entropy of the corresponding ciphertext [START_REF]Encyclopedia of Cryptography and Security[END_REF].

Use of entropy in privacy measurements

In computer security, a very widely admitted way to verify the security of a system is to suppose the existence of an adversary, give him capacities and limits, and observe the harm that he can do to the system. More or less powerful models of adversary can be imagined according to possibilities given to the adversary and the strength of the assumptions made on the system and the environment. In general, models try to mimic real situations, and to over-estimate the adversary's capacities so that security is overevaluated (rather than optimistically evaluated). When measuring privacy, we proceed following the same paradigm. We suppose the existence of an adversary who observes the system and the events produced within it, and tries to guess the outcome of an event. For instance, an adversary observing network communications can try to determine who sent a specific message. The knowledge of the adversary is then modeled by a random variable X which distribution probability gives the guesses of the adversary. In the latter example, X may take as value any identity within the network. To measure privacy guaranteed by the system, entropies of all event which outcome needs to be kept secret are computed. Note that the precise list of these events of interest depends on the privacy goals of the system, and may be hard to draw. Notably, there is no way to be certain that all sensible events have been considered.

Starting from this basic protocol for measuring privacy with entropy, several works enhanced the measuring by pointing and resolving flaws of the above measuring technique [GTD + 08, THV04]. In the sector of anonymous communication and traffic analysis, Tóth et al. [START_REF] Tóth | Measuring anonymity revisited[END_REF] notice that even though entropy gives the average guaranteed privacy, high entropy does not always mean good privacy. For instance, the authors consider hiding the identity of a source sending a message: when an adversary studies the outcome of X, where X is the identity of the source, and knows that P r[X = ID 0 ] = 0.5 and ∀i ∈ [1...100] P r[X = ID i ] = 0.005, entropy H(X) is the same as uniform distribution over 20 possibilities. However, the adversary will most certainly infer that ID 0 sent the message because this value has much higher probability than any other. The authors thus introduce the notion of local anonymity that additionally requires an upper bound on all probabilities. In the presented approach, however, the assumed model does not always reflect real situations or is not trivially usable in practice because of incompatible assumptions between the measurement framework and the communication protocol. In particular, in the presented measures of privacy in anonymous communications, the use of MIX routers in the protocol is assumed, which is not the case in Tor for instance, and in many privacy-preserving communication protocol.

In definitive, information theory is a well defined, formal and powerful tool, but applying and using it must be done with great care. First one must point out what needs to be measured, but the most challenging is drawing the probability distribution correctly, i.e. in a manner adequately describing reality. The most effective way of doing so is, for now, using simplifying models to describe the environment.

k-privacy

A much more simple but less accurate metric can be derived from the technique of k-anonymity that has been presented in section 1.3.2, which deals with statistical databases. It is indeed a technique transforming a database by forming classes of k undistinguishable entries, but more generally, k-anonymity denotes the partition of the universe of entities in classes of size ≥ k where all members are equally probable candidates related to a given event. Therefore, the parameter k determines the size of the anonymity set(s) and measures privacy in the sense that a greater k gives better anonymity. In practice, the universe of entities is simply divided in two: one group of size k containing the possible candidates (the anonymity set), and the rest of the universe. Note that k-anonymity can be seen as a very simple form of information theory: in a sense, the Inria size k of the anonymity set measures the uncertainty of a random variable X associated to an identity. Within the anonymity set, X is a uniform distribution overt k values, and probability associated to values outside the anonymity set is 0.

However, this quantification suffers from several shortcomings. The assumption that all k candidates are equally probable may be flawed, there is no framework or formalisation of kprivacy, and as there is no systematic way to apply it, forgetting or adding false candidates in the anonymity set is always possible. Also, k-privacy is only suitable in contexts where events are issued (or related) to entities, and the aim is to hide who issued which event. Note that information theory is more general as it models the knowledge of the adversary in a context-agnostic manner. Though very informal, this metric is useful as a pre-analysis of privacy properties. Instead of directly using information theory, one will prefer employing the simpler tool of k-privacy. It is easy then to quantify the probability of each candidate within the set of k entities in order to compute the entropy of the random variable answering the question "who is the originator of this action" for instance.

Example using k-privacy

In the sector of privacy-preserving location-based systems, it is possible to define privacy requirements in terms of k-privacy: a subject is "k-anonymous with respect to location information, if and only if the location information presented is indistinguishable from the location information of at least k -1 other subjects" [START_REF] Gruteser | Anonymous usage of location-based services through spatial and temporal cloaking[END_REF]. In other words, k-privacy in location-based systems is achieved for a given user when at least k -1 other users were in the approximately same place at the approximately same time. The system designed by Gruteser and Grunwald [START_REF] Gruteser | Anonymous usage of location-based services through spatial and temporal cloaking[END_REF] takes as parameter a minimum bound on the anonymity set, k min , and ensures it by decreasing the accuracy of spatial information as much as necessary in order to always have k users in the same region at any time. This anonymity comes at the cost of decreased utility: if a user employs very deteriorated location information to enquire a locationbased service (e.g. a listing the restaurants in the neighborhood), the answer will contain a lot of useless data, and the user might not actually obtain the information he was looking for. As in many sectors of privacy, a trade-off between utility and privacy is necessary.

Differential privacy

Differential privacy has also been presented in section 1.3.2, and, as k-privacy, it can also be seen as a metric. In its basic meaning and roughly speaking, differential privacy ensures that the removal or addition of a single database item does not substantially affect the outcome of any analysis [START_REF] Dwork | Differential privacy: A survey of results[END_REF]. However, in a broader sense, a differentially private mechanism M on data space D guarantees that the amount of information that is leaked when executing M on the sensible input data x ∈ D is bounded and divided equally among all items in the data. The fundamental equation expressing the above definition for a -differentially private randomized mechanism M : D → D is:

∀x, x ∈ D ∀t ∈ D , P r[M(x) = t] P r[M(x ) = t]
≤ e , with x ⊂ x and x contains 1 more item only Probability is taken over the coin tosses of M. A mechanism M satisfying this definition ensures that by the presence or absence of any item in the dataset, no outputs would become more or less likely. Thus M protects every item in the dataset independently in a very strong sense, as the above equation is a statistical property of M, independent from the computational power and knowledge of the adversary.

This equation is not a privacy protection per se, but a goal and a constraint a mechanism must observe. We mentioned in section 1.3.2 the use of Laplacian noise in order to achieve differential privacy. However, this is only one way of satisfying the above equation. When constructing a privacy-preserving mechanism, one may want to achieve differential privacy, so as to obtain strong proven privacy properties, and it is possible to do so with theoretically any system (actually, if M is a completely random function, it satisfies differential privacy). In a short survey [START_REF] Dwork | Differential privacy: A survey of results[END_REF], Dwork gives examples of differentially private mechanisms.

In the previous equation, the quantification of privacy is given by the parameter. It can either be fixed to a value arbitrary close to 0 (but then utility of the output is very low), and up to 2 or 3 in some cases, or it can be expressed as a function of the other system parameters. The value of depends on the acceptable information leakage and the sensitivity of the data. The advantage of this metric is the compositionality property that comes with differentially private mechanism: given a dataset x, if a user makes a k queries on D, the i th query being i -differentially private, then the overall mechanism is i -differentially private. This property is useful to bound the sensible information a user of the mechanism can learn with at most k queries. If necessary, the mechanism M can refuse to answer to a client who has consumed all its "privacy budget", i.e. when the client learned k i=0 i ≥ ∆ quantity of information. A proposition for a generalized metric based on -differential privacy has been recently proposed [START_REF] Konstantinos Chatzikokolakis | Broadening the scope of differential privacy using metrics[END_REF] and applied to sectors different from statistical databases.

Example using differential privacy BLIP (BLoom then FLip) [START_REF] Alaggan | Blip: Noninteractive differentially-private similarity computation on bloom filters[END_REF] is a technique invented by Alaggan et al. to compute profile similarities, for instance in social networks. The profile is represented by a Bloom filter [START_REF] Burton | Space/time trade-offs in hash coding with allowable errors[END_REF], and in order to protect the items contained in the profile, the authors propose a simple bit flipping mechanism that they prove to be differentially private. Each bit is simply independently flipped with a probability p < 0.5, and as a result, items are -differentially private, with relation p = 1/(1+e /k ), where k is the number of hash functions of the Bloom filter. The utility is best when p ≈ 0, but the authors show that for their application (similarity computations), utility is non-trivial even for "small" values for the parameter . As a result, each item is independently protected against computationally unbounded adversary, the information leaked by a bit-flipped bloom filter does ot exceed a certain threshold , and the authors show that reconstructing a user's profile is hard.

Discussion

This overview of problematics inherent to privacy protection gives rise to various reflexions on existing solutions and subsequent works that need to be addressed. The proposed view of privacy will also be discussed.

The Approach × Sector view

This chapter puts forward a categorization of the existing privacy works in research, following a Approach × Sector matrix. We argue this categorization provides a pertinent and useful synthetic view, and consists in a trade-off between a very complex but complete and exact categorization, and a disorderly inconsistent listing.

As said earlier, the choice of approach and sector as the only two criteria is motivated by their predominance and the possibility to easily compare solutions within the same sector and approach. Of course, many particular privacy works will be problematic and will not fit in one particular class. As an example, biometric authentication relates to the "identity management and authentication" sector, but is also relevant in the "protection of personal data" sector, Inria because biometric data are extremely personal. Conversely, there will also be "holes" in the Approach × Sector matrix. Indeed, some sectors are approach-specific, for instance the sector of cryptography is only relevant in the technological approach.

A particular issue with the proposed categorization is that it does not provide an easily retrievable list of general privacy-enhancing tools. Actually, depending on what we are interested in, a new categorization is necessary for each purpose. However, note that the approach criteria is always implicit (i.e. when using the word "privacy", one often has an approach in mind) and will most probably always be the first criteria of a categorization. The choice we made is using it together with the sector criteria, which is indeed discutable. Here, our goal was to obtain a synthetic view of the field of numerical privacy using a minimal number of criterion. Choosing sector above tools, privacy goals or models is justified by the relative precedence of sectors on others dimensions, and above all by the need we expressed.

Another point worth questioning is the completeness of the approaches and sectors lists in sections 1.2 and 1.3, as well as the list of criteria in section 1.1.2. They reflect modern privacy considerations and the author's sensibilities. Although one might have other criteria in mind, the current list in section 1.1.2 contains the main important ones, and adding more criterion could lead to more, useless complexity. Concerning the list of sectors, as mentioned in introduction of section 1.3, all information systems are subject to privacy research. Thus we merely sketched the main fields in computer science where privacy is an active research theme. As for the list of approaches, although persons from different profession or sensibility might propose different ways to consider privacy, these 4 are the only one concerning numerical privacy, to our knowledge.

In a few words, privacy may be conceived under many angles, others than those proposed here. Because of the complexity of the field, a complete, exact and efficient categorization is hard to achieve. Although our categorization is approximative, to our knowledge, this initiative is the first intending to provide such a systematic categorization.

Trust management

In light of existing propositions, we note that trust management is a common issue in privacy, and more generally in information system security. A common goal for all privacy solutions is to ensure the user protection of his privacy when using numerical services and resources, by the mean of diverse technological solutions (we only consider the technological approach here). However, technological solutions are often deployed by the service/resource provider himself, who is precisely the entity that would benefit from a privacy violation. Therefore, default trust of the user should be minimal in the service provider, and instead should rely on other objects.

Typically, to resolve trust issues, there exist two main ways: to invoke a "trusted third party" (e.g. a governmental agency) in which the user is willing to place his trust, or to distribute the trust. The first proposition only "moves" trust from one entity to another, and in practice takes the form of certification authorities, audit of systems by experts and/or legal enforcements. Distribution of trust divides the user's trust in multiple entities and relies on the assumption that a majority of entities will be honest. This latter approach avoids the unique point of failure, but it is vulnerable to collusions. In practice, trust is often distributed among the other users of a given system, with the assumption that there are many other users.

We envision a third option to trust management: when a technology is formally proven secure (as well as its implementation), and its deployment depends on the user's initiative, then the user can place his trust in the technology, and not in entities controlled by human administrators. By user's initiative, we mean that the user himself can decide alone to use a given technology which ensures that the service provider can not harm his privacy. Of course, the service provider must comply with the technology, but deployment and implementation do not depend on him: if the user, and solely the user, follow the proper protocol, the service provider can not tamper with his privacy. This is a very strong requirement, and trust is at the lowest in this case (i.e. user does not need to trust any entity) provided technology is reliable.

Privacy in public opinion

As, fundamentally, privacy is a social concern, we could have described a "social approach" to privacy in section 1.2. However we argue that the social approach is actually implicit in each other approach and can not form an approach on its own in a categorization of privacy works or privacy solutions. There are however purely social studies dealing with numerical privacy that we did not mention in this chapter. Those studies need to be taken into account in order to design systems that will be used and have a non-negligible utility in society.

To sum up results in this field, a quotation from a survey by Taylor [START_REF] Taylor | Most people are "privacy pragmatists" who, while concerned about privacy, will sometimes trade it off for other benefits[END_REF] is sufficient:

Most people are "privacy pragmatists" who, while concerned about privacy, will sometimes trade it off for other benefits.

Indeed, Taylor's survey draws three categories of persons: "privacy fundamentalists" who care about privacy (26 %), "privacy unconcerned" who explicitly do not value their privacy (10 %), and "privacy pragmatists", who claim to care about their privacy, but are willing to trade it against short term benefits (64 %). As explained in section 1.2.4, this is mainly due to misinformation, bounded rationality and human psychology limitations. Another experimentation, by Grossklags and Acquisti [START_REF] Grossklags | When 25 cents is too much: An experiment on willingness-to-sell and willingness-to-protect personal information[END_REF], investigates the "willingness to pay" for protecting personal information and "willingness to sell" the same information. Although biased because of a small tested population, who does not represent well of the global population (47 persons, almost all students), and the fact that interviewees were aware of the general principle of the study (thus were already willing to take the risk to disclose personal information), this study shows the overwhelming willingness to sell over willingness to pay, or in other words, monetary benefits are preferred over privacy in a large majority of cases.

Several studies attest the misinformation and misunderstanding of the general public regarding consequences of private information disclosure [WNK + 11, SCK + 13, WCS + 13]. Individuals often accept disclosing a large amount of unnecessary information in order to access a service that is convenient for a given purpose, well designed or very used among their social circle. However, they either do not know that their data is collected, the value of those data for information brokers or the consequences and serious harms this collection can do to them, or they simply "do not care" and declare having "nothing to hide".

Do we need privacy ?

The question immediately emerging from the observations made in the previous section is: "Do we actually need privacy ?". Indeed, privacy in a social concern, but paradoxically the public opinion, in practice, do not want or need privacy. We leave aside special contexts as surveillance in totalitarian regime where common opinion agrees on the fact that privacy is inexistent and people's right are flouted ; or specific cases involving crimes or socially unacceptable acts where privacy should on the contrary be avoided. We briefly review common arguments against privacy and show their weaknesses, and eventually point two reflexions on the meaning and implications of (numerical) privacy in modern societies.

The most common argument is the "nothing to hide" one: supposedly, if an individual has done nothing "wrong", i.e. illegal or socially unacceptable actions, he should not bother being watched and under surveillance, and should not need to keep information about himself secret.

Inria

This argument is very close to the "surveillance is necessary for the nation's security" one, extensively employed since the 9/11 events in the United States, and can be refuted in the same manner. A first, easy answer is simply that actually everyone has something to hide, would it only be the moments and discussions with his/her partner. As put forth by David Flaherty [START_REF] David | Visions of Privacy: Policy Choices for the Digital Age, chapter Visions of Privacy: Past, Present, and Future[END_REF], no one can "withstand even a few minutes' questioning about intimate aspects of their lives". For a more complete analysis of the "nothing to hide" argument, see Daniel Solove's paper on this matter [START_REF] Daniel | i've got nothing to hide' and other misunderstandings of privacy[END_REF], who argues that this argument narrows privacy to information concealing and surveillance, whereas the problems raised by data collection are numerous and privacy has multiple facets (see section 1.1). Among other issues, Solove mentions the "secondary use" of the data: at first, data is collected for a given purpose, but the data may easily be used for an unrelated goal, without the consent of the user. Thus the data collected by government agencies, at first gathered for public good, may travel across several platforms and be in definitive publicly published.

Other typical arguments include phrases like "no one cares about privacy anymore" or "privacy is dead at the digital age". They are more observations than real arguments. Privacy is dead only if all research and social efforts are abandoned, which is far from the case at this moment. The "secondary use" and misinformation issues can also be invoked here to mitigate the first phrase: if individuals were better informed on the use of their data and the true consequences of data collections/analysis/disclosures, they may reconsider their judgement.

On the privacy advocates side we can point the reader toward two reflexions. First, in 2009, Danah Boyd presented a talk on privacy in the context of Big Data [START_REF] Boyd | Privacy and publicity in the context of big data[END_REF]. Although she recognizes the potentially great utility of analysing very large datasets (e.g. analysing DNA to help cure diseases), she questions the ethics of doing so. Actually, the author calls for a more ethic use of big data and personal data in general. She tries to mitigate the enthusiasm and haste of information brokers who very quickly took hold of the concept of Big Data.

Finally ,a recent MIT technology review by Evgeny Morozov, entitled "The Real Privacy Problem" [START_REF] Morozov | The real privacy problem[END_REF], offers a deep understanding of privacy and the social meaning of the lack thereof. In this reflexion, the author considers privacy as a mean (as opposed to a goal in itself) toward democracy, arguing that arising automated decision processes, in particular via analysis of large datasets, are replacing societal debates, reflexions and discussions and lead to unjustifiable and unjustified decisions. This is in accordance with Boyd's opinion. But according to Morozov, in order to grant privacy its right place in the public debate, and to efficiently protect privacy in the long term, legal and technological means are insufficient. There is a true need for a political debate and an ethic vision of privacy, and the solution can only come from a public realization. For this, Morozov argues that individuals need to "sabotage the system and provoke more questions", in particular by refusing to use services tracking users.

Chapter conclusion Privacy, even restricted to the numerical context and to the technological approach, is a very vast field of research. As put forward in section 1.3, many or all information systems can benefit from privacy properties. In other words, privacy researches can focus on any existing system: the choice is open. Of course, some systems or sectors are more relevant than others, in the sense that protecting privacy is more important. For instance, protecting privacy in medical information systems is more important than in digital rights management because privacy leaks in the former lead to more serious consequences. The aim is to clear out pertinent sectors where privacy is crucial.

In this chapter, we offered a possible view of numerical privacy that we consider sufficient to organize the knowledge in this field of research. We also presented the main tools to measure privacy, letting us hope for a way to quantify the privacy of newly designed solutions. All these elements provide the necessary tools and knowledge to improve upon existing privacy works or initiate new directions of research in privacy, e.g. by formalizing privacy and privacy metrics, or by pointing to new sectors where privacy is yet to be considered.

We now describe in the enxt chapter how, or more precisely with what tool privacy can be enforced. We turn toward cryptography, which is the one of main tools in privacy solutions, and in this case we are interested in homomorphic cryptography. The great possibilities offered by this cryptographic paradigm let us hope for meaningful applications to the protection of privacy.

Inria

Chapter 2

Homomorphic Encryption

As we are interested in protection of numerical privacy in all its forms, we expect the need for powerful confidentiality-enhancing tools. Here we consider the use of a rather new, (theoretically) extremely powerful cryptographic tool to achieve privacy requirements in various systems: homomorphic encryption. This particular type of encryption allows to process data in the encrypted domain, i.e. it allows any party in possession of the corresponding public key to perform logical operation on encryption of messages, yielding logical operations on the underlying messages. In particular, homomorphic encryption allows to outsource computations on sensible data to a (possibly untrusted) third party while preventing it from learning the actual contents of the data, which is specifically the expressed need in the context of private cloud-assisted computing for instance. For more than 30 years now, this type of encryption has been extensively studied, and in 2009 a major breakthrough by Craig Gentry gave rise to the first fully homomorphic encryption (FHE) scheme, a scheme capable of evaluating any function on encrypted data.

This chapter presents the concept and history of homomorphic encryption, details several fully and non-fully homomorphic encryption schemes along with their implementations and their practical use. This chapter is solely focused on describing homomorphic encryption, while its use to enable privacy is left as discussion in the conclusion (section 2.4.5).

General points

This first section introduces the notion of homomorphic cryptography and provides the reader with the necessary notions and tools to approach this chapter with the appropriate knowledge. We first define homomorphic encryption, and then give an abstract view of this particular field of cryptography by drawing a short history and categorizing schemes in 3 main classes according to their homomorphic properties. At last, we give a good insight of the main pending issues, both theoretical and practical, in homomorphic cryptography research.

Definition

In a traditional public key encryption (PKE), schemes are typically composed of three probabilistic polynomial-time (PPT) algorithms 1 primitives: Key generation (pk, sk) ← KeyGen(1 λ , params): According to the parameters params, outputs a public encryption key pk, and a secret decryption key sk, guaranteeing a security of λ bits, i.e. ≥ 2 λ operations are needed to break the scheme. Typically, λ = 80, 128, 256 or more. Note that λ specified via a value of λ bits, but we merely use its length as parameter for security. Sometimes, KeyGen is split in two primitives: Setup inputs 1 λ and outputs params, and KeyGen only uses params as input. Basically, a homomorphic encryption scheme possesses a fourth PPT primitive, which captures its capacity to evaluate functions on encrypted data:

Evaluation C ← Eval(pk, f, c 1 , . . . , c n ): with c i ← Enc(pk, m i ), computes f (m 1 , . . . , m n ) in
the encrypted domain, and outputs an encryption of the result under pk such that

Dec(sk, C) = f (m 1 , . . . , m n ) (2.1)
The set F of functions f ∈ F a scheme can accept as input for Eval while guaranteeing correct decryption determines its homomorphic capacities. This set is defined by the properties of the scheme and can be expressed through various computation model (see section 2.1.4). Equation 2.1 formalizes the correctness of the homomorphic scheme's operations, and in some case is expressed in a probabilistic manner: a scheme is said correct if equation 2.1 holds with very high probability.

Example of homomorphic encryption: RSA Unpadded In its original design, RSA is multiplicatively homomorphic, that is to say it is possible to compute Enc(pk, m 1 × m 2 ) from the encryptions of m 1 and m 2 : with pk = (N, e), we have

Enc(pk, m 1 ) = m e 1 mod N Enc(pk, m 2 ) = m e 2 mod N Enc(pk, m 1 ) × Enc(pk, m 2 ) = m e 1 × m e 2 mod N = (m 1 × m 2 ) e mod N = Enc(pk, m 1 × m 2 ) = Eval(pk, [(x, y) → x × y], Enc(pk, m 1 ), Enc(pk, m 2 ))

Historical overview

The search for an homomorphic encryption scheme goes back to the year 1978, shortly after the invention of RSA: the accidental malleability of RSA led Rivest, Adleman and Dertouzos [START_REF] Rivest | On data banks and privacy homomorphisms[END_REF] to form the idea of computing on encrypted data. The existence of such a mechanism was unknown at the time and considered an open question. A first answer was (informally) given in the form "Yes, but there must be interaction between the owner of the secret key sk and the evaluator", and led to the creation of Secure Multi-party Computation [START_REF] Goldreich | The Foundations of Cryptography -Basic Applications[END_REF], a possible way to compute with encrypted data. See section 2.4.5 for a brief description of this technology and its link with our concerns here. The question of the existence of a non-interactive mechanism was reformulated and somewhat formalized by Feigenbaum and Merritt [START_REF] Feigenbaum | of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, chapter Open Questions[END_REF] in 1991, who proposed the notion of algebraic homomorphic cryptographic schemes that could securely evaluate Enc(pk, m 1 + m 2 ) and Enc(pk, m 1 × m 2 ) solely from pk, Enc(pk, m 1 ) and Enc(pk, m 2 ), without interaction between any party, Inria and without knowledge of the secret key. Such a homomorphic scheme enables arbitrary computations on encrypted data, i.e. its associated set of evaluable functions F contains all functions that are computable in the clear. Indeed, if the message space is {0, 1}, addition of messages corresponds to a logical XOR, and multiplication to a logical AND. As the set of gates {XOR, AN D} is functionally complete, any circuit and thus any function can be computed with such a scheme.

However, the first homomorphic schemes that appeared allowed only addition or multiplication but not both. The first known, if we leave aside RSA which is insecure in its unpadded version, is the scheme of Goldwasser and Micali [START_REF] Goldwasser | Probabilistic encryption & how to play mental poker keeping secret all partial information[END_REF] in 1982. It allowed homomorphic addition of messages in {0, 1}, which corresponds to a homomorphic XOR on bits. Goldwasser-Micali is also the first probabilistic semantically-secure scheme, and at the time, the size of a ciphertext encrypting 1 bit was very large, e.g. ≥ 1024 bits. Many other schemes allowing one operation were proposed, among them the most known are ElGamal [START_REF] Elgamal | A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF] in 1985 and Paillier [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF] in 1999 (see section 2.2).

Early 2000s began to appear schemes that allowed more than one operation [START_REF] Boneh | Evaluating 2-dnf formulas on ciphertexts[END_REF]. For instance, MGH [START_REF] Aguilar Melchor | Additively homomorphic encryption with d-operand multiplications[END_REF] can perform many additions and "several" multiplications. However, these schemes are particularly inefficient and can not handle a reasonable number of multiplications (e.g. 100), because of the exponential ciphertext size blowup phenomenon which seriously limits the schemes: after L multiplications, the size of a resulting ciphertext is C L for some (possibly constant) C, and becomes too large to be manipulated. Because of the difficulties encountered while trying to enable homomorphic addition and multiplication in a same scheme, some works relied on simpler computation models different from Feigenbaum and Merritt's such as boolean circuits [START_REF] Sander | Non-interactive cryptocomputing for nc1[END_REF] or branching programs [START_REF] Ishai | Evaluating branching programs on encrypted data[END_REF]. Note that schemes of this type all share this exponential ciphertext blowup characteristic and are inherently limited in their homomorphic operations: we will call these schemes somewhat homomorphic.

It is only recently, in 2009, that was invented the first fully homomorphic encryption (FHE) in the sense of Feigenbaum and Merritt, i.e. allowing both unlimited additions and multiplications. Before this date, neither theoretical or practical solution existed to evaluate any function on encrypted data. Gentry's thesis [START_REF] Gentry | A Fully Homomorphic Encryption Scheme[END_REF] brought the first theoretical result for doing so, basing security on hard problems in ideal lattices. His construction was designed to encrypt bit messages only, and to evaluate boolean circuits. Two elements were decisive for the apparition of FHE: first, Gentry proposed a powerful somewhat homomorphic scheme capable of evaluating many additions and a few multiplications, but with constant ciphertext size. In other words, Gentry solved the exponential ciphertext size growth. To be more accurate, Gentry moved the problem: the ciphertext from his schemes did not grow in size but contained "noise" that would grow exponentially inside the ciphertext, such that when the noise exceeds a certain threshold, decryption can not be performed anymore (or decryption outputs erroneous values). The key idea to obtain a FHE scheme from this somewhat homomorphic encryption scheme is then to "refresh" ciphertexts when noise becomes too large by homomorphically evaluating the decryption primitive on ciphertexts, thus reseting its noise to a minimal level. This step is called bootstrapping, and is still today the only known method to obtain pure fully homomorphic encryption (see section 2.3.1 for details).

Since 2009, FHE has been an extensively studied subject, especially since 2011 when Brakerski and Vaikuntanathan [START_REF] Brakerski | Fully homomorphic encryption from ring-lwe and security for key dependent messages[END_REF] noted that FHE could be based on the Learning With Errors (LWE) problem, a much simpler tool compared to ideal lattices. The result from Gentry's thesis was almost purely theoretical: as expressed by Smart in his talk at CRYPTO'12 [START_REF] Gentry | Homomorphic evaluation of the aes circuit[END_REF], in 2009 FHE was "totally and utterly impractical", in 2012 it became "totally impractical" and was already about to become only "impractical". Today, FHE is still impractical compared to efficient public key schemes such as RSA or elliptic curve-based schemes, but are (almost) practical for use-cases involving a reasonable number of multiplication [AMFF + 13].

Mathematical tools and notations

Before starting the main matter of this chapter, we define the main mathematical notions and notations we use.

First, all logarithms, unless specified otherwise, are logarithms base 2. We use Landau complexity notations in O(•), o(•), Ω(•), ω(•). The notation Õ(n) refers to O(n) along with logarithmic factors disregarded because of their asymptotic smaller values compared to n (for instance). We also sometimes use the notation poly(n) to denote a polynomial complexity in n and polylog(n) to denote a polynomial complexity in log n. By |N | we denote the bit-size of the number N, equal to log 2 N (we make use of both notations alternatively).

Vectors are denoted by bold font letters a, matrices by upper case bold font letters A and its transpose A T . The term a, b denotes the scalar product of vector a and b. The reduction of x modulo some number n, x mod n, is sometimes denoted [x] n for compactness. When applied to vectors or matrix, e.g. [a] n , it is simply defined as the reduction modulo n of the vector or matrix coefficients.

Cryptography

We use the notions of security from the Foundations of Cryptography (Vol. 2) [Gol04]: IND-CPA, IND-CCA1 and IND-CCA2. When using other security notions, they will be explained. We sometimes mention elliptic curve cryptography and pairing-based cryptography [START_REF] Hankerson | Guide to Elliptic Curve Cryptography[END_REF]. In the document, λ always denotes the security parameters of cryptographic schemes, unless specified otherwise.

In order to characterize homomorphic schemes, we make use of Nick's complexity classes, denoted N C. In particular, N C i refers to circuits of polynomial size (number of gates) and depth (number of gates of the longest path from inputs to output) in O(log i (size of input)) built from fan-in 2 logical gates. The schemes' capacities can also be expressed in terms of multivariate polynomials, which most general form is

P (x 1 , . . . , x k ) = M i=1 a i k j=1 x di,j j
With M the number of monomials, k the number of variables, d i = j=1..k d i,j the degree and a i the coefficient of the i th monomial, and d = max i=1..M d i the degree of the polynomial. The link between the polynomial and circuit models is direct: evaluating a polynomial of degree d requires a circuit of depth O(log d) [START_REF] Vaikuntanathan | How to compute on encrypted data[END_REF][START_REF] Aguilar Melchor | Additively homomorphic encryption with d-operand multiplications[END_REF].

Categorization of homomorphic schemes

As observed in previous sections, a homomorphic encryption scheme is mainly defined by its computational capacities over encrypted data, i.e. the set F of functions it can evaluate. The functions in this set can be expressed though various computation models: polynomials of a specific degree, Nick's classes or more generally boolean circuits. The simplest way of characterizing the capacities of a scheme is in terms of simple algebraic operations, as Feigenbaum and Merritt propose. Typically, the two desirable operations are multiplication and addition of messages in the encrypted domain. Indeed, as explained earlier, these two operations lead to functional completeness if plaintexts are bits.

Inria

We propose the following categorization of homomorphic schemes. For each category, we detail its computational capacities in terms of algebraic operations (in nature and number), as well as in terms of polynomials2 and/or circuits if relevant.

Partially homomorphic encryption (PHE)

Allowing only 1 operation, i.e. addition or multiplication but not both, in a limited or unlimited number. This corresponds to the evaluation of multivariate polynomials of degree d = 1 in the case of unlimited additions, or multivariate monomials of arbitrary degree in the case of unlimited multiplication.

Somewhat homomorphic encryption (SHE)

Allowing 2 operations, one of which in a very limited number. In general, multiplications are limited, and additions are unlimited (or considered as such, because they are negligible compared to multiplications' cost). This corresponds to evaluation of multivariate polynomials of degree d = L if L multiplications are possible in the scheme.

In some cases, it is relevant to characterize the scheme in terms of boolean circuits of bounded size and depth, using Nick's classes for instance.

Fully homomorphic encryption (FHE)

Allowing both operations in an unlimited manner. This corresponds to multivariate polynomials of arbitrary degree.

There are two other elements we did not take into account in this categorization by homomorphic capacities: the category called Leveled homomorphic encryption which is the main matter of section 2.3.1, and the homomorphic scalar multiplication property. The scalar multiplication is an operation that takes place at the frontier between the encrypted and clear domains: one operand m 2 is in clear, and the other m 1 is encrypted by Enc(pk, m 1 ). Schemes allowing scalar multiplication respect the equation: Enc(pk, m 1 ) m 2 = Enc(pk, m 1 .m 2 ) (for an astract operator). In other words, they allow multiplication of an encrypted value with a clear value.

In the rest of this chapter, we rely on this categorization and provide one section each for partially and fully homomorphic encryptions (respectively, sections 2.2 and 2.3). However, because of their small number, their inefficiency and their relatively limited capacities, somewhat homomorphic schemes are not given a section on their own. We merely mention them in section 2.2.6.

Main theoretical and practical issues

In order to offer the reader a better understanding of problematics encountered when designing a homomorphic scheme, we provide in this section a brief description of horizontal issues in homomorphic encryption.

In traditional encryption schemes, we have to perform trade-off between security and efficiency: the scheme must be secure in order to adequately hide information, and efficient so that its primitives are easily computable by the appropriate parties. Indeed, in a perfectly efficient scheme we have Enc(pk, m) = m, and to communicate m to Bob, Alice simply sends it in clear. On the contrary, a secure but inefficient solution (to the point it is not actually working) is for Alice to keep the message m secret and not disclosing it. To this security-efficiency duo, homomorphic encryption adds a third element to take into account: the homomorphic capacities. Indeed, in somewhat homomorphic encryption, the homomorphic capacities of the schemes could be made arbitrary large, but it comes at the cost of exponential or worse running times of cryptographic primitives, and notably Eval. All three components have to be taken into account in the same time, and trade-offs have to be performed.

The above abstract remarks do not reveal much on the actual points of issues of homomorphic schemes. To be more precise, the common issues in homomorphic encryption include:

Inefficiency or Insecurity Obviously, as per the security-efficiency-homomorphism tradeoff, in order to enable homomorphism, it is often necessary to give up some security and/or efficiency. As security can hardly be compromised, most homomorphic schemes trade some efficiency against homomorphic capacities. This is especially true for SHE and FHE.

Public key size A common issue with traditional cryptography: reducing the public key size. This is especially a problem in SHE and FHE, where some schemes have extremely large public keys, up to several GBs.

Ciphertext expansion

The ciphertext expansion is defined as the ratio of the ciphertexts size on the messages size (in bits). During many years cryptographers tried to minimize this ratio in order to save space and bandwidth. Starting from the Goldwasser-Micali cryptosystem [START_REF] Goldwasser | Probabilistic encryption & how to play mental poker keeping secret all partial information[END_REF] in 1982, with a ciphertext expansion of roughly |N | bits (with N similar to a RSA modulus, of e.g. 1024 bits), a ratio arbitrary close to 1 has been achieved by Damgård-Jurik [START_REF] Damgård | A generalisation, a simplification and some applications of paillier's probabilistic public-key system[END_REF] only in 2001. This result comes at the cost of degraded running time performances, and increased messages and ciphertexts sizes (paradoxically). However, many SHE and FHE schemes created afterwards show even worse ciphertext expansions than the Goldwasser-Micali scheme.

Ciphertext size growth Independently from the ciphertext expansion, the ciphertext size growth is defined as the growth of ciphertexts' size when they are applied homomorphic operation. In other words, the ciphertext size growth is the ratio between | Eval(pk, f, c 1 , . . . , c 2 )| and |c i |. This problem mainly rises in SHE schemes, where it is uneasy to enable multiplication on top of addition, and schemes use redundant structures to store information (see section 2.2.6).

Ciphertext noise growth Equivalent of the ciphertext expansion problem of SHE in the FHE context. In a sense, this issue is replaced by the noise growth issue (see section 2.3).

Computation model

The goal of homomorphic encryption is to compute on encrypted data. In this sense, we naturally think of computations in the encrypted domain in the random-access machine (RAM) model, i.e. if possible, we would like to execute RAM programs directly in the encrypted domain. But as we already showed, in practice, much simpler but less powerful models are used. In PHE we mainly use the simple algebraic model because of the limited capacities of the scheme. In SHE and FHE schemes capable of evaluating more complex processes, we use circuits. It is known that any RAM program can be turned into a circuit, yet this comes at a great cost. We discuss the this point in more details in section 2.4.3.

Partially homomorphic schemes

The main idea of this section is to introduce the main existing partially homomorphic schemes, and detail their capacities, performances and security. The aim is not to draw an exhaustive Inria listing, but rather to give an overview of the field and what can be achieved with such schemes. This sections is partially inspired by a 2007 survey on homomorphic cryptography [START_REF] Fontaine | A survey of homomorphic encryption for nonspecialists[END_REF]. The 4 first subsections present the 4 main PHE schemes, along with their derivatives. For each scheme, we briefly describe its functioning and the involved mathematics. We then provide details on its homomorphic capacities, security and efficiency. Non cryptographic-oriented readers may skip the technical parts. All the schemes are summarized in Table 2.1, page 52. The 5th subsection considers PHE schemes under a practical point of view, and the last one briefly presents a few SHE schemes.

Goldwasser-Micali

Created in 1982 by Shafi Goldwasser and Silvio Micali [START_REF] Goldwasser | Probabilistic encryption & how to play mental poker keeping secret all partial information[END_REF], the GM cryptosystem is the first semantically secure public key encryption scheme, and thereby the first semantically secure homomorphic scheme.

To explain this scheme, we need to define the notions of quadratic residue and the Legendre and Jacobi symbols. Very briefly, we say that an integer a is a quadratic residue modulo N if there exist an integer b such that b 2 ≡ a mod N , i.e. such that a is congruent to a square modulo N . If N is prime, a is a quadratic residue modulo N if and only if a (N -1)/2 = 1 mod N , which is easily computable [START_REF] Goldwasser | Probabilistic encryption & how to play mental poker keeping secret all partial information[END_REF]. The Legendre symbol of an integer a with respect to prime number p, noted a p , is equal to: 0 when a ≡ 0 mod p, +1 when a is a quadratic residue modulo p, and -1 when it is not. The Jacobi symbol 3 is defined with the Legendre symbol and its notation is similar: for any integers a and N with N = p 1 p 2 the product of two primes, the Jacobi symbol of a is defined as a N = a p1 a p2 . Note that computing the Jacobi symbol a N is considered easy in general (even when the factorization of N is not known) [START_REF] Goldwasser | Probabilistic encryption & how to play mental poker keeping secret all partial information[END_REF].

The security of the GM scheme is based on the quadratic residuosity problem. The idea is to use the fact that in the special case when a N = +1, it is difficult to known if a is a quadratic residue modulo N or not. Indeed, by definition, for a to be a quadratic residue modulo N , it must be a quadratic residue modulo p 1 and p 2 [START_REF] Goldwasser | Probabilistic encryption & how to play mental poker keeping secret all partial information[END_REF]. Yet, to have a N = +1, we can have a p1

= a p2 = +1 or -1. In the first case, a is indeed a quadratic residue modulo N , in the other it is not. Knowing only a N = +1, and without the factorization of N , it is believed to be hard to distinguish the two cases. Note that with the factorization of N the problem is easy, but factoring is known to be hard for large primes factors. We can now detail the functioning of the scheme: Key generation (pk, sk) ← KeyGen(1 λ ): Pick two large prime numbers p 1 and p 2 , compute The GM scheme is homomorphic for the XOR operation:

N = p 1 p 2 ∈ Z. Pick x ∈ Z * N such that x N = +1
Enc(pk, b 1 ) × Enc(pk, b 2 ) = x b1+b2 .r 2 1 .r 2 2 mod N ∈ Enc(pk, b 1 ⊕ b 2 )
Ciphertexts can be combined this way in an unlimited manner. The homomorphic operation is indeed a XOR, and not a OR, because when b 1 = b 2 = 1, the resulting ciphertexts is

x 2 r 2 1 r 2 2
mod N which is a quadratic residue modulo N , thus it decrypts to 0. GM is also scalar homomorphic

Enc(pk, b 1 ) b2 = x b1.b2 .r 2.b2 mod N ∈ Enc(pk, b 1 .b 2 )
Note however that if b 2 = 0, the resulting ciphertext is equal to 1 and leaks information on b 2 . This can be thwarted using re-randomization: a ciphertext encrypting some message can be turned into another randomly distributed ciphertext that looks like a totally unrelated ciphertext, but that encrypts the same message. For this, given c = x m r 2 mod N , compute c.r 2 = x m (rr ) 2 mod N for a random number r . Re-randomizing requires knowing the public key used to encrypt the ciphertext. This feature is useful in many contexts, for example to avoid the tracing of messages in networks [START_REF] Doerte | Homomorphic Cryptosystems and their Applications[END_REF].

The cryptosystem is semantically secure (i.e. IND-CPA secure) under the assumption that the quadratic residuosity problem modulo a composite number N is intractable, and on the assumption that factorizing such a N is hard. To obtain λ = 80 bits of security, it is widely believed that with |N | = 1024 is sufficient. Finally, note that according to Gjøsteen [START_REF] Gjøsteen | Homomorphic cryptosystems based on subgroup membership problems[END_REF], the security of GM can also be based on the decisional subgroup membership problem. This problem is defined over a group H (the ciphertext space) and two non-trivial subgroups H 1 (the encoded message space) and H 2 (the set of the "cloaking" elements of the encryption) such that H = H 1 × H 2 and H 1 ∩ H 2 = {1}. It consists in deciding if, given an element x ∈ H, it also belongs to H 1 or not. For an appropriate choice of groups, the problem is believed to be hard. GM is actually a special case of the subgroup membership problem, where H is the subgroup of Z * N whose elements have Jacobi symbol +1, and H 1 is the subgroup of H of quadratic residue modulo N . In the same article, Gføsteen actually notes that many homomorphic cyptosystems' security is based on the subgroup membership problem.

ElGamal

Defined three years later by Taher ElGamal [START_REF] Elgamal | A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF], this cryptosystem is one of the most used in practice, after RSA. Note however that it is not always used for its homomorphic property, but merely as a standard, efficient, public key scheme. It is defined as follows:

Key generation (pk, sk) ← KeyGen(1 λ ): Pick an adequate (see below) cyclic group G subgroup of Z * p , of large prime order q (such that q|(p -1)) with generator g. Pick at random x ∈ Z q and compute h = g x ∈ G. Output ((p, q, g, h), x).

Inria

Encryption c ← Enc(pk, m): For m ∈ Z q , pick a random r ∈ Z q . Encode m into an element m of G. Output the pair (g r , m .h r ) ∈ G 2 (values are modulo p).

Decryption m ← Dec(sk, c): Let c = (c 1 , c 2 ). Compute c 2 c x 1 = m h r (g r ) x = m g xr g xr = m mod p Output m, the decoding of m in Z q .
Before exposing the homomorphic properties of ElGamal, we detail the scheme's security and explain why we need to encode messages. First, bear in mind that it would convenient if the message space was M = {0, . . . , n} for some n, as it is often the case in public key cryptography. ElGamal proposed initially [START_REF] Elgamal | A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF], to set M and G to be Z * p for a large prime p: as M = G, we can directly encrypt integers from a set close to our goal, i.e. {1, . . . , p}. However, in this setting, the scheme is insecure [START_REF] Chevallier-Mames | Encoding-free elgamal encryption without random oracles[END_REF]. Indeed the security ElGamal relies on the Decision Diffie-Hellman (DDH) assumption [START_REF] Tsiounis | On the security of elgamal based encryption[END_REF] which states that given g a generator of some commutative group G = g , along with three values g a , g b , h ∈ G for some a, b ∈ Z, it is impossible to know if h = g ab or not. For this assumption to hold, G must be a group of prime order q. This is not the case when G = Z * p because the order of G is (p -1), which is not a prime number when p is prime. Hence, we need to change our choice for G. There are several types of groups in which the DH assumption holds, but typically G is chosen as a small subset of F * p of prime order q, with p a large prime, and q that divides (p -1) (i.e. G is a Schnorr group). Typically, |p| = 1024 bits and |q| = 160 bits. However, if we want to keep the message space close to {0, . . . , n} for some n, it is necessary to encode messages into G, because the scheme operates inside this structure. Also, this encoding must be efficiently invertible so that at the decryption phase, the correct message is decoded. Thus, we set the message space to be Z q . With these settings and parameters, ElGamal, as described above, is proved IND-CPA secure under the DDH assumption.

Finally, as GM, ElGamal's security alternatively relies on a specific case of the subgroup membership problem, where the ciphertext space is H = G × G, H 1 is generated by (g, g x ) with x ∈ Z * q , and H 2 is generated by (1, g) [START_REF] Gjøsteen | Homomorphic cryptosystems based on subgroup membership problems[END_REF]. We now consider homomorphism. Let's first suppose that the message space is actually G. For i ∈ {1, 2}, m i ∈ G and c i = Enc(pk, m i ) = (c i,0 , c i,1 ) = (g ri , m i .h ri ), we have:

c 1 × c 2 = (c 1,0 × c 2,0 , c 1,1 × c 2,1 ) = (g r1+r2 , m 1 .m 2 .h r1+r2 ) ∈ Enc(pk, m 1 .m 2 )
ElGamal is also supports scalar multiplication: if (c 1 , c 2 ) = Enc(pk, m 1 ), then (c 1 , c 2 × m 2 ) encrypts m 1 .m 2 ; homomorphic scalar exponentiation: (c m2 1 , c m2 2 ) encrypts m m2 1 , for any m 2 ∈ Z q ; and re-randomization: (c 1 .g r , c 2 .y r ), with r ∈ Z q a random number, is a randomly distributed ciphertext for the same message as c = (c 1 , c 2 ).

Then, if the encoding from the message space M = Z q to G is an isomorphism, the resulting scheme is homomorphic for these properties stated above, with a message space as desired. For this, we must have Encode(m 1 ). Encode(m 2 ) = Encode(m 1 .m 2 ). However, as noted in [START_REF] Chevallier-Mames | Encoding-free elgamal encryption without random oracles[END_REF], the existence of such an efficient encoding is unclear, and it is most likely that encoding will degrade homomorphism. A solutions is to directly work in M = G, which is suitable in some contexts but not in general, or to use the encoding-free version of ElGamal from Chevalier-Mames et al. [START_REF] Chevallier-Mames | Encoding-free elgamal encryption without random oracles[END_REF]. In this work, the authors slightly modify the scheme to avoid encoding and still ensure IND-CPA security. This scheme's performances are similar to the original ElGamal, but security relies on the Decisional Class Diffie-Hellman problem, which has not been proven equivalent to the DDH problem. Thus, the IND-CPA security of the scheme is conjectured, but not proven (yet).

Another alternative to avoid encoding consists in using the hash-based ElGamal, in which hash messages before encryption. We disregard this solution, as it implies losing all homomorphic properties. Finally, one can also use the additive variant of ElGamal, where the encryption of a message m ∈ Z q is (g r , g m h r ) and no encoding is needed. Multiplying two ciphertexts gives (g r1+r2 , g m1+m2 h r1+r2 ) ∈ Enc(m 1 + m 2 mod q), and decryption requires computing a discrete logarithm, which is computationally impossible in general, but feasible for small message values.

Generally speaking, ElGamal is among the most efficient PHE schemes. We consider the multiplicative variant, without taking encoding in account. As the messages are represented by 1 group element, and the ciphertexts by 2 group elements, the ciphertext expansion is 2, which is much better than GM and quasi-optimal4 . Encryption requires 2 exponentiations and 1 multiplication and its complexity is Õ(|q||p|), as decryption consists in 1 exponentiation and 1 division, computable in time Õ(|q||p|).

Benaloh, Naccache-Stern and Okamoto-Uchiyama

Benaloh's cryptosystem can be seen as an improved generalization of GM to higher residues [START_REF] Benaloh | Dense probabilistic encryption[END_REF]. Designed in 1994, the main goal of the scheme was to create a dense probabilistic cryptosystem, i.e. a scheme with ciphertext expansion as small as possible. We detail the scheme as described by Fousse et al. [START_REF] Fousse | Benaloh's dense probabilistic encryption revisited[END_REF] who provide a corrected version of Benaloh5 : Key generation (pk, sk) ← KeyGen(1 λ ): Choose a block size l ∈ Z, and two large primes p and q, such that:

• l divides (p -1)

• gcd(l, (p -1)/l) = 1

• gcd(l, q -1) = 1

Set N = pq. Pick y ∈ Z * N such that:

• ∀ prime factor r of l, y (p-1)(q-1)/r = 1 mod N Output ((y, l, N ), (p, q)). ,c): Notice that, because we have r (p-1)(q-1) = 1 mod N by Euler's theorem, c (p-1)(q-1)/l = y m(p-1)(q-1)/l r l(p-1)(q-1)/l = y m(p-1)(q-1)/l mod N Because, by construction, y (p-1)(q-1)/l = 1 mod N , if c (p-1)(q-1)/l = 1 mod N , output m = 0. Else, if l is small enough, perform an exhaustive search, i.e. ∀m ∈ Z l , test if y -m c is an encryption of 0. If yes, output m = m .

Encryption c ← Enc(pk, m): For m ∈ Z l , pick a random r ∈ Z * N . Output y m r l mod N ∈ Z * N . Decryption m ← Dec(sk
If l is of moderate size, we can use the baby-step giant-step algorithm to speed up decryption.

If l is larger but has many small prime factors, we can rely on index calculus techniques [START_REF] Fousse | Benaloh's dense probabilistic encryption revisited[END_REF].

Benaloh is additively homomorphic and supports homomorphic scalar multiplication:

Enc(pk, m 1 ) × Enc(pk, m 2 ) = y m1+m2 (r 1 r 2 ) l mod N ∈ Enc(pk, m 1 + m 2 mod l) Enc(pk, m 1 ) m2 = y m1×m2 (r m2 ) l mod N ∈ Enc(pk, m 1 × m 2 mod l)
This scheme is also re-randomizable: for a random number r ∈ Z * N , c = c.r l mod N is a randomly distributed ciphertext for the same message that c encrypts.

Security of the private key is based on factorization, so p and q should be large enough so that |N | ≥ 1024. The scheme is IND-CPA secure, based on the higher residuosity problem, which is similar to the quadratic residue problem: the assumption is that given z, l and N , it is computationally impossible to decide if z is a l th residue modulo N , i.e. it is hard to find x such that x l ≡ z mod N . Once more, according to Gjøsteen [START_REF] Gjøsteen | Homomorphic cryptosystems based on subgroup membership problems[END_REF], this scheme's security can be based on the subgroup membership problem where H = Z * N , H 1 is the cyclic subgroup of order l of H generated by y, and H 2 is the set of invertible l th powers in H.

We can see that there is a balance between security, ciphertext expansion and efficiency. On one hand, the ciphertext expansion is |N |/|l|, which decreases when l increases. On the other hand, encryption (consisting in 2 exponentiations) runs in time Õ(|l||N |) and decryption in time Õ(|l||N | 2 ) for the exhaustive search method, Õ( √ l) for the baby-step giant-step method, and the index-calculus method is in-between. However, in this last method, the parameter l need to be a large smooth factor of (p -1). As l is part of the public key, this provides a hint towards the factorization of N , and endangers the security of the secret key. In definitive, complexity increases but ciphertext expansion decreases with l. [START_REF] Naccache | A new public key cryptosystem based on higher residues[END_REF] (1998) is a derivative of Benaloh and improves upon the basic scheme. The main differences lie in the properties of the values p, q and l and in the definition of the decryption process, which uses the Chinese Remainder theorem. This leads to a less complex decryption, in time Õ(|N | 3 ) (using pre-computations). Thus l can be set higher than in Benaloh, yielding a better ciphertext expansion for similar performances. Security is based on the same assumptions (the higher residuosity problem or alternatively the subgroup membership problem) and homomorphic properties are the same as Benaloh. [START_REF] Okamoto | A new public-key cryptosystem as secure as factoring[END_REF] (1998) can be seen as a improvement of Benaloh. But it is actually very close to Paillier's scheme and lays its foundations The main difference with previous works is that N is defined as p 2 q, for p and q primes of k bits. Messages m are taken modulo p and encrypted by c = g N r+m mod N with g ∈ Z * n and r a random element of Z n . The general ideas behind encryption and decryption are the same in this scheme and in Paillier's (but the parameters and requirements are different). Thus, we defer their description to the section on Paillier's scheme. Ciphertext expansion in Okamoto-Uchiyama is exactly 3: messages are modulo p (thus k bits) and ciphertext are modulo N (thus 3k bits). Security is based on the factorization of N .

Naccache-Stern

Okamoto-Uchiyama

Paillier and derivatives

Designed in 1999 by Pascal Paillier, this scheme is the most known, and maybe the most efficient partially homomorphic encryption scheme. Although Paillier interestingly comes back to a standard RSA modulus N = pq, it is the direct continuation of the work of Okamoto and Uchiyama. In the following description, λ(N ) denotes the Carmichael function (in our case, λ(N ) = lcm(p -1, q -1)), and L N (•) denotes the function defined over the set

S N = {x < N 2 |x = 1 mod N } as L N (x) = (x -1)/N .
Key generation (pk, sk) ← KeyGen(1 λ ): Pick two large primes p and q and compute N = pq. Randomly select g ∈ Z * N 2 such that gcd(L N (g λ(N ) mod N 2 ), N ) = 1. Output ((N, g), (p, q)). Alternatively, the secret key can be λ(N ).

Encryption c ← Enc(pk, m): For m ∈ Z N , pick a random r ∈ Z * N . Output g m r N mod N 2 ∈ Z * N 2 . Decryption m ← Dec(sk, c): Output L N (c λ(N ) mod N 2 ) L N (g λ(N ) mod N 2 )
mod N

Note that L N (g λ(N ) mod N 2 ) can indeed be inverted, as in KeyGen we verified that its gcd with N is 1.

We explain how the decryption works in a few paragraphs. First, note that the scheme is additively homomorphic and scalar multiplicatively homomorphic:

Enc(pk, m 1 ) × Enc(pk, m 2 ) = g m1+m2 (r 1 .r 2 ) N mod N 2 ∈ Enc(pk, m 1 + m 2 mod N ) Enc(pk, m 1 ) m2 = g m1×m2 (r m2 ) N mod N 2 ∈ Enc(pk, m 1 × m 2 mod N )
As the other schemes, Paillier is re-randomizable. For a random number r ∈ Z * N , c.r N mod N 2 looks unrelated to c but encrypts the same message.

The security of Paillier is based on the composite residuosity class problem, which states that deciding whether a number z is a N th residue modulo N 2 , i.e. deciding if there exists y ∈ Z * N 2 such that y N = z mod N 2 , is intractable. Alternatively, we can base security of Paillier on the decisional subgroup membership, where H = Z * n 2 is the ciphertext space, H 1 is the subgroup generated by g, and H 2 is the subgroup of invertible N th powers modulo N 2 .

Paillier, as ElGamal, has a quasi-optimal ciphertext expansion equal to 2. As for performances, encryption requires 2 exponentiations computable in time Õ(|N | 2 ). The most computationally expensive task in decryption is the exponentiation c λ(N ) mod N 2 , computable in time Õ(|N | 2 ). The value L N (g λ(N ) mod N 2 ) -1 mod N can be pre-computed once and for all at the key generation. Those asymptotic complexities are comparable to previous works, but the scheme is sensibly better in practice. Now, to understand how the decryption works, we first describe the case when the generator g is 1 + N , which is the typical choice in most implementations (it is easy to check that 1 + N is a suitable candidate for g in the KeyGen procedure). In this case because of Carmichael's theorem Inria stating that for all x, x N.λ(N ) = 1 mod N 2 , we have for any c = (1 + N ) m r N mod N 2 :

c λ(N ) = (1 + N ) mλ(N ) r N λ(N ) = (1 + N ) mλ(N ) = 1 + mλ(N ) 1 N + mλ(N ) 2 N 2 + . . . = 1 + mλ(N ).N mod N 2
Now, applying L N on c λ(N ) mod N 2 yields mλ(N ). Computing L N ((1 + N ) λ(N ) mod N 2 ) in the same way leads to λ(N ), therefore the decryption procedure outputs mλ(N ) λ(N ) = m mod N . In the general case, when g = 1 + N , the decryption procedure is also correct. Indeed, as all suitable g in the KeyGen procedure (including 1 + N ) are generators of the subgroup of Z * N 2 we denoted H 1 earlier, they are all interchangeable. Thus, for any ciphertext c = g m .r N ∈ Z * N 2 there is a unique pair (m , r ) such that c = (1 + N ) m r N mod N 2 . And in particular, ∃x, N s+1 . Also, the parameter g is simply set to 1 + N , reducing the public key size without endangering security. We can see that, if s = 1 this yields Paillier's cryptosystem, and when s increases, the ciphertext expansion s+1 s gets closer to 1. This is the main achievement of DJ: to offer an expansion arbitrary close to 1. However, the cost is a quadratic overhead in s: the encryption and decryption costs are respectively at least s 2 and s times Paillier's complexity. As a result, it is actually more efficient to use Paillier k times than DJ with s = k. The authors show that the security of their scheme is equivalent to Paillier's security. In the same paper, Damgård and Jurik describe a threshold version of Paillier, and detail an application to electronic voting.

y ∈ Z * N s.t. g = (1 + N ) x y N mod N 2 . Thus c = g m r N = ((1 + N ) x ) m .(y m r) N mod N 2 ,
Galbraith [START_REF] Steven | Elliptic curve paillier schemes[END_REF] (2002) transposes Paillier and DJ in the elliptic curves setting. The scheme is however less efficient: expansion is equal to 3, and encryption and decryption are slower than Paillier's, but the exact comparison of the schemes is unclear [START_REF] Fontaine | A survey of homomorphic encryption for nonspecialists[END_REF]. The scheme works over the group defined by the elliptic curve E(Z N 2 ). In this context, we have as public parameters N = pq and the description of the elliptic curves (i.e. its coefficients). The secret key is a value derived from the factorization of N , noted d = lcm(#E(F p ), #E(F q )). The public key also contains a point Q, such that the order of Q is a divisor of d, i.e. such that dQ = 0 in E(Z N 2 ). To encrypt m ∈ Z N , choose a random r ∈ Z * N and output the point S = rQ + (mN : 1 : 0). Homomorphic addition of messages is performed by point addition. Decryption is done by multiplying S with the secret value d: dS = r(dQ) + (mdN : 1 : 0) = (mdN : 1 : 0). Knowing d and N , it is easy to recover m using the first coordinate of the result. In Rappe's thesis, a threshold version of Galbraith's cryptosystem can be found [START_REF] Doerte | Homomorphic Cryptosystems and their Applications[END_REF]. This paragraph closes the presentation of PHE schemes. This list is not meant to be exhaustive, but merely presents the main PHE schemes and put in light their evolution. We could have also mentioned the scheme of Castagnos [START_REF] Castagnos | Quelques schémas de cryptographie asymétrique probabiliste[END_REF], the Paillier-ElGamal amalgam [START_REF] Damgård | A length-flexible threshold cryptosystem with applications[END_REF], or the Regev [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF] and LPR [START_REF] Lyubashevsky | On ideal lattices and learning with errors over rings[END_REF] schemes. The last two schemes are actually the foundations of some recent FHE schemes and will be given more attention in section 2.3.5. All the presented schemes are summed up in Table 2.1. We detail homomorphic capacities (except rerandomization, which is a common feature to all PHE schemes), ciphertext expansion, complexity of encryption and decryption, and parameters size for a 128-bit security.

Scheme

Implementations and practical considerations

In conclusion of this section on PHE schemes, we discuss the most practical PHE schemes, and present known implementations. In practice the main schemes used by the cryptographic community or in cryptographic libraries are either ElGamal, Paillier (and its generalization), and Okamoto-Uchiyama. To the best of our knowledge, other schemes' implementations (if they exist) are merely academic proof of concepts.

ElGamal is a serious alternative to RSA, and is actually used in many standards, for instance in GPG (Gnu Privacy Guard, an implementation of the PGP protocol). However, this scheme is not used in its homomorphic form. Instead, its hash-based variant is used, so as to provide IND-CCA2 security (a higher security than IND-CPA, desirable in general). Thus, ElGamal's usage seems to be restricted to traditional cryptography, and it is unclear why its homomorphic version has been disregarded. It may be partially explained by the necessary message encoding, that either makes the scheme inefficient or harms homomorphism. In the same order of idea, Inria the scheme of Okamoto and Uchiyama was used to design EPOC, a cryptosystem standardized by IEEE (IEEE P1363, submitted in 2000), but here again the scheme is in a IND-CCA2, nonhomomorphic variant, thus of little interest to us.

In definitive, only Paillier and Damgård-Jurik are actually used for their homomorphic properties. The main applications of Paillier include electronic voting [START_REF] Steffen | E-voting simulator based on the paillier cryptosystem[END_REF] and private information retrieval [START_REF] Chang | Single database private information retrieval with logarithmic communication[END_REF]. There exists many implementation of Paillier, in Java6 , Python7 or in C8,9 . However, according to the authors themselves, these implementations should not be used to perform sensible computations, as their code have not been studied and secured. Therefore, in practice, even Paillier and its derivatives are still academic objects, and no standard implementation has been issued as of today.

We still report running times for the C implementation of Paillier by John Bethencourt. Tests were run on a Intel i7 2.20GHz. Timings are reported in Table 2 In a parallel work, Jakobsen et al. [JMN10, Section 5.3] construct an efficient version of Paillier and measure their performances in terms of CPU cycles for the encryption primitive. In particular, for |N | = 2048, the number of CPU cycles for encryption is around 2 25 , which approximately corresponds to a time of 16ms on a 2GHz single core CPU, and is in accordance with our own measurements. Note that the measured running times are above what could be expected. This is mainly due to the simple and unoptimized implementations used. Also, surprisingly, encryption takes more time than decryption. This can be explained by the precomputation of λ(N ) and L N (g λ(N ) mod N ) -1 in KeyGen instead of Dec. Also, this last fact is in accordance with Damgård and Jurik's estimations [DJ01, Fig. 1], which show that the number of multiplications in Paillier's encryption is |N |/2 times more than in RSA's.

Although it would be desirable to also measure Paillier's performances in a simple use-case such as electronic voting, there is actually very few tests that were run, or at least, the results were not published. There exist an interactive demonstration of electronic voting with Paillier10 , but it runs on Javascript (which has very poor performances), and only works for very small modulus size |N | that do not represent real world settings. This demonstration is however useful to understand a concrete example of e-voting with Paillier.

At last, note that the practical applications of PHE schemes in general are numerous: electronic voting, secure multi-party computation, private information retrieval, oblivious transfer, (non-interactive) knowledge proofs, secret sharing, commitment schemes, e-auctions, ... Many of these applications can be found in Rappe's thesis [START_REF] Doerte | Homomorphic Cryptosystems and their Applications[END_REF].

Somewhat homomorphic schemes

As mentioned before, SHE schemes are of little interest. Therefore we do not dedicate an section to them, but briefly present the most known schemes in the literature.

The first construction allowing to compute on encrypted data in an non-interactive manner dates from 1999 [START_REF] Sander | Non-interactive cryptocomputing for nc1[END_REF]. It was designed to evaluate N C 1 circuits (i.e. circuits of logarithmic depth and gates fan-in 11 2): one party, Alice, possesses an input x, and the other, Bob, has a circuit C. Both parties want to keep their input secrets, but should learn iC(x) at the end. Though it is not a SHE scheme per se, this construction allows computation of several OR and NOT gates. As the set of logical gates {N OT, OR} provides functional completeness, we can theoretically evaluate any function. However, the limitation comes from the huge ciphertext size growth: for a depth d circuit, ciphertexts' size at output is O(8 d ). This is why the construction can only evaluate logarithmic depth circuits, i.e. in order to obtain polynomial time running times, one ought to limit the circuit's depth to O(log |inputs|).

A second construction have been proposed by Ishai and Paskin in 2007 [START_REF] Ishai | Evaluating branching programs on encrypted data[END_REF]. The main difference with the previous construction is that this work relies on branching programs (BP) instead of circuits. Barrington proved that a branching programs include N C 1 circuits [Bar89], thus this construction is slightly better than the previous one. This work allows the evaluation of a branching program BP owned by Bob on Alice's secret input x. The idea can be summed up as follows: to encrypt x, Alice encrypts each of its bits by generating |x| Oblivious Transfer requests, and sends them all at once to Bob. Bob recursively generate Oblivious Transfers answers in a bottom-up manner, and sends to Alice the answer associated to the branching program's initial node. Alice then recursively decodes the Oblivious Transfer answers and eventually recovers the branching program output corresponding to x. Ciphertexts size are polynomial in the BP length (i.e. the longest path in the branching program). Alice's workload is also polynomial in length(BP ), but Bob's workload depends polynomially on the size (i.e. number of nodes) of the program. However, as a N C 1 circuit of depth O(log n) is equivalent to a branching program of length O(n), we did not make much progress and the scheme is limited to evaluating polynomial size branching programs (with gates fan-in possibly above 2), or equivalently, logarithmic depth N C 1 circuits (with gates fan-in equal to 2, by definition).

One of the most known SHE scheme, though not used in practice, is BGN (for Boneh-Goh-Nissim). It was designed in 2005 [START_REF] Boneh | Evaluating 2-dnf formulas on ciphertexts[END_REF], and improved by Gentry et al. in 2010 [START_REF] Gentry | A simple bgn-type cryptosystem from lwe[END_REF]. The homomorphic properties of this scheme are quite odd: it allows unlimited additions and 1 multiplication. As the title of the original article suggests, this corresponds to evaluation of multi-variate polynomials of degree 2. Actually, BNG is simply an additive homomorphic scheme where ciphertexts lie in a multiplicative group in the manner of Paillier. To enable 1 multiplication, the idea of Boneh et al. is to use a bilinear application. The security is directly based on the subgroup membership problem. The main limitation of this scheme is the size of the plaintexts space: the scheme allows encryption of small values up to a bound T . Indeed, the decryption operation depends polynomially on T , limiting its value. There is no ciphertext size growth (contrarily to other SHE schemes), but ciphertext expansion is quite large: |N |/|T | with T ≈ log N . In Gentry's improvement [START_REF] Gentry | A simple bgn-type cryptosystem from lwe[END_REF], the homomorphic capacities stay the same, but the plaintext space is larger, the encryption/decryption complexities are lower, and the ciphertext expansion is also lower. The scheme actually uses matrices and is well suited to encrypt polynomials or large integers. This scheme is also the first SHE scheme which security is based on the LWE problem (see section 2.3.5).

We close our short SHE schemes list with the MGH cryptosystem [START_REF] Aguilar Melchor | Additively homomorphic encryption with d-operand multiplications[END_REF], the most recent but also the most powerful one. Indeed, it allows many additions and several multiplications, or equivalently it evaluates multivariate polynomials of degree d, which corresponds to circuits of depth log d. The scheme is limited because of the exponential ciphertexts growth in d. However, as the growth is slower than Sander et al. [START_REF] Sander | Non-interactive cryptocomputing for nc1[END_REF] and Ishai et al. [START_REF] Ishai | Evaluating branching programs on encrypted data[END_REF], more multiplications are possible in practice. The main idea is to use a simple additive homomorphic encryption scheme (satisfying some reasonable properties), along with a tensorial product technique in order to enable multiplications. In a sense, multiplication of encrypted messages corresponds to the tensorial product of their ciphertexts. The resulting ciphertext then contains redundant data, and its size is quadratic (i.e. if |c| = n, |c ⊗ c| = n 2 ). The workload at decryption depends exponentially on d (the degree of the evaluated polynomial). Their construction is actually a general template to transform any additive scheme into a SHE scheme by chaining it multiple times with itself. The authors argue that their template fits very well with the BNG transformation of Gentry et al., allowing unlimited additions and 2d multiplications for the same price.

To sum up, SHE schemes all allow many additions and either a very limited number of multiplications (with no ciphertext size growth), either several multiplications but at the cost of an exponential ciphertext growth. Moreover, none of these schemes is efficient, and their security may be somewhat hazardous. Therefore, we disregard these schemes in the rest of the chapter.

Fully homomorphic schemes

As we have seen so far, cryptographers have been searching for a way to compute arbitrary functions on encrypted data for more than 30 years. Early 2000s, homomorphic encryption has made a lot of progress, and eventually, in 2009, the groundbreaking work of Gentry in his thesis [START_REF] Gentry | A Fully Homomorphic Encryption Scheme[END_REF] gave rise to the first (theoretically) fully homomorphic encryption scheme. This type of scheme is capable of evaluating any program that would be executable in the clear. This section is dedicated to the description of techniques and schemes derived from Gentry's construction, starting from 2009 until early 2014.

First, we describe the emergence of FHE schemes and the idea developed by Gentry. We then detail the main existing schemes, dividing them according to their underlying cryptographic concepts. At last, we consider FHE from a practical point of view.

Overview of FHE

Outbreak of FHE and Gentry's idea

Before Gentry's thesis, even theoretically, FHE was believed impossible to achieve. In 2009, it became a tangible possibility, although it was at the time extremely far from practical (and still today, to some extent). Two main ideas were crucial for the apparition of FHE: the suppression of the ciphertext size growth, and the bootstrapping technique.

The starting point of Gentry is a powerful somewhat homomorphic scheme capable of evaluating a small (but reasonable) number of additions and multiplications, i.e. a few AND and XOR logical gates. However, contrarily to other SHE schemes, the ciphertexts from Gentry's scheme no longer suffered size growth when they were applied homomorphic operations. In other words, Gentry solved the problem of the compactness: the size of the output of the Eval primitive no longer depended on the complexity of the evaluated function or the number of inputs. However, this gave rise to a new problem, inherent to Gentry's SHE scheme: the noise growth. For security reasons, ciphertexts in Gentry's scheme contained some randomness (as all semantically secure schemes), and this randomness was added and multiplied along with plaintexts during homomorphic operations. This is what Gentry called the noise. When the noise (i.e. the accumulated randomness) exceeded a certain threshold (typically, a modulo), decryption would output erroneous values, i.e. the scheme would no longer be correct. To sum up, Gentry's ciphertexts were of fixed size, but in their inner structure, the noise was growing exponentially, in such a way that after a few operations, decryption was erroneous.

To circumvent this issue, the trick proposed by Gentry was to refresh ciphertext when the noise became too large. Indeed, as freshly encrypted ciphertext had very low noise level, Gentry proposed to decrypt and immediately re-encrypt noisy ciphertexts, so as to reset their noise. As a result, to evaluate a complex function on encrypted data, an evaluator would need to decryptthen-re-encrypt data every time the noise reached a critical level. The issue was however that this seemed to imply giving away the secret decryption key for third parties to be able to compute on encrypted data, which is unacceptable. The workaround imagined by Gentry was to perform the decrypt-then-re-encrypt operation in the encrypted domain. This means homomorphically decrypting ciphertexts when their noise became too large, so as to reset it. Gentry called this idea bootstrapping, because it implies the SHE scheme to be able to evaluate its own decryption circuit. This decrypt-then-re-encrypt procedure is called Recrypt, and is the key to create a FHE scheme. Note that, in practice this procedure begins by re-encrypting and then decrypts, for obvious security reasons. We describe it here in an abstract manner.

Recrypt c clear ← Recrypt(pk, f Dec , Enc(pk, sk) , c noisy ): Takes as input the public key, the function describing the scheme's own decryption primitive, the secret key sk encrypted under its corresponding public key, and a noisy ciphertext c noisy ∈ Enc(pk, m). Performs the following operations:

1. Generates c = Enc(pk, c noisy ). c can be seen as a doubly encrypted ciphertext.

2.

Outputs Eval(pk, f Dec , Enc(pk, sk), c ).

If the SHE scheme can correctly evaluate f Dec , i.e if f Dec ∈ F, the result is a valid ciphertext of m encrypted under pk, with low noise. The Recrypt primitive is meant to be run by any third party that needs to compute on the encrypted data. The basic idea is for the evaluator, who only knows the public key and a circuit she wants to evaluate, to apply logical gates of the circuit one by one, and use the Recrypt primitive between each gate. Note that the Recrypt primitive takes as input the secret key encrypted under its own public key. This means that the value Enc(pk, sk) must be public. This value is sometimes called evaluation key, and may be part or distinct from the public key. Publicizing the evaluation key may be harmful for the scheme's security. Actually, there is no proof (at the moment) that it does not. Gentry merely made the assumption that it was not harmful. This (strong) assumption is called circular assumption.

We now have all the elements to formulate Gentry's bootstrapping theorem, central in his work.

Theorem 1 -Bootstrapping [Gen09a] (Informal) A SHE scheme capable of evaluating its own decryption primitive, plus at least one non-negligible operation, can be transformed into a FHE scheme under the circular security assumption.

We presented the main ideas that gave rise to the first FHE scheme. We sum them up in the following description of what is now called Gentry's blueprint, or Gentry's procedure to construct FHE schemes (we provide a simplified version of it). Note that this procedure uses a computational model based on circuits instead of programs or functions: because designing a FHE scheme is very complex, we resort to a very simple computational model.

Definition 1 -Gentry's blueprint 1. Construct a SHE scheme capable of evaluating a few AND and XOR gates.

Inria

Express the decryption primitive under the form of a circuit, and simplify (Gentry uses

the term "squash") the decryption circuit so that the SHE scheme is capable of evaluating its own decryption circuit plus an additional AND gate.

3.

Make the circular security assumption, and use the bootstrapping theorem to turn the scheme into a FHE one.

This procedure is, still today, the only known way to achieve fully homomorphic encryption. Gentry details how to apply this blueprint to the scheme of van Dijk et al., making the parallel between FHE and a jewelery store owner delegating tasks to untrusted workers [START_REF] Gentry | Computing arbitrary functions of encrypted data[END_REF].

A more recent paradigm: Leveled FHE Gentry's initial procedure presents several strong shortcomings, and although it is the only way to achieve pure FHE, many modern schemes deviate from it. Therefore, they are no longer actually fully homomorphic schemes, but we will see that they offer consequent homomorphic capacities and far better performances. This section explains why and how recent FHE schemes deviate from Gentry's blueprint.

The first shortcoming of Gentry's blueprint is its (in)security. Indeed, the circular assumption has not been extensively studied yet, and when simplifying the decryption circuit, one may need to make additional strong assumptions. For instance, in his thesis, Gentry simplifies the decryption procedure by publicizing a hint on the secret key, so as to offload decryption work to KeyGen (see section 2.3.3). Secondly, the Recrypt primitive is extremely costly. In the first schemes, its complexity was Ω(λ 4 ), with λ the security parameter, and it was called after each circuit gate evaluation.

In view of these remarks, there are two possibilities: to directly address these shortcomings, or simply to disregard bootstrapping. Works following the first possibility allowed to reduce the asymptotic cost of bootstrapping to Õ(λ. log λ) [START_REF] Alperin | Practical bootstrapping in quasilinear time[END_REF][START_REF] Alperin | Faster bootstrapping with polynomial error[END_REF], to remove some assumptions [START_REF] Gentry | Fully homomorphic encryption without squashing using depth-3 arithmetic circuits[END_REF], and to reduce the number of calls to Recrypt during the homomorphic evaluation of a circuit (i.e. avoid using it systematically at each gate) [START_REF] Lepoint | On the minimal number of bootstrappings in homomorphic circuits[END_REF]. However, even with these advances, bootstrapping remains very costly in practice. This is why the second solution, which propose not to use bootstrapping at all, actually prevails today. Although the resulting schemes are not strictly speaking fully homomorphic ones, they offer substantial capacities, and are far less costly. The first scheme without bootstrapping was introduced by Brakerski, Gentry and Vaikuntanathan in 2012 [START_REF] Brakerski | leveled) fully homomorphic encryption without bootstrapping[END_REF], and represents a major milestone in the evolution of FHE: since then, this has been the favored approach by the community. The authors named this kind of FHE schemes leveled fully homomorphic encryption (LHE):

Definition 2 -Leveled Fully Homomorphic Encryption

A HE scheme is said leveled if it can evaluate circuits of polynomial size and depth at most L, with L a parameter of the scheme.

Understand that L can be set arbitrarily high, thus LHE schemes are also (theoretically) capable of evaluating any function on encrypted data. Of course, the complexity of the scheme increases with L. To better understand the notion of LHE, we detail its differences with SHE and FHE: Somewhat vs. Leveled. In SHE schemes, the homomorphic capacities are not clearly defined, i.e. we do not have precise bounds on the complexity of the functions they can evaluate. In most cases, the multiplicative depth of evaluable circuits is logarithmic (in size of the inputs). On the other hand, LHE schemes can evaluate circuits of linear multiplicative-depth, this depth can be exactly controlled with the parameter L, and correctness is guaranteed for circuits of depth lower or equal to L. At last, ciphertext size growth is often exponential in SHE, while it is null In definitive, research in FHE can be divided in two main (complementary) directions: improving bootstrapping and pure FHE, or improving LHE. The two directions follow the same goal, i.e. to manage and minimize the ciphertext noise growth efficiently. Pure FHE manages noise via bootstrapping, but LHE has to find other ways to keep noise at a low level, at least until the depth L is reached. Thus, research in LHE focuses on inventing and improving techniques, such as tensoring [START_REF] Brakerski | leveled) fully homomorphic encryption without bootstrapping[END_REF], modulus switching [START_REF] Brakerski | leveled) fully homomorphic encryption without bootstrapping[END_REF], key switching (also called re-linearization) [START_REF] Brakerski | leveled) fully homomorphic encryption without bootstrapping[END_REF][START_REF] Brakerski | Fully homomorphic encryption without modulus switching from classical gapsvp[END_REF], packing (or batching) of many plaintexts in 1 ciphertext [START_REF] Smart | Fully homomorphic encryption with relatively small key and ciphertext sizes[END_REF][START_REF] Brakerski | leveled) fully homomorphic encryption without bootstrapping[END_REF], and scale invariance [START_REF] Brakerski | Fully homomorphic encryption without modulus switching from classical gapsvp[END_REF] (which actually replace the costly technique of modulus switching).

In the rest of this section, the generic term FHE refers to both pure FHE and LHE.

Three different types of FHE schemes

We borrow the categorization from Note that in the rest of this work, we present public key FHE schemes, but most schemes can be either symmetric or asymmetric. Actually, there exist a generic transformation from symmetric to asymmetric FHE [START_REF] Rothblum | Homomorphic encryption: From private-key to public-key[END_REF]. Also, bear in mind that, unless specified otherwise, all FHE schemes are meant to encrypt only bits, i.e. the message space is {0, 1}, and to evaluate circuits.

Schemes over ideal lattices

The first FHE schemes were based on ideal lattices [Gen09a, Gen09b, SV10, SS10, GH11b, GH11a], and involved complex mathematical and cryptographic notions. In a nutshell, a lattice L is a discrete subgroup of R n , often taken on Z n . A lattice is generated by a basis

B = (b 1 , . . . , b n ) ∈ Z n×n composed of n linearly independent vectors, i.e. L = n i=1 a i b i |a i ∈ Z . An
ideal of some ring R is defined as the set I ⊂ R such that ∀a ∈ I, ∀b ∈ R, a × b ∈ I, i.e. I absorbs multiplication by elements of R. An ideal lattice IL of the lattice L described above is thus an ideal of the ring R = Z[X]/f (X) (the set of polynomials over Z modulo an irreducible polynomial f (X) ∈ Z[X]). Indeed, the set Z[X]/f (X), with f (X) a polynomial of degree n, is isomorphic to the set Z n , which is the support of L.

Schemes based on these tools are in limited number, of very limited practical use, and none of them is LHE (i.e. they all use bootstrapping). Their theoretical complexity is huge, and in practice, running times of their primitives are far beyond reasonable. We still describe the characteristics of the scheme of Gentry as it appears in [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF].

The structure of ideal lattices seemed well suited as a first candidate for FHE, because they naturally provide additive and multiplicative homomorphism. Also, schemes in ideal lattices typically have low complexity decryption functions, e.g. logarithmic in the size of the lattice [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF], which is convenient to enable bootstrapping. Gentry's first scheme's security was based on the (decisional) closest vector problem (CVP) for ideal lattices, which consists, given a lattice L, a vector space V and a vector v ∈ V not in the lattice, in finding v ∈ L the vector in L closest to v up to an approximation factor γ. That is, finding v such that ||v || ≤ γ.||v exact || with v exact the actual closest vector to v in L. The building block SHE scheme was, according to Gentry, slightly better than the SHE scheme BGN [START_REF] Boneh | Evaluating 2-dnf formulas on ciphertexts[END_REF], i.e. it allowed unlimited additions and more than one multiplication for comparable efficiency. However, the original decryption primitive consisting in a matrix-vector product, it could not be evaluated by the scheme as is. In order to simplify the decryption circuit and enable bootstrapping, the scheme was modified to publish a set of vectors at key generation. This set contained a secret subset which sum was roughly equal to the secret key. As a result, the simplified decryption circuit simply consisted in a sparse subset sum plus some other minor operations, and could be evaluated by the scheme. The hardness assumption invoked to prove the security of the modified scheme is the sparse subset sum (SSS) problem, which states that it is impossible to distinguish a random set of elements from a set of elements for which the sum of a secret subset is equal to 0. The hardness assumptions of SSS and SVP are strong ones, and need to be further studied. Thus, although the security of the scheme was proved, it relies on strong assumptions. The per-gate overhead (i.e. the additional cost of homomorphic gate evaluation) of this scheme is roughly Õ(λ 6 ) [SS10], a cost mainly explainable by the need for ciphertext refreshing at each gate.

Two main contributions tried to improve upon this scheme. Stehlé and Steinfield obtained a per-gate overhead of Õ(λ 3.5 ) by providing a more precise analysis of the SSS problem yielding smaller parameters, and by allowing negligible but non-zero decryption error. The second work, by Gentry an Halevi [START_REF] Gentry | Fully homomorphic encryption without squashing using depth-3 arithmetic circuits[END_REF], marks the first deviation from the blueprint: it still uses bootstrapping, but it does not need to simplify the decryption circuit, and thus removes of the SSS assumption. To do so, they express the decryption function of their basic SHE scheme as a sequence composed of: a series of additions, then a series of multiplications, and another series of additions. The series of additions are performed by the SHE scheme, as the multiplications are done by switching to a multiplicative PHE scheme such as ElGamal. This involves homomorphically evaluating ElGamal's decryption function to switch back to the SHE. Eventually, they obtain a scheme as complex as the original one, they also use bootstrapping, but avoid the strong SSS assumption and achieve better security.

Schemes over the integers

As soon as 2010, van Dijk et al. decided to transpose Gentry's FHE scheme to plain integers [START_REF] Van Dijk | Fully homomorphic encryption over the integers[END_REF], a much less complex tool to work with compared to ideal lattices. Drafts of these schemes were previously proposed prior to 2009 as SHE candidates, but van Dijk et al. formalized it, improved it, and integrated it within Gentry's blueprint to create a FHE scheme. Along the years, more integers-based schemes were designed [CMNT11, CNT12, CCK + 13, CLT14], mostly adapting the new techniques borrowed from the (R-)LWE to the integer settings, an operation which is often non-trivial. Some new techniques also emerged from integer-based schemes, such as the public key compression techniques [START_REF] Coron | Public key compression and modulus switching for fully homomorphic encryption over the integers[END_REF]. As the authors note, the main appeal of the integer approach is its conceptual simplicity.

Concerning efficiency, integer-based schemes perform equivalently or even worse than their ideal lattice counterparts. Similarly to Gentry's original scheme which security is based on approximation problems in ideal lattices, schemes on the integers are based on the approximate GCD problem. This problem asks to find p given many x i = p.q i + r i ≈ p.q i for q i large integers, r i small values (compared to q i ), and p an odd integer. Note that this assumption is still being studied and new attacks have recently been disclosed [START_REF] Chen | Faster algorithms for approximate common divisors: Breaking fully-homomorphic-encryption challenges over the integers[END_REF][START_REF] Coron | Public key compression and modulus switching for fully homomorphic encryption over the integers[END_REF].

As the 2010 scheme from van Dijk et al. is one of the simplest, we describe it here. More exactly, we describe the SHE scheme that constitutes the building block of the FHE one. Note: in the following, the value x mod y lies in (-y/2, y/2], and not in [0, y).

Setup params ← Setup(1 λ ): Set ρ = ω(log λ) the bit-length of the noise (high enough to protect against brute-force attack on the noise) ; η ≥ ρ.Θ(λ. log 2 λ) the bit-length of the secret key (high enough to support homomorphism and evaluate the simplified decryption circuit) ; γ = ω(η 2 log λ) the bit-length of the integers in the public key (high enough to thwart attacks on the approximate GCD problem) ; and τ ≥ γ + ω(log λ) the number of integers in the public key (high enough for the security proof to hold). Let D γ,ρ (p) be the distribution outputting

x i = pq i + r i for q i ∈ {0, . . . , 2 γ /p } and r i ∈ { -2 ρ , . . . , 2 ρ }. Output params = (ρ, η, γ, τ, D γ,ρ (p)).
Key generation (pk, sk) ← KeyGen(params): Pick a large η-bit prime p ∈ {2 η-1 , . . . , 2 η -1}. Sample τ + 1 values x i from D γ,ρ (p) and relabel then so that x 0 is the largest.

Inria

Restart unless x 0 is odd and (x 0 mod p) is even. Output ((x 0 , . . . , x τ ), p).

Encryption c ← Enc(pk, m): For m ∈ {0, 1}, pick a random r ∈ {-2 2ρ + 1, . . . , 2 2ρ -1}, and a random subset S ⊆ {1, . . . , τ }.

Output c = m + 2r + 2 i∈S x i mod x 0 . Decryption m ← Dec(sk, c): Output c p 2 = m + 2r + 2 i∈S x i mod x 0 p 2 = m + 2r + 2 i∈S x i -(p.q 0 + r 0 ). c/x 0 p 2 = m+2r+2(p i∈S qi+ i∈S ri)-(p.q0+r0). c/x0 p 2 = m + 2r + pq p 2 = m if r < p/4
Noting that ciphertexts have the form Enc(pk, m) = m + 2r + pq , we can see that

c 1 + c 2 = m 1 + m 2 + 2(r 1 + r 2 ) + p(q 1 + q 2 ) ∈ Enc(pk, m 1 + m 2 mod 2)
The addition of two ciphertexts gives an encryption of the addition of their underlying plaintexts, with noise bit-length 2ρ + 1 (assuming c 1 and c 2 are freshly encrypted ciphertext with noise bitlength roughly equal to |r | = 2ρ) 12 . In the same way, we have

c 1 × c 2 = m 1 .m 2 + 2(r 1 .m 2 + r 2 .m 1 + 2r 1 .r 2 ) + p(q 1 m 2 + q 2 m 1 + pq 1 q 2 + 2r 2 q 1 + 2r 1 q 2 ) = m 1 .m 2 + 2r + pq ∈ Enc(pk, m 1 .m 2 mod 2)
If c 1 and c 2 are fresh ciphertexts, the resulting ciphertext has a noise bit-length roughly 2 × 2ρ + 2. After l multiplications, the noise bit-length is approximately 2 l .2ρ: the noise grows exponentially with the number of multiplications applied. As for the decryption to be correct, the noise must remain smaller than the half of the modulo p, i.e. 2 l .2ρ < |p/4| ≤ η -2, the scheme roughly allows l = log η/ρ multiplications. In other words, the bit size of p is exponential in l, which imposes a strong limitation of l to small values. Note that this scheme is not leveled homomorphic, and the aim is only to be able to evaluate the decryption circuit (and one additional operation).

For the proposed parameters [vDGHV10] ρ = λ, η ≈ λ 2 , γ ≈ λ 5 and τ = γ + λ, the public key size is above Õ(λ 10 ) (because the public key is composed of (τ + 1) γ-bit values). This results in 10 6 TB for λ = 80, which is above any practical system. Approximately l = log(η/ρ) = log λ successive multiplications are possible, which is barely enough to evaluate the decryption circuit. To simplify the decryption circuit, which in its original form asks for a computation of c/p , the authors augment the public and secret keys so that the decryption can be computed with only additions and subtractions. Finally, note that the ciphertext expansion is approximately |x 0 |/1 = γ ≈ λ 5 , which is enormous.

Several works improve upon this first integer-based scheme. In 2011 Coron et al. [START_REF] Coron | Fully homomorphic encryption over the integers with shorter public keys[END_REF] reduce the public key size from Õ(λ 10 ) to Õ(λ 7 ), by encrypting using a quadratic (instead of linear) form in the x i values, thus yielding a scheme asymptotically comparable to ideal latticebased schemes. In 2012, Coron et al. [START_REF] Coron | Public key compression and modulus switching for fully homomorphic encryption over the integers[END_REF] again reduce the public key size, to Õ(λ 5 ) using higher degree in the x i values, and import the modulus switching technique from [START_REF] Brakerski | leveled) fully homomorphic encryption without bootstrapping[END_REF] to the integer setting, yielding a LHE scheme on the integers (the first one). From 2012 and after, all integer-based schemes are LHE ones. A year later, Cheon et al. [CCK + 13] import the ciphertext batching/packing technique from [SV10, BGV12] using the Chinese Remainder Theorem. With this technique, one ciphertext can now encrypt Õ(λ 2 ) plaintexts at a time, and the ciphertext expansion is lowered from Õ(λ 5 ) in the original scheme to Õ(λ 3 ). Finally, in 2014, Coron et al. [START_REF] Coron | Scale-invariant fully homomorphic encryption over the integers[END_REF] integrate the scale invariant property of Brakerski [START_REF] Brakerski | Fully homomorphic encryption without modulus switching from classical gapsvp[END_REF], allowing |p| = η to be linear in the parameter L of the LHE scheme, instead of exponential. This means that exponentially more multiplications are possible with the same p compared to the 2010 scheme.

Schemes based on the (R-)LWE problem

The third type of FHE schemes are the ones based on the LWE and Ring-LWE problems [BV11a, BV11b, BGV12, GHS12a, Bra12, FV12, BLLN13, GSW13, BV14, ASP14]. The (R-)LWE branch of FHE is the most active one, and these schemes are the most efficient ones to date. Except for the two 2011 schemes, all the schemes from this branch are LHE ones, but can be made fully homomorphic using bootstrapping. In general, leveled schemes are quite efficient, but using bootstrapping lowers their efficiency to a level comparable to ideal lattice-based schemes. In this section, we will present the LWE problem and Brakerski's scheme [START_REF] Brakerski | Fully homomorphic encryption without modulus switching from classical gapsvp[END_REF]. Then, to put in light the security-efficiency-homomorphism trade-off in modern fully HE schemes, we briefly show how to derive concrete parameters for Brakerski's scheme. Finally, we give the differences between LWE and Ring-LWE, and sump up recent advances in FHE.

The Learning With Error problem

The Learning With Errors (LWE) problem was put forward in 2005 by Regev [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]. It comprises 3 parameters: the dimension n, the modulus q, and the error factor α. The last two often depend on n, which is the main parameter.

In the rest of the section, we denote U(S) the uniform distribution over some set S. N s denotes a discrete Gaussian distribution on Z centered in 0 and of parameter s. For more information on discrete Gaussians, see the description of Regev [Reg05, Sec. 2, §2]. By x ← D we denote the sampling of an element from distribution D. Definition 3 -The LWE n,q,α problem Let n > 1 and q > 2 be two integers, and α ∈]0, 1[. Define D LWE n,q,α (s) for a vector s ∈ Z n q as the distribution over Z n+1 q obtained as follows:

a ← U(Z n q ), e ← N αq , output (a, a, s + e) ∈ Z n+1 q
The decisional version asks to distinguish between D LWE n,q,α (s) and U(Z n+1 q

). The computational version asks, given polynomially many samples of D LWE n,q,α (s), to find s.

Both versions are intractable for the right choice of parameters, and were proven equivalent [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]. We do not describe the ring-based variant of this problem, because it is very similar except that it works with the ring R = Z[X]/f (X) for f (X) an irreducible polynomial of degree d, and that a and s are no longer vectors but polynomials. We will see later what this implies for FHE schemes.

Inria

For the security of LWE to hold, n, q and α need to respect several constraints. We defer the description of these constraints to section 2.3.5.

Brakerski's scheme

Brakerski's 2012 scheme [START_REF] Brakerski | Fully homomorphic encryption without modulus switching from classical gapsvp[END_REF] is one of the simplest LWE-based LHE schemes to date, and we use it as a representative example of recent FHE scheme. To be more precise, the following scheme is a description of Regev's encryption scheme [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF], which is the starting point of Brakerski.

Setup params ← Setup(1 λ ): Output the LWE parameters (n, q, α) accordingly to λ (see section 2.3.5).

Key generation (pk, sk) ← KeyGen(params): Sample s ← U(Z n q ). Let N = (n + 1) log q . Sample a matrix A ← U(Z N ×n q ) and a vector e ← N N αq . Compute b = [A.s+e] q ∈ Z N q . Output ( (A,b),s). Note that the public key is an instance of LWE n,q,α for the vector s = sk.

Encryption c ← Enc(pk, m): For m ∈ {0, 1}, pick a random r ∈ {0, 1} N and output c = r T A, r T b + q 2 m ∈ Z n+1 q
Note that c is again the re-randomized version of the LWE instance linking pk and sk. By the Leftover Hash Lemma [START_REF] Impagliazzo | Pseudo-random generation from oneway functions[END_REF], this re-randomized version is equivalent to a normal LWE instance.

Decryption m ← Dec(sk, c): Let c = (u, v). Compute v -u, s = r T (As + e) + q 2 m -r T A, s = q 2 m + r T e
If the result is closer to 0, output 0, if the result is closer to q/2, output 1.

Note that for decryption to work, it is necessary to have r T e < q/4, else, decryption may output erroneous values. More exactly, we must have r T e < q 2 /2, but we simplify the notation. It is easy to see that the scheme is additively homomorphic:

c 1 + c 2 = (u 1 + u 2 , v 1 + v 2 ) = (r T 1 + r T 2 )A, (r T 1 + r T 2 )b + q 2 (m 1 + m 2 ) ∈ Enc(pk, m 1 + m 2 mod 2)
However, decryption works only if (r T 1 + r T 2 )e ≤ q/4. This limits the number of additions that can be performed on a same ciphertexts.

Multiplication is far less trivial, as the Regev scheme is not originally multiplicatively homomorphic. Because ciphertexts are vectors, the multiplication of two ciphertexts yields a matrix or a scalar number. In the latter case, the ciphertext can no longer be decrypted. In the other case, the size of a ciphertext is squared at multiplication, which is in contradiction with the compactness property of FHE schemes (see section 2.3.1).

To enable multiplication and give rise to a LHE scheme with allowed multiplicative depth L, Brakerski modifies the Regev scheme as described below. The operation ⊗ denotes the vector or matrix tensorial product.

• Encryption and decryption primitives do not need substantial changes;

• In KeyGen, Brakerski generates:

-L + 1 secret keys, i.e. s i ∈ Z n q for i ∈ {0, . . . , L}, set sk i = s i and the decryption secret key to sk = s L ; -L matrices P i-1:i ∈ Z N 2 log q ×(n+1) q (recall that N = (n + 1) log q ), called relinearization matrices. The matrix P i-1:i can be seen as an application transforming a ciphertext matrix resulting from a multiplication and encrypted under sk i-1 , into a ciphertext vector for the same message, encrypted under sk i .

• To multiply two ciphertexts c 1 , c 2 ∈ Z n+1 q :

1. Compute the vectors c

(1) i = PowersOfTwo(c i ) = [(c, 2c, 4c, . . . , 2 log q -1 c)] q ∈ Z N q . 2. Compute the tensor product of c (1) 1 ⊗ c (1)
2 . This yields a matrix of size N × N , which is flattened in a vector c (2) of size N 2 . At this point, c (2) contains in some way the encryption of m 1 .m 2 under a tensor secret key sk 2 i = s i ⊗ s i : indeed, the secret key hidden in the ciphertext was multiplied along with the messages 13 . The ciphertext c (2) also contains a lot of noise because randomness inside c 1 and c 2 (r, A and e) was also multiplied. In particular, an undesirable factor q appears in the noise, and largely participate in the noise increase.

The goals of the next steps are threefold: [START_REF]2 A 3-anonymous medical database[END_REF] to reduce the noise, (2) to come back to a linear secret key, and (3) to obtain a ciphertext vector in Z n+1 q .

3. Compute c (3) = 2 q .c (2) . This step is crucial to cancel the factor q in c (2) and to reduce the noise in the ciphertext. This is the main contribution of Brakerski: it allows scale invariance.

Compute c

(4) = BitDecomp(c (3) ) = (w 0 , . . . , w log q -1 ) ∈ Z N 2 log q q Such that c (3) = i 2 i w i mod q.

Finally, compute and output P

T i-1:i • c (4) q ∈ Z n+1 q
. We eventually come back to a vector of size n+1, because P i-1:i is of size (N 2 log q )× (n + 1) and c (4) is of size N 2 log q . And thanks to the structure of P i-1:i the ciphertexts is now encrypted under sk i = s i , without losing information. This last step is called re-linearization (in the sense that ciphertexts are transformed back into a vector) or key-switching (in the sense that ciphertexts are now encrypted under s i instead of s i-1 ). It is the crucial procedure making the difference with the MGH scheme [START_REF] Aguilar Melchor | Additively homomorphic encryption with d-operand multiplications[END_REF]: MGH is actually the first scheme to use the tensor product for HE, but did not find the way to avoid the ciphertext size expansion phenomenon. It is the most expensive step of the whole scheme. Therefore, multiplication is the most expensive operation.

At the end of the procedure, for freshly encrypted ciphertexts c 1 and c 2 with bounded noise |e 1 | = |e 2 | ≤ B ≈ αq14 the noise becomes B.poly(n). Generalizing this for L multiplications, the noise will be B.poly(n) L . As we can see, multiplication increases noise much more than addition (this is usually the case in FHE). Then, to be able to perform L multiplications, we must have B.poly(n) L < q/4. A detailed analysis of the noise growth in Brakerski's scheme [START_REF] Brakerski | Fully homomorphic encryption without modulus switching from classical gapsvp[END_REF] leads to the relation O(n log q) L+O(1) ≤ q/B, that the scheme should satisfy to allow L multiplications.

In practice, the public key is extremely large, because it contains L re-linearization matrices P i-1:i , each of size N 2 log q × (n + 1) ≈ (n log q ) 3 . And the ciphertext expansion is (n + 1).|q|/1 ≈ n|q|, which is also huge. In a general manner, the overall complexity of the scheme increases when n or q increase.

Deriving the parameters: the security-efficiency-homomorphism trade-off

On one hand, we known that q/B must be high enough to allow the desired L multiplications: we can derive lower bounds on the LWE parameters. On the other hand, n and q must not be too large to make the scheme practical: we can derive asymptotic upper bounds. There is a third family of constraints on the values of n, q and α: those dictated by the security requirements of LWE.

Indeed, as for any cryptographic problem, the parameters of LWE must be set according to the best known attack against it. In our case, the best known attacks against LWE are algorithms resolving approximation problems in (standard) lattices such as the shortest vector problem denoted GapSV P γ (in its decisional variant). It is interesting to note that FHE schemes tried to emancipate from lattices using the LWE problem, but their security still relies on problems similar to Gentry's original scheme. In the computational problem associated to GapSV P γ , the goal is to find a short vector in a given lattice, up to an approximation factor γ. This problem is believed hard for small values of γ. Two different cryptographic proofs (reductions) show that if an algorithm exists for breaking LWE n,q,α in polynomial time, there exists an algorithm to break GapSV P γ in polynomial time for an approximation factor γ = Õ(n/α). This means that LWE n,q,α is at least as hard as GapSV P Õ(n/α) . The first reduction is quantum [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF] (i.e. uses a quantum algorithm), and the second is classical [BLP + 13] (i.e. uses a classical algorithm). We will only consider the classical proof, which imposes more constraints on the parameters. The best practical algorithm against GapSV P γ is BKZ2.0 [CN11], a lattice basis reduction algorithm running in time 2 Ω(n/ log γ) . Therefore, to obtain a security of λ bits, we must have 2 Ω(n/ log γ) ≥ 2 λ . The following list sums up the constraints from the classical reduction, along with the accumulated relations from previous paragraphs. Recall that B ≈ αq, by definition. (1) (for homomorphism), 2. n, log q ≤ poly(λ) (for efficiency), 3. q ≥ 2 n/2 (for reduction to GapSV P ),

1. q/B ≥ O(n log q) L+O

αq ≥

√ n (for reduction to GapSV P ), 5. γ ≈ Õ(n/α) (for reduction to GapSV P ),

6. γ ≤ O(n O(log n) ):
γ should be at the maximum sub-exponential in n for GapSV P γ . But here, Brakerski considers quasi-polynomial approximation factors. Ideally it should be in O(n c ) for a small c, e.g. 2. (for security), 7. 2 Ω(n/ log γ) ≥ 2 λ (for security against BKZ2.0).

There are several links between these constraints, and some of them are opposed. In particular, by constraints 1 and 3, q should be greater than B.n 2L (if we simplify greatly). However, according to constraints 5 and 6, n/α ≤ n log n , so we need to have q ≤ B.n log n-1 . This means that, for a constant initial noise B = 8 for instance (which is the proposed value in [START_REF] Lepoint | A comparison of the homomorphic encryption schemes fv and yashe[END_REF]):

8n 2L ≤ q ≤ 8n log n-1
This inequality can be satisfied only when 2L + 1 ≤ log n. Therefore, n must be exponential in L: to be able to perform several multiplications, n must be set very high. Yet, constraint 2 requires n to be polynomial in λ. Thus, L is limited to values in O(log(poly(λ))). More generally, we can see that augmenting q/B leads to better homomorphism because it leaves room for the noise within ciphertext to grow, but lowers security and/or performances.

Finally, constraint 7, which expresses the LWE parameters in function of the desired bitsecurity λ, dictates how concrete parameters values should be chosen. However, as of today, the running time of the BKZ2.0 algorithms are still unclear, and further studies are necessary to disclose what is hidden in the Ω notation in exponent. In the literature, n is often set between 10 3 and 10 5 , but the exact resulting security is unclear.

The reader may find a similar (far more thorough and accurate) analysis for two Ring-LWEbased schemes in [START_REF] Lepoint | A comparison of the homomorphic encryption schemes fv and yashe[END_REF]. The authors follow the same abstract procedure as in this section: analyse noise growth and deduce lower bounds, analyse security and deduce lower bounds, and finally deduce parameters values. The results highlight that, given a reasonable value for L, it is impossible for security and correctness to hold for "small" values of n (as it would be desirable for efficiency). For instance, for L = 50, Fig. 2.3 shows the maximum and minimum bit-size of q in function of n for security and correctness to hold (respectively). These curves were estimated based on the 5 points provided by Lepoint et al. [LN14, Table 3]. As we can see, before n ≈ 34000, it is impossible to have L = 50.

Differences between LWE and Ring-LWE-based schemes

This section describes the differences between Ring-LWE and LWE constructions, and explain why the former leads to more efficient schemes. For a full description of Ring-LWE and Ring-LWE Inria based schemes, the reader may refer to the works of Fan et al. [FV12] or Bos et al. [START_REF] Joppew | Improved security for a ring-based fully homomorphic encryption scheme[END_REF]. Firstly, we have seen that LWE is resistant against quantum and classical algorithms. Ring-LWE is only proven quantum resistant. Its classical security is conjectured, but still need to be proved. Also, Ring-LWE reduces to GapSV P γ , but in ideal lattices, while LWE reduces to GapSV P γ in classical lattices.

Secondly, LWE works with vectors and matrices, as Ring-LWE works with polynomials. It is known that a polynomial can be represented as the vector of its coefficients (and conversely), but the great difference is that R-LWE-based schemes can use the natural and efficient arithmetics of polynomial rings to combine ciphertexts, which is not the case with vectors. This is why the public key and ciphertexts in Ring-LWE are only a couple of ring elements, whereas in LWE, they are large matrices or vectors. Note however, that Ring-LWE still need the costly key-switching operation because multiplying ciphertexts also gives rise to "doubly encrypted" ciphertexts.

To sum up LWE is (for now) more secure, but has an inherent quadratic overhead compared to Ring-LWE.

Recent evolutions

In 2012, at the moment Brakerski, Vaikuntanathan and Gentry [START_REF] Brakerski | leveled) fully homomorphic encryption without bootstrapping[END_REF] introduced leveled homomorphic encryption, the approximation factor of GapSV P γ was sub-exponential (which is the maximum allowed), and security was based on quantum GapSV P γ (less restrictive on n, q and α than the classical version). The great achievement of this work is to manage the noise efficiently (using modulus switching) so that after L multiplications the noise would be (B.poly(n)) L instead of (B.poly(n)) 2 L in previous works. In other words, for the same parameters and performances, exponentially more multiplications were possible.

Later in the same year, Brakerski [START_REF] Brakerski | Fully homomorphic encryption without modulus switching from classical gapsvp[END_REF] managed to reduce the approximation factor to quasi-polynomial while basing security on classical GapSV P γ at the same time. Brakerski was able to achieve such improvements mainly thanks to its scale invariance property, which do not consider the noise magnitude, but the noise ratio, defined as q/B. In practice, Brakerski's idea (put very simply) consists in dividing ciphertexts by a factor q after each multiplication (see step 3 of Brakerski's multiplication procedure, section 2.3.5).

The schemes from [START_REF] Brakerski | leveled) fully homomorphic encryption without bootstrapping[END_REF] and [START_REF] Brakerski | Fully homomorphic encryption without modulus switching from classical gapsvp[END_REF] were initially described for LWE, but can be easily ported to R-LWE for better performances. The schemes of Fan-Vercauteren [FV12] (2012) and Bos et al. [START_REF] Joppew | Improved security for a ring-based fully homomorphic encryption scheme[END_REF] (2013), however, were directly designed on R-LWE. They follow the lines of Brakerski's scheme, using scale invariance, and benefit from the great efficiency of R-LWE. As a result, they are among the most efficient schemes today. In particular, Bos et al. rely on a slightly modified variant of R-LWE, and exhibits better efficiency than Fan and Vercauteren's scheme.

In parallel, in 2013, a new scheme introduced by Gentry et al. [START_REF] Gentry | Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[END_REF] brought new techniques for FHE. In this scheme, ciphertexts are directly represented by matrices. Consequently, homomorphic addition and multiplication are respectively performed by natural matrix addition and multiplication. Decryption is based on techniques relying on eigenvectors and eigenvalues. The main improvement compared to previous scheme is that there is no longer the need for keyswitching or re-linearization, which are the most costly operations in modern schemes (both in terms of space and computation). Also, the noise growth is again lowered: for L multiplications, it grows from B to B.(n + 1) L . The approximation factors are roughly the same as in Brakerski. Unfortunately, this scheme is based on LWE and does not transpose to R-LWE. As a result, in practice, it does not show significant improvements in terms of efficiency compared to R-LWE schemes.

Finally, a 2014 scheme from Brakerski and Vaikuntanathan [START_REF] Brakerski | Lattice-based fhe as secure as pke[END_REF] reached a major stage in FHE: they made LWE-based FHE as secure as traditional lattice-based public key encryption. That is to say, they achieved LHE with approximation factors in O(n 2 ). Their construction improves upon the above 2013 scheme of Gentry et al. [START_REF] Gentry | Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[END_REF], and shows a very low noise growth: after L multiplications, the noise magnitude is only B.L.poly(n). This is the first scheme with linear noise growth in L, allowing (again) exponentially more multiplication compared to previous schemes. This almost optimal result allows to set polynomial factors in O(n 2+ ), with as close to 0 as necessary. Their scheme is however very inefficient. Indeed, the parameter n depends exponentially on 1/ , which means that efficiency degrades exponentially when the approximation factor get closer to O(n 2 ). Also, the authors make several assumptions on the circuit evaluated in order to optimize homomorphic operations, and thus restrict the functions evaluable by the scheme.

Implementations and practical considerations

This section gives details on the performances and practical efficiency of FHE and LHE schemes, and provides a list of known FHE implementations (for all types of schemes).

Schemes on ideal lattices

Two ideal lattice-based schemes were implemented: one by Smart and Vercauteren [START_REF] Smart | Fully homomorphic encryption with relatively small key and ciphertext sizes[END_REF], the other by Gentry and Halevi [START_REF] Gentry | Implementing gentry's fully-homomorphic encryption scheme[END_REF]. As the Smart-Vercauteren implementation only includes the basic SHE scheme, we do not consider it here. The second implementation realizes all the scheme, including the bootstrapping part, and make use of many minor optimizations in order to make the scheme work in practice. We report performances in Table 2.3, for a claimed security of λ ≈ 80 bits15 . Even though the implementation gave up some security in order to gain some performances, these numbers are far from practical. The goal of the authors was merely yo show that FHE was possible.

Schemes on the integers

Every year or so, a new integer-based scheme is published and a new implementation is provided. We report in Table 2.4 running times and public key sizes for the 2014 LHE scheme which includes all the improvements from section 2.3.4. The platform used was an Intel Xeon at 2.9GHz. Note that for λ = 80, figures are worse than those of ideal lattices, but this is explained by two factors: in the ideal lattice implementation, security is actually below 80 bits, and the platform is more powerful. Indeed, for λ = 62, the 2014 integer scheme performs better than the ideal lattice one. In addition to these implementations, the authors propose a detailed analysis of the scheme and deduce possible values for the parameter q for several values of the parameters n and L. From these results, it is straightforward to compute the ciphertext and keys sizes, and to evaluate the number of multiplications allowed L (by interpolation from [LN14, Table 3]). Indeed, in FV, ciphertexts consist in 2 ring elements, secret keys are 1 ring element, and public keys comprise (1+log 2 32 q) ring elements. A ring element itself is a degree n polynomial with |q|-bits coefficients, and thus consists in a n × |q|-bit value. Table 2.6 shows the ciphertexts and keys sizes of the FV scheme for a selection of three settings, where the claimed security is λ = 80. Although far above traditional public key encryption schemes, figures in Tables 2.5 and 2.6 are very reasonable, compared to all previous implementations we presented. This can be explained by the efficiency of R-LWE-based schemes, and by the precise analysis of Lepoint et al. However, remind that messages are bits, thus the ciphertext expansion is at least 127KB/1 ≈ 13.10 3 , which is even higher than the Goldwasser-Micali scheme 30 years ago.

Params

Homomorphic evaluations of block ciphers

In some works, in addition to implementing a scheme, the authors also test the performances of the scheme in a use-case. Often, the test consists in evaluating a block cipher on encrypted data. Initially, the motivation was to show that quite complex computation could be performed with FHE, and that FHE was possible. More recently, being able to evaluate block ciphers is motivated by the impossibility to send FHE encrypted data over the network, for example to the cloud. Indeed, as noted by Lepoint et al. [START_REF] Lepoint | A comparison of the homomorphic encryption schemes fv and yashe[END_REF], the ciphertext expansion of FHE schemes is so large that 4MB of data becomes 75TB of ciphertext once encrypted. The proposed solution for a user to be able to send encrypted data to the cloud it is to first encrypt the data using a block cipher such as AES. In a first phase, the user sends its data encrypted under a secret AES key K, along with Enc(pk, K) (where pk is the user's FHE public key). The cloud can then encrypt a second time the data using the client's public key pk, and homomorphically evaluate the decryption procedure of the block cipher in order to obtain data solely encrypted under the FHE public key pk. This solution trades communication complexity against computation load, but the cloud has supposedly huge computational power.

The first evaluation of a block cipher using FHE was performed by Note that all works first transform the block cipher into a circuit evaluable by their scheme. Also, they all use use leveled homomorphic encryption schemes and the ciphertext batching technique. When using batching, each ciphertext contains several slots, where each slot can contain 1 plaintext, and homomorphic operations are performed slot-wise. Said otherwise, 1 ciphertext can contain a certain number l of plaintexts, and operations on the plaintexts inside a given ciphertext are performed in parallel in a SIMD (Single-Instruction-Multiple-Data) manner. The authors use this technique to speed up the evaluation of the block cipher. As a result, the relative time per AES (or SIMON) block is reasonable. However, bear in mind that the overall time to evaluate the block cipher on all the blocks is important (e.g. 65h with BGV), and that the evaluator only obtains the result after this long period of time (the results arrive all together in one batch). Finally, bear in mind that the claimed security of FHE schemes is approximative.

Table 2.7 shows that the time per block of recent schemes are very reasonable, if latency is not an issue. In particular, the BLLN scheme is almost efficient, for λ = 80 and the SIMON block cipher. This gives hope for practical applications in the next years, and may efficiently resolve the problem of communicating homomorphically encrypted data to the cloud (but not to regular entities). Furthermore, Table 2.7 shows the great progress made in two years in R-LWE-based LHE, and the inefficiency of integer-based schemes even in 2014.

List of known implementations

Finally, we list the existing FHE implementation in Table 2.8. Note that many are not public, most of them are only at the stage of academic tool, and none is actually secure (their code has not been audited). Also, to manipulate large number, most of them use the GMP or Flint libraries. Keep in mind that this table is not a comparison of FHE schemes implementation, as it would be vain to try and compare them. Trying to compare running times of schemes based on different concepts, with different security levels (not always well defined), and whose Column 2 says whether the implementation is based on ideal lattices ("Ideal L"), integers, R-LWE, LWE or both ("R-/LWE"). Column 3 says whether the leveled or fully homomorphic version was implemented.

Future of FHE

Along the section, we have seen the progress made by the FHE technology. Although running times of LHE schemes are becoming reasonable, they are still above RSA 2048 by a factor 100, and the huge ciphertext expansion of LHE scheme is prohibitive.

In addition to the efficiency (and security) issues, cryptographers have identified several other problems worth considering.

• Can bootstrapping be practical, and performed with natural operations? [START_REF] Alperin | Faster bootstrapping with polynomial error[END_REF] • Is there an alternative to bootstrapping to achieve pure FHE?

RR n°8568

• Can FHE be as secure and as efficient as standard lattice cryptography?

• Is it possible to construct an Identity-based LHE/FHE scheme? The answer is theoretically, yes [START_REF] Gentry | Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[END_REF].

• Is it possible to construct an Attribute-based LHE/FHE scheme? Idem [START_REF] Gentry | Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[END_REF].

• Is it possible to use FHE to design functional encryption schemes, or vice-versa? [GGH + 13] • Is it possible to use FHE to obfuscate programs, or vice-versa? [GGH + 13] Finally, we conclude this section by recalling that the state-of-the-art FHE is constantly changing, and that in only 5 years, the complexity of FHE has dropped dramatically, thanks to a very active community and a great interest of cryptographers in this topic. Although not practical as of today, we can conjecture that in a few years, FHE will be practical for simple use-cases such as email filtering, and for a computationally powerful entity such as the cloud.

Discussion

In the light of the elements presented in this chapter, we now have enough knowledge to start using homomorphic encryption in new systems designs. However, there are several points we did not mention, mainly for simplicity reasons. First of all, we did not compare the security of homomorphic encryption schemes and traditional ones: indeed, as HE ciphertexts are by definition alterable, security can seem to be compromised. Also, in this last section we review the basic pros and cons of PHE and FHE, the evaluation of programs on encrypted data with FHE, advanced homomorphic properties of other types of schemes than encryption, and the link between HE and other similar technologies to compute over encrypted data.

Security of homomorphic encryption

In traditional public-key encryption schemes, the highest and most desirable level of security is IND-CCA2, i.e. indistinguishablility under adaptive chosen ciphertext attack [START_REF] Goldreich | The Foundations of Cryptography -Basic Applications[END_REF]. With a simple glance at the definition of the IND-CCA2 security (with decryption oracle access before and after the challenge step), it is easy to see that any homomorphic scheme can not attain this level of security. Indeed, after supplying m 0 and m 1 in the challenge part, and upon receiving Enc(pk, m b ) for a random b, the adversary can simply ask for the decryption of Enc(pk, m 1 -m b ) (resp. Enc(pk, m 1 /m b ) for multiplicative schemes) as she knowns the encryptions Enc(pk, m 1 ) and Enc(pk, m b ). If the result is 0 (resp. 1), the adversary knows that m b = m 1 , else m b = m 2 , and wins the game with probability 1.

Therefore, because of the malleable nature of HE schemes (i.e. the possibility to apply operations on ciphertexts that imply meaningful transformations on underlying messages), in general, their maximum security level is IND-CPA [START_REF] Fontaine | A survey of homomorphic encryption for nonspecialists[END_REF]. Some schemes were proven IND-CCA1 secure [START_REF] Boneh | Targeted malleability: Homomorphic encryption for restricted computations[END_REF], but in the general case it is unclear. Actually, to the best of our knowledge, this question have not been studied yet. We can say however, that bootstrappable FHE schemes are never IND-CCA1 secure: as the encryption of the secret key is public, the adversary only needs to ask for its decryption to break the scheme. This (in)security is not a point in favor of homomorphic encryption: using a HE scheme means that ciphertexts and their messages can be modified publicly by any entity, creating an open door for various attacks. However, note that this malleability is precisely what is sought in homomorphic encryption, and the loss of security and the homomorphic properties are bound: Inria we can not strictly have both IND-CCA2 security and homomorphism. Thus, in practice, one may need a second layer of traditional encryption to communicate ciphertexts over untrusted channels, or to authenticate the messages.

There are however recent works that try to reconcile homomorphism and security. For instance, Canneti et al. [START_REF] Canetti | Relaxing chosen-ciphertext security[END_REF] relax and modify the IND-CCA2 security game so as to forbid decryption oracle queries with ciphertexts that are related to the challenge messages m 1 and m 2 . This yields a new security definition denoted "Replayable CCA" (RCCA). In a similar way, An et al. [START_REF] An | On the security of joint signature and encryption[END_REF] define gCCA security for "benignly-malleable security", where the decryption oracle do not answer to queries on ciphertexts satisfying a particular binary relation with the challenge ciphertext. These two notions were generalized by Prabhakaran et al. [START_REF] Prabhakaran | Homomorphic encryption with cca security[END_REF], with the notion of "homomorphic CCA" (HCCA) security. In their definition, only some operations on the ciphertexts are allowed, and the oracle does not answer queries on ciphertexts obtained from non-authorized operations. However these result only modify the security definition, but do not provide more security, i.e. homomorphic schemes' security stays the same, but security definitions change so as to match their reality. Indeed, in gCCA and RCCA security, the "attack" described above where the adversary asks for the decryption of Enc(pk, m 1 -m b ) is still possible, and HCCA security does not guarantee any higher security neither.

In order to actually reconcile homomorphism and IND-CCA2 security in the same scheme, Emura et al. [EHO + 13] proposed the notion of Keyed-Homomorphic Public-Key encryption, where the knowledge of a secret evaluation key sk ev allows to modify ciphertexts (but not to decrypt them). Without this key the scheme is IND-CCA2 secure, and when it is known, the scheme is only IND-CCA1 secure. With this definition, CCA2 security is guaranteed for all parties without knowledge of sk ev , while homomorphism is still possible for privileged parties. This construction does not give rise to a strictly speaking IND-CCA2 secure homomorphic scheme, but it is as close as we can get, considering the opposition between the two notions. A realisation of a threshold keyed homomorphic encryption scheme has been proposed by Libert et al. [START_REF] Libert | Non-malleability from malleability: Simulation-sound quasi-adaptive nizk proofs and cca2-secure encryption from homomorphic signatures[END_REF], the first of this kind according to the authors.

Broken HE schemes

We conclude this paragraph on HE schemes security by a brief overview of broken HE schemes. Indeed, several attempts for efficient PHE or SHE schemes were proposed and dismounted shortly after their release. In particular, two PHE schemes by Domingo-Ferrer [START_REF] Domingo-Ferrer | A new privacy homomorphism and applications[END_REF][START_REF] Domingo-Ferrer | A provably secure additive and multiplicative privacy homomorphism[END_REF] were broken respectively by Cheon et al. in 2006 [CKN06] and Wagner et al. [START_REF] Wagner | Cryptanalysis of an algebraic privacy homomorphism[END_REF], and a 2006 PHE scheme by Grigoriev and Ponomarenko [START_REF] Grigoriev | Homomorphic public-key cryptosystems and encrypting boolean circuits[END_REF] was broken the same year [START_REF] Choi | Cryptanalysis of a homomorphic public-key cryptosystem over a finite group[END_REF]. By "broken" we mean that the attacks against the schemes showed that the claimed IND-CPA security was actually flawed. These attacks do not seem to use the homomorphic properties of the schemes, i.e. their cryptanalysis do not rely on their homomorphism, and therefore are of little interest to us.

There is however, to our knowledge, one cryptanalysis using the homomorphic properties of the scheme it attacks. Indeed, Brakerski [START_REF] Brakerski | When homomorphism becomes a liability[END_REF] showed that the powerful SHE scheme from Bogdanov and Lee [START_REF] Bogdanov | Homomorphic encryption from codes. Cryptology ePrint Archive[END_REF] was insecure due to its homomorphic capacities. Even better, the author proved that homomorphism "becomes a liability" when the decryption function is weakly-learnable. A weakly learnable function is, very informally, a function whose output can be guessed with non-negligible but small probability, given many input-output samples. In the case of Bogdanov-Lee, the decryption function is a noisy scalar product. What Brakerski shows is that, if a scheme is "homomorphic enough" (in this case, if it can evaluate the majority function), and if its decryption function is "weakly learnable", then it is insecure. Using the majority function, Brakerski transforms ciphertexts with noise, say, 1/10 to ciphertexts with noise 1/(10n) for some n > 1, thus yielding a collection of low-noise ciphertexts, making the decryption function easier to learn, to a point that the secret key can be uncovered. The Bogdanov-Lee scheme was based on the "Learning parity with noise" problem, very close to the LWE problem but for elements in {0, 1}, it was quite efficient, allowed several additions and multiplications and was considered as a FHE candidate. But due to this cryptanalysis, it was not retained.

Partially or Fully homomorphic encryption ?

There are several differences between PHE and FHE schemes. Firstly, the formers are almost as efficient as traditional public-key encryption (PKE) schemes but allow very restricted computations, while the others are computationally very expensive (although a lot of progress were made) but are theoretically extremely powerful. As for their security, they both claim to be IND-CPA, but FHE/LHE schemes work on less standard and less studied assumptions. This implies a possibly lower security for FHE, but ongoing studies on FHE schemes' assumptions may re-establish equivalent security between PHE and FHE. Finally, we can say that, in general, PHE schemes provide algebraic homomorphic operations, such as natural addition over the integers, while FHE/LHE schemes are meant to encrypt and manipulate bits. This implies in particular that programs to be evaluated on encrypted data must before be transformed into a circuit (on this point, see paragraph 2.4.3).

As guidelines, we can say that the choice of using a PHE or FHE/LHE scheme completely depend on the use-case and the expressed needs. Indeed, before choosing a scheme, one should always clearly state what information needs to be kept secret from which party, and what are the operations that must be performed in the encrypted domain. Then, if there exist a PHE scheme powerful enough to perform these operations, use it preferably over FHE (for instance, addition and scalar multiplication are enough for several secure multi-party protocols). FHE/LHE schemes should be considered only if there is no other possibility. Typically, the FHE/LHE machinery is used only in very complex systems or delicate open problems, to exhibit a theoretical possibility result (a proof-of-concept).

Also, it is widely recommended to use LHE rather than FHE, at least up to a certain multiplicative depth. In many occasions, only a few multiplications are needed, and for L = 1, 2 or 3, R-LWE-based schemes are relatively efficient when used on computationally powerful platforms.

Evaluating a program on encrypted data: in practice

FHE schemes can theoretically compute arbitrary functions on encrypted data. However, we did not detail the procedure to do so. Indeed, it is not possible to simply take a program in C and run it on encrypted data.

Suppose an evaluator has a RAM program17 P (•) that she wants to evaluate on input x in the encrypted domain. First, as FHE schemes work with bit messages, x needs to be encrypted bit-wise. We denote x = {Enc(pk, x[i])} i this collection of encryptions. Then, the evaluator can not give x as input to P (•): the program needs to be transformed into a boolean circuit. Moreover, in this circuit, gates must be replaced by their corresponding operations on ciphertexts (typically, addition and multiplication of ciphertexts). At the end, the circuit may output several encrypted bit, which need to be decrypted separately and re-assembled to give the final result.

The transformation of P (•) from a RAM program into a circuit implies a high overhead in terms of time and space, in addition to the overhead caused by homomorphic gate evaluations. Indeed, a RAM program running in time T yields a circuit of size (i.e. number of gates) O(T 3 log T ) [START_REF] Gentry | Garbled ram revisited, part i[END_REF]. The intuition of this result is explained quite simply by Vaikuntanathan [START_REF] Vaikuntanathan | How to compute on encrypted data[END_REF]: imagine that given an encryption of an integer n > 0, we are asked to execute the RAM program "while(n < 10 6 ) n++;". As we do not have access to the actual value of n, the only way known as of today is to flatten the program, i.e. to create 10 6 hard coded conditional statements. Where the RAM program takes 10 6 rounds in the worst case, the equivalent circuit will always need 10 6 rounds. In particular, the RAM program stops directly if n = 10 6 +1, but the circuit needs go through 10 6 rounds still: the circuit represents the worst case execution of the program.

It is considered an open problem to design input-specific (as opposed to worst-case) program evaluation on encrypted data. With an input-specific procedure, the circuit from the above example would not always perform 10 6 rounds, and its average complexity would be lower. However, input-specific evaluation poses another threat: if the evaluation of the above program on encrypted data terminates early, this means n was slightly under 10 6 (or above it), and if it takes a long time to terminate, this means n was closer to 0. Therefore information on n is leaked, although, this value was precisely the one we wanted to keep secret in the first place (that is why we encrypted it). The source of difficulty in the program-circuit transformation is the presence of input-dependent loops or conditional statements in programs: the evaluation is highly inefficient, and/or information is leaked on the sensible data.

To mitigate the results from above and avoid circuit transformation, Garbled RAM can be used [START_REF] Lu | Garbled ram revisited, part ii[END_REF][START_REF] Gentry | Garbled ram revisited, part i[END_REF]. The main idea is to get rid of the costly circuit transformation step and directly evaluate RAM programs on encrypted (or "garbled") data. However, Garbled RAM constructions are not meant to work with FHE, and the link between the two technologies is still unclear.

Advanced notions: other homomorphic constructions

This chapter presented the notion of homomorphic encryption, and encryption only. However, other cryptographic constructions can be said homomorphic.

Homomorphic Signatures Johnson et al. [START_REF] Johnson | Homomorphic signature schemes[END_REF] put forward the notion of homomorphic signature, the analog of homomorphic encryption for signature schemes. A signature scheme is said homomorphic if it allows operations on signed messages, in the sense that the modified signature is a valid signature of the modified message. It is not trivial to understand why one would want such a property on signatures, which are precisely meant to attest the integrity and authenticity of a message. Initially motivated by applications to network coding, they are actually very useful to enable verifiable computation mechanisms. Verifiable computation is employed when some computation is delegated to an untrusted third party: we give the input and a homomorphic signature on it, the third party modifies the data and the signature accordingly, so that when the third party outputs the result, the authenticity of the data can still be universally verifiable.

Of course, a homomorphic signature scheme is not secure against existential forgeries (EUF-CMA), and a new security definition is required for these construction. Basically, a homomorphic signature scheme is secure with respect to the operations it can compute if an adversary can not forge signatures for messages independent from the message she previously queried to the signing oracle. In the seminal paper of Johnson et al. [START_REF] Johnson | Homomorphic signature schemes[END_REF], the authors construct 3 signature schemes, respectively homomorphic for: set operations, integer addition, and for sanitization. Interestingly, Johnson et al. prove that an additive homomorphic signature scheme can not be secure.

Several constructions have then been designed, and in particular, Libert et al. recently proposed structure preserving18 homomorphic signatures [START_REF] Libert | Linearly homomorphic structure-preserving signatures and their applications[END_REF]. There are other types of signatures supporting alterations, which we did not investigate: sanitizable signatures [START_REF] Ateniese | Sanitizable signatures[END_REF][START_REF] Canard | Sanitizable signatures with several signers and sanitizers[END_REF], and content extraction signatures [START_REF] Steinfeld | Content extraction signatures[END_REF].

Malleable proofs Along the same lines, there exist proofs and commitment systems allowing modifications on what is proved/committed [AFG + 10, CKLM12]. Motivations for these construction are more or less the same as homomorphic signatures, i.e. mainly, to enable verifiable computation with short and non-interactive proofs. Chase et al. [START_REF] Chase | Malleable proof systems and applications[END_REF] put forward the notion of controlled malleability for proofs, which refers to the limitation of the possible modifications on the proofs. Indeed, in practice, one may want to restrict and control what modifications third parties are allowed to perform. The authors also note that Groth-Sahai proofs are malleable, and show how simulation sound extractability and controlled malleability properties can be both satisfied in a same construction.

Targeted Malleability Using malleable proofs, Chase et al. [START_REF] Chase | Malleable proof systems and applications[END_REF] then propose the construction of controlled malleable encryption schemes: thanks to the controlled malleability property of their proofs, they actually attain the HCCA security level put forward by Prabhakaran et al. (and presented in section 2.4.1). This type of encryption has been formalized later by Boneh et al. [START_REF] Boneh | Targeted malleability: Homomorphic encryption for restricted computations[END_REF] and given the name of targeted malleability. Whereas Chase et al. use a IND-CPA secure encryption scheme along with malleable proofs, Boneh et al. use homomorphic schemes along with standard proofs. The main challenge in their construction is to avoid proofs size blowup. Indeed, the naive solution for targeted malleability is to ask to the entity modifying the ciphertexts to output a proof for each computation she performed that the new ciphertext was obtained applying an authorized function on the original one. However, this solution makes the proofs size grow at least linearly with the number of homomorphic operations. Here, the authors require the proof growth to be sub-linear. They achieve this goal using a double encryption paradigm (the same message is encrypted twice, under two different keys), and succinct (non-interactive) arguments that have the property to be smaller than their corresponding witness by a constant factor (say, 1/4). Then again, the notion of targeted malleability is useful in the setting of computation delegation, in order to ensure that only a certain set of allowed functions are computed on encrypted data.

Multi-key and threshold (F)HE

Another interesting feature of homomorphic schemes are their threshold capacity. For instance, in PHE, the Damgård-Jurik scheme is an adaptation of Paillier to the threshold setting, and in FHE the BGV scheme has been similarly adapted by Asharov et al. [AJLA + 12]. In a threshold encryption scheme, basically, several parties hold 1 secret key each but share the same public key: encryptions with the public can only be decrypted using all (or a subset of) the secret keys. In the FHE case, the same authors also note another interesting properties of (R-)LWE-based schemes: they are naturally key-homomorphic, i.e. addition of two key pairs yields a valid key pair. Threshold FHE allows server-aided multiparty computation: several parties provide inputs encrypted under the same public key to the server, who performs the computation and send back the output to all parties, who in turn cooperate together in a small decryption protocol using their respective secret keys. However, in this setting, the users have to interact to generate the public key and the secret keys, i.e. they have to be online before the computation. To thwart this issue, Lòpez-Alt et al. [START_REF] López-Alt | On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[END_REF] go even further and propose the notion of multi-key FHE: based on NTRU (a LWE-based scheme that can be turned into a FHE scheme), they construct a scheme capable of evaluating operations on data encrypted under several, totally unrelated keys. They also provide a generic construction to transform other FHE schemes into a multi-key FHE one. Unfortunately, in their solution the clients involved in the computation still have to cooperate at the decryption phase in order to get the result of the server's computation. However, as it has been proven that completely offline server-aided multi-party computation using only FHE is impossible [START_REF] Van Dijk | On the impossibility of cryptography alone for privacy-preserving cloud computing[END_REF], this solution is so far optimal in terms of communication and cooperation between parties. The threshold or multi-key properties may prove useful, as in many settings we need to "mix" data encrypted under different keys.

Link with Functional Encryption, Garbled Circuits, MPC and Searchable Encryption

Homomorphic cryptography links to many other cryptographic constructions that we did not mention in this document. We briefly present a selection of notions, explicit their link (or differences) with homomorphic cryptography, and point references for the interested reader.

Secure Multi-party Computation Secure multi-party computation (SMPC) [START_REF] Andrew | Protocols for secure computations (extended abstract)[END_REF] is a setting where n parties want to compute a function f on the collection of their private inputs x i . The constraint is that each party keeps its input x i secret from all other parties during the protocol. In the end, all (or a subset) of parties should learn f (x 1 , . . . , x n ). Variants of SMPC also exist: in Verifiable SMPC all parties should be able to check that the computation performed was indeed the agreed function f , which is useful when only 1 party (the evaluator) performed the computation ; in Non-interactive SMPC, each party should send only 1 message in total during the protocol ; and in Private SMPC, it is required that f stays private to the evaluator (i.e. it can be considered as its private input). Verifiable SMPC is achievable thanks to zero-knowledge proofs for instance, and Private SMPC can use Garbled Circuits (see below).

Like HE, SMPC allows to compute on "hidden" inputs. Also, it is interesting to note that one of the (many) ways to achieve SMPC is to use FHE or PHE. Actually, the works of Lòpez-Alt et al. [START_REF] López-Alt | On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[END_REF] and Asharov et al. [AJLA + 12] presented in section 2.4.4 are mainly focused on FHE-based SMPC. As for PHE schemes, there are many multi-party computation protocols that can be found in the literature [START_REF] Doerte | Homomorphic Cryptosystems and their Applications[END_REF].

Garbled Circuits Garbled circuits (GC) are the first practical tools invented to compute on "encrypted data". Proposed by Yao [START_REF] Andrew | How to generate and exchange secrets[END_REF] 19 , the main idea behind GCs was to enable secure two-party computations with function privacy. Yao proposed a two-party protocol between a garbler who creates the garbled circuit and encodes its inputs, and an evaluator who evaluates the garbled circuit on the garbler's and her own inputs. The protocol ensures that each party keeps her input private. To garble a given circuit, the idea is to replace each of its gates with a garbled version of it, such that the truth table of the gate is preserved but unintelligible. The garbled circuit can then be evaluated by any party, but this party can not guess what she is actually evaluating. A garbled circuits, in Yao's original construction, is usable only one time. Indeed, if the evaluator could evaluate the garbled circuit more than once on different inputs, she would learn information on the inner structure of the circuit, and in the worst case, completely un-garble it. Recent works [GKP + 13] show how to construct secure re-usable garbled circuits (but the solution is quite inefficient).

Although GC are inefficient (especially because of the circuit computational model), they are still studied today and considered as a possible candidate for computing over encrypted data. An interesting work from Kolesnikov [KSS09] show how to combine HE and garbled circuits to produce two-party computation protocols with better efficiency.

Garbled RAM As discussed earlier in this section, executing random access machines programs is much more efficient than transforming them into circuit and evaluating them. Consequently, a (relatively) new field or research aims to directly garble RAM programs [LO13, GHRW14, LO14]. As defined by Lu and Ostrovsky [START_REF] Lu | How to garble ram programs?[END_REF], garbled RAM consists in an alternative to securely evaluate programs. The idea is, instead of always evaluating all the paths of a program, i.e. instead of evaluating the worst-case execution of the program flattened into a circuit, to prune off dead paths in the execution tree. In other words, only the relevant path in the program execution are evaluated. This yields a great efficiency improvement when the program accepts large inputs. The main challenge is then to keep the path and the memory access patterns secret. To hide the access pattern, garbled RAMs use the Oblivious RAM computation model of Goldreich et al. [START_REF] Goldreich | Software protection and simulation on oblivious rams[END_REF], that exactly fulfills this goal. To hide the execution path, the authors actually use one garbled circuit for each atomic step of the execution. The trick is that, the garbled circuit at step i actually dynamically generates the garbled circuit for the step i + 1. As garbled circuits, garbled RAMs are meant to be used in a protocol between an evaluator and a garbler.

Garbled RAMs are still at early an development stage, and are quite inefficient for now. The authors in [START_REF] Gentry | Garbled ram revisited, part i[END_REF] claim a running time in t.poly(λ).polylog(n).|C CP U |, where t is the original running time of the program, λ is the security parameter, n is the size of the input, and |C CP U | is the size of the step-circuit. In other words, the overhead of garbled RAMs is polylogarithmic. Also re-usable garbled RAMs have not been investigated yet, but are an open problem. In definitive, garbled RAMs are still theoretical object, but may become a viable candidate for computing on encrypted data without having to flatten the whole program into a circuit.

Functional Encryption Functional encryption (FE) may be the best concurrent to FHE. As formalized by Boneh et al. [START_REF] Boneh | Functional encryption: Definitions and challenges[END_REF], functional encryption schemes comprise special secret keys that allow evaluation of a given function and decryption at the same time. A FE scheme is composed of the 4 traditional primitives, but slightly modified: Setup outputs the public key and a master secret key msk, KeyGen takes as input a function f and msk and outputs a secret key sk f , Enc works as usual, but Dec, given sk f and a ciphertext Enc(pk, m), outputs f (m). The function f robustly embedded in the secret key sk f is applied simultaneously with the decryption procedure. The more functions f the scheme is able to evaluate, the more powerful it is. The security of such scheme is not trivial. Note that FE is a generalization of several encryption paradigm (including standard encryption). It can lead to attribute-based encryption (ABE), where the class of function is restricted to predicates on a user's attribute (i.e. Dec outputs m only if P (attributes) = true for some predicate P , else ⊥). In ABE, the secret key of the user contains its attributes and the predicate is fixed, or, alternatively, the secret key contains the predicate definition, and the attributes are embedded in the ciphertext. FE is also an abstraction of identity-based encryption (IBE) where the predicates are further restricted to identity checking (i.e. Dec outputs m only if id_decryptor = ID for some ID, else ⊥). In this case, the secret key simply contains its owner's identity, and the authorized decryptor's identity is contained in the ciphertext.

It is easy to see the resemblance between FE and HE. However, there are several important conceptual differences: evaluation on encrypted data with HE is made publicly using only the scheme's public key while in FE special secret keys must be delivered by the authority holding Inria msk. Also, evaluation with FE outputs plaintexts whereas after an FHE evaluation, one has to ask the owner of the secret key for decryption. Another difference is that (F)HE is actually more advanced than FE: it is more powerful and more efficient (because designing a secure FE scheme with is also efficient and somewhat powerful is very hard).

Proposed constructions of FE schemes [START_REF] Boneh | Function-private identity-based encryption: Hiding the function in functional encryption[END_REF][START_REF] Boneh | Function-private subspacemembership encryption and its applications[END_REF] are very limited in the set of functions f it allows, and are quite inefficient. But it is interesting to note that FE for any function f can be enabled using FHE, at least in theory [GGH + 13]. The idea is to (1) evaluate the function f with FHE, and (2) to input the result and non-interactive proofs that the computed function was indeed f to a secured functionality (e.g. a tamper-proof secure hardware token [START_REF] Döttling | Basing obfuscation on simple tamper-proof hardware assumptions[END_REF]) so that (3) it checks the proofs and securely executes the FHE decryption function (the secret key can be hard-coded into the secure functionality). An alternative to the hardware token method is using obfuscation (see last paragraph of this section). Both constructions are very far from practical, and consist in a first step toward powerful FE.

Searchable Encryption Searchable encryption (SE) can yet be seen as another flavor of FE, where the functions f are of the form "Is the word w present in the document?". However, it has a literature of its own thus we present it apart from FE. The basic, most general setting in SE is as follows. A database owner D needs to delegate storage of her database to a computationally powerful server E (e.g. the cloud). We suppose that the database contains sensible data, thus it is encrypted before it is handed to E. Then, some clients C, upon authorization from D, can perform requests to the server on the database, with the constraint that E does not learn the content of the queries but answers it appropriately, and without C learning anything more than the information requested. This setting is the one described by Jarecki et al. [JJK + 13], but then, many settings can be derived from this one: for instance, E can be a mail server, D the receiver of some mails, and the goal is for E to test (non-interactively) tags on emails so as to forward them in the proper folder (e.g. it can act as a spam filter). In this sense E will also act as client and use SE to filter mails. This example setting is the one put forward in [START_REF] Boneh | Public key encryption with keyword search[END_REF].

We distinguish two kinds of SE schemes: public key (asymmetric) or private-key (symmetric). In the public key setting, anyone can publish data in the database (so there is no actual owner D). Generally speaking symmetric SE is more efficient thanks to the efficiency of symmetric over asymmetric cryptography. Also, we can differentiate single-keyword SE, general boolean queries SE, and fully-qualified queries SE: the former allows the search for 1 keyword at a time, boolean queries SE allows queries consisting in any boolean formula, and the latter allows any SQL-like queries. Recently, two works proposed practical symmetric SE schemes for arbitrary boolean queries on relational databases or free text. The first [CJJ + 13] mainly provide a protocol for conjunction queries, which is extensible to general boolean queries, and works for 1 client only, which is actually the owner of the database. The other [JJK + 13] extends this work in the multi-client setting, where the database owner can delegate querying rights to other clients. The authors present their work as an outsourced symmetric private information retrieval protocol. All their constructions are practical, and the complexity of the scheme is substantially independent of the size of the database. A protocol supporting general SQL queries can be found in [START_REF] Raluca | Cryptdb: Protecting confidentiality with encrypted query processing[END_REF], but is not as efficient.

Misc. As we can see all the presented constructions (SMPC, GC, GRAM, FE, SE) are ways to "compute on encrypted data". This notion can be extended to comprise even more constructions, such as obfuscation. Actually the notions of FE, FHE, garbling and obfuscation are closely related. In particular, an obfuscator for any program can be constructed using FHE plus an obfuscator for N C 1 circuits. And the resulting obfuscator in turn leads to functional encryption for any function f [GGH + 13].

Chapter conclusion As the first chapter provided a detailed view of numerical privacy, this chapter consists in a survey of homomorphic encryption. The first section is a high level historical and technical overview of homomorphic encryption, while the following sections detail partially and fully homomorphic schemes, list them, and compare them when possible. We expect to only use homomorphic cryptography, and not to design new schemes, but argue that a deep understanding of this tool is necessary. Indeed, it ensures we use them in proper the way, e.g. it avoids degrading security by using them in context they are not supposed to. It also permits to take into account the efficiency-security-homomorphism trade-off and to be able to compose HE with other cryptographic primitives. At last, if some minor modifications to some scheme are necessary, for example to adapt it to some setting, a good understanding of the scheme allows to easily conclude if and how it is possible.

The field of (fully) homomorphic cryptography is thriving, and the state-of-the-art schemes are constantly changing. Also, as a general trend, we can see that the paradigm of homomorphic cryptography is being extended to other schemes than encryption, and this progression should continue during the next years. Generally speaking, the "computing on encrypted data" idea has too many applications in society for its development to stop suddenly.

Because our main goal in this document is to protect privacy, and because we assume that for this end, homomorphic encryption is the main necessary tool, we only briefly exposed other homomorphic constructions. Indeed, homomorphic signatures and proofs are mainly useful to handle malicious parties: they come on top of a privacy solution, to re-enforce its security and ensure it is well applied.

Inria

Conclusion and perspectives

This document presented in details privacy in computer science on one hand, and homomorphic cryptography on the other hand. This succinct concluding chapter gives insight on how to combine both, i.e. how to use homomorphic cryptography for the protection of privacy.

What can homomorphic cryptography do for privacy?

Our main goal, as stated in introduction, is to design privacy-enhancing systems using homomorphic cryptography and similar technologies. The natural question we need to tackle is "what can HE do to enable/enhance privacy in information systems?". We give two different answers, a first naive one, and a less trivial one.

A first naive answer As noted in section 1.3, almost any information system can benefit privacy properties, although some systems are more pertinent than others, i.e. although it makes more sense to protect privacy in some systems than others. On the other hand, we have at our disposal the power of (fully) homomorphic encryption, that can theoretically evaluate any processing on data without actually accessing it.

Therefore, a first answer to the above question is "everything": FHE can resolve every privacy problem. Indeed, intuitively and for any system, we can imagine encrypting all sensible data with a FHE scheme, and for any necessary processing by any party, this party uses the homomorphic properties of the scheme to produce the desired encrypted output. To decrypt, 1 round of communication with the owner of the data (which is also the owner of the secret key) is then necessary. By this mean, the owner of the data can also verify what computation were performed using verifiable computation techniques, and what output the evaluator is going to learn.

Actually, this fact has already been put forward by Barak and Brakerski in a couple of blog posts [BB12b, BB12a], in a slightly more formal manner. They say of FHE that it is the "swiss-army knife of cryptography", a tool which resolves many cryptographic problems. As examples, they detail how to design two-party SMPC and zero-knowledge proofs systems from FHE. But there are many more applications, such as electronic voting, social networks, program obfuscation, ... They argue that FHE provides a unified and generic solution to many problems, but are aware that for each specific system, there exist more secure and efficient solutions tailored for it.

A more cautious answer As second, more moderate, non trivial and efficient answer to our question is possible. It consists in saying that a solution must be designed case by case in a tailored and "smart" way for each problem we encounter. It is the favored answer in the community, and actually, in the literature it is possible to find many use of PHE or FHE schemes for specific applications. We detail some of these applications in the following section, where we make the difference between PHE and FHE applications.

HE-based privacy in the literature

In light of our second answer, we give several existing solution of homomorphic encryption based privacy. We will see that this approach is far not recent, and many systems have been considered already.

Using PHE schemes As the first PHE scheme appeared more than 30 years ago, its applications are many. Though not all are privacy-oriented, a non-negligible part is. The main, established application is secure electronic voting, where the users' vote must absolutely stay private. Generally speaking, constructing on Yao's concept of multi-party computation [START_REF] Andrew | Protocols for secure computations (extended abstract)[END_REF], many works are devoted to designing efficient and secure multi-party protocols for various purposes such as integer comparison (known as the millionaires problem), PIR, Oblivious Transfer, Commitment, (Non-Interactive) Zero-knowledge Proofs, electronic auctions or secret sharing schemes. There are even proposition for system as complex as media fingerprinting for traitor tracing [START_REF] Pfitzmann | Anonymous fingerprinting[END_REF]. Many references of privacy-preserving PHE applications can be found in Rappe's thesis [START_REF] Doerte | Homomorphic Cryptosystems and their Applications[END_REF].

To provide a minimum insight on how constructions with PHE work, we detail simple protocols: one for electronic voting, and one MIX-net protocol (see section 1.3.3), both extracted from [START_REF] Damgård | A length-flexible threshold cryptosystem with applications[END_REF], which propose yet another extension of Paillier, building on the work of Damård-Jurik [START_REF] Damgård | A generalisation, a simplification and some applications of paillier's probabilistic public-key system[END_REF]. Their scheme is a threshold variant of Paillier: for a given public key, the secret key can be split into several parts so that all owners of the parts must collaborate to decrypt a ciphertext. Alternatively, the public key can also be split in several parts. The authors also design simple ways to prove validity of encryption, i.e. to prove that a given ciphertext actually encrypts a valid message. We simplify the protocols in order to put in light the use of homomorphic properties.

Electronic voting using Threshold Paillier

Setting The scheme is designed for a set of voters V = {1, . . . , n}, 1 candidate and "yes/no" votes. It can be used l times for l candidates. No need for trusted authority.

Protocol 1. Each voter i ∈ V publishes (i.e. broadcasts) n values c ij = Enc(pk j , s ij ) for j ∈ [1, n], where pk j is voter j's public key and such that j∈V s ij = 0.

2. Each voter j ∈ V retrieves encryptions c ij for all i ∈ V and computes

c j = i∈V c ij = Enc(pk j , i∈V s ij )
3. Each voter j ∈ V computes t j = Dec(sk j , c j ) (t j is a "random looking" value).

4. Each voter j ∈ V submits his vote v j ∈ {0, 1} by publishing x j = v j + t j .

5.

All voters can compute and agree on the result of the vote:

result = j∈V x j = j∈V v j + j∈V t j = j∈V v j + i∈V j∈V s ij = j∈V v j

Inria

Properties of the protocol Decentralized, dispute-free (honest voters all agree on the result), perfect ballot secrecy (even a majority of corrupted voters can not learn honest voters' votes).

Handling cheaters The complete protocol handles cheaters using several proofs of valid encryptions and NI-ZK proofs at step 1 and 4, and by discarding invalid values.

MIX-net using Threshold Paillier

This MIX-net protocol is not network oriented, and merely focuses on hiding the sender of a message. In other words, there is no routing procedure, and the model supposes a "bulletin board" where all users and server can read/write values publicly.

Setting Any number n of users and w MIX servers. Need for a trusted trust party at setup. Protocol 1. The trusted third party generates (pk i , sk i ) for each server i and securely distributes them. It also publishes on the board the public parameters of the scheme, g and N , and the product of the public keys, resulting in 1 valid Paillier public key, noted pk = h = g sk1+•••+skw . 2. To send a message m a user posts its encryption c = Enc(pk, m) on the board. 3. Iteratively, each MIX server (one at a time) re-randomize the encryption on the board and re-writes the result. For example in basic Paillier, re-randomisation of a given c = g m r N mod N 2 is c = c.r N mod N 2 for a random r . Note that the link between c and c is hidden because each MIX server always processes a batch of ciphertexts, all of which are of the same size. 4. When all MIXes finished the iterative re-randomization phase on c, they proceed to a threshold decryption protocol, and write the output on the board. As a result, the sender of a message can not be found.

Properties of the protocol Universally verifiability of MIXes outputs, strong correctness even against (w -1)/2 malicious MIXes and n -2 malicious users, order flexible (order of MIXes at step 3 is not important). Ciphertext and public key sizes are do not depend on the number of servers and the protocol is provably secure.

Handling malicious servers or users Proofs of valid encryptions and NI-ZK proofs are used at several steps Using FHE schemes Although fully homomorphic encryption is much more recent and still in development, there are already many applications envisioned by cryptographers. Considering our second answer from the previous section, where we require solutions to be (relatively) efficient and tailored for the system they apply to, we will not use FHE as a simple magic tool for all problems. Instead, we will only use the heavy and powerful machinery of FHE for very complex systems or for hard open problems in computer science. Indeed, there are some systems or problems at the cutting edge of computer research, where finding even a theoretical solution is very complex. In such a setting, we can consider using FHE.

As with PHE schemes, the literature already contains privacy solutions using FHE, which roughly correspond to the ones presented in section 2.4: functional encryption for all functions [GKP + 13, GGH + 13], program obfuscation [GKP + 13, GGH + 13], private machine learning [START_REF] Graepel | Ml confidential: Machine learning on encrypted data[END_REF], re-usable garbled circuits [GKP + 13]...

There is also a setting we mentioned several times in this document where using FHE is relevant: storage and computation delegation in the cloud. FHE is indeed suited, because the cloud is supposed to have a very large computing power, and because there is (as of today) no other known way of delegating computation to a third party without giving up access to the underlying data. Even garbled circuits and RAMs presented in section 2.4.5 are less pertinent, as their efficiency is comparable to FHE or worse, and most of those constructions yields a one-time executable program. Furthermore, garbled circuits/RAMs hide the computed function, which is not the main goal in this setting.

Note that using FHE in the cloud is not as simple as just encrypting and sending data: there are several difficulties, when looking into it. Indeed, if we consider the most general case, the requirements are quite challenging. Ideally, we would like every cloud client to simply encrypt her data with her public key, send it to the cloud along with a description of the functions it is allowed to compute on it, and then be able to adaptively ask for computations involving her data and possibly data from other users. Additionally, if some user u 1 asks for a computation involving data from herself, u 5 , u 8 and u 12 for instance, we would like that neither u 5 , u 8 nor u 12 need to be online (i.e. connected to the cloud) at this moment. As a simple use-case, social networks profile similarity computations are included in this setting. Now, in this quite simple description, there are already several issues. First, the basic step of encrypting and sending data to the cloud using a FHE scheme is as of today impracticable: a few megabytes of cleartext yields several terabytes of encrypted data [START_REF] Lepoint | A comparison of the homomorphic encryption schemes fv and yashe[END_REF]. The solution proposed to overcome this issue is to encrypt the data using a symmetric block cipher, encrypt the symmetric key with the FHE scheme, and send that to the cloud. As a result, the necessary bandwidth is dramatically reduced, and the server can obtain the data encrypted under the FHE scheme by re-encrypting what it received from the client with the FHE public key, and then homomorphically evaluating the decryption procedure of the block cipher, using the encrypted symmetric key. But the most serious limitation have been pointed out by Van Dijk et al. [START_REF] Van Dijk | On the impossibility of cryptography alone for privacy-preserving cloud computing[END_REF]: the authors actually prove that if the protocol described above is possible, then virtual black box obfuscation is possible. Yet, this is in contradiction with the impossibility result from Barak et al. [BGI + 12] stating that this kind of obfuscation is, in general, impossible. Solutions to overcome this issue were already described in section 2.4.4: the idea is to require a minimum of interaction between the users, i.e. between u 1 , u 5 , u 8 and u 12 in our example [AJLA + 12, LATV12].

What's left to do?

We have seen that there are many applications of HE to protect privacy in the literature. Yet, our goals is actually yo use HE for privacy. Therefore, it is reasonable (and necessary?) to ask "what more can be done in this field of research?". Indeed, with a glance at the existing works, it may seem like there is "no room left" for other privacy solutions using homomorphic encryption. However, we believe it is not the case, may it be simply because FHE is a very recent technology and no practical privacy solution has ever been proposed yet. We go even further, arguing that the full potential of FHE may not have been discovered yet. And generally speaking, new privacy issues keep appearing every year, providing matter for new works in this field.

We give three general directions to design HE-based privacy solutions.

Direction 1: proceed « traditionally » The first, natural one is to proceed as presented in the previous section, and by following the procedure described in section 1.2.3: Chose one or several existing information system(s), study them, and use homomorphic cryptography to ensure privacy. The main difficulty in this direction is to clear out pertinent and relevant systems where HE is (or at least seems) the suited tool to ensure privacy. In other words, the difficulty is to show Inria that HE is a or the good solution, possibly compared to state-of-the-art privacy solutions, for the chosen system(s). Indeed, as said earlier, HE and specially FHE are generic tools that can be used for privacy, but they produce generic and sometimes inefficient solutions. The chosen system(s) should fit well with HE, in the sense that a non-trivial and efficient way of using HE should be possible.

The envisioned systems are the following:

Computation delegation to the cloud As explained earlier, this setting is the main usecase for FHE.

Private network communications

The literature in censorship [START_REF] Winter | Censorship bibliography[END_REF], i.e. in strongly private anonymous communications, is thriving. In particular, the efficient Tor [START_REF] Dingledine | Tor: The secondgeneration onion router[END_REF] protocol is very popular. However, its efficiency comes at the cost of degraded privacy, and we believe that stronger privacy properties such as deniability, which makes it nearly impossible to even know if a user uses a privacy-preserving protocol or not, can and need to be ensured in this kind of system.

Authentication protocols Authentication and authenticated key-exchange protocols are the building blocks of many cryptographic protocol. Achieving authentication and privacy at the same time is very challenging, but may prove useful in many contexts such as seller-buyer interactions on Internet. Recently, a milestone was reached by Gambs et al. by achieving prover anonymity, deniability and security at the same time [START_REF] Gambs | Prover anonymous and deniable distance-bounding authentication[END_REF].

Direction 2: Improving controlled homomorphic cryptography A second option is to improve the nascent field of controlled (or targeted) malleability for encryption, signature and/or proof schemes. This direction is very cryptographic-oriented and requires the knowledge and ability to compose complex cryptographic primitives while preserving the security proofs. The finality would be to create a generic (but non trivial) solution for privacy using controlled FHE: instead of "simply" encrypting the sensible data and allowing anyone to perform any computation on the data, one would precisely control what is done with it. By covering the gap between security and homomorphism, we believe homomorphic cryptography would become more easily accepted as privacy-preserving solution.

The basic idea would be to continue the works of Boneh et al. presented in section 2.4.4, while improving efficiency and ciphertext size growth. Ideally, we can imagine a controlled malleability system directly embedded into the gears of homomorphic schemes. That is to say, a scheme would, by itself and without need for proofs on the side, inherently limit the possible operations on ciphertexts. Also, it would be interesting to combine the keyed-homomorphism property from Emura et al. [EHO + 13] with controlled malleability, so as to fully control who modifies the data and what are the modifications.

The main difficulty in this approach is, as said earlier, the acquisition of a strong knowledge in cryptography and cryptographic proofs. The task is also uneasy because there are already several highly skilled cryptographers working on this matter. At last, even if this the objective is fulfilled, there is a great chance that efficiency turn out to be even worse than plain FHE. This is a limitation for short term practical consideration, but improving efficiency may be, of course, part of further works. Direction 3: a « HE-based privacy » framework Finally, we see a third possible, very abstract goal: designing a generic (non-trivial) framework for "homomorphic cryptography based privacy", which would directly answer our ultimate goal. In other words, instead of proposing very specific solutions for some systems, the idea would be to offer a solution for a substantial number of systems. The desired framework would need to be very generic, but different from the "encrypt-and-publish" one discussed earlier, and it should not be void (i.e. it should provide privacy technicians useful, non-trivial information). And of course, the framework should mainly use homomorphic cryptography. Finally, to instantiate the framework, one should need less work than for designing a tailored solution.

This very abstract description is a desiderata, but tells very little about how to design it. To obtain elements of answer, one need to first work on several systems, study them and enforce privacy within them. With the acquired experience, we can hope that some common elements between particular solutions will emerge. In other words, the goal would be to infer general properties from particular solutions. Then, one needs to see how homomorphic cryptography connects with these general properties, i.e. how homomorphic cryptography can help ensuring them.

This exercise might prove very difficult, and such a framework may actually not exist. Even though the practicality of the solutions derived from the framework might be limited (because generic solutions often imply limited efficiency), cryptography and privacy always benefit from theoretical positive result. The idea is that the framework would directly yield theoretical solution for many privacy problems, thus bringing an easy answer to the question "is ensuring privacy in that context possible?". Therefore, we believe a HE-based privacy framework would be pertinent and desirable. As side contribution, it would bring a formalization of privacy with HE, which as of today lacks to the literature. We could also say there is a fourth approach/direction, which is a combination of the others. Indeed, one way to proceed may be to begin with direction 1, deduce general properties, and join with direction 3 afterwards. Alternatively, the join can be made with direction 2, if we assume that the acquired experience from direction 1 can be put to profit of understanding homomorphic cryptography and the needs in term of controlled malleability. The limiting factor of this fourth composite approach is the time: studying one system and ensuring privacy in it is already timeconsuming, and trying to repeat this for 2 or 3 other systems in order to tackle direction 2 or 3 afterwards is quite ambitious.

Concluding remarks

This document offers a deep understanding of privacy and presents homomorphic cryptography. Privacy is an emergent problematic on the rise. Recent actuality and the fact that the general public is now willing to use privacy-enhancing technologies such as Tor in censorships, anti-PRISM systems in the USA, or anonymizing proxy everywhere in the world, witnesses it. Also, the blazing fast evolution of (F)HE let us hope for practical solutions within the next decades. On the other hand, because the state-of-the-art (F)HE is instable, it is hard to conceive systems using current schemes: one needs to foresee and plan ahead in order to produce viable solutions in the long term.

To sum up the knowledge extracted from the two chapters, we can say that there are many possibilities to combine HE and protection of privacy: a very large portions of information systems can benefit from privacy properties, and FHE is a solution for many cryptographic or privacy issues. In other words, there are many ways to use (F)HE for privacy, but some choices are more pertinent than others. The goal is now to clear out the most relevant ones, and focus on the applications the most useful to the public.

Inria

Inria

Figure 1 . 2 :

 12 Figure 1.2: A 3-anonymous medical databaseQuasi-identifiers: {ZIP Code, Age}, Sensible = {Disease}[START_REF] Li | t-closeness: Privacy beyond k-anonymity and l-diversity[END_REF]

  For more information on MIXes and MIXing techniques, one may refer to Diaz and Preneel's taxonomy [DP04]. A possible implementation of MIX router is depicted in Figure 1.3.

Figure 1 . 3 :

 13 Figure 1.3: A simple MIX, using re-ordering and re-encryption

Encryption c ←

 ← Enc(pk, m): Outputs an encryption c of message m under public key pk. Decryption m ← Dec(sk, c): Using sk, decrypts the ciphertext c to recover the message m. If sk is not the key corresponding to the encryption key pk, or if an error occurs, outputs ⊥.

  and x is not a quadratic residue modulo N . Output ((N, x), (p 1 , p 2 )). Encryption c ← Enc(pk, m): For m ∈ {0, 1}, pick a random r ∈ Z * N and output x m r 2 mod N . Note that in any case c N = +1, but c is a quadratic residue modulo N only if m = 0. Decryption m ← Dec(sk, c): Test if c is a quadratic residue modulo N using the factorization of N and the fact that c p = +1 ⇔ c (p-1)/2 = 1 mod p for any prime p. If c is a quadratic residue modulo N , output 0, else output 1.

  For λ = 128 bits, |N | should be 2048, etc. Considering efficiency, note that a message composed of l bits expands to l.|N |. Ciphertext expansion is thus l.|N |/l = |N | bits, which is very large. The complexity of these primitives largely depends on |N | as well: encryption asks for a square and one multiplication and can be computed in time Õ(|N |), and decryption requires 2 exponentiations, computable in time Õ(|N | 2 ) [GM84]. Thus, a trade-off security-efficiency appears: as |N | increases, security increases, but efficiency decreases.

  and we have Dec(sk, c) = x.m.λ(N )/(x.λ(N )) = m mod N . Damgård-Jurik [DJ01] (2001) simplifies and generalizes Paillier. The main modification is the replacement of the message and ciphertext space: messages are taken in Z * N s , and ciphertexts lie in Z *

Figure 2 . 3 :

 23 Figure 2.3: Maximal (resp. minimal) bit-size of q in function of n for the security (resp. correctness) of the BLLN scheme to hold (for L = 50)

Table 2 .

 2

1: Comparison of PHE schemes

  .2.

	|N |	KeyGen	Enc	Dec	Add	Sc. mult
	512	8.7ms	1.4ms	0.3ms	< 0.1ms < 0.1ms
	1024	63.1ms	3.7ms	2.4ms	< 0.1ms	0.2ms
	2048 649.5ms 19.5ms 17.1ms < 0.1ms	1.2ms

Table 2 . 2

 22

: Implementation of

Paillier (libpaillier)

  Leveled vs. Fully. Complexity and overhead of LHE schemes depend on the requested depth L. In FHE, complexity only depends on the security parameter (i.e. it is independent of the evaluated function). In both FHE and LHE, ciphertext size growth is null. It may seem like FHE is better, because its cost is independent of the size oft he evaluated circuit. But because of the great cost of the Recrypt operation, LHE is much more efficient in practice, at least up to a certain threshold L max . Above this threshold, the circuit's depth becomes very large, and the cost of LHE becomes larger than FHE's. The value of this threshold is unclear and depends on the scheme considered.

	Ideal Lattices LWE or RLWE Integers
		vDGHV10	CMNT11	CNT12	CCK+13	CLT14
				BGV12
					GHS12
			BV11a	Bra12	BLLN13	BV14
	GentryThesis	SV10	GH11	BV11b	FV12	GSW13	AP14
	2010		2011	2012		2013	2014
		Figure 2.1: Listing of FHE schemes
	in LHE.

  Cheon et al. [CCK+ 13] and divide schemes in 3 main classes, according to the concepts and cryptographic problems they relate to. First schemes, including Gentry's original one, were based on ideal lattices. After what, in 2011, Brakerski and Vaikuntanathan[START_REF] Brakerski | Fully homomorphic encryption from ring-lwe and security for key dependent messages[END_REF] noticed that FHE could be based on much simpler problems, to wit Learning With Errors (LWE) or Ring-LWE (R-LWE). A year after, the number of new FHE schemes per year exploded, as shown by Figure2.1, and remains high until today (note that several schemes are not represented in the timeline). Also, starting from 2010, a different branch of FHE schemes, based on plain integers, is investigated in parallel. At the rate of 1 new scheme every year approximately, this branch adapts the new techniques from the (R-)LWE branch to the integer setting. Although integer-based schemes are very inefficient, they provide different assumptions and concepts to base security on, which is crucial in cryptography. Figure 2.1 presents the main FHE schemes from 2009 until today, and Fig 2.2 shows the evolution of underlying cryptographic concepts used to enable FHE. As we can see, the (R-)LWE branch is by far the most productive one.

	Figure 2.2: Evolution of underlying concepts of FHE schemes
	Inria

Table 2 .

 2 3: Implementation of an ideal lattice scheme[START_REF] Gentry | Implementing gentry's fully-homomorphic encryption scheme[END_REF] (2011)

Table 2 .

 2 We report in Table2.5 running times for two Ring-LWE based schemes: FV [FV12] and BLLN 16[START_REF] Joppew | Improved security for a ring-based fully homomorphic encryption scheme[END_REF]. These results are extracted from a work by Lepoint and Naehrig[START_REF] Lepoint | A comparison of the homomorphic encryption schemes fv and yashe[END_REF] who compare the capacities and efficiencies of the two schemes. The tests were performed on a Intel Core i7-2600 at 3.4 GHz. We can see that, apart from the key generation procedure, BLLN performs better than FV, especially when multiplying ciphertexts. 5: Implementation of two Ring-LWE-based schemes[START_REF] Lepoint | A comparison of the homomorphic encryption schemes fv and yashe[END_REF] (2014)

	Security	|pk|	KeyGen	Enc	Dec	Recrypt
	λ = 42	3.2MB	0.5s	< 0.1s <0.1s	0.1s
	λ = 62	704MB	5min	3s	0.2s	2.8s
	λ = 80	100GB	213h	5min	24s	4.6min
	Table 2.4: Implementation of an integer-based scheme [CLT14] (2014)
	Schemes on (R-)LWE
	Scheme Security KeyGen	Enc	Dec	Mult.
	FV	λ = 80	0.2s	34ms 65ms 148ms
	BLLN	λ = 80	3.4s	16ms 15ms	49ms

Table 2 .

 2 6: Ciphertexts and key sizes in the FV scheme

  Gentry et al. in 2012 [GHS12b], using the R-LWE version of [BGV12] (typically denoted BGV) to evaluate AES. This idea later inspired Coron et al. who performed the same exercise for integer-based scheme [CLT14]. And in 2014 Lepoint et al. evaluated the SIMON block cipher [BSS + 13], a slightly simpler block cipher, with the same implementations of the FV and BLLN schemes as in section 2.3.6. Results are summed up in Table 2.7. The platforms used to run the tests are respectively: the BlueCrystal Phase 2 super computer from Bristol University, an Inter Xeon E5-2690 (2.9GHz), and an Intel Core i7-2600 (3.4GHz).

  For every work, λ is the security of both the block cipher and the FHE scheme.

	Year	Cipher	Scheme	Based on	λ	# slots Evaluation time Time per block
	2012	AES	BGV [BGV12]	R-LWE	128	54	34h	37min
	2012	AES	BGV [BGV12]	R-LWE	128	720	65h	5min
	2014	AES	CLT [CLT14]	Integers	72	569	3h35min	23s
	2014	AES	CLT [CLT14]	Integers	80	1875	102h	3min15s
	2014 SIMON	FV [FV12]	R-LWE	80	1800	51min	1.70s
	2014 SIMON	FV [FV12]	R-LWE	128	2048	3h27min	6.06s
	2014 SIMON BLLN [BLLN13]	R-LWE	80	1800	17min	0.57s
	2014 SIMON BLLN [BLLN13]	R-LWE	128	2048	1h08min	2.04s
								Inria

Table 2 .

 2 7: Homomorphic evaluations of block ciphers implementation is run on different platform would not let us learn anything we do not already know: qualitatively, R-LWE schemes perform better than LWE schemes, which in turn are better than integer-based schemes (and ideal lattices come last).

	Scheme	Based on L/FHE Origin	Public Remarks
	vDGHV10	Integers	Fully	[vDGHV10]	No	Updates: [CMNT11, CNT12, CCK + 13, CLT14]
	Gen09	Ideal L	Fully	[GH11b]	No
	vDGHV09	Integers	Fully	Stephen Crane	Yes	C++, Not maintained
	SV11	Ideal L	Fully	hcrypt [BPS12]	Yes	Encrypted VM, C++ and Java
	BGV12	R-LWE	Leveled	[GHS12b]	No	Eval. AES
	BGV12	R-/LWE	Leveled	[AMFF + 13]	No
	BGV12	R-LWE	Leveled	Shai Halevi et al.	Yes	C++, Still maintained
	FV12 BLLN13	R-LWE	Leveled	[LN14]	Yes	Most up-to-date

Table 2 .

 2 8: Main FHE/LHE implementations

RR n°8568

Even though a law may recommend the use of a certain technology in its text, e.g. some cryptographic scheme, it will not actually use it and it does not look into the details of the scheme. Same goes for the opposite case: a technological approach will not consider using EU directives or governmental institutions to achieve its goals.

It is true if we suppose that the privacy works are uniformly distributed among the N val crit 1 values of crit 1 .RR n°8568

The sensitivity of Q is maxDB 1 ,DB2 |Q(DB 1 ) -Q(DB 2 )|,where DB 1 and DB 2 differ only in one entry. RR n°8568

For source/destination unlinkability to be verified, source/message and message/Destination unlinkability must both be verified.RR n°8568

The idea is that the lower the probability that X takes value a, the more bits needed to describe a.RR n°8568

Probabilistic algorithms running in polynomial time in the size of their inputs.RR n°8568

For simplicity, we will consider all polynomials coefficients a i as equal to 1 in the following paragraphs.RR n°8568

For simplicity, we present a restricted definition of the Jacobi symbol.RR n°8568

An expansion factor in ]1, 2] is possible, but 2 is the smallest possible integer factor.

[START_REF] Fousse | Benaloh's dense probabilistic encryption revisited[END_REF] proves the original scheme incorrect in the sense that decryption is ambiguous.Inria

The homomorphic encryption project

https://github.com/mikeivanov/paillier

libpailler, from John Hopkins University

PaillierGMP

http://security.hsr.ch/msevote/paillier RR n°8568

The gate's number of input wire.Inria

This is an approximation. See the original paper for a detailed analysis of the noise growth.RR n°8568

Equivalently, we can see c(2) as an encryption under a double public key, because sk is hidden in pk via a LWE instance.Inria

More formally, we say that the distribution Nαq of the error vector e is supported on [-B, B] with very high probability.RR n°8568

The actual security is below 80 bits, as the authors do not make n, the lattice dimension, depend on λ Inria

A program running on a random-access machine, the natural computation model for computer programs.Inria

Structure preserving signatures have the particularity that messages, signatures and public keys are all bilinear group elements [AFG + 10], which makes them easy to compose with other cryptographic tools such as Groth-Sahai proofs.Inria

Yao actually first presented GC in an oral presentation associated to the paper[START_REF] Andrew | How to generate and exchange secrets[END_REF]. A writing description can be found in [Gol03, Section 5.3.2].RR n°8568

Inria

Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399