Theodoros Spyridopoulos
email: th.spyridopoulos@bristol.ac.uk

Ioanna Topa

Theo Tryfonas
email: theo.tryfonas@bristol.ac.uk

Maria Karyda

A holistic approach for Cyber Assurance of Critical Infrastructure with the Viable System Model

Industrial Control Systems (ICSs) are of the most important components of National Critical Infrastructure. They can provide control capabilities in complex systems of critical importance such as energy production and distribution, transportation, telecoms etc. Protection of such systems is the cornerstone of essential service provision with resilience and in timely manner. Effective risk management methods form the basis for the protection of an Industrial Control System. However, the nature of ICSs render traditional risk management methods insufficient. The proprietary character and the complex interrelationships of the various systems that form an ICS, the potential impacts outside its boundaries, along with emerging trends such as the exposure to the Internet, necessitate revisiting traditional risk management methods, in a way that treat an ICS as a system-of-systems rather than a single, one-off entity. Towards this direction, in this paper we present enhancements to the traditional risk management methods at the phase of risk assessment, by utilising the cybernetic construct of the Viable System Model (VSM) as a means towards a holistic view of the risks against Critical Infrastructure. For the purposes of our research, utilising VSM's recursive nature, we model the Supervisory Control and Data Acquisition (SCADA) system, a most commonly used ICS, as a VSM and identify the various assets, interactions with the internal and external environment, threats and vulnerabilities.

Introduction

Industrial Control Systems (ICSs), have been a fundamental part of Industry automation for many years. They are typically used to control industrial processes, such as power production, oil extraction, transportation, telecommunications etc. [START_REF] Stouffer | Guide to industrial control systems (ics) security[END_REF]. Those processes have a direct impact on the National Critical Infrastructure (CI) [START_REF] Commission | Council directive 2008/114/ec of 8 december 2008[END_REF], making their protection against cyber-attacks a process of national significance. Effective Cyber-Security Risk Assessment methods are vital in order to manage security risks against the ICSs.

Assessing and managing cyber-security risks in traditional IT systems has followed certain well established techniques [START_REF] Peltier | Information security risk analysis[END_REF][START_REF] Stoneburner | SP 800-30. risk management guide for information technology systems[END_REF][START_REF] Alberts | Managing information security risks: the OCTAVE approach[END_REF][START_REF] Karabacak | Isram: information security risk analysis method[END_REF]. Nevertheless, the complexity and the interconnectivity of Industrial Control Systems (ICSs) hinder the application of traditional cyber-security risk management methods. In many cases though, the methods applied are adaptations of the conventional methods for managing cyber-security risks within the environment of an organisation [START_REF] Stouffer | Guide to supervisory control and data aquisition (scada) and industrial control systems security[END_REF], therefore addressing only part of the threat landscape and certainly mostly the traditional IT components, as opposed to sensor/actuator or other control elements [START_REF] Georgios | Risk assessment methodologies for critical infrastructure protection. part i: A state of the art[END_REF]. For that reason, new methods are being developed. However, the majority of these lack the perspective of resilience [START_REF] Georgios | Risk assessment methodologies for critical infrastructure protection. part i: A state of the art[END_REF], while in many cases the identification of the threats and vulnerabilities is conducted in each domain of the ICS separately, omitting the interactions between the various assets or threats. As a consequence they tend to protect the various domains of the system independently, applying overwhelming security measures driven by the worst case scenarios [START_REF] Georgios | Risk assessment methodologies for critical infrastructure protection. part i: A state of the art[END_REF]. This way, even though the system is considered secure, cost-efficient risk mitigation strategies can not be identified. Therefore, novel holistic cyber-security risk assessment and management approaches that can overcome the drawbacks of past approaches have to be explored.

Towards this direction, we propose a conceptual framework for the enhancement of the cyber-security risk assessment in ICSs, adopting principles of the Viable System Model (VSM) [START_REF] Espejo | The viable system model: interpretations and applications of Stafford Beer's VSM[END_REF]. We use the VSM to model the cyber-assets and functions within an ICS and identify the way cyber-threats against them affect the viability of the system, taking into account the various interactions that take place.

The rest of the paper is structured as follows. In Section 2 we discuss related work in the field of cyber-security risk assessment in Critical Infrastructure. Section 3 presents the basic background on the VSM. The description and analysis of our proposed model are given in Section 4. Finally, Section 5 discusses conclusions drawn from our work.

Related Work

Cyber-security risk assessment constitutes a fundamental element for the protection of ICSs. According to [START_REF] Georgios | Risk assessment methodologies for critical infrastructure protection. part i: A state of the art[END_REF] , Critical Infrastructure risk assessment methods are divided into two distinct categories, the sectoral methods, which refer to those who treat each sector separately in the risk assessment process, and those that follow a systemic approach examining the CIs as interconnected networks. Most existing methods fall into the first category. In order to cope with ICS, those methods have been extended. Nevertheless, they have limitations when they are applied in cross-sectoral environments. Furthermore, in most methods of both categories resilience concerns are not addressed or exist only implicitly. Our model falls into the second category, utilising the VSM as a vehicle for the identification and description of the cyber assets and cyber-security risks. The inherent scalable nature of VSM ensures resilience while its systemic behaviour allows the investigation of the emerging interconnections.

The authors in [START_REF] Rinaldi | Identifying, understanding, and analyzing critical infrastructure interdependencies[END_REF] examine Critical Infrastructure as Complex Adaptive Systems. They represent ICSs as large sets of components that interact with each other while synergies emerge through those interactions. They introduce the notion of interacting agents where each agent carries data regarding its location, capabilities and memory. However, the modelling and simulation of such models poses significant challenges and thus has not been taken into account for the risk assessment process. Since our model is based on the VSM, a model that has already been tested against the viability management of an ICS, it poses no similar challenges. In [START_REF] Chunlei | A simulation environment for scada security analysis and assessment[END_REF] the authors present a simulation environment for SCADA security analysis and assessment. However, even though their work takes into account the interdependencies to an extend and provides resilience, it is purely focused on the network communications between different parts of system, without taking into account several cyber-threats that are not network-driven.

In another approach [START_REF] Taylor | Risk analysis and probabilistic survivability assessment (rapsa): An assessment approach for power substation hardening[END_REF] the authors combine Survivability System Analysis (SSA) with Probabilistic Risk Assessment (PRA) in order to develop a new approach towards risk management in power substations that inherits the strengths of both. The principles of survivability analysis used in their work resemble the viability concept adopted in the VSM that we use in our work. However, this work lacks the ability to thoroughly explore the emerging inter-and intra-disciplinary interactions.

Basic Background on the VSM

Our research mostly focuses on the risk assessment process in ICSs. We have combined the traditional risk assessment methodology with principles of the Viable System Model, providing a new way of thinking towards the "cyber-asset identification" and "cyber-threat assessment" steps within a typical cyber-security risk assessment process, as described e.g. in [START_REF] Peltier | Information security risk analysis[END_REF]. In this section we provide background information relevant to the Viable System Model and its application to the cyber domain. The Viable System Model was originally designed by Stafford Beer to model the viability of an organisation [START_REF] Beer | Brain of the firm: the managerial cybernetics of organization[END_REF][START_REF] Beer | The heart of enterprise[END_REF]. Beer studied the human organism and constructed an organisational model for enterprises based on the methods used by the central and autonomic nervous systems to manage the operations of the organs and muscles. The model divides the organisation into three fundamental parts, i.e. Management, Operations and the Environment. The Operations part entails all the operations that take place inside the organisation while the management part controls the smooth operation of the system, ensures its stability, facilitates its adaptation to the future trends and structures the policies of the organisation. The environment entails all external entities that exchange data with the system. A general view of the model is shown in Figure 1. Beer suggests that we should model an organisation in the way the human body works, in a way that is not so strict and solid as the pyramid but flexible to adapt to changes caused by the environment. As seen in Figure 1, the VSM is composed of six different systems, each one of a distinct role. by System 2 and controlled by System 3 which is also responsible for the provision of synergies. System 3* is responsible to conduct audits upon System 1 to check if System's 3 directions and commands are implemented properly and address the existence of any issues to System 3. System 4 communicates with the external environment so that it can deal with the future trends and identify the various changes that take place in the external environment. It is in contact with System 3 in order to deliver the changes that have to be done and with System 5 which forms the upper level of management that deals with the system's policies and role inside the environment. System 5 is connected with System 3 since it monitors the homoeostasis between System 4 and System 3. Furthermore, System 5 has the responsibility to deliver the ethos of the organisation and take long term decisions that will be passed to System 3 in order to direct System 1 on how to implement them. Also, System 5 has to know the current state of the Organisation, through reports from System 3, in order to take a long term decision. An interesting characteristic of the VSM is its recursive nature. Each operation in System 1 forms a VSM subsystem with its own operational and management parts.

