Effiziente Ähnlichkeitssuche über verschlüsselte Daten

In den letzten Jahren wurden aufgrund der attraktiven Eigenschaften des Cloud-Computing große Datenmengen in der Cloud gespeichert. Obwohl cloudbasierte Dienste viele Vorteile bieten, sind Datenschutz und Sicherheit sensibler Daten große Anliegen. Um diese Bedenken zu mildern, ist es wünschenswert, sensible Daten in verschlüsselter Form auszulagern. Verschlüsselte Speicherung schützt die Daten vor illegalem Zugriff, erschwert jedoch einige grundlegende, aber wichtige Funktionen wie die Suche in den Daten. Um die Suche über verschlüsselte Daten zu ermöglichen, ohne die Privatsphäre zu kompromittieren, wurden in der Literatur beträchtliche Mengen an durchsuchbaren Verschlüsselungsschemata vorgeschlagen. Fast alle von ihnen behandeln jedoch die exakte Abfrageübereinstimmung, nicht jedoch die Ähnlichkeitsübereinstimmung, die eine entscheidende Anforderung für Anwendungen in der realen Welt ist. Obwohl einige ausgeklügelte kryptografische Techniken auf der sicheren Multi-Party-Berechnung für Ähnlichkeitstests zur Verfügung stehen, sind sie rechnerisch intensiv und skalieren nicht für große Datenquellen. In diesem Papier schlagen wir ein effizientes Schema für die Ähnlichkeitssuche über verschlüsselte Daten vor. Dazu nutzen wir einen modernen Algorithmus für die schnelle Suche nach nahegelegenen Nachbarn in hochdimensionalen Räumen, der als lokalitätsempfindliches Hashing bezeichnet wird. Um die Vertraulichkeit der sensiblen Daten zu gewährleisten, bieten wir eine strenge Sicherheitsdefinition und beweisen die Sicherheit des vorgeschlagenen Schemas unter der gegebenen Definition. Darüber hinaus präsentieren wir eine Anwendung des vorgeschlagenen Schemas in der realen Welt und verifizieren die theoretischen Ergebnisse mit empirischen Beobachtungen auf einem realen Datensatz.