Humboldt-Universität zu Berlin

Dissertation

Privacy trade-offs
in web-based services

Zur Erlangung des akademischen Grades
doctor rerum politicarum
(Doktor der Wirtschaftswissenschaft)

eingereicht an der
Wirtschafswissenschaftlichen Fakultät
der Humboldt-Universität zu Berlin

von
Herrn Diplom-Wirtschaftsingenieur
Claus Boyens
geboren am 17.9.1975 in Kiel

Präsident der Humboldt-Universität zu Berlin:
Prof. Dr. Jürgen Mlynek

Dekan: der Wirtschaftswissenschaftlichen Fakultät:
Prof. Dr. Joachim Schwalbach

Gutachter:
1. Prof. Oliver Günther, Ph.D.
2. Prof. Ramayya Krishnan, Ph.D.

eingereicht: 26. August 2004

Datum der Promotion: 15. Dezember 2004

Abstract

Recent developments in networking and storage technology have led to the dissemination of information over many different sources such as personal computers or corporate and public databases. As these information sources are often distributed and heterogeneous, effective tools for data collection and integration have been developed in parallel. These tools are employed e.g. in library search catalogues or in Internet search engines to facilitate information search over a wide range of different information sources.

In more sensitive application areas however, the privacy of the data holders can be compromised. In medical disease research for example, scientists collect and analyze patient data for epidemiological characterizations and for the construction of predictive models. Whereas the medical researchers need patient data at the highest level of detail, patients are only willing to provide data when their privacy is guaranteed. This conflict of interest between the data holders and the users occurs in many different settings, for example in the use of web-based services that require confidential input data such as financial or tax data. The more accurate and rich the provided private information, the higher the quality of the provided service. Not all data holders are aware of this trade-off and for lack of knowledge tend to the extremes, i.e. provide no data or provide it all.

This thesis explores the borderline between the competing interests of data holders and service users. In particular, we investigate the technical opportunities to model and describe this borderline. These techniques allow the two opposing parties to express their preferences and to settle the conflict with a solution that is satisfactory to both. The specific contributions of this thesis are the following:

• Privacy classification of service architecturesWe present a privacy classification of different service architectures after the number of involved parties and the reactivity of the data provision. For each class, we provide examples of practical applications and explain their relevance by discussing preceding cases of real-world privacy violations.
• Design, analysis and implementation of an encryption-based service architecture in an untrusted two-party environmentWe analyze the foundations of trust in web-based services and point out cases where trust in the service provider alone is not enough e.g. for legal requirements. For these cases, we derive a new privacy-preserving architecture that is based on an adapted homomorphic encryption algorithm. We map important database and arithmetic operations from plain data to encrypted data, and we present sample services that can be carried out within the framework.
• Design, analysis and implementation of an aggregation-based service architecture in an untrusted three-party environmentUsing a privacy-compromising health report as a running example through the thesis, we show how mathematical programming can be used to derive tight intervals for confidential data fields from non-critical aggregated data. We propose a new class of privacy mediators that settle the conflict between data holders and service users. A core component is the "audit & aggregate" methodology that detects and limits this kind of disclosure called interval inference.
• Quantification of the privacy trade-off and implications for electronic commerce and public policy
  We analyze several frameworks to quantify the trade-off between data holders and service users. We also discuss the implications of this trade-off for electronic commerce and public policy.

To summarize, this thesis aims to (a) increase data holders' and service users' awareness of the privacy conflict, (b) to provide a framework to model the trade-off and (c) to develop methods that can settle the conflict to both parties' satisfaction.

Keywords: Privacy, Security, Confidentiality, Encryption, Aggregation, Electronic Commerce, Service Architecture

Zusammenfassung

Rapide Fortschritte in der Netzwerk- und Speichertechnologie haben dazu geführt, dass Informationen über viele verschiedene Quellen wie z.B. Personal Computer oder Datenbanken verstreut sind. Weil diese Informationen oft auch sehr heterogen sind, wurde gleichzeitig die Entwicklung effektiver Softwaretechniken zur Datensammlung und -integration vorangetrieben. Diese werden beispielsweise in Online-Katalogen von Bibliotheken oder in Internetsuchmaschinen eingesetzt und ermöglichen eine breitgefächerte Suche von Informationen unterschiedlichster Art und Herkunft.