The VSM has already been used in the cyber-security domain, as a framework for examining the impacts of attacking organisations [START_REF] Hutchinson | Information warfare: using the viable system model as a framework to attack organisations[END_REF]. The authors utilised the VSM in order to identify the weak points within an organisation by modelling cyber-attacks as attacks against the various systems of the model. This way they managed to explore the impact of an attack based on the systems it affected. However, their work bears certain limitations as it only focuses on one VSM model, disregarding its recursive nature. Neither does it provide information regarding the VSM's relationship with the environment as well as other organisations.

In another approach [START_REF] Alqurashi | A viable system model for information security governance: Establishing a baseline of the current information security operations system[END_REF] the authors use the VSM to model Information Security Governance establishing a baseline of the current information security operations system. In their work they model the cyber-security mechanisms of an organisation as a VSM, mapping the various protection mechanisms on the VSM depending on the way they function. However, their research focuses exclusively on the protection mechanisms, omitting information regarding the cyber-assets and impact assessment of a cyber-attack. This is because they follow the implementation of a standard (ISO27001) and thus a checklist-based approach. In our work we use the VSM differently, modelling the cyber-assets of the system as operational or managerial components of a VSM, and examining the impact of a cyber attack upon it.

Proposed Model

In this Section we detail our model and its component and also an analysis of the VSM and how we utilise its features for the purposes of the risk assessment in ICSs.

Model Description

For the purpose of our research, we use VSM to model the assets of the system and the emerging relationships between those assets and the internal and external environment. Considering those relationships as another type of asset, we identify the threats against them and examine the vulnerabilities of the system that can be exploited by the identified threats. Since VSM was originally used to model the viability of a system, identifying the threats against the security of its system-components and their relationships equates to identifying the threats against the viability of the system. Therefore, in order to identify threats against the organisation we can do this by identifying the possible threats against the viability of the system as presented in [START_REF] Hutchinson | Information warfare: using the viable system model as a framework to attack organisations[END_REF]. In each of the six systems of the VSM we identify the threats that can:

make the system unavailable to the rest of the systems disrupting its connection to them (Denial of Service attack), corrupt the connection of the system to the rest of the systems by sending false data to them (Man in the Middle attack), render the system unavailable to its external environment (Denial of Service attack), corrupt the connection of the system to its external environment (Man in the Middle attack), disclose or corrupt data transferred from/to the system to/from the external environment or another system inside the organisation (data theft, data tampering), disclose or corrupt data that reside within the system (data theft, data tampering), make its subsystems or suprasystem unavailable, corrupt the connection with its subsystems or suprasystem, alter or disclose the data transferred to its subsystems or suprasystem.

Afterwards we explore the vulnerabilities that can be exploited by the threats identified in the previous step. The rest of the risk assessment process follows the traditional methodologies. Figure 2 illustrates our proposed risk assessment process. The first step of the process includes the construction of the VSM of the upper level organisation and it is repeated for every subsystem until the lowest level of the organisation where operations are performed by hardware. This way, all the possible assets and interactions are taken into account. At this point it is important to note that in order to identify all the assets and map them to the VSM as operational or management systems, knowledge from people within the ICS is also required. Managers form the upper management levels of the ICS along with engineers from the operational levels have to be consulted.

Model Analysis

In general, the proposed process starts with the construction of the VSM of the upper organisational levels. A general VSM model addressing the most common upper level functions that can be found in an ICS, such as Finance, Sales and Marketing, Production, Legal Services, IT, Human Relations etc., can be seen in Figure 3.

All departments of System 1 are coordinated through regular meetings between the activities directors, an action that forms System 2, and organised by the executive director (System 3). The Quality Control Direction forms System 3*, which is responsible for the monitoring and auditing activities on the various departments. System 4 and System 5 are defined as the Marketing and Forward Planning Direction and the Management Board respectively. At a first glance, VSM at this level has nothing to offer to the cybersecurity risk assessment. However, the lack of a System (for instance System 3*) may result in significant effects to the subsystems of the various departments of System 1, or a less effective Forward Planning Direction may result in missing critical security news. Thus, even at this level certain threats against cyber security of the ICS that derive from poor organisation of the ICS can be identified. In the context of VSM, the viability of the whole system is inextricably linked with the viability of its subsystems, therefore, each unit should function as a VSM in itself. Applying recursively the VSM in every department of the ICS and delving deeper into the lower levels can reveal more threats against cyber security. In Figure 4, after applying VSM recursively we reach the SCADA system-level. At this level all operations consist of hardware components, known as field devices. The impact of a successful cyber-attack there is much higher, because it can affect directly the function of the whole ICS. The VSM helps us identify all the interactions between the various field devices and the control/management equipment/department. Furthermore, interconnections with the external environment can also be identified. For example cyber-threats can origin from trusted insiders carrying knowingly or not compromised equipment, e.g. a malware-infected flash drive, or a compromised mobile device etc. As part of the environment we can find other ICSs that exchange data or services with the ICS under attack. The investigation of those interconnections provides the ability to examine the impact of a cyber-attack on other ICSs.

Conclusion

Risk assessment is an essential part of the protection process of Critical Infrastructure. There is a wide variety of risk assessment tools that are currently being used, however the complexity of these systems poses major challenges to the traditional approaches. Existing methods struggle to manage the dependencies in such environments, and resilience remains in most cases an unsolved issue.

In this paper we have used the Viable System Model in order to identify the relationships between the different parts within and outside the Critical Infrastructure system, scope the area of concern with respect to 'cyber' and construct a whole-system view of the assets, threats and vulnerabilities within that scope. Our work enriches the identification steps of conventional risk assessment methods. The VSM approach yields improved results as a diagnostic tool and so combined with a risk management method it can provide system resilience at multiple hierarchical levels. This approach takes into consideration organisational issues (management, coordination etc.) that play a vital role in the ability of a system to mitigate cyber-threats and could otherwise be overlooked.

As part of future work we are currently investigating agent-based modelling techniques where each agent embodies certain characteristics based on its position within the VSM. Furthermore, we aspire to develop novel risk management tools based on VSM, rather than using it as part of traditional methods. This requires the development of a quantitative risk evaluation process that will make use of the findings of the VSM to compute risks. Further work will focus on the development of a game theoretic model that tackles this issue.

System 1 :Fig. 1 .

 11 Fig. 1. The Viable System Model.

Fig. 2 .

 2 Fig. 2. VSM Risk Assessment Process.

Fig. 3 .Fig. 4 .

 34 Fig. 3. VSM General Model of the Upper Organisational Level of an ICS.

This work has been supported by the Univ. of Bristol's Systems Centre.


Jaap-Henk Hoepman
email: jhh@cs.ru.nl.

Privacy Design Strategies (extended abstract) ⋆

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Privacy by design [START_REF] Cavoukian | Privacy by design -the 7 foundational principles[END_REF] is a system design philosophy that aims to improve the overall privacy 1 friendliness of IT systems. Point of departure is the observation that privacy (like security) is a core property of a system that is heavily influenced by the underlying system design. As a consequence, privacy protection cannot be implemented as an add-on. Privacy must be addressed from the outset instead. The fundamental principle of privacy by design is, therefore, that privacy requirements must be addressed throughout the full system development process. In other words starting when the initial concepts and ideas for a new system are drafted, up to and including the final implementation of that system. Privacy by design is gaining importance. For example, the proposal for a new European data protection regulation [START_REF]Proposal for a Regulation of the European Parliament and of the Council. On the protection of individuals with regard to the processing of personal data and on the free movement of such data[END_REF] explicitly requires data protection by design and by default. It is therefore crucial to support developers in satisfying these requirements with practical tools and guidelines.

