Struttura di una riduzione

Assunzione: il problema $X$ è difficile → non può essere risolto con algoritmi PPT

Vogliamo provare che la costruzione $\Pi$ è sicura

1. Fissiamo un Adv $A$ PPT che attacca $\Pi$ con probabilità di successo $\epsilon(n)$

2. Costruiamo $A'$ PPT (riduzione) che risolve $X$ usando $A$ come subroutine

   $A'$ non conosce il funzionamento interno di $A$, sa solo che serve ad attaccare $\Pi$

   Quindi data $x$ istanza di $X$, $A'$ simula per $A$ un’istanza della costruzione $\Pi$ in modo tale che:

   1. $A$ pensa di star interagendo con $\Pi$ → ha la stessa vista che quando interagisce realmente con $\Pi$
   2. se $A$ ha successo nel rompere $\Pi$ sull’istanza che ha ricevuto da $A'$ allora $A'$ risolve l’istanza $x$ del problema $X$ che ha ricevuto in input con probabilità almeno $\frac{1}{p(n)}$

3. Le condizioni 2.1 e 2.2 implicano che

   • $A'$ risolve $X$ con probabilità almeno $\frac{\epsilon(n)}{p(n)}$, pertanto se $\epsilon(n)$ è non trascurabile anche $\frac{\epsilon(n)}{p(n)}$ è non trascurabile
   • $A'$ è efficiente se $A$ è efficiente

4. Data l’assunzione di difficoltà sul problema $X$ concludiamo che nessun Adv $A$ PPT può avere successo nel rompere $\Pi$ con probabilità non trascurabile → $\Pi$ è computazionalmente sicuro