In der Kryptographie ist ein Hardcore-Prädikat einer Einwegfunktion f ein Prädikat b (d. h. eine Funktion, deren Ausgabe ein einzelnes Bit ist), das leicht (als Funktion von x ) zu berechnen ist, aber schwer zu berechnen ist, wenn f(x) gegeben ist . Formal ausgedrückt: Es gibt keinen probabilistischen Polynomialzeitalgorithmus (PPT-Algorithmus) , der b(x) aus f(x) mit einer Wahrscheinlichkeit berechnet , die deutlich größer als 0,5 bei zufälliger Wahl von x ist . [ 1 ] : 34 Anders ausgedrückt: Wenn x gleichverteilt zufällig gewählt wird, kann ein PPT-Angreifer, gegeben f(x) , das Hardcore-Bit b(x) und ein gleichverteilt zufälliges Bit nur mit vernachlässigbarem Vorteil gegenüber der Länge von x unterscheiden . [ 2 ]

Eine Hard-Core-Funktion lässt sich analog definieren. Das heißt, wenn x gleichverteilt zufällig gewählt wird, kann jeder PPT-Algorithmus bei gegebenem f(x) den Hard-Core-Funktionswert h(x) und gleichverteilt zufällige Bits der Länge |h(x)| nur mit vernachlässigbarem Vorteil gegenüber der Länge von x unterscheiden . [ 3 ] [ 4 ]

Ein Hard-Core-Prädikat erfasst „im konzentrierten Sinne“ die Schwierigkeit der Invertierung von f .

Während die Invertierung einer Einwegfunktion schwierig ist, gibt es keine Garantie dafür, dass sich aus dem Bild f(x) partielle Informationen über das Urbild c berechnen lassen . Beispielsweise wird RSA zwar als Einwegfunktion vermutet, doch lässt sich das Jacobi-Symbol des Urbilds leicht aus dem des Bildes berechnen. [ 1 ] : 121

Es ist klar, dass eine injektive Funktion , die ein festes Prädikat besitzt, eine Einwegfunktion sein muss. Oded Goldreich und Leonid Levin (1989) zeigten, wie jede Einwegfunktion trivial so modifiziert werden kann, dass sie eine Einwegfunktion mit einem bestimmten festen Prädikat besitzt. [ 5 ] Sei f eine Einwegfunktion. Wir definieren g(x,r) = (f(x), r), wobei die Länge von r der Länge von x entspricht . x <sub> j</sub> bezeichne das j -te Bit von x und r <sub>j</sub> das j -te Bit von r . Dann

ist ein Kernprädikat von g . Beachten Sie, dass b(x, r) = < x, r > gilt, wobei <·, ·> das Standard- Skalarprodukt auf dem Vektorraum ( Z² ) ⁿ bezeichnet . Dieses Prädikat ist aufgrund von Rechenproblemen ein Kernprädikat; es ist also nicht schwer zu berechnen, weil g(x, r) informationstheoretisch verlustbehaftet ist . Vielmehr existiert, wenn ein Algorithmus dieses Prädikat effizient berechnet, auch ein anderer Algorithmus, der f effizient invertieren kann.

Eine ähnliche Konstruktion liefert eine Hard-Core-Funktion mit O(log |x|) Ausgabebits. Sei f eine starke Einwegfunktion. Wir definieren g(x, r) = (f(x), r), wobei | r | = 2| x |. Wir wählen eine Längenfunktion l(n) = O(log n) st l(n) ≤ n .

Dann ist h(x, r)  := b 1 (x, r) b 2 (x, r) ... b l(|x|) (x, r) eine Hard-Core-Funktion mit Ausgabelänge l(|x|) . [ 6 ]

Es kommt vor, dass ein einzelnes Bit der Eingabe x ein fester Bestandteil ist. Beispielsweise ist jedes Bit der Eingaben der RSA-Funktion ein fester Bestandteil von RSA, und Blöcke von O(log |x|) Bits von x sind in Polynomialzeit nicht von zufälligen Bitfolgen zu unterscheiden (unter der Annahme, dass die RSA-Funktion schwer invertierbar ist). [ 7 ]

Hartkernprädikate ermöglichen die Konstruktion eines Pseudozufallsgenerators aus jeder Einwegpermutation . Wenn b ein Hartkernprädikat einer Einwegpermutation f ist und s ein Zufallsgenerator ist, dann

ist eine pseudozufällige Bitfolge, wobei f <sub>n</sub> die n-te Iteration der Anwendung von f auf s bezeichnet und b das in jeder Runde n generierte Hardcore-Bit ist . [ 1 ] : 132

Hartkernprädikate von Einwegpermutationen mit Falltür (bekannt als Falltürprädikate ) können zur Konstruktion semantisch sicherer Public-Key-Verschlüsselungsverfahren verwendet werden . [ 1 ] : 129

Siehe auch

  • Listendekodierung (beschreibt die Listendekodierung; der Kern der Goldreich-Levin-Konstruktion von Hard-Core-Prädikaten aus Einwegfunktionen kann als Algorithmus zur Listendekodierung des Hadamard-Codes betrachtet werden ).

Referenzen

  1. ^ a b c d Goldwasser, S. und Bellare, M. „Lecture Notes on Cryptography“. Archiviert am 21.04.2012 im Internet Archive . Sommerkurs Kryptographie, MIT, 1996–2001
  2. ^ Definition 2.4 in Lindell, Yehuda. „Foundations of Cryptography 89-856“ (PDF) . Informatik, Bar-Ilan-Universität . Bar-Ilan-Universität. Archiviert vom Original (PDF) am 19. Januar 2022. Abgerufen am 11. Januar 2016 .
  3. ^ Goldreichs FoC, Band 1, Definition 2.5.5.
  4. ^ Definition 3 in Holenstein, Thomas; et al. „Complete Classification of Bilinear Hard-Core Functions“ (PDF) . IACR eprint . IACR . Abgerufen am 11. Januar 2016 .
  5. ^ O. Goldreich und LA Levin, Ein Hard-Core-Prädikat für alle Einwegfunktionen , STOC 1989, S. 25–32.
  6. ^ Goldreichs FoC, Band 1, Satz 2.5.6.
  7. ^ J. Håstad , M. Naslund, Die Sicherheit aller RSA- und diskreten Log-Bits (2004) : Journal of the ACM, 2004.
  • Oded Goldreich, Grundlagen der Kryptographie Band 1: Grundlegende Werkzeuge , Cambridge University Press, 2001.