Motivation

Es ist im Allgemeinen nicht sinnvoll, bei kryptologischen Verfahren von „Sicherheit“ zu sprechen, ohne diese genauer zu qualifizieren. Ein Sicherheitsbegriff besagt, dass ein Angreifer ein bestimmtes Ziel nicht erreichen kann. Die Definition besteht also aus zwei Teilen: Einem Angreifer mit genau beschriebenen Fähigkeiten und dem Sicherheitsziel. Ciphertext indistinguishability (IND) ist ein Sicherheitsziel, nämlich dass es einem Angreifer nicht möglich sein soll, zwischen der Verschlüsselung zweier beliebiger Klartexte gleicher Länge zu unterscheiden (die Verschlüsselungen zweier Klartexte unterschiedlicher Länge können sich durch die Länge des Chiffrats unterscheiden, daher wird die Geheimhaltung der Länge des Klartextes im Allgemeinen nicht gefordert). Damit das auch bei ungünstiger Wahl der Klartexte zutrifft, darf der Angreifer sich zwei Klartexte aussuchen, von denen einer verschlüsselt wird. Dazu können verschiedene Angreiferstärken definiert werden. In der Regel wird der Angreifer in seiner Laufzeit beschränkt, um zu verhindern, dass er den ganzen Schlüsselraum durchsucht oder Aufgaben löst, die in der realen Welt, wo Rechenleistung nicht unbegrenzt verfügbar ist, praktisch unlösbar sind. Bei einem asymmetrischen Verschlüsselungsverfahren muss zudem immer angenommen werden, dass der Angreifer den öffentlichen Schlüssel kennt. Damit kann er selbst beliebige Klartexte seiner Wahl verschlüsseln und mit dem Geheimtext vergleichen, um so etwas über den unbekannten Klartext zu lernen. Dieser Angriff heißt Chosen-plaintext Angriff (CPA). Ein Verschlüsselungsverfahren hat also das Sicherheitsniveau IND-CPA (ciphertext indistinguishability under chosen plaintext attacks), wenn es keinem CPA-Angreifer gelingen kann, das Ziel IND zu erreichen, also die Geheimtexte zweier selbstgewählter Klartexte zu unterscheiden.

Definition

Um das formal auszudrücken, wird das Experiment IND-CPA definiert, das zwischen zwei probabilistischen Algorithmen mit polynomialer (in einem Sicherheitsparameter ${\displaystyle k}$) Laufzeitbeschränkung, dem Angreifer A und der Umgebung U, in fünf Schritten abläuft.

1. Zuerst erzeugt die Umgebung zu dem gegebenen Sicherheitsparameter ${\displaystyle k}$ ein Schlüsselpaar aus einem geheimen und einem öffentlichen Schlüssel. Der Angreifer erhält den öffentlichen Schlüssel.
2. Nun darf der Angreifer beliebige Berechnungen ausführen. Am Ende dieses Schritts muss er zwei Klartexte gleicher Länge ${\displaystyle M_{0}}$ und ${\displaystyle M_{1}}$ ausgeben.
3. Die Umgebung zieht ein zufälliges Bit ${\displaystyle b}$ und verschlüsselt ${\displaystyle M_{b}}$. Diesen Geheimtext erhält nun der Angreifer.
4. Der Angreifer darf wiederum beliebige Berechnungen oder Verschlüsselungen ausführen. Am Ende gibt er ein Bit ${\displaystyle b'}$ aus.
5. Falls ${\displaystyle b=b'}$, so gibt die Umgebung „1“ aus, sonst „0“.

Falls die Umgebung eine „1“ ausgibt, hat der Angreifer richtig geraten. Ein Angreifer, der im vierten Schritt unabhängig von allem, was vorher passiert ist, ein Zufallsbit zieht und es ausgibt, liegt mit Wahrscheinlichkeit 1/2 richtig. Ein Verschlüsselungsverfahren wird IND-CPA sicher genannt, wenn kein Angreifer eine Erfolgswahrscheinlichkeit hat, die wesentlich höher als 1/2 liegt, wenn also ${\displaystyle Pr[U=1]-1/2}$ vernachlässigbar klein ist (wenn sie für jedes Polynom ${\displaystyle p}$ ab einer bestimmten Größe von ${\displaystyle k}$ kleiner bleibt als ${\displaystyle 1/p(k)}$). Ein vernachlässigbarer Unterschied muss zugelassen werden, weil es für einen Angreifer sehr leicht ist, seine Erfolgswahrscheinlichkeit über 1/2 zu steigern: Er rät einfach einen geheimen Schlüssel und versucht damit den Geheimtext zu entschlüsseln. Die Erfolgswahrscheinlichkeit dabei ist sehr klein, aber größer als 0. Es ist bei der Definition wichtig, dass über den Angreifer bis auf seine Laufzeitbeschränkung keinerlei Annahmen getroffen werden.

Der Begriff IND-CPA taucht schon 1984 bei Goldwasser und Micali unter dem Namen „polynomiale Sicherheit“ (polynomial security) auf. Die oben gegebene Definition ist formal nicht ganz korrekt, weil ein Algorithmus in der Informatik nach der Ausgabe stoppt. Ein Angreifer besteht also aus zwei Algorithmen, von denen der erste die zwei Klartexte und seinen Zustand ausgibt. Der zweite erhält als Eingabe die beiden Klartexte, den Zustand und den Geheimtext und gibt ein Bit aus. Durch die Übergabe des Zustandes kann der zweite Algorithmus aber auch als Fortsetzung des ersten verstanden werden.