In sensiblen Anwendungsgebieten kann der Einsatz solcher Techniken aber zu einer Gefährdung der Privatsphäre der Datenhalter führen. Bei der Erforschung häufig auftretender Krankheiten beispielsweise sammeln und analysieren Wissenschaftler Patientendaten, um Muster mit hohem Erkrankungspotenzial zu erkennen. Dazu werden von den Forschern möglichst präzise und vollständige Daten benötigt. Der Patient hat dagegen großes Interesse am Schutz seiner persönlichen Daten. Dieser Interessenkonflikt zwischen Datenhaltern und Nutzern tritt auch in anderen Konstellationen wie beispielsweise in Internetdiensten auf, die die Eingabe von persönlichen Finanz- und Steuerdaten erfordern. Oft kann ein qualitativ höherwertiger Dienst angeboten werden, wenn persönliche Informationen preisgegeben werden. Über die hierzu notwendige Abwägung von Datenschutz und Dienstqualität sind sich nicht alle Datenhalter im Klaren und neigen zu Extremverhalten wie der Übermittlung aller persönlicher Daten oder gar keiner.

Diese Dissertation erforscht den Grenzbereich zwischen den scheinbar konträren Interessen von Datenhaltern und Dienstnutzern. Dabei werden insbesondere die technischen Möglichkeiten zur Modellierung und Beschreibung dieses Bereiches betrachtet. Die erarbeiteten Techniken sollen den beteiligten Parteien ermöglichen, den bestehenden Konflikt unter Einbeziehung ihrer Präferenzen zur beiderseitigen Zufriedenheit zu lösen. Die Beiträge dieser Dissertation sind im Einzelnen:

• Eine Klassifizierung von Dienstarchitekturen im Hinblick auf Datenschutzprobleme
  Verschiedene Dienstarchitekturen werden nach ihrer Datenschutzproblematik klassifiziert. Für jede Kategorie werden praktische Anwendungen erläutert.
• Entwurf, Analyse und Implementierung einer verschlüsselungsbasierten Dienstarchitektur in einer nicht vertrauenswürdigen 2-Parteien-Umgebung
  Es werden Gründe für Vertrauen von Datenhaltern in Anbieter von netzbasierten Diensten dargestellt. Für Fälle, in denen dieses Vertrauen alleine nicht ausreicht, wird eine Datenschutz garantierende Dienstarchitektur abgeleitet, die auf einem modifizierten Verschlüsselungsalgorithmus basiert. Wichtige Datenbankoperationen und arithmetische Elemente werden auf die verschlüsselten Daten übertragen und in beispielhaften Diensten zum Einsatz gebracht.
• Entwurf, Analyse und Implementierung einer aggregationsbasierten Dienstarchitektur in einer nicht vertrauenswürdigen 3-Parteien-Umgebung
  Am Beispiel eines den Datenschutz verletzenden Gesundheitsberichts wird gezeigt, wie Methoden des Operations Research dazu eingesetzt werden können, aus veröffentlichten Statistiken enge Intervalle für vertrauliche numerische Daten abzuleiten ("Intervallinferenz"). Zur Lösung des Interessenkonflikts zwischen Datenhaltern und Dienstnutzern wird die Verwendung eines sogenannten Datenschutzmediators vorgeschlagen. Dessen Kernkomponente ist die "Audit & Aggregate" Methodologie, die das Auftreten von Intervallinferenz aufdecken und verhindern kann.
• Quantifizierung der Datenschutzabwägungen und Schlussfolgerungen für den elektronischen Handel
  Es werden verschiedene Ansätze zur Quantifizierung der Datenschutzabwägungen betrachtet und Schlussfolgerungen für den elektronischen Handel gezogen.

Zusammengefasst versucht diese Arbeit, (a) die Wahrnehmung von Datenhaltern und Dienstnutzern für den bestehenden Interessenkonflikt zu erhöhen, (b) einen Rahmen zur Modellierung der Datenschutzabwägungen bereitzustellen und (c) Methoden zu entwickeln, die den Interessenkonflikt zur beiderseitigen Zufriedenheit beilegen können.

Eigene Schlagworte: Datenschutz, Sicherheit, Vertraulichkeit, Verschlüsselung, Aggregation, Elektronischer Handel, Dienstarchitekturen

Dedication:

Meinen Eltern

Table of contents

• 1  Introduction
  • 1.1  Privacy trade-offs in web-based service environments
  • 1.2 Contributions
  • 1.3 Structure of the thesis
• 2 A classification of privacy issues in service architectures
  • 2.1  Definitions and terminology
    • 2.1.1  Web-based services
    • 2.1.2 Privacy issues
  • 2.2 2-party service architectures
    • 2.2.1  Basic idea
    • 2.2.2 Instances in real-world information systems
    • 2.2.3 Related work
      • 2.2.3.1  Private Information Retrieval
      • 2.2.3.2 Partitioning and encryption
      • 2.2.3.3 Our contribution
  • 2.3 3-party service architectures
    • 2.3.1  Basic idea
    • 2.3.2 Instances in real-world information systems
    • 2.3.3 Related work
      • 2.3.3.1  Data integration
      • 2.3.3.2 Statistical disclosure control
      • 2.3.3.3 Privacy-preserving data mining
      • 2.3.3.4 Our contribution
  • 2.4 A classification of typical services
    • 2.4.1  Reactive vs. non-reactive data provision
    • 2.4.2 Sample services
  • 2.5 What this thesis is not about
