Secure outsourcing of IT services in a non-trusted environment [Elektronische Ressource] / von Sergei Evdokimov

Evdokimov Sergei

Sujets

• Informatik
• Management

Informations

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

Extrait

Secure Outsourcing of IT Services in a
Non-Trusted Environment
DISSERTATION
zur Erlangung des akademischen Grades
doctor rerum politicarum
(Dr. rer. pol.)
im Fach Wirtschaftswissenschaft
eingereicht an der
Wirtschaftswissenschaftlichen Fakultät
Humboldt-Universität zu Berlin
von
Herr Dipl.-Math. Sergei Evdokimov
geboren am 15.03.1980 in Minsk
Präsident der Humboldt-Universität zu Berlin:
Prof. Dr. Dr. h.c. Christoph Markschies
Dekan der Wirtschaftswissenschaftlichen Fakultät:
Prof. Oliver Günther, Ph.D.
Gutachter:
1. Prof. Oliver Günther, Ph.D.
2. Prof. Bharat Bhargava, Ph.D.
Tag des Kolloquiums: 5. August 2008Abstract
This thesis considers the possibilities of secure outsourcing of databases
and of content-based routing operations to an untrusted service provider.
We explore the limits of the security that is achievable in these scenarios.
When discussing security, we refer to the state of the art definitions from
cryptography and complexity theory. The key contributions of the thesis are
the following:
- We explore the applicability of cryptographic constructs that allow per-
forming operations over encrypted data, also known as privacy homomor-
phisms, forcreatingprotocolsthatcouldenablesecuredatabaseoutsourcing.
We also describe a framework for secure database outsourcing that is based
on searchable encryption schemes, and prove its correctness and security.
- We describe a new searchable encryption scheme that exceeds existing
analogueswithregardtocertainparameters: comparedtotheexistingworks,
the proposed scheme allows for performing a larger number of operations
over a securely outsourced database and has significantly lower chances of
returning erroneous results of a search.
- We propose an approach for managing discretionary access to securely
outsourced and encrypted databases. Compared to existing techniques, our
approach is applicable to more general scenarios, is simpler and has similar
performance characteristics.
- We examine possibilities of performing a secure content-based routing
by building a formal security model that describes a secure content-based
routing system, evaluate existing approaches against this model, and provide
an analysis of the possibilities for achieving confidentiality when performing
therouting. Comparedtotheexistingworks,whichfailinprovidingcomplete
confidentiality, our security model considers shortcomings of these solutions.
We also describe a content-based routing system that satisfies this model
and to the best of our knowledge is the first of its kind to provide a complete
confidentiality.
Keywords:
Privacy, Security, Confidentiality, Access Control, Outsourcing, Database,
Content-Based RoutingZusammenfassung
IndieserArbeitwerdendieMöglichkeitensichererAusgliederungvonDa-
tenbanken und inhaltsbasiertem Routing an einen nicht voll vertrauenswür-
digen Dienstanbieter betrachtet. Wir untersuchen die Grenzen der Sicher-
heit, die in diesem Szenario erreicht werden können. Sicherheit wird dabei
unter Zuhilfenahme aktueller komplexitätstheoretischer Arbeiten definiert.
Dies ermöglicht die Verwendung formaler Methoden zur Untersuchung der
Bedingungen, unter denen verschiedene Grade von Sicherheit möglich sind.
Die Beiträge dieser Dissertation sind im Einzelnen:
-WiruntersuchendieEignungsog.Privacy-Homomorphismen,welchedie
Ausführung von Operationen auf verschlüsselten Daten erlauben. Dies dient
der Entwicklung von Protokollen zur sicheren Datenbankausgliederung. Wei-
ter beschreiben wir ein allgemeines Framework für sichere Datenbankausglie-
derung, das auf sog. Volltextsuch-Verschlüsselungsverfahren basiert. Ferner
stellen wir einen Beweis für die Sicherheit und Korrektheit vor.
- Wir beschreiben ein neues Volltextsuch-Verschlüsselungsverfahren, das
im Vergleich zu bekannten Arbeiten eine größere Anzahl verschiedener Ope-
rationen für das Datenbank-Outsourcing-Problem ermöglicht und signifikant
niedrigere Fehlerraten hat.
- Wir schlagen einen Ansatz vor, um im Kontext der sicheren Datenbank-
AuslagerungBlanko-ZugriffeaufdieverschlüsseltenDatenzuverwalten.Ver-
glichen mit existierenden Techniken ist unser Ansatz anwendbar auf generel-
lere Szenarien, ist einfacher und hat ähnliche Effizienzeigenschaften.
-WiruntersuchendieMöglichkeitdessichereninhaltsbasiertenRoutings,
in dem wir ein formales Sicherheitsmodell konstruieren, existierende Ansät-
ze in diesem Modell bewerten und eine formale Analyse der Möglichkeit von
Vertraulichkeitdurchführen.UnserSicherheitsmodelldecktdieUnzulänglich-
keiten der bestehenden Ansätze auf. Schließlich beschreiben wir ein inhalts-
basiertes Routingverfahren, welches das Modell erfüllt.
Schlagwörter:
Datenschutz, Sicherheit, Datenvertraulichkeit, Vertraulichkeit,
Zugriffskontrolle, Ausgliederung, Datenbanken, Inhaltsbasiertes RoutingContents
1 Introduction 1
1.1 Secure Outsourcing of IT Services . . . . . . . . . . . . . . . . 1
1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Structure of the Thesis . . . . . . . . . . . . . . . . . . . . . . 4
2 Preliminaries 6
2.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Computation Model . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Random Functions and Permutations . . . . . . . . . . . . . . 8
2.4 Cryptographic Primitives . . . . . . . . . . . . . . . . . . . . . 8
2.5 Provable Security . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.6 Homomorphic Encryption . . . . . . . . . . . . . . . . . . . . 18
3 Secure Database Outsourcing 20
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1.1 Motivation and Problem Statement . . . . . . . . . . . 20
3.1.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . 22
3.1.3 Our Contribution . . . . . . . . . . . . . . . . . . . . . 24
3.2 A Security Analysis of Database Privacy Homomorphisms . . 26
3.2.1 Known Database Privacy Homomorphisms . . . . . . . 26
3.2.2 Security Levels and Limitations . . . . . . . . . . . . . 27
3.3 A Database Privacy Homomorphism Preserving Exact Selects 34
3.3.1 Basic Idea . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3.2 Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3.3 Homomorphism . . . . . . . . . . . . . . . . . . . . . . 35
3.3.4 Defining the Database Privacy Homomorphism . . . . 36
3.3.5 Security Proof . . . . . . . . . . . . . . . . . . . . . . . 37
3.3.6 Example . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.3.7 Boolean Expressions . . . . . . . . . . . . . . . . . . . 39
3.3.8 Complexity . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4 New Searchable Encryption Scheme . . . . . . . . . . . . . . 41
iv3.4.1 Basic Idea . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.4.2 Construction . . . . . . . . . . . . . . . . . . . . . . . 41
3.4.3 Operations on Encrypted Relational Databases . . . . 44
3.4.4 Security Analysis . . . . . . . . . . . . . . . . . . . . . 50
3.4.5 Indexing and Hashing . . . . . . . . . . . . . . . . . . 58
3.4.6 Comments on the Scheme Described in Yang et al. . . 60
3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4 Access Control to Outsourced Databases 63
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.1.1 Motivation and Problem Statement . . . . . . . . . . . 63
4.1.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . 65
4.1.3 Our Contribution . . . . . . . . . . . . . . . . . . . . . 67
4.2 Read-Write Access Control . . . . . . . . . . . . . . . . . . . . 68
4.2.1 Basic Idea . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.2.2 Read Access Control in a Linear Scenario . . . . . . . . 69
4.2.3 Read Access Control in a General Scenario . . . . . . . 70
4.2.4 Performance Tests . . . . . . . . . . . . . . . . . . . . 73
4.2.5 Write Access Control . . . . . . . . . . . . . . . . . . . 76
4.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5 Secure Outsourcing of Content-Based Routing Operations 78
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
5.1.1 Motivation and Problem Statement . . . . . . . . . . . 78
5.1.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . 80
5.1.3 Our Contribution . . . . . . . . . . . . . . . . . . . . . 82
5.2 Confidentiality in a Content-Based Routing System . . . . . . 83
5.2.1 Basic Idea . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.2.2 Definition of a Content-Based Routing System . . . . . 84
5.2.3 Confidentiality . . . . . . . . . . . . . . . . . . . . . . 88
5.2.4 Limitations for Confidential Content-Based Routing
Systems . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.2.5 Relaxed Model . . . . . . . . . . . . . . . . . . . . . . 98
5.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
6 Conclusion 102
vList of Figures
1.1 Possible ASP architectures . . . . . . . . . . . . . . . . . . . . 2
3.1 Secure database outsourcing . . . . . . . . . . . . . . . . . . . 21
3.2 Architecture of a securely outsourced database management
system . . . . . . . . . . . . . . . . . . . . .