Criptare cu cheie publică/asimetrică în care puteți scurge mesajul decriptat doar prin scurgerea parolei

O mulțime de prieteni folosesc criptarea cu cheie publică pentru a trimite mesaje criptate unul altuia folosind un forum public deschis. i.e. fiecare prieten are o cheie publică (pe care o poți folosi pentru a cripta mesajele pentru ei) și o cheie privată (pe care o folosesc pentru a decripta mesajele pentru ei).

Bob îi trimite lui Alice mesajul criptat $y$, care, atunci când este decriptat, dă textul $x=$„O să te ucid dacă nu-mi trimiți $1000”. Alice, evident supărată, trimite tuturor mesajul necriptat „Bob este o persoană rea. El a spus $x$ pentru mine, pe care îl puteți verifica cu toții criptându-l cu cheia mea publică pentru a o produce $y$, pe care l-a postat anterior pe forumul nostru public.” Aceasta este o metodă completă pentru Mary de a expune mesajul lui Bob tuturor.

Întrebarea mea este, există vreo cheie publică/scheme de criptare asimetrică care ar împiedica Mary să expună tuturor mesajul criptat al lui Bob? De exemplu, o schemă în care Mary ar putea dovedi care este mesajul decriptat al lui Bob ar fi să-și dezvăluie cheia secretă (parola pe care o folosește pentru a decripta).

Edit: O idee pe care o am este ca o schemă de criptare să permită un fel de nonce sau randomizare sigură a mesajului în care este criptat. De exemplu, dacă $x$ este textul pe care Bob vrea să-l cripteze, el poate alege un „nonce” aleatoriu $s$, și produc $y_s$. Atunci Mary poate decripta $y_s$ a obține $x$, dar ea nu va ști $s$, așa că ea nu poate spune doar asta $x$ produce $y_s$ dacă nu-și dezvăluie cheia secretă. Știu că acest concept de nonce există în criptografie, dar dacă cineva ar putea să-mi dea un exemplu explicit despre cum să-l implementez (poate cu ceva simplu precum RSA), ar fi foarte apreciat.

Ideea ta despre o metodă de criptare care să includă un nonce și într-un mod în care Alice nu poate recupera nonce este practică; totusi nu iti rezolva problema.

O posibilitate ar fi o variantă a El Gamal; în acest sistem, cheia publică a lui Alice este o valoare $A= G^a \bmod p$, cu $a$ fiind cheia privată a lui Alice și $G, p$ fiind parametri publici (cu $p$ fiind un safe-prime, și $G$ un reziduu cuadratic).

Pentru a cripta un mesaj M$ < p/2$, Bob ar selecta o valoare aleatorie $r$, și generați textul cifrat $G^r \bmod p, M^2 \cdot A^r \bmod p$.

Pentru a decripta perechea $X, Y$, ar calcula Alice $M^2 = Y \cdot X^{-a} \bmod p$ (și apoi luați rădăcina pătrată modulară a $M^2$ a recupera $M$).

Dacă Alice primește perechea $X, Y$, ea nu cunoaște valoarea $r$, și așa, la prima vedere, arătând asta $G, A = G^a, X = G^r, Y \cdot M^{-2} = G^{ar}$ sunt un set DH este problema Decisional Diffie-Hellman, care este grea în general; ar putea face asta cu ușurință expunând $a$, cu toate acestea, pentru ea, asta ar înfrânge scopul.

Cu toate acestea, ceea ce ar putea face ea este să genereze o dovadă de zero cunoștințe că $G^x = A$ și $X^x = Y \cdot M^{-2}$ au o soluție comună $x$ (ceea ce poate face, deoarece știe care este acea soluție comună); această dovadă a cunoștințelor zero ar arăta că $M$ este decriptarea, fără a-și expune cheia privată.

Aceasta duce la o observație mai generală; dacă algoritmul de decriptare $D$ și generarea cheii publice $Gen$ ambele rulează în politimp, apoi afirmația că $D(a, C) = M \land (a, A) = Gen(sămânță)$ (pentru un public $C$ si $M$ despre care Alice pretinde că decriptarea este o declarație în NP (cu $a$ și $sămânță$ fiind „martorii”), iar pentru o astfel de afirmație în cadrul NP, se poate construi o dovadă de cunoștințe zero, arătând că $M$ este o decriptare corectă.

Deci, dacă Bob nu poate pretinde că nu a trimis textul cifrat $C$ (și presupun că cumva se presupune că cumva toată lumea știe că a făcut-o), nu sună ca o problemă rezolvabilă.

Eu cred că ceea ce cauți este imposibil. Cu toate acestea, vă voi sugera o altă modalitate de a aborda această problemă care ar putea fi utilă, care se bazează pe o negație plauzibilă.

În primul rând, voi încerca să explic de ce cred că este imposibil să o forțez pe Alice să-și dezvăluie cheia secretă atunci când le demonstrez altora ce mesaj a decriptat. Astăzi, odată cu apariția dovezilor Zero-Knowledge din circuitul general (de exemplu, STARKS și SNARKS) aproape orice relație între o valoare secretă și o valoare publică poate fi dovedită altor părți.(Orice relație care poate fi exprimată prin numărul polinom de porți ale $ȘI $ și $SAU$)

În general, un criptosistem cu cheie publică este definit de un tuplu de $(Gen, Enc, Dec)$:

• $(pk, sk) \leftarrow Gen(\lambda, rnd)$: algoritmul de generare a cheii care generează cheia publică $pk$ și cheie secretă $sk$ conform unui parametru de securitate $\lambda$ și un șir aleatoriu $rnd$.

• $c \leftarrow Enc(m, pk, rnd)$: algoritmul de criptare care criptează mesajul $m$ cu cheie publică $pk$ și creează textul cifrat $c$. Acest algoritm trebuie să fie un algoritm probabilist, ceea ce înseamnă că ar trebui să genereze text cifrat diferit de fiecare dată când îl rulăm. În caz contrar, nu are cel mai scăzut nivel de securitate a cheii publice (IND-CPA).

• $m \leftarrow Dec(c, sk)$ algoritmul de decriptare este determinist.

Dacă Alice se poate întoarce $Dec$ într-un circuit Zero-Knowledge cu o valoare privată de $sk$ atunci ea poate dovedi că un text cifrat cunoscut $c$ decriptează în $m$ cu cheia secretă $sk$ care corespunde $pk$. Indiferent care este criptosistemul cu cheie publică.

Cu toate acestea, poate exista o altă modalitate de a rezolva problema folosind mesaje off-the-record (OTR) care face ca o comunicare bazată pe cheie publică să fie refuzată.

În OTR, orice transcriere a mesajelor înregistrate poate fi fabricată de orice parte a comunicării. În consecință, este ușor să negi totul.