• 3 Protecting sensitive information in data for web-based services
  • 3.1  Motivation
  • 3.2 Privacy concerns for users of web-based services
  • 3.3 A privacy-preserving architecture
  • 3.4 Data transformation
  • 3.5 The deployed privacy homomorphism
    • 3.5.1  Encryption
    • 3.5.2 Decryption
    • 3.5.3 A simple example
  • 3.6 Enabled services: Which services can be performed
    • 3.6.1  Database services
    • 3.6.2 Arithmetic operations
  • 3.7 Practical services
  • 3.8 A prototypical implementation
    • 3.8.1  Sketch of the implementation
    • 3.8.2 Experiments
    • 3.8.3 Practical implementation issues
  • 3.9 Limitations and opportunities
• 4 Protecting sensitive information in data for public use
  • 4.1  Motivation and running example
    • 4.1.1  2-party case vs. 3-party case
    • 4.1.2 Running example: Regional health initiatives
    • 4.1.3 Data warehouse and mediator architectures (Information integration)
    • 4.1.4 Trust in the mediator
  • 4.2 Inference problems
    • 4.2.1  Inference control in statistical databases
    • 4.2.2 Exact, statistical and interval inference
  • 4.3 Model and definitions
    • 4.3.1  A two-dimensional table model
    • 4.3.2 Mathematical programming
    • 4.3.3 Privacy protection policies
    • 4.3.4 Insider threats
    • 4.3.5 Interval inference
  • 4.4 Limiting interval inference
    • 4.4.1  Data perturbation
    • 4.4.2 Query restriction
    • 4.4.3 Aggregation
  • 4.5 The "audit & aggregate" methodology
    • 4.5.1  Data holders' privacy concerns vs. service users' data quality needs
    • 4.5.2 Data dissemination strategies and categories of interest
    • 4.5.3 An iterative methodology
  • 4.6 A method based on choosing information categories (Method-IC)
    • 4.6.1  Auditing
    • 4.6.2 Aggregation
      • 4.6.2.1  Dual prices
  • 4.7 A method based on value suppression (Method-VS)
  • 4.8 A prototypical implementation
    • 4.8.1  Goals of the implementation
    • 4.8.2 Sketch of the implementation
    • 4.8.3 Sensitivity of interval inference with regard to protection intervals
    • 4.8.4 Quality of the disseminated information
      • 4.8.4.1  Measuring data quality
      • 4.8.4.2 Method-IC and Method-VS vs. RDP
    • 4.8.5 Sensitivities of interval inference with respect to table size and skew
      • 4.8.5.1  Table size vs. number of inferred cells.
      • 4.8.5.2 Skew vs. number of inferred cells
    • 4.8.6 Complexity
  • 4.9 Limitations and opportunities
• 5  Privacy trade-offs: Quantitative aspects and implications
  • 5.1  Quantification
    • 5.1.1  Frameworks in Statistical Disclosure Control
      • 5.1.1.1  Measures for information loss
      • 5.1.1.2 Measures for disclosure risk
    • 5.1.2 The Risk-Utility confidentiality map
    • 5.1.3 A R-U confidentiality map for Health Maintenance Organizations
    • 5.1.4 Interpretation of the R-U confidentiality map
  • 5.2 Implications
    • 5.2.1  Impact on electronic commerce
    • 5.2.2 Implications for public policy
      • 5.2.2.1  National security
      • 5.2.2.2 Medical research
• 6 Conclusion and future research
• Acknowledgements
• Abbreviations
• References
• Appendix A: Data tables
• Appendix B: Java classes and methods
• Appendix C: AMPL Files
• Appendix D: Screenshots
• Appendix E: Relational model for the 3-party case implementation
• Empfangene Unterstützung und Hilfe durch Kollegen
• Eidesstattliche Erklärung

Tables

