Puncte:0

Cum să dovedești cunoașterea unui secret și să permiti destinatarului să-l deduplică?

drapel ug

Luați în considerare următorul scenariu:

Avem doi agenți, A și B.

B trebuie să demonstreze că cunosc un secret A, fără a împărtăși secretul real.

de exemplu.: A are nevoie de o modalitate de a deduplica secretele de la care primesc B, dar nu trebuie să cunoască secretele reale. (și B nu vrea ca ei sa stie)

Gândește-te la asta ca și cum ai împărtăși un hash din acel secret, cu exceptia: este o sursă foarte mică, cu entropie scăzută (există aproximativ 1 miliard de valori posibile). Aceasta înseamnă că un simplu hash ar fi vulnerabil la un atac de dicționar.

Acum, B ar putea adăuga o „sare” ascunsă la fiecare secret pe care îl împărtășesc și apoi să-l hacheze, iar asta ar îngreuna A a face un atac de dicționar. Din câte îmi dau seama, asta ar „rezolva” problema pentru cazul 1-1.

Cu toate acestea, să introducem acum un al treilea agent, C. C trimite același tip de secrete către A. B și C nu-și pot împărtăși secretele între ei.

C poate ajunge să trimită „duplicate” de secrete care B are, chiar dacă ei nu știu ce B are la capătul lor.

A, desigur, acum trebuie să dedubleze nu numai secretele de la B, dar și din C.

Sarea ascunsă nu va mai funcționa pentru că acum C ar trebui să cunoască sarea pentru a putea genera aceleași hashes. In caz contrar A nu ar putea deduplica între chei de la B și C. A avea o sare comună înseamnă însă că C ar putea face un atac de dicționar asupra B sau vice versa.

Poate sa A, B și C ajunge la un acord unde B și C pot împărtăși „dovezile” lor A, într-un fel în care A le poate deduplica, dar nimeni nu poate dezvălui secretele celuilalt?

Dacă da, se poate generaliza acest lucru la un număr mare de consumatori/producători?

Fiind departe de a fi un expert în criptografie (cunosc doar elementele de bază), nu sunt sigur dacă folosesc termenii corespunzători aici. Anunță-mă dacă pot clarifica ceva. De asemenea, aceasta nu este temă sau ceva asemănător - deși a fost motivat de o problemă concretă pe care am citit-o recent, aceasta este în mare parte doar curiozitate. O explicație aproximativă despre motivul pentru care nu este posibil (în cazul în care nu este) ar fi cu siguranță suficientă pentru mine. Același lucru pentru o scurtă descriere a unui algoritm cunoscut, chiar dacă doar numele - cu direcția corectă, pot face eu unele cercetări.

(Doar pentru a fi clar dacă nu este deja: A, B și C nu aveți încredere unul în celălalt)

Exemplu (inventat).

Alice și Bob vor să vândă timbre unui colectionar de timbre. Gândiți-vă la o ștampilă ca fiind un șir de 7 caractere cu doar litere mici, iar colecționarul de ștampile nu poate să le fabrice singur.

Colecționarul de timbre va cumpăra orice ștampilă pe care nu o deține în prezent. Cu toate acestea, nu va cumpăra ștampila imediat: va aștepta să vadă câți vânzători o au, astfel încât să poată cumpăra ștampila la cel mai mic preț.

Așadar, înainte de a trimite ștampila propriu-zisă, Alice (sau Bob) trebuie să trimită o „licitație” colecționarului, astfel încât acesta să poată verifica dacă are deja ștampila sau dacă altcineva a oferit-o. Ei nu pot trimite ștampila reală cu acea ofertă, sau colecționarul ar avea-o gratuit, ceea ce nu este distractiv pentru nimeni. Colecționarul trebuie să știe „care” ștampilă este pentru oferta, chiar dacă nu cunoaște șirul real de 7 caractere - sau nu va putea compara ofertele.

