Das Leftover Hash Lemma und seine Anwendung in der Kryptographie

Abstract

Das Leftover Hash Lemma ist ein in verschiedenen Bereichen der Kryptographie verwendeter Hilfsatz, welcher eine Aussage über den durch Anwendung universeller Hashfamilie erzeugten Quasizufall trifft. Diese Arbeit verwendet eine allgemeine Formulierung des Leftover Hash Lemmas für universelle Hashfamilien mit einer maximalen Kollisionswahrscheinlichkeit 𝛿, welche in verschiedenen Anwendungen eingebracht werden kann. Es werden alle nötigen mathematischen Grundlagen dargelegt, um eine in sich geschlossene Darstellung des Themas zu ermöglichen. Daraufhin wird das Leftover Hash Lemma bewiesen und explizit in zwei verschiedenen Kontexten angewandt. Die erste Anwendung beschäftigt sich mit der Privacy Amplification beim Austausch eines symmetrischen Schlüssels. Das betrachtete Szenario wird genau beschrieben und anhand der gegebenen Entropien wird mithilfe des Leftover Hash Lemmas argumentiert, dass ein Angreifer nur exponentiell kleine Information über den geheimen Schlüssel besitzt. Als weitere Anwendung wird das gitterbasierte Regev-Kryptosystem betrachtet. Dieses wird definiert und seine Korrektheit gezeigt. Um schließlich die Sicherheit des Kryptosystems zu beweisen, wird eine Reduktion auf das Decisional Learning With Errors-Problem durchgeführt, welche eine Verwendung des Leftover Hash Lemmas beinhaltet.