Data confidentiality and reputation schemes in distributed information systems [Elektronische Ressource] / von Matthias Fischmann

Fischmann Matthias

Sujets

• Informatik

Informations

• Publié par: humboldt-universitat_zu_berlin
• Publié le: 01 janvier 2008
• Nombre de lectures: 11
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

Data Confidentiality and Reputation Schemes
in Distributed Information Systems
DISSERTATION
zur Erlangung des akademischen Grades
doctor rerum politicarum
(Dr. rer. pol.)
im Fach Wirtschaftsinformatik
eingereicht an der
Wirtschaftswissenschaftlichen Fakultät
Humboldt-Universität zu Berlin
von
Herr Dipl.-Inform. Matthias Fischmann
geboren am 4. Januar 1973 in Tübingen
Präsident der Humboldt-Universität zu Berlin:
Prof. Dr. Dr. h.c. Christoph Markschies
Dekan der Wirtschaftswissenschaftlichen Fakultät:
Prof. Oliver Günther, PhD
Gutachter:
1. Prof. Oliver Günther, PhD
2. Prof. Dr. Bettina Berendt
eingereicht am: 4. Februar 2008
Tag der mündlichen Prüfung: 23. Mai 2008Abstract
In this thesis we discuss two demanding problems from the field of com-
puter and communication security that involve trust.
The first is known as the database service provider problem: A database
owner wants a database service provider (DSP) to host her database. She
only trusts this DSP to a limited extent, so she does not want to rely solely
on contractual solutions. It is therefore necessary to enforce confidentiality
of her data by technical means. The second problem concerns a (potentially
very large) number of network nodes in a peer-to-peer (P2P) environment.
Both problems are notoriously hard because, other than in traditional
computer security problems, the adversary has a lot of control over the sit-
uation. The untrusted DSP needs to be able to process the data without
learning anything about it, which seems to be a contradiction. In P2P appli-
cations it is desirable that nodes can join anonymously, but anonymity makes
it easy to spread false reputation information. A node that enters a P2P ap-
plication network for the first time needs to trust the claimed observations
of other nodes, independent of the rate of malicious behaviour.
Our findings are not perfect solutions, but nevertheless instructive in sev-
eral ways: We propose relaxed, but still practically useful, notions of security
for the DSP problem; we identify theoretical limitations of the DSP solution
space; and we gradually reduce the impact of adversarial behaviour in P2P
reputation systems using heuristic methods. As a side effect of our work,
we present a special-purpose framework for simulation of P2P reputation
systems that can be used to compare and fine-tune previous and upcoming
work.
Keywords:
confidentiality, databases, service provider, reputationZusammenfassung
Diese Arbeit betrachtet zwei anspruchsvolle Probleme aus dem Bereich
Computer- und Kommunikationssicherheit und Vertrauen.
Beim Datenbank-Serviceprovider-Problem moechte ein Anwender seine
Datenbank an einen Datenbank-Serviceprovider (DSP) uebergeben, damit
dieser sie betreiben und ihm zur Verfuegung stellen kann. Er vertraut diesem
DSP, und damit auch vertraglichen Abmachungen, nur bedingt und muss
die Vertraulichkeit seiner Daten durch technische Massnahmen sicherstellen.
Das zweite Problem ist das Verbreiten verlaesslicher Reputationsinformation
ueber eine (moeglicherweise sehr grosse) Anzahl von Netzwerk-Knoten in
einer Peer-to-Peer-Umgebung (P2P).
Beide Probleme straeuben sich hartnaeckig gegen einfache Loesungen. Im
Gegensatz zu traditionellen Sicherheitsproblemen in der Informatik hat der
Gegner in beiden ein hohes Mass an Kontrolle ueber die Situation. Der nicht
ausreichend vertrauenswuerdige DSP muss in der Lage sein, die Daten seines
Kunden zu verarbeiten, ohne etwas ueber sie zu lernen, was intuitiv wie ein
Widerspruch erscheint. In P2P-Anwendungen ist es wuenschenswert, dass
Knoten anonym beitreten und jederzeit wieder austreten koennen, aber die-
se Anonymitaet erleichtert es, falsche Reputationsinformation zu verbreiten.
Ein Knoten, der erstmalig in ein P2P-Netzwerk eintritt, muss den behaup-
teten Beobachtungen anderer Knoten vertrauen.
Die Resultate dieser Arbeit sind keine Idealloesungen, und dennoch auf-
schlussreich in mehrerlei Hinsicht: Es werden gelockerte, aber immer noch
nuetzlicheSicherheitsbegriffefuerdasDSP-Problemvorgeschlagen;eswerden
theoretische Grenzen des DSP-Loesungsraums gezogen; und die Auswirkung
feindseligen Verhaltens in P2P-Reputationssystemen wird durch heuristische
Methoden reduziert. Ein Nebeneffekt unserer Arbeit ist ein speziell fuer Re-
putationssysteme in P2P-Netzwerken geeignetes Simulations-Tool, das zum
Vergleich und zum Fine-Tuning bestehender und zukuenftiger Forschungsar-
beiten genutzt werden kann.
Schlagwörter:
Vertraulichkeit, Datenbanken, Service-Provider, ReputationivContents
1 Two Approaches to Information Security 1
I Homomorphic Encryption of Databases 7
2 Introduction 9
2.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Database Foundations . . . . . . . . . . . . . . . . . . . . . . 12
2.2.1 Relational Algebra . . . . . . . . . . . . . . . . . . . . 12
2.2.2 SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.3 Object-Oriented Databases . . . . . . . . . . . . . . . . 17
2.3 Cryptographic Foundations . . . . . . . . . . . . . . . . . . . 18
2.3.1 Probability Theory . . . . . . . . . . . . . . . . . . . . 18
2.3.2 Algorithms, Complexity Theory, and Oracles . . . . . . 20
2.3.3 Encryption Schemes . . . . . . . . . . . . . . . . . . . 25
2.3.4 Security Definitions . . . . . . . . . . . . . . . . . . . . 27
2.3.5 Other Cryptographic Building Blocks . . . . . . . . . . 39
2.3.6 Homomorphic Cryptography . . . . . . . . . . . . . . . 49
3 Related Work 55
3.1 Homomorphic Encryption Schemes . . . . . . . . . . . . . . . 55
3.1.1 ATE: Homomorphic Encryption in Databases . . . . . 55
3.1.2 Field Arithmetics . . . . . . . . . . . . . . . . . . . . . 62
3.1.3 Full-Text Search . . . . . . . . . . . . . . . . . . . . . 66
3.1.4 Homomorphic Signatures . . . . . . . . . . . . . . . . . 71
3.2 Homomorphic Security Definitions . . . . . . . . . . . . . . . . 72
3.2.1 Small and Finite Operand Domains . . . . . . . . . . . 72
3.2.2 Full-Text Search . . . . . . . . . . . . . . . . . . . . . 75
3.2.3 Relational Algebra . . . . . . . . . . . . . . . . . . . . 76
3.3 Code Obfuscation . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.3.1 Proposed Solutions . . . . . . . . . . . . . . . . . . . . 80
v3.3.2 Impossibility Results . . . . . . . . . . . . . . . . . . . 83
3.4 Private Information Retrieval . . . . . . . . . . . . . . . . . . 90
3.5 Secure Co-Processors . . . . . . . . . . . . . . . . . . . . . . . 92
3.6 Data Mining and Privacy . . . . . . . . . . . . . . . . . . . . . 95
3.6.1 Negative Databases . . . . . . . . . . . . . . . . . . . . 95
3.6.2 Privacy-Preserving Data Mining . . . . . . . . . . . . . 96
4 Adversary Models and Analysis 99
4.1 Heuristic Security: of ATE . . . . . . . . . . . . . . . 99
4.1.1 Order Revelation through Range Queries . . . . . . . . 101
4.1.2 Small Attribute Domain Size . . . . . . . . . . . . . . . 104
4.1.3 On the Impact of Aggregation . . . . . . . . . . . . . . 107
4.1.4 Noise . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
4.2 Partial Security: Analysis of Full-Text Search . . . . . . . . . 111
4.2.1 The Problem . . . . . . . . . . . . . . . . . . . . . . . 112
4.2.2 Partial Security . . . . . . . . . . . . . . . . . . . . . . 115
4.2.3 A Note on Multi-Message Security . . . . . . . . . . . 116
4.3 The “Good Server Going Bad” Model . . . . . . . . . . . . . . 117
4.3.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 118
4.3.2 Cryptographic Schemes . . . . . . . . . . . . . . . . . . 122
4.3.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . 127
4.4 Private Information Retrieval, revisited . . . . . . . . . . . . . 129
4.5 A Note on Data Integrity . . . . . . . . . . . . . . . . . . . . . 130
5 Security and Performance Bounds 133
5.1 Strong Security Definitions . . . . . . . . . . . . . . . . . . . . 133
5.2 Relational Algebra, Code Obfuscation . . . . . . . . . . . . . . 136
5.2.1 Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . 137
5.2.2 Turing Machines . . . . . . . . . . . . . . . . . . . . . 140
5.2.3 Reduction Proofs . . . . . . . . . . . . . . . . . . . . . 144
5.3 Open Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 148
5.3.1 Performance . . . . . . . . . . . . . . . . . . . . . . . . 149
5.3.2 Covert Channels and Advanced Cryptanalysis . . . . . 150
6 Conclusions 153
II Trust and Reputation in P2P Networks 157
7 Introduction 159
7.1 Concepts and Outline . . . . . . . . . . . . . . . . . . . . . . . 159
vi7.2 Application Scenarios . . . . . . . . . . . . . . . . . . . . . . . 163
7.3 The Adversary . . . . . . . . . . . . . . . . . . . . . . . . . . 167
7.4 Monetary Incentives vs. Reputation . . . . . . . . . . . . . . . 169
7.5 Game Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
8 Building Blocks and Related Work 177
8.1 Identity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
8.1.1 Forms of Identity Abuse . . . . . . . . . . . . . . . . . 179
8.1.2 Blind Signatures and Trusted Third Parties . . . . . . 182
8.1.3 Hash Cash and Enforcing Exclusivity . . . . . . . . . . 187
8.1.4 Graph-Theoretical Approaches . . . . . . . . . . . . . . 190
8.2 Routing . . . . . . . . . . . . . . . . . . . .