„Instanță dificilă” înseamnă probleme greu de rezolvat, cum ar fi ipoteza DDH (Decisional Diffie Hellman)?
Practic da, înseamnă un specific instanță a unei probleme grele - în cazul DDH, de exemplu, înseamnă o provocare anume $(g^a, g^b, g^c)$.
Reducerile funcționează arătând că, dacă aveți o metodă/algoritm pentru rezolvarea unei probleme (de obicei, întreruperea unui protocol), atunci puteți utiliza același algoritm pentru a rezolva problema dificilă precum DDH. Acest lucru demonstrează că ruperea protocolului este cel puțin la fel de grea ca ruperea DDH. Și dimpotrivă, dacă DDH este greu, atunci protocolul este sigur.
Reducerile încep de obicei prin obținerea unei instanțe a problemei grele, de exemplu, problema DDH. Atunci ai spune ceva de genul „să presupunem $\mathcal{A}$ este un adversar/algoritm care poate rupe protocolul XXX cu avantaj $\epsilon$„. În continuare, veți arăta cum vă puteți transforma instanța problemei DDH $g^a, g^b, g^c$ în valori cărora le-ai putea da $\mathcal{A}$, astfel încât orice $\mathcal{A}$ returnează, ați afla răspunsul la instanța DDH (poate cu o probabilitate mai mică decât $\epsilon$, care este cunoscut sub numele de „pierderea etanșeității”). Este acest mod de a transforma cumva instanța DDH în ceva căruia îi poți oferi $\mathcal{A}$ care se numește „încorporarea” a unei instanțe a problemei DDH în protocolul dumneavoastră.
Dar ai calcula probabilitățile și dacă ai putea demonstra că avantajul tău în rezolvarea problemei DDH folosind $\mathcal{A}$ este deloc neglijabilă dacă $\epsilon$ este, atunci ați demonstrat cu succes o reducere a securității protocolului dvs. de la DDH.