As explained in Section 2, an important design methodology is the application of so called software design patterns. These design patterns refine the system architecture to achieve certain functional requirements within a given set of constraints.

During software development the availability of practical methods to protect privacy is high during actual implementation, but low when starting the project. Numerous privacy enhancing technologies (PETs) exists that can be applied more or less 'off the shelf'. Before that implementation stage, privacy design patterns can be used during system design. Significantly less design patterns exist compared to PETs, however. And at the start of the project, during the concept development and analysis phases, the developer stands basically empty handed.

This paper aims to close this gap [START_REF] Gürses | Engineering privacy by design[END_REF][START_REF] Spiekermann | Engineering privacy[END_REF]. Design patterns do not necessarily play a role in the earlier, concept development and analysis, phases of the software development cycle. The main reason is that such design patterns are already quite detailed in nature, and more geared towards solving an implementation problem. To guide the development team in the earlier stages, we define the notion of a privacy design strategy. Because these strategies describe fundamental, more strategic, approaches to protecting privacy, they enable the IT developer to make well founded choices during the concept development and analysis phase as well. These choices have a huge impact on the overall privacy protection properties of the final system.

The privacy design strategies developed in this paper are derived from existing privacy principles and data protection laws. These are described in section 3. We focus on the principles and laws on which the design of an IT system has a potential impact. By taking an abstract information storage model of an IT system as a point of departure, these legal principles are translated to a context more relevant for the IT developer in section 4. This leads us to define the following privacy design strategies: MINIMISE, HIDE, SEPARATE, AGGREGATE, INFORM, CONTROL, ENFORCE and DEMONSTRATE. They are described in detail in section 5.

We believe these strategies help to support privacy by design throughout the full software development life cycle, even before the design phase. It makes explicit which high level decisions can be made to protect privacy, when the first concepts for a new information system are drafted. The strategies also provide a useful classification of privacy design patterns and the underlying privacy enhancing technologies. We therefore believe that these privacy design strategies are not only useful when designing privacy friendly systems, but that they also provide a starting point for evaluating the privacy impact of existing information systems.

Software development

Software architecture encompasses the set of significant decisions about the organisation of a software system2 , including the selection of the structural elements and their interfaces by which a system is composed, the behaviour as specified in collaborations among those elements, the composition of these structural and behavioural elements into larger subsystem, and the architectural style that guides this organisation.

Typically, the development of a software system proceeds in six phases: concept development, analysis, design, implementation, testing and evaluation. In fact, these phases are often considered a cycle, where after evaluation a new iteration starts by updating the concept as appropriate. In this paper we distinguish design strategies (defined in this paper), design patterns and concrete (privacy enhancing) technologies as tools to support the decisions to be made in each of these phases. The design strategies support the concept development and analysis phases, the design patterns are applicable during the design phase, and the privacy enhancing technologies are useful during the implementation phase.

Design patterns

The concept of a design pattern is a useful vehicle for making design decisions about the organisation of a software system. A design pattern "provides a scheme for refining the subsystems or components of a software system, or the relationships between them. It describes a commonly recurring structure of communicating components that solves a general design problem within a particular context." [START_REF] Buschmann | Pattern-Oriented Software Architecture[END_REF] Typically, the description [START_REF] Gamma | Design Patterns: Elements of Reusable Object-Oriented Software[END_REF] of a design pattern contains at least its name, purpose, context (the situations in which it applies), implementation (its structure, components and their relationships), and the consequences (its results, side effects and trade-offs when applied). Many design patterns exist, at varying levels of abstraction.

A classical software design pattern is the Model-View-Controller3 , that separates the representation of the data (the model) from the way it is represented towards the user (the view) and how the user can modify that data (using the controller). Few privacy design patterns have been explicitly described as such to date. We are aware of the work of Hafiz [START_REF] Hafiz | A collection of privacy design patterns[END_REF][START_REF] Hafiz | A pattern language for developing privacy enhancing technologies[END_REF], Pearson [START_REF] Pearson | Context-aware privacy design pattern selection[END_REF][START_REF] Pearson | Decision support for design for privacy: A system focused on privacy by policy[END_REF], van Rest et al. [START_REF] Jeroen Van Rest | Designing privacy-by-design[END_REF], and a recent initiative of the UC Berkeley School of Information4 . Many more implicit privacy design patterns exist though, although they have never been described as such. We will encounter them in our discussion of the patterns corresponding to the privacy design strategies we develop below.

Design strategies

Because certain design patterns have a higher level of abstraction than others, some authors also distinguish architecture patterns, that "express a fundamental structural organisation or schema for software systems. They provide a set of predefined subsystems, specify their responsibilities, and include rules and guidelines for organising the relationships between them."5 http://best-practice-software-engineering.ifs.tuwien.ac.at/ patterns.html, and The Open Group Architecture Framework (TOGAF) http://pubs.opengroup.org/architecture/togaf8-doc/arch/chap28.html

The Model-View-Controller pattern cited above is sometimes considered such an architecture pattern. The distinction between an architecture pattern and a design pattern is not always easily made, however. Moreover, there are even more general principles that guide the system architecture. We choose, therefore, to express such higher level abstractions in terms of design strategies. We define this as follows.

A design strategy describes a fundamental approach to achieve a certain design goal. It favours certain structural organisations or schemes over others. It has certain properties that allow it to be distinguished from other (fundamental) approaches that achieve the same goal.

Whether something classifies as a strategy very much depends on the universe of discourse, and in particular on the exact goal the strategy aims to achieve. A privacy design strategy is a design strategy that achieves (some level of) privacy protection as its goal.

Design strategies do not necessarily impose a specific structure on the system although they certainly limit the possible structural realisations of it. Therefore, they are also applicable during the concept development and analysis phase of the development cycle 6 .

Privacy enhancing technologies

Privacy Enhancing Technologies (PETs) are better known, and much more studied. Borking and Blarkom et al. [START_REF] Borking | Der identity-protector[END_REF][START_REF] Van Blarkom | Handbook of Privacy and Privacy-Enhancing Technologies -The case of Intelligent Software Agnets[END_REF] define them as follows.

"Privacy-Enhancing Technologies is a system of ICT measures protecting informational privacy by eliminating or minimising personal data thereby preventing unnecessary or unwanted processing of personal data, without the loss of the functionality of the information system."

This definition was later adopted almost literally by the European Commission [START_REF]the Commission to the European Parliament and the Council. On Promoting Data Protection by Privacy Enhancing Technologies (PETs)[END_REF].

In principle, PETs are used to implement a certain privacy design pattern with concrete technology. For example, both 'Idemix' [START_REF] Camenisch | An efficient system for non-transferable anonymous credentials with optional anonymity revocation[END_REF] and 'u-prove' [START_REF] Brands | Rethinking Public Key Infrastructures and Digital Certificates; Building in Privacy[END_REF] are privacy enhancing technologies implementing the (implicit) design pattern anonymous credentials. There are many more examples of privacy enhancing technologies, like 'cut-and-choose' techniques [START_REF] Chaum | Untraceable electronic cash[END_REF], 'onion routing' [START_REF] Chaum | Untraceable electronic mail, return addresses, and digital pseudonyms[END_REF] to name but a few.

The foundations of data protection

We aim to derive privacy design strategies from existing data protection laws and privacy frameworks. We therefore briefly summarise those here.

In the European Union, the legal right to privacy is based on Article 8 of the European Convention of Human Rights of 1950. In the context of data protection, this right has been made explicit in the 1995 data protection directive [START_REF]On the protection of individuals with regard to the processing of personal data and on the free movement of such data[END_REF], which is based on the privacy guidelines of the Organisation of Economic Co-Operation and Development (OECD) from 1980 [START_REF]OECD guidelines on the protection of privacy and transborder flows of personal data[END_REF].

The OECD guidelines

The OECD guidelines, of which the US fair information practices (FIPs) [START_REF]Privacy online: Fair information practices in the electronic marketplace[END_REF] notice, choice, access and security -are a subset, define the following principles.

-The collection of personal data is lawful, limited, and happens with the knowledge or consent of the data subject (Collection Limitation). -Personal data should be relevant to the purposes for which they are to be used, and be accurate, complete and kept up-to-date (Data Quality). -The purposes of the collection must be specified upfront (Purpose Specification), and the use of the data after collection is limited to that purpose (Use Limitation). -Personal data must be adequately protected (Security Safeguards).