knaccc avatar
drapel es
B și C ar trebui să pună o oarecare încredere în A, deoarece A ar putea să-i dezvăluie lui B sau C dacă B și C împărtășesc orice duplicat unul cu celălalt. Dacă B a împărtășit o valoare la un moment dat cu A, B ar putea fi informat de A de îndată ce A observă că o anumită valoare este împărtășită de C. Poate că dacă ați explica problema concretă ar putea fi mai ușor să înțelegeți pe deplin constrângerile de încredere.
Cássio Renan avatar
drapel ug
B sau C nu pot avea deloc încredere în A sau unul în celălalt. Nu sunt sigur că problema (odinioară) concretă ar adăuga ceva TBH. După cum am spus, a motivat întrebarea, dar nu este problema la care încerc să o rezolv sau la care mă gândesc.
knaccc avatar
drapel es
Vreți să spuneți că o cerință este ca A să nu poată colabora cu B pentru a-l informa pe B care dintre valorile orbite ale lui B are B în comun cu C? Prin urmare, ar trebui să fie imposibil pentru B să trimită valorile orb către A unul câte unul, astfel încât A să îl poată informa pe B de îndată ce se observă un duplicat? Mai spuneți că alți „agenți” nu ar trebui să poată participa fără permisiunea tuturor agenților existenți, pentru a preveni o variantă a unei astfel de coluziune?
kelalaka avatar
drapel in
Căutați [criptarea convergentă](https://crypto.stackexchange.com/q/729/18298)?
Cássio Renan avatar
drapel ug
@knaccc nu, asta nu este o cerință. În teorie, B și C nici măcar nu sunt conștienți unul de celălalt (ei comunică doar cu A și nimeni altcineva)
Cássio Renan avatar
drapel ug
@kelalaka Din răspunsul acceptat, se pare că una dintre cerințe este ca „fișierul” de criptat să fie suficient de lung. Una dintre limitările acestei întrebări este că secretul este mic (altfel un hash bun al secretului ar fi suficient, deoarece atacurile de dicționar nu ar mai fi o problemă)
Cássio Renan avatar
drapel ug
Din ultimul meu comentariu, cred că „dovada” nu este o descriere bună - Deoarece nu-mi pasă dacă un „agent” trimite un hash „fals” lui A - prin urmare, nu sunt cu adevărat interesat de o dovadă, ci mai degrabă de unele formular dacă identificare/jeton unic. Voi încerca să vin cu un termen mai bun și să îmbunătățesc întrebarea.
Cássio Renan avatar
drapel ug
@knaccc Am adăugat un exemplu, cred că rezumă bine restricțiile. Anunță-mă dacă funcționează!
knaccc avatar
drapel es
Dacă agenții nelimitați îl pot contacta pe A fără aprobarea vreunui agent existent, atunci A ar putea participa ca agent și ar putea verifica fiecare combinație posibilă pentru a vedea dacă alți agenți au oferit acel secret. Prin urmare, ar trebui să aveți un mecanism care să limiteze numărul de articole pe care agenții le pot oferi la A, în care fiecare agent se va angaja și va fi dispus să-și anunțe lista orbită, în același timp, că un număr limitat de alți agenți sunt oferind un număr limitat de oferte dovedit. Deoarece nu ați oferit cazul real de utilizare, nu am idee dacă acest lucru ar fi acceptabil sau nu.
Cássio Renan avatar
drapel ug
Nu, cred că ai dat un punct foarte bun aici. Gândul meu inițial a fost „de ce ar vrea A să verifice asta împotriva lui însuși? Teoretic, ei știu deja ce au oferit alți agenți, chiar dacă nu știu secretul”, dar apoi m-a lovit - orice astfel de aranjament ar trebui să-i permită lui A să doar forță brută în modul în care descrii și oricum ai secretele.
Cássio Renan avatar
drapel ug
În exemplul de ștampilă, colecționarul ar putea doar să „vândă” toate ștampilele posibile și apoi ar cunoaște fiecare ștampilă a celorlalți vânzători, abuzând de mecanismul de deduplicare. Bănuiesc că acesta este răspunsul meu.
knaccc avatar
drapel es
Există o modalitate prin care A ar putea verifica cu fiecare agent pentru a vedea dacă fiecare agent are ceva ce A nu are deja. Acest lucru se poate face fără ca agentul să descopere ce secrete are A și fără ca agentul să dezvăluie vreunul dintre secretele pe care le are (altele decât cele pe care A le are deja). Agentul ar putea limita numărul de articole pe care A le verifică, pentru a evita să fie forțat.Din păcate, acest lucru nu îi permite lui A să vadă dacă mai mulți agenți au același secret pe care A nu îl are.
Cássio Renan avatar
drapel ug
Nu, asta nu ar funcționa în scenariul la care mă gândesc. Gândiți-vă la „A”, sau la colecționarul de timbre, ca și cum ar fi un API pe care l-au lovit ceilalți. Nu se poate întâmpla invers. În orice caz, după ultimul tău comentariu, sunt destul de încrezător că aranjamentul, prin natura sa, pur și simplu nu poate oferi garanția secretului pentru „ștampile”, împreună cu mecanismul de deduplicare. Va multumesc foarte mult domnule!
Cássio Renan avatar
drapel ug
Sau, cu alte cuvinte, „a păstra secretul ștampilelor” și „a putea dedupa ștampilele din diferite surse” sunt cerințe contradictorii, atunci când numărul de ștampile posibile este suficient de mic pentru a face forța brută.

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.