Beim Entwurf von Kryptosystemen versucht man deren Sicherheit mittels Reduktionen auf gewisse mathematische Basisprobleme zu gründen. Wer das Kryptosystem brechen kann ist damit auch in der Lage, das Basisproblem zu lösen. Wird dem Angreifer nicht zugestanden, das Basisproblem zu lösen, gilt das Kryptosystem als sicher. Ein Problem dieser Beweisführung ist jedoch, dass Basisprobleme meist nur im Allgemeinen schwer sind. Bei der Reduktion von Kryptosystemen treten jedoch typischerweise durchschnittliche Probleminstanzen auf, die unter Umständen sehr viel leichter zu lösen sind.Deshalb erregte das Public-Key Kryptosystem von Ajtai und Dwork einiges an Aufsehen. Ihnen war es erstmals gelungen, eine Worst-Case / Average-Case Äquivalenz zwischen dem Kryptosystem und dem zugrunde liegenden Basisproblem zu zeigen. Ajtai und Dwork beschränkten sich allerdings auf den Reduktionsbeweis. Eine formalere Beschreibung der Annahmen über die Fähigkeiten und Absichten eines potentiellen Angreifers liefern Sicherheitsmodelle. In diesem Buch wird daher untersucht, in welchen Sicherheitsmodellen das Ajtai-Dwork-Kryptosystem als sicher gelten kann.