-The nature and extent of the data processing and the controller responsible must be readily available (Openness). -Individuals have the right to view, erase, rectify, complete or amend personal data stored that relates to him (Individual Participation). -A data controller must be accountable for complying with these principles (Accountability).

Data protection in Europe

The OECD principles correspond roughly to the main provisions in the European data protection Directive of 1995 [START_REF]On the protection of individuals with regard to the processing of personal data and on the free movement of such data[END_REF]. For example, Article 6 states that personal data must be processed fairly and lawfully, must be collected for a specified purpose, and must not be further processed in a way incompatible with those purposes. Moreover the data must be adequate, relevant, and not excessive. It must be accurate and up to date, and kept no longer than necessary. These provisions express a need for purpose limitation, data minimisation, and data quality. Other articles of the Directive deal with transparency and user choice. For example, article 7 requires unambiguous consent from the data subject, while article 10 and 11 require data controllers to inform data subjects about the processing of personal data. Article 12 gives data subjects the right to review and correct the personal data that is being processed about them. Finally, security as a means to protect privacy is addressed by article 17, that mandates adequate security of processing.

We note that the European data protection directive covers many more aspects, that are however less relevant for the discussion in this paper. The directive is currently under review. A proposal for a regulation to replace it has been published [START_REF]Proposal for a Regulation of the European Parliament and of the Council. On the protection of individuals with regard to the processing of personal data and on the free movement of such data[END_REF], and an amendment was recently adopted by the European Parliament. This regulation is still in flux and under heavy debate, but it contains the following rights and obligations that are relevant for our discussion in this paper.

-A controller must implement data protection by design and by default (art. 23).

-A controller must be able to demonstrate compliance with the regulation (art.

5, and also art. 22). -Data subjects have the right to be forgotten and to erasure (art. 17).

-Data subjects have the right to data portability, allowing them 'to obtain from the controller a copy of data undergoing processing in an electronic and structured format which is commonly used and allows for further use by the data subject' (art. 18). -A data controller has the duty to issue a notification whenever a personal data breach occurs (art. 31 and 32).

The ISO 29100 Privacy Framework perspective

In the full paper [START_REF] Hoepman | Privacy design strategies[END_REF] we also include the ISO 29100 Privacy framework [START_REF]Information technology -Security techniques -Privacy framework[END_REF] in our analysis, but due to space constraints this is omitted from this extended abstract.

Summary of requirements

Not every legal requirement can be met by designing an IT system in a specific way. Legitimacy of processing is a good example. If the processing is illegitimate, then it will be illegitimate irrespective of the design of the system. We therefore focus our effort on studying aspects on which the design of an IT system has a potential impact. These are summarised in the list below.

-Purpose limitation (comprising both specification of the purpose and limiting the use to that stated purpose). -Data minimisation.

-Data quality.

-Transparency (Openness in OECD terms).

-Data subject rights (in terms of consent, and the right to view, erase, and rectify personal data). -The right to be forgotten.

-Adequate protection (Security Safeguards in OECD terms).

-Data portability.

-Data breach notifications.

-Accountability and (provable) compliance.

These principles must be covered by the privacy design strategies that we will derive next. Whether this is indeed the case is analysed in section 6.

Deriving privacy design strategies

A natural starting point to derive privacy preserving strategies is to look at when and how privacy is violated, and then consider how these violations can be prevented. Solove's taxonomy [START_REF] Solove | A taxonomy of privacy[END_REF], for example, identifies four basic groups of activities that affect privacy: information collection, information processing, information dissemination and invasions. This is in fact similar to the distinction made between data transfer, storage and processing by Spiekermann and Cranor [START_REF] Spiekermann | Engineering privacy[END_REF]. This general subdivision inspired us to look at IT systems at a higher level of abstraction to determine where and how privacy violations can be prevented.

In doing so, we can view an IT system as an information storage system (i.e., database system) system. Many of today's systems, like classical business or government administration systems, are database systems. The same holds for social networks. Current data protection legislation [START_REF]On the protection of individuals with regard to the processing of personal data and on the free movement of such data[END_REF] is pretty much written with such a database model in mind. In a database, information about individuals is stored in one or more tables. Each table stores a fixed set of attributes for an individual. The columns in the table represent this fixed set of attributes. A row is added for each new individual about whom a record needs to be stored. Sometimes, data is not stored at the level of individual persons, but is instead aggregated based on certain relevant group properties (like postal code).

Within the legal framework described in section 3, the collection of personal data should be proportional to the purpose for which it is collected, and this purpose should not be achievable through other, less invasive means. In practice, this means that data collection should be minimised. This can be achieved by not storing individual rows in a database table for each and every individual. Also the collection of attributes stored should correspond to the purpose, leading to fewer columns being stored. Data collected for one purpose should be stored separately from data stored for another purpose. Linking of these database tables should not be easy. When data about specific individuals is not necessary for the purpose, only aggregate data should be stored. Personal data should be properly protected, and hidden from other parties. A data subject should be informed about the fact that data about her is being processed, and she should be able to request modifications and corrections where appropriate. In fact the underlying principle of information self-determination [START_REF] Westin | Privacy and Freedom[END_REF] dictates the she should be in control. Finally, the collection and processing of personal data should be done in accordance to a privacy policy, that should be actively enforced. The current proposal for the revision of the European privacy directive (into a regulation) also stresses the fact that data controllers should be able to demonstrate compliance with data protection legislation. The data controller has the burden of proof with respect to compliance and must, for example, run and document a privacy impact assessment (PIA).

Given this analysis form the legal point of view, we distinguish the following eight privacy design strategies: MINIMISE, SEPARATE, AGGREGATE, HIDE, INFORM, CON-TROL, ENFORCE and DEMONSTRATE. A graphical representation of these strategies, when applied to a database system, is given in Figure 1.

The eight privacy design strategies

We will now proceed to describe these eight strategies in detail. We have grouped the strategies into two classes: data-oriented strategies and process-oriented strategies. The first class roughly corresponds to the privacy-by-architecture approach identified by Spiekermann and Cranor [START_REF] Spiekermann | Engineering privacy[END_REF], whereas the process-oriented strategies more-or-less cover their privacy-by-policy approach.

Data oriented strategies

Strategy #1: MINIMISE The most basic privacy design strategy is MINIMISE, which states that

The amount of personal data that is processed7 should be restricted to the minimal amount possible. This strategy is extensively discussed by Gürses et al. [START_REF] Gürses | Engineering privacy by design[END_REF]. By ensuring that no, or no unnecessary, data is collected, the possible privacy impact of a system is limited. Applying the MINIMISE strategy means one has to answer whether the processing of personal data is proportional (with respect to the purpose) and whether no other, less invasive, means exist to achieve the same purpose. The decision to collect personal data can be made at design time and at run time, and can take various forms. For example, one can decide not to collect any information about a particular data subject at all. Alternatively, one can decide to collect only a limited set of attributes.

Design patterns Common design patterns that implements this strategy are select before you collect [START_REF] Jacobs | Select before you collect[END_REF] , anonymisation and use pseudonyms [START_REF] Pfitzmann | Anonymity, unlinkability, undetectability, unobservability, pseudonymity, and identity management -a consolidated proposal for terminology[END_REF].

Strategy #2: HIDE The second design strategy, HIDE, states that Any personal data, and their interrelationships, should be hidden from plain view.

The rationale behind this strategy is that by hiding personal data from plain view, it cannot easily be abused. The strategy does not directly say from whom the data should be hidden. And this depends on the specific context in which this strategy is applied. In certain cases, where the strategy is used to hide information that spontaneously emerges from the use of a system (communication patterns for example), the intent is to hide the information from anybody. In other cases, where information is collected, stored or processed legitimately by one party, the intent is to hide the information from any other party. In this case, the strategy corresponds to ensuring confidentiality.

