Folgende Aussagen über die Existenz von kryptographischen Basisfunktionen sind im komplexitätstheoretischen Sinne im wesentlichen äquivalent:
Aus A folgt D: wurde eben gezeigt.
Von D nach A kommt man z. B. durch die Bitstrom-Verschlüsselung.
Von A nach C kommt man, wie unter »Hash-Funktionen« erwähnt, durch Cipher Block Chaining (CBC) (wobei die Kollisionsfreiheit evtl. nur mit Zusatzbedingungen erfüllbar ist).
Von C nach B braucht man nur die Hash-Funktion auf Zeichenketten der Länge des Hash-Wertes einzuschränken. (Hier ist eigentlich eine genauere Betrachtung nötig, wenn man die Bijektivität der Einweg-Funktion haben will.)
Von B nach A (MDC = Message Digest Cryptography, z. B. nach E. Backus) kommt man etwa (im Ansatz) so:
F(a, k) = f(a) XOR f(k).Ist nämlich der Klartext a zum Geheimtext c = F(a, k) bekannt, so ist f(k) = c XOR f(a) bekannt, die Bestimmung von k also auf die Umkehrung von f reduziert.
Aus D folgt E ist ein Satz von Yao.