Adversarul $A$ schema de pauze $\Pi$ prin generarea unui fel de fals.
Fiecărui fals i se poate atribui o etichetă $i$.
Această etichetă $i$ este ales de adversar, dar există doar un număr polinom de opțiuni pentru $i$.
Algoritmul de reducere poate configura lucrurile să arate exact ca lumea asta $A$ se asteapta.
În plus, algoritmul de reducere poate configura lucrurile cu un anumit $i^*$ în minte, astfel încât dacă adversarul produce un fals a cărui etichetă se întâmplă să fie $i^*$, atunci algoritmul de reducere poate rupe schema cu succes $\Theta$.
Important, și acesta poate fi lucrul care vă lipsește, $A$Viziunea lui asupra lucrurilor este independentă de $i^*$.
Cu alte cuvinte, indiferent de specific $i^*$ reducerea are în vedere, produce întotdeauna o simulare perfect fidelă a lumii care $A$ se asteapta.
Cum ar trebui să aleagă algoritmul de reducere $i^*$?
Nu poate prezice dinainte ce etichetă va avea falsul adversarului.
Deci, în schimb, va alege $i^*$ uniform la întâmplare dintre polinomiile multe alegeri.
De ce funcționează asta?
În cele din urmă, adversarul produce un fals, iar falsul are o etichetă $i$.
Dacă întreaga vedere a adversarului este independentă de alegerea $i^*$, apoi alegerea adversarului de $i$ este independent de alegerea $i^*$.
De cand $i^*$ este distribuit uniform și independent de $i$, putem spune că $\Pr[i=i^*] = \frac{1}{\mbox{# de opțiuni}}$.
În setarea dvs., „eticheta” $i$ a unui fals este (aparent -- am urmat instrucțiunile dvs. de a nu citi de fapt lucrarea) indexul primei interogări de semnare-oracol care se face folosind perioada de timp numită în fals.
Dacă algoritmul de reducere poate prezice care interogare de semnare-oracol va fi prima făcută în perioada de timp a falsului adversarului, atunci va face ceva special ca răspuns la acea interogare (încorporați câteva informații care o vor ajuta să se rupă $\Theta$).
Desigur, nu poate prezice această proprietate a falsului, așa că ghicește.
Sunt doar $q(k)$ posibilități pentru identitatea acestei interogări „speciale”.
În setarea dvs., există și unele avorturi, dar aceasta este o distragere a atenției către întrebarea probabilității reale.
Ceea ce se întâmplă cu adevărat este asta:
Reducerea are succes doar la rupere $\Theta$ când se presupune $i^*$ este egal cu eticheta $i$ de $A$falsul lui.
Autorii de aici spun că reducerea ar putea la fel de bine să renunțe (adică să renunțe) atunci când vede că presupunerea sa va fi greșită.
Ar fi fost bine dacă ar fi scris algoritmul de reducere pentru a nu avorta niciodată și, în schimb, ar fi făcut o „înjunghiere în întuneric” la rupere. $\Theta$ în aceste cazuri.