The HIDE strategy is important, and often overlooked. In the past, many systems have been designed using innocuous identifiers that later turned out to be privacy nightmares. Examples are identifiers on RFID tags, wireless network identifiers, and even IP addresses. The HIDE strategy forces one to rethink the use of such identifiers. In essence, the HIDE strategy aims to achieve unlinkability and unobservability [START_REF] Pfitzmann | Anonymity, unlinkability, undetectability, unobservability, pseudonymity, and identity management -a consolidated proposal for terminology[END_REF]. Unlinkability in this context ensures that two events cannot be related to one another (where events can be understood to include data subjects doing something, as well as data items that occur as the result of an event).

Design patterns

The design patterns that belong to the HIDE strategy are a mixed bag. One of them is the use of encryption of data (when stored, or when in transit). Other examples are mix networks [START_REF] Chaum | Untraceable electronic mail, return addresses, and digital pseudonyms[END_REF] to hide traffic patterns [START_REF] Chaum | Untraceable electronic mail, return addresses, and digital pseudonyms[END_REF], or techniques to unlink certain related events like attribute based credentials [START_REF] Camenisch | An efficient system for non-transferable anonymous credentials with optional anonymity revocation[END_REF], anonymisation and the use of pseudonyms. Note that the latter two patterns also belong to the MINIMISE strategy.

Strategy #3: SEPARATE The third design strategy, SEPARATE, states that Personal data should be processed in a distributed fashion, in separate compartments whenever possible.

By separating the processing or storage of several sources of personal data that belong to the same person, complete profiles of one person cannot be made. Moreover, separation is a good method to achieve purpose limitation. The strategy of separation calls for distributed processing instead of centralised solutions. In particular, data from separate sources should be stored in separate databases, and these databases should not be linked. Data should be processed locally whenever possible, and stored locally if feasible as well. Database tables should be split when possible. Rows in these tables should be hard to link to each other, for example by removing any identifiers, or using table specific pseudonyms.

These days, with an emphasis on centralised web based services this strategy is often disregarded. However, the privacy guarantees offered by peer-to-peer networks are considerable. Decentralised social networks like Diaspora 8 are inherently more privacy friendly than centralised approaches like Facebook and Google+.

Design patterns

No specific design patterns for this strategy are known.

Strategy #4: AGGREGATE The fourth design pattern, AGGREGATE, states that Personal data should be processed at the highest level of aggregation and with the least possible detail in which it is (still) useful.

Aggregation of information over groups of attributes or groups of individuals, restricts the amount of detail in the personal data that remains. This data therefore becomes less sensitive. When the information is sufficiently coarse grained, and the size of the group over which it is aggregated is sufficiently large, little information can be attributed to a single person, thus protecting its privacy.

Design patterns Examples of design patterns that belong to this strategy are the following: aggregation over time (used in smart metering), dynamic location granularity (used in location based services), and k-anonymity [START_REF] Sweeney | k-anonymity: A model for protecting privacy[END_REF].

Process oriented strategies

Strategy #5: INFORM The INFORM strategy corresponds to the important notion of transparency: Data subjects should be adequately informed whenever personal data is processed.

Whenever data subjects use a system, they should be informed about which information is processed, for what purpose, and by which means. This includes information about the ways the information is protected, and being transparent about the security of the system. Providing access to clear design documentation is also a good practice. Data subjects should also be informed about third parties with which information is shared. And data subjects should be informed about their data access rights and how to exercise them.

Design patterns A possible design patterns in this category is the Platform for Privacy Preferences (P3P) 9 . Data breach notifications are also a design pattern in this category. Finally, Graf et al. [START_REF] Graf | A pattern collection for privacy enhancing technology[END_REF] provide an interesting collection of privacy design patterns for informing the user from the Human Computer Interfacing perspective.

Strategy #6: CONTROL The control strategy states that Data subjects should be provided agency over the processing of their personal data.

The CONTROL strategy is in fact an important counterpart to the INFORM strategy. Without reasonable means of controlling the use of one's personal data, there is little use in informing a data subject about the fact that personal data is collected. Of course the converse also holds: without proper information, there is little use in asking consent. Data protection legislation often gives the data subject the right to view, update and even ask the deletion of personal data collected about her. This strategy underlines this fact, and design patterns in this class give users the tools to exert their data protection rights.

CONTROL goes beyond the strict implementation of data protection rights, however. It also governs the means by which users can decide whether to use a certain system, and the way they control what kind of information is processed about them. In the context of social networks, for example, the ease with which the user can update his privacy settings through the user interface determines the level of control to a large extent. So user interaction design is an important factor as well. Moreover, by providing users direct control over their own personal data, they are more likely to correct errors. As a result the quality of personal data that is processed may increase.

Design patterns

We are not aware of specific design patterns that fit this strategy.

Strategy #7: ENFORCE The seventh strategy, ENFORCE, states:

A privacy policy compatible with legal requirements should be in place and should be enforced.

The ENFORCE strategy ensures that a privacy policy is in place. This is an important step in ensuring that a system respects privacy during its operation. Of course the actual level of privacy protection depends on the actual policy. At the very least it should be compatible with legal requirements. As a result, purpose limitation is covered by this strategy as well. More importantly though, the policy should be enforced. This implies, at the very least, that proper technical protection mechanisms are in place that prevent violations of the privacy policy. Moreover, appropriate governance structures to enforce that policy must also be established.

Design patterns Access control is an example of a design patterns that implement this strategy. Another example are sticky policies and privacy rights management: a form of digital rights management involving licenses to personal data.

Strategy #8: DEMONSTRATE The final strategy, DEMONSTRATE, requires a data controller to Be able to demonstrate compliance with the privacy policy and any applicable legal requirements. This strategy goes one step further than the ENFORCE strategy in that it requires the data controller to prove that it is in control. This is explicitly required in the new draft EU privacy regulation [START_REF]Proposal for a Regulation of the European Parliament and of the Council. On the protection of individuals with regard to the processing of personal data and on the free movement of such data[END_REF]. In particular this requires the data controller to be able to show how the privacy policy is effectively implemented within the IT system. In case of complaints or problems, she should immediately be able to determine the extent of any possible privacy breaches. Design patterns Design patterns that implement this strategy are, for example, privacy management systems [START_REF] Casassa | An adaptive privacy management system for data repositories[END_REF], and the use of logging and auditing.

Conclusions & Acknowledgements

We have derived eight privacy design strategies from an IT system perspective, taking the legal requirements as point of departure. The coverage of these legal principles by the design strategies is summarised in Table 1 (using the detailed description of each strategy in section 5). As discussed before, not every legal data protection principle can be covered by a privacy design strategy, simply because the design of the system has no impact on that principle. Some data protection principles, like purpose limitation, are only partially covered by some of the strategies. Realising purpose limitation in full also requires procedural and organisational means.

With respect to design pattern coverage, we first observe that design patterns may belong to several design strategies. For example the use pseudonyms design pattern both implements the MINIMISE strategy and the HIDE strategy. In the course of our investigations we also observed huge differences between design strategies in terms of the number of design patterns known to implement them. For the strategies MINIMISE and HIDE, a large number of design patterns exist. This is not surprising, given the focus of most research in privacy enhancing technologies on these aspects of privacy protection. For the SEPARATE and CONTROL strategies on the other hand, no corresponding design patterns are known.

This paper discusses work in progress. In particular, further research will be performed to classify existing privacy design patterns into privacy design strategies,

Fig. 1 .

 1 Fig. 1. The database metaphor of the eight privacy design strategies.

Table 1 .

 1 Mapping of strategies onto legal principles.

		Purpose limitation	Data minimisation	Data quality	Transparency	Data subject rights	The right to be forgotten	Adequate protection	Data portability	Data breach notification	(Provable) Compliance
	MINIMISE	o +
	HIDE		+					o
	SEPARATE	o						o
	AGGREGATE	o +
	INFORM				+ +				+
	CONTROL			o		+			+
	ENFORCE	+		+			+ +			o

DEMONSTRATE

+

Legend: +: covers principle to a large extent. o: covers principle to some extent.

Based on an original definiton by Mary Shaw, expanded in 1995 by Grady Booch, Kurt Bittner, Philippe Kruchten and Rich Reitman as reported in[START_REF] Kruchten | An ontology of architectural design decisions[END_REF].

Originally formulated in the late 1970s by Trygve Reenskaug at Xerox PARC, as part of the Smalltalk system.

http://privacypatterns.org/

See

