În Introducerea lui Katz în criptografia modernă, există mai multe probleme dificile și pentru fiecare problemă, există un experiment, în care un algoritm generează o instanță de problemă și un alt algoritm rezolvă instanța problemei. De exemplu, luați în considerare problema logaritmului discret din 9.3.2:
Fie GG un algoritm generator de grup care pentru fiecare n, generează (G,q,p).
Fie A un algoritm pentru rezolvarea problemei.
Experimentul cu logaritm discret DLog_{A,GG} (n):
- Rulați GG(1^n ) pentru a obține (G , q, g), unde G este un grup ciclic de ordinul q (cu kqk = n) și g este un generator de G .
- Alegeți o uniformă h în G.
- A este dat G, q, g, h și iese x în Z_q.
- Ieșirea experimentului este definită a fi 1 dacă g^x = h și 0 în caz contrar.
DEFINIȚIA 9.63 Spunem că problema logaritmului discret este dificilă în raport cu GG dacă pentru toți algoritmii probabilistici de timp polinomial A există o funcție neglijabilă negl astfel încât Pr[DLog
A,GG(n) = 1] = negl(n).
Este acest tip de definiție și analiză a durității unei probleme, care implică conceptul de „experiment”, o analiză standard până la complexitate a problemelor în general (nu doar în criptografie)?
Cărțile despre analiza complexității problemelor folosesc acest tip de definiție și analiza durității unei probleme?
Mulțumiri.