• Table 2-1: The four privacy constellations depending on the data holder's trust
• Table 2-2: Data provision in different services (means of data provision in parenthesis)
• Table 2-3: Typical services in 2-party architectures
• Table 2-4: Typical services in 3-party architectures
• Table 3-1: Threats to confidential business data of ASP customers
• Table 3-2: Difficulty of cryptographic attacks
• Table 3-3: Overview of existing privacy homomorphisms
• Table 3-4: Database query operators on encrypted data
• Table 3-5: Arithmetic operators on encrypted data
• Table 3-6: Technological components of the implementation
• Table 4-1: Compliance rates for diabetes test
• Table 4-2: Average test compliance rates for different HMOs
• Table 4-3: Confidential inner cells and public marginal information
• Table 4-4: Marginal information summarized by an anonymous snooper
• Table 4-5: Inferred intervals for the initial running example
• Table 4-6: Protection intervals for HMO₂
• Table 4-7: Underlying information for snooping HMO₁
• Table 4-8: Inferred intervals by HMO₁ with insider information
• Table 4-9: Interval inferences at different tolerance levels
• Table 4-10: Original (above) and aggregated (below) Census tables
• Table 4-11: Data utility of marginal information
• Table 4-12: A sample dissemination strategy
• Table 4-13: Adaptation of the dissemination strategy
• Table 4-14: Critical dual prices for published marginal data elements
• Table 4-15: Technological components of the implementation
• Table 0-1: Creation times and disk space for the unencrypted and the encrypted employee table
• Table 0-2: Creation times and disk space for the unencrypted and the encrypted monthly_account table
• Table 0-3: Methods in class PHTest
• Table 0-4: Methods in class ServiceProvider
• Table 0-5: Methods in class Main
• Table 0-6: AMPL Files

Images

• Figure 1-1: Different scope of data holders and service users
• Figure 1-2: Two important cases of interaction between data holder and service user
• Figure 1-3: Structure of the dissertation
• Figure 2-1: Input data and provided service
• Figure 2-2: Confidential data flow in 2-party services
• Figure 2-3: Confidential data flow in 3-party services
• Figure 3-1: A sketch of the proposed service architecture
• Figure 3-2: Steps of the proposed service architecture
• Figure 3-3: The basic idea of a privacy homomorphism
• Figure 3-4: Encryption procedure
• Figure 3-5: Decryption procedure
• Figure 3-6: Sketch of the implementation
• Figure 3-7: Service execution time with regard to encryption key length
• Figure 3-8: Table creation time with regard to encryption key length
• Figure 3-9: Table size with regard to encryption key length
• Figure 3-10: Implementation via plug-ins (left) and via proxy server (right)
• Figure 4-1: 2-party case vs. 3-party case (dashed line)
• Figure 4-2: A driver underlying the creation of healthcare initiatives Source: [PHC4, 2002]
• Figure 4-3: Privacy concerns of data providers for chronic disease reports
• Figure 4-4: A security mediator for healthcare
• Figure 4-5: Detecting interval inference
• Figure 4-6: Data perturbation (a) vs. query restriction (b)
• Figure 4-7: Random data perturbation with ε-δ-Gaussian Source: [Li,et al., 2002]
• Figure 4-8: Generalization and suppression for purposes of aggregation
• Figure 4-9: The audit & aggregate methodology
• Figure 4-10: Dissemination strategies and corresponding mathematical programming problems for confidential cells
• Figure 4-11: Pseudo-code for Method-IC
• Figure 4-12: Reducing data utility after suppressing all values of a category
• Figure 4-13: A sketch of Method-VS
• Figure 4-14: Pseudo-code for Method-VS
• Figure 4-15: Sketch of the implementation
• Figure 4-16: Dissemination strategies and inferred intervals for different protection policies
• Figure 4-17: Total average relative error (TARE)
• Figure 4-18: Average relative column error (ARE_col)
• Figure 4-19: Table size vs. ratio of inferred cells for different protection policies
• Figure 4-20: Skew in raw data vs. ratio of inferred cells
• Figure 5-1: The R-U confidentiality map for the disclosure limitation method topcoding with varying parameters Source: [Duncan,et al., 2001]
• Figure 5-2: R-U confidentiality maps for all HMOs
• Figure 5-3: Variance of the disclosure risk threshold in the R-U confidentiality map
• Figure 5-4: Privacy attitudes of online users
• Figure 4-16: Dissemination strategies and inferred intervals for different protection policies:
• Figure 4-17: Total average relative error (TARE)
• Figure 4-18: Average relative column error (ARE_col)
• Figure 4-19: Table size vs. ratio of inferred cells for different protection policies
• Figure 5-2: R-U confidentiality maps for all HMOs
• Figure 0-1: AMPL script file
• Figure 0-2: AMPL model file
• Figure 0-3: Screenshot from the adapted Java interface for AMPL
• Figure 0-4: Screenshot of "audit and aggregate", Method-IC
• Figure 0-5: Screenshot of "audit and aggregate", Method-VS
• Figure 0-6: Relational model for the 3-party case