We note that the notion of a privacy design strategy should not be confused with the foundational principles of Cavoukian[START_REF] Cavoukian | Privacy by design -the 7 foundational principles[END_REF] or the concept of a privacy principle from the ISO 29100 Privacy framework[START_REF]Information technology -Security techniques -Privacy framework[END_REF].

For brevity, and in line with Article 2 of the European directive[START_REF]On the protection of individuals with regard to the processing of personal data and on the free movement of such data[END_REF], we use data processing to include the collection, storage and dissemination of that data as well.

http://www.w3.org/P3P/

and to describe these design patterns in more detail. Moreover, we have identified several implicitly defined design patterns (like attribute based credentials) that arise from our study of existing privacy enhancing technologies. Further developments and collaboration in this line of research will also be documented on our Wiki 10 . We would very much welcome contributions from the research community.

I would like to thank the members of the Privacy & Identity Lab 11 for discussions and valuable feedback. In particular I am grateful to Ronald Leenes, Martin Pekarek and Eleni Kosta for their detailed comments and recommendations that greatly improved this paper.

by the research program Sentinels (www.sentinels.nl) as project 'Revocable Privacy' (10532). Sentinels is being financed by Technology Foundation STW, the Netherlands Organization for Scientific Research (NWO), and the Dutch Ministry of Economic Affairs. This research was (partially) conducted within the Privacy and Identity Lab (PI.lab, www.pilab.nl). +0100 / ifip-sec-2014-final 1 In this paper we focus on data protection, and treat privacy and data-protection as synonyms.


Alberto Blanco
email: alberto.blanco@urv.cat

Josep Domingo-Ferrer

Oriol Farràs
email: oriol.farras@urv.cat

David Sánchez
email: david.sanchez@urv.cat

Distance Computation between Two Private Preference Functions

Keywords: Private distance computation, privacy, social networks, utility functions, preferences, user profiles, private matching

We consider the following problem: two parties have each a private function, for example one that outputs the party's preferences on a set of alternatives; they wish to compute the distance between their functions without any of the parties revealing its function to the other. The above problem is extremely important in the context of social, political or business networks, whenever one wishes to find friends or partners with similar interests without having to disclose one's interests to everyone. We provide protocols that solve the above problem for several types of functions. Experimental work demonstrates that privacy preservation does not significantly distort the computed distances.

Introduction

Shyness often has a rational component. Getting to know a stranger normally requires us to disclose some of our privacy to that stranger. Indeed, in a fair relationship there is normally a tit-for-tat approach, in which each of the parties must disclose something in order to learn something. It would be more privacy-preserving and less risky if two parties could determine whether they have similar interests without prior disclosure of such interests to each other. Of course, the more similar their interests turn out to be, the greater the posterior mutual disclosure: in the extreme case, if their interests turn out to be at distance 0, total mutual disclosure occurs.

In game-theoretic terms, the above problem can be expressed as two players being interested in determining how close their utility functions are without disclosing these utility functions to each other. In particular, this allows forming coalitions with homogeneous interests without prior utility disclosure.

Solving this problem is very relevant in many practical situations:

-In social networks, users could find friends or other users to follow who share their interests, without being forced to disclose their own private interests (e.g. religion, sexual orientation, health condition, etc.). For example, in the social network Pa-tientsLikeMe [START_REF]PatientsLikeMe[END_REF] users currently need to disclose their diseases in order to find users with similar ailments, a privacy loss which could be mitigated by our approach.

-Grooming attacks in social networks could be hindered to a good extent with our approach. Note that the groomer would need to guess the victim's interests in order to become her/his friend.

-Targeted consumer profiling could be also made possible. A company could create dummy users of a social network with the profile of the consumers it is looking for. In this way, the company could identify communities of potential consumers with the desired profile, without encroaching on the privacy of people who do not fit the profile being sought.

-In commercial transactions, parties could determine whether the values they assign to a collection of goods are similar, without prior disclosure of their chosen value(s). For example, in some cases a company may be interested in associating with companies with dissimilar interests, in order to form a complementary partnership, rather than associating with companies with too similar interests, which may be regarded as competitors.

-In job recruitment, companies and candidates would be able to confidentially determine to what extent the corporate vision is shared by each candidate. Thanks to the privacy-preserving mechanism, a lot of different factors could be included in the evaluation, without the company being forced to reveal its strategic goals to unsuccessful candidates or the latter needing to disclose their views.

Contribution and plan of this paper

We present in this paper privacy-preserving protocols that allow computing the distances between various types of functions. After that, we report on experimental work that shows that privacy preservation does not cause a significant distortion in the computed distance.

Section 2 defines several cases of privacy-preserving distance computation between functions, depending on the nature of the function and the type of distance being considered. Section 3 describes a protocol for privacy-preserving distance computation based on set intersection. Section 4 reports on experimental work. Section 5 describes related work. Conclusions and future research lines are summarized in Section 6.

Taxonomy of distance computation between functions

The protocol to compute the distance between two functions in a privacy-preserving way depends on the nature of the functions and the way the distance is to be measured. We next discuss several cases.

Case A: counting common qualitative preferences

In this case, the interests or preferences of each player are characterized as binary features on various independent topics. For example, in a social networks like Facebook, users are asked to provide their opinions on different topics as "like" or "do not like". In Patients-LikeMe [START_REF]PatientsLikeMe[END_REF], users are requested to detail their medical histories as binary selections from sets of alternatives (diseases, symptoms, etc.). We can consider the preferences or profile of a player as a set containing his/her opinions or personal details. Let this set be X for the first player C and Y for second player S. Then the distance between the interests of C and S can be evaluated as the multiplicative inverse of the size of the intersection of X and Y , that is 1/|X ∩ Y |, when the intersection is not empty. If it is empty, we say that the distance is ∞.

Clearly, the more the coincidences between X and Y , the more similar the preferences of both players, and the smaller the distance between them.

Case B: correlating qualitative preferences

As in the previous case, the players' preferences are expressed as qualitative features. However, if these features are not independent (e.g. related diseases) or they are not binary (e.g. expressed as free textual answers to questionnaires), the distance between the players' profiles cannot be computed as the size of the intersection between their sets of features. For example, if C suffers from anorexia and S from bulimia, there is some coincidence between them because they both present eating disorders. This coincidence must be captured by the resulting distance.

Assume we have a correlation function s : E × E → Z + that measures the similarity between the values in the sets of features of C and S, where E is the domain where the sets of features of both players take values. For nominal features (e.g. disease names), semantic similarity measures can be used for this purpose [START_REF] Sánchez | Ontology-based semantic similarity: A new feature-based approach[END_REF]; for numerical features that take values over bounded and discrete domains (e.g. ages, zip codes), standard arithmetic functions can be used. Assume further that both players know this function s from the very beginning.

Here the distance between the set X of C's features and the set Y of S's features can be computed as 1/( x∈X y∈Y s(x, y)) when the denominator is nonzero. If it is zero, we say that the distance is ∞.

Case C: quantitative preference functions

In this case, we want to compute the difference between two quantitative functions over the same domain, which define the preferences or profiles of the two players. We assume that they are integer functions. That is, C has a private preference function f : E → Z and S has a private preference function g : E → Z.

A way to measure the dissimilarity between f and g is to com-

pute d(f, g) = t i=1 |f (x i ) -g(x i )|, where D = {x 1 , . . . , x t } is a representative discrete subset of elements from E.
This scenario fits well the usual way of learning, modeling and managing social network user profiles in the literature [START_REF] Abel | Semantic enrichment of Twitter posts for user profile construction on the social web[END_REF][START_REF] Viejo | Preventing automatic user profiling in Web 2.0 applications[END_REF][START_REF] Zoltan | Semantic analysis of microposts for efficient people to people interactions[END_REF]. It consists in associating a vector of weights to each user, where each weight expresses the preference of the user on a certain topic (e.g. sports, science, health, etc.). Users are thus compared according to the distance between their vectors of weights.

Computing distances based on set intersection

It will be shown further below that the above three cases A, B and C can be reduced to computing the cardinality of set intersections. Hence, we first review the literature for solutions to secure two-party computation of set intersection cardinality. Secure multiparty computation (MPC) allows a set of parties to compute functions of their inputs in a secure way without requiring a trusted third party. During the execution of the protocol, the parties do not learn anything about each other's input except what is implied by the output itself. There are two main adversarial models: honest-but-curious adversaries and malicious adversaries. In the former model, the parties follow the protocol instructions but they try to obtain information about the inputs of other parties from the messages they receive. In the latter model, the adversary may deviate from the protocol in an arbitrary way.

We will restrict here to a two-party setting in which the input of each party is a set, and the desired output is the cardinality of the intersection of both sets. The intersection of two sets can be obtained by using generic constructions based on Yao's garbled circuit [START_REF] Yao | How to generate and exchange secrets[END_REF]. This technique allows computing any arithmetic function, but for most of the functions it is inefficient. Many of the recent works on two-party computation are focused on improving the efficiency of these protocols for particular families of functions.

Freedman, Nissim, and Pinkas [START_REF] Freedman | Efficient private matching and set intersection[END_REF] presented a more efficient method to compute the set intersection, a private matching scheme, that is secure in the honest-but-curious model. A private matching scheme is a protocol between a client C and a server S in which C's input is a set X of size i C , S's input is a set Y of size i S , and at the end of the protocol C learns X ∩ Y . The scheme uses polynomial-based techniques and homomorphic encryption schemes.

Several variations of the private matching scheme were also presented in [START_REF] Freedman | Efficient private matching and set intersection[END_REF]: an extension of the malicious adversary model, an extension of the multi-party case, and schemes to compute the cardinality of the set intersection and other functions. Constructing efficient schemes for set operations is an important topic in MPC and has been studied in many other contributions. Several works such as [START_REF] Blanton | Private and oblivious set and multiset operations[END_REF][START_REF] De Cristofaro | Fast and private computation of cardinality of set intersection and union[END_REF][START_REF] Hohenberger | Honest-verifier private disjointness testing without random oracles[END_REF][START_REF] Kissner | Privacy-preserving set operations[END_REF][START_REF] Vaidya | Secure set intersection cardinality with application to association rule mining[END_REF] present new protocols to compute the set intersection cardinality.

We now proceed to specifying protocols to deal with cases A, B and C above. In all cases, the distance between the private preferences of the two parties is computed using a protocol that yields the cardinality of a set intersection. We will use the protocol described in [START_REF] Freedman | Efficient private matching and set intersection[END_REF] for the cardinality of the set intersection, that is secure in the honest-but-curious model. The homomorphic encryption scheme we use is the Paillier cryptosystem [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF]. The protocol exploits the property that, given three elements m 1 , m 2 , m 3 , it is possible to efficiently compute Enc(m 1 + m 2 ) and Enc(m 1 •m 3 ) from Enc(m 1 ), Enc(m 2 ), and m 3 . We assume that C and S agree on a way to represent the elements of E as elements of the Enc function. They also agree on a special string m. The protocol is outlined next.

Step 1 C chooses the secret-key parameters, and publishes its public keys and parameters.

Step 2 C computes the polynomial p(x) = s i=1 (x -a i ).

Step 3 C sends Enc(p 0 ), . . . , Enc(p s ) to S, where p i is the coefficient of degree i of p.

Step 4 S picks a random element r j ∈ Z n for every 1 ≤ j ≤ t. S computes Enc(r j • p(b j ) + m) for 1 ≤ j ≤ t. Then S sends these ciphertexts to C.

Step 5 C decrypts the received ciphertexts. The result of each decryption is m or a random element.

If the size of the domain of Enc is much larger than |X|, the scheme computes |X ∩Y | with high probability: indeed, the number of times that m is obtained in the last step indicates the number of common elements in X and Y . Observe that C learns |X ∩ Y |, but C does not learn any additional information about Y or X ∩ Y (in particular, C does not learn the elements of these sets). Moreover S cannot distinguish between cases in which C has different inputs.

Case B

Here, C inputs X and S inputs Y , two sets of features, and they want to know how close X and Y are without revealing their set. In the protocol below, only C learns how close X and Y are; for S to learn it as well, the protocol should be run a second time (sequentially or concurrently) with the roles of C and S being exchanged. We assume that the domain of X and Y is the same, and we call it E. The closeness or similarity between elements is computed by means of a function s. In particular, we consider functions s : E × E → Z + . Observe that Case A is a particular instance of this Case B in which s(x, x) = 1 and s(x, y) = 0 for x = y.

Let Y be the input of S. For every z ∈ E, S computes z = y∈Y s(z, y). Observe that z measures the overall similarity of z and Y . Let Y = {z ∈ E : z > 0}. It is common to consider functions satisfying s(z, z) > 0 for every z ∈ E, and so in general Y ⊆ Y .

A protocol for such a computation can be obtained from the previous protocol, by replacing Step 4 with the following one:

Step 4' For every z ∈ Y , S picks z random elements r 1 , . . . , r z ∈ Z n and computes Enc(r j • p(z) + m) for 1 ≤ j ≤ z . Then S sends all these ciphertexts to C.

Thus, for every z ∈ Y , S sends z ciphertexts. In Step 5 C will recover m from these ciphertexts only if z ∈ X. Hence, at the end of the protocol the total number of decrypted messages that are equal to m is

x∈X x = x∈X y∈Y s(x, y),
that is, the sum of similarities between the elements of X and Y . This clearly measures how similar X and Y are. At the end of the protocol C knows |Y | and S knows |X|. Besides that, C and S cannot gain any additional knowledge on the elements of each other's set of preferences.

Case C

Here C inputs a private function f and S inputs a private function g, and they want to know how close these functions are without revealing them to each other.

The value d(f, g) will be computed in a vectorial setting. We assume that f, g : E → Z + . Note that if f or g take negative values, then C and S can define f : E → Z + : x → f (x) + c and g : E → Z + : x → g(x) + c for some large enough constant c ∈ Z + . Observe that d(f, g) = d(f , g ).

Given D = {x 1 , • • • , x t } ⊆ E publicly known, C defines the vector u = (u 1 , . . . , u t ) ∈ Z t + , where u i = f (x i ) for i = 1, . . . , t, and S defines v = (v 1 , . . . , v t ) ∈ Z t + , where v i = g(x i ) for i = 1, . . . , t. The problem described in Section 2.3 can be reduced to computing

u -v = t i=1 |u i -v i |.
Given u and v, we define the sets X = {(i, j) : u i > 0 and 1 ≤ j ≤ u i } and Y = {(i, j) : v i > 0 and 1 ≤ j ≤ v i }. Following the protocol for computing the cardinality of the set intersection presented above, C and S can compute |X ∩ Y | in a private way (the protocol needs to be run twice with the roles of C and S being exchanged in the second run). Observe that

|X ∩ Y | = |{(i, j) : u i > 0 and v i > 0 and 1 ≤ j ≤ min{u i , v i }}| = 1≤i≤t min{u i , v i }.
According to [START_REF] Freedman | Efficient private matching and set intersection[END_REF], in addition to learning |X ∩ Y |, during the protocol S learns |X| and C learns |Y |. Hence both C and S can compute

|X| + |Y | -2|X ∩ Y | = = m i=1 max{u i , v i } + min{u i , v i } -2 m i=1 min{u i , v i } = = m i=1 max{u i , v i } -min{u i , v i } = m i=1 |u i -v i | = u -v in a private way.

Experimental analysis

This section illustrates the applicability of the proposed protocols to compare profiles of social network users in a privacy-preserving way.

Empirical work was based on 16 Twitter users selected among the most relevant ones from WeFollow [START_REF] Wefollow | [END_REF] and WhoToFollow [START_REF] Whotofollow | [END_REF]. These sites rank and classify Twitter users in a set of categories. As done in [START_REF] Viejo | Preventing automatic user profiling in Web 2.0 applications[END_REF][START_REF] Viejo | Using profiling techniques to protect the user's privacy in Twitter[END_REF], we took the two 2012 most influential users for each of the following eight categories: Arts, Health, Shopping, Science, Computers, Sports, Society and Business.

Both client and server use the following computing environment: Asus S56C computer with an Intel core i7 3517U 8GB RAM DDR3 1600Mhz, running Ubuntu 13.10 and Java7 (opendjk-1.7). The size of the keys used is 1024 bits. The implementation of the Paillier cryptosystem is the one in [START_REF]The Homomorphic Encryption Project[END_REF], which we patched to evaluate polynomials using Horner's method.

We profiled each Twitter user by following the procedure described in [START_REF] Viejo | Preventing automatic user profiling in Web 2.0 applications[END_REF]. In a nutshell, we extract the noun phrases from the user's most recent set of 100 tweets, and we classify them in the above eight categories. Then, the contribution of each noun phrase to the corresponding category is measured as its informativeness, computed from its distribution in the Web. The aggregated contributions of all the noun phrases of a category measure the interest of the user in the category topic. Profiles are thus represented by a set of vectors containing eight normalized weights, each one quantifying the interest of the user in each of the eight categories. For example, the profile of the Twitter user CERN, which corresponds to the European Center for Nuclear Research, is: {Arts=15.1%, Health=0.27%, Shop-ping=1.79%, Science=47.93%, Computers=7.5%, Sports=5.45%, So-ciety=10.65%, Business=11.31%}, which shows a clear preference for Science-related topics. Thus, user profiles can be seen as preference functions that can be completely represented by a discrete set of eight quantitative features. This fits the case C discussed above, whose privacy preserving protocol is presented in Section 3.3.

To evaluate the suitability of the privacy-preserving protocol in terms of accuracy, we first computed the pairwise distance d between all 16 user profiles as described in Section 2.3:

d(f, g) = m i=1 |f (x i ) -g(x i )|
, where x i ∈ {Arts, Health, Shopping, Science, Computers, Sports, Society, Business}, and f and g represent the profiles of two different users by assigning the user's weight to each input category x i . Then, we computed the same pairwise distances using the privacy-preserving protocol described in Section 3.3.

Since our protocol assumes that the functions f and g to be compared output integer values, in a first experiment we rounded weights to the nearest integer. To measure the accuracy of the results, we computed the average error between the distances obtained by straightforward (non-private) computation and the distances obtained by our privacy-preserving distance computation. Such an average error was 1.69% with a standard deviation of 2.25%. This shows that our protocol does not cause a significant distortion in spite of the rounding needed to accommodate values.

On the other hand, the average run time for a privacy-preserving distance computation was 36.7 seconds, whereas it was negligible for a non-private computation. From direct analysis of the protocol (Section 3.3), it can be seen that the run time for a privacy-preserving distance computation depends on the number of weights to be compared (eight) and on the ranges of such weights. Since we rounded percentages to be integers between 0 and 100, the range of weights was 100.

In situations in which reducing the response time is especially important, one may sacrifice some accuracy to speed by using an integer representation with a smaller range. For example, by dividing all weights by 10 and rounding to the nearest integer, we reduce the weight range to 10, which in turn reduces the required number of encryption/decryption steps in the set intersection protocol by an order of magnitude. We did this and we obtained an average run time of 2.7 seconds per privacy-preserving distance computation. However, the average error with respect to non-private distances was 18.49% with a standard deviation of 17.8%, which illustrates how the (lack of) accuracy in the input discretization impacts on the (lack of) accuracy of the output.

Last but not least, we examined scalability. Figure 1 shows the growth of the computing times for C and S as the size of X and Y grow. The linear behavior is clear, with S having a higher computational load than C. More on computational complexity is discussed in Section 5 below.

Related work

We consider the problem of computing the distance between two private utility or preference functions. In the proposed cases, we deal with discrete or discretized domains, which allows us to lean on the literature on private record matching. In this type of matching, the problem is slightly different: it consists of matching the records of the same entity (individual, company, etc.) distributed across different data sets, while keeping those data sets private to their owners. There are three main approaches in the private record matching literature: sanitization-based, cryptographic and hybrid.

In sanitization-based methods, matching is performed on perturbed versions of the private data sets, in order to protect them against disclosure; a survey of perturbation/sanitization methods and record linkage methods can be found in [START_REF] Hundepool | Statistical Disclosure Control[END_REF]. This class of methods is usually computationally efficient but it incurs an obvious accuracy toll: matching on perturbed data sets is less accurate than matching on the original data sets. Indeed, false positive and false negative matches can appear.

Cryptographic methods are based on secure multiparty computation and they achieve privacy without accuracy loss. As mentioned above, we follow this approach, as we use MPC to compute the cardinality of set intersection, specifically the protocol in [START_REF] Freedman | Efficient private matching and set intersection[END_REF]. Our approach could be easily adapted to use other set intersection cardinality protocols in the literature, such as the ones mentioned at the beginning of Section 3 ([2, 3, 5, 10, 15]).

The communication complexity of our protocol is O(i C + i S ), where i C and i S are the sizes of C's input and S's input, respectively. C's computation complexity is O(i C +i S ), while S's computation complexity is in fact O(i C i S ), but it can be reduced to O(i C log log i S ) [START_REF] Freedman | Efficient private matching and set intersection[END_REF]. The computational complexity of the scheme in [START_REF] De Cristofaro | Fast and private computation of cardinality of set intersection and union[END_REF] is linear in i C +i S . Other protocols like the ones presented in [START_REF] Kissner | Privacy-preserving set operations[END_REF] do not differentiate the users C and S: both receive the set intersection cardinality at the end of the protocol.

There are also solutions for the private computation of the set intersection cardinality of n > 2 sets from n parties, and constructions that are secure in the malicious adversary model [2-5, 10, 15]. In a private matching scheme, the size of the inputs is known by both parties. Some techniques presented in [START_REF] Blanton | Private and oblivious set and multiset operations[END_REF] allow hiding the size of the inputs, but the communication and computation complexity of the resulting protocol is higher.

Hybrid methods try to achieve a trade-off between the sanitizationbased and cryptographic methods, to retain as much accuracy as possible while keeping computational complexity reasonable. The idea is to use a blocking phase that operates over sanitized data in order to rule out pairs of records that do not satisfy the matching condition. Then cryptographic MPC matching is applied only to blocks of both data sets which contain pairs of candidate matches. Methods following this approach are [START_REF] Inan | A hybrid approach to private record linkage[END_REF] (where k-anonymity is used as saniti-zation), [START_REF] Inan | Private record matching using differential privacy[END_REF] (where differential privacy is used as sanitization) and [START_REF] Inan | A hybrid approach to private record matching[END_REF] (which refines [START_REF] Inan | Private record matching using differential privacy[END_REF]). The approach proposed in our paper could also be adapted to the hybrid approach, as the final MPC stage of this approach can also be implemented via set intersection.

Conclusions and future research

Computing the distance between the private preference functions held by two different parties is very relevant in a number of applications. We have motivated several application scenarios in which the private functions express the preferences or profiles of the parties or, in game-theoretic terms, the utility of the players. These scenarios include finding friends or partners with similar interests in social networks, hindering grooming attacks, etc.

We have defined the problem for several types of private functions and, for each function type, we have given a protocol that solves the problem based on two-party secure computation of the cardinality of a set intersection. Empirical work shows that preserving the privacy of the preferences does not meaningfully affect the accuracy of the distances obtained.

Future work will involve designing a protocol to compute the distance between two private functions based on their whole domain E, rather than on a discrete subset D. This general approach will require dealing with continuous domains.

3. 1

 1 Case A C inputs X and S inputs Y , and they want to compute |X ∩ Y | without revealing their own set. In the protocol specified below, C inputs X = {a 1 , . . . , a s } ⊆ E, S inputs Y = {b 1 , . . . , b t } ⊆ E, where s and t are known, and finally C learns |X ∩ Y |. For S to learn also |X ∩ Y |, the protocol below should be run a second time (sequentially or concurrently) with the roles of C and S being exchanged.

Fig. 1 .

 1 Fig. 1. Execution time of the client C and the server S for different input sizes

Acknowledgments

This work was partly supported by the Government of Catalonia under grant 2009 SGR 1135, by the Spanish Government through projects TIN2011-27076-C03-01 "CO-PRIVACY", TIN2012-32757 "ICWT", IPT-2012-0603-430000 "BallotNext" and CONSOLIDER INGENIO 2010 CSD2007-00004 "ARES", and by the European Commission under FP7 projects "DwB" and "Inter-Trust". J. Domingo-Ferrer is partially supported as an ICREA Acadèmia researcher by the Government of Catalonia. The authors are with the UNESCO Chair in Data Privacy, but they are solely responsible for the views expressed in this paper, which do not necessarily reflect the position of UNESCO nor commit that organization.