Puncte:5

ZKP: Demonstrați că >18 ani în timp ce vă ascundeți vârsta

drapel cn
deb

Sunt relativ nou în criptografie, dar programez de ceva vreme. Iată o poveste care stabilește bine problema pe care încerc să o rezolv:

Alice are un pașaport digital semnat cu cheia privată a guvernului ei. Fiecare proprietate este semnată separat, și ar fi totuși verificabil că, de exemplu, prenumele ei este „Alice”, fără a mai spune că numele ei de familie este „Smith”.

De aici, știind că poate dovedi că data ei de naștere este 05/04/1975, poate dovedi că are peste 18 ani, fără să-și dezvăluie data nașterii și nici să ceară ajutor unei terțe persoane?

Bănuiesc că nu poate, dar sper că mă vei surprinde!

Eugene Styer avatar
drapel dz
Înrudit: https://crypto.stackexchange.com/questions/19265/finding-out-the-greater-number-under-zero-knowledge-conditions
drapel ar
De asemenea, legat de: https://crypto.stackexchange.com/questions/58349/zero-knowledge-proof-using-hash-chains-is-there-a-flaw-in-the-algorithm
Vadym Fedyukovych avatar
drapel in
Dacă nu vă deranjează snarks în timpul verificării și urmați Cenușăreasa https://antoine.delignat-lavaud.fr/doc/oakland16.pdf, există șansa de a ascunde întregul conținut al certificatului în timp ce dovediți declarațiile despre acesta.
Puncte:7
drapel ar

AFAICT, nu, ea nu poate face asta folosind doar informațiile de pe pașaportul ei, așa cum le descrieți* și tratând algoritmul de semnătură digitală ca pe o cutie neagră.

Cu toate acestea, dacă guvernul a prevăzut acest caz de utilizare și a inclus doar puțin mai multe informații despre pașaportul ei, acolo este o modalitate de a face acest lucru folosind de ex. metoda hash chain descrisă în acest thread de întrebări și răspunsuri anterioare (bazat pe o lucrare din 2013 de Angel & Walfish).

În special, ceea ce are nevoie Alice este:

  1. O funcție hash criptografic rezistentă la preimagine $H$ standardizate de guvern. Ceva asemănător cu SHA-256 va fi bine.

  2. Un jeton secret emis de guvern $s$, care nu se poate distinge din punct de vedere computațional de o ieșire a $H$. (De exemplu, $s$ poate fi generat prin selectarea unui șir aleatoriu $r$ cu cel puțin la fel de mulți biți de entropie cât lungimea de ieșire a $H$ și lăsând $s = H(r)$.)

  3. O declarație semnată de guvern, sub forma:

    Alice** s-a născut pe sau înainte de 2050-01-01 (hash = $H^a(e)$).

    Unde $a$ este vârsta lui Alice în zile pe 2050-01-01 și $H^a$ denotă $H$ repetat $a$ ori, adica $H^0(s) = s$ și $H^{n+1}(s) = H(H^n(s))$

Acum, pentru a-i dovedi lui Bob că are în prezent (2021-11-24) 18 ani sau mai mult, Alice trebuie să prezinte declarația semnată de mai sus, împreună cu $h = H^b(s)$, Unde $b$ este vârsta lui Alice în zile cu exact 18 ani în urmă (adică pe 24-11-2003).

Bob poate calcula atunci $H^c(h)$, Unde $c = 16840$ este numărul de zile dintre 24-11-2003 și 01-01-2050 și comparați-l cu hash-ul din declarația semnată de Alice. Dacă afirmația lui Alice este validă, ar trebui să se potrivească, deoarece $a = b + c$, și, astfel $H^c(h) = H^c(H^b(s)) = H^a(s)$.

(Desigur, Bob ar trebui să verifice, de asemenea, că declarația Alicei este într-adevăr semnată corect cu cheia de semnare a guvernului și că îi aparține cu adevărat ei și nu, să zicem, surorii ei mai mari.)


Rețineți că, pentru comoditate de calcul și pentru a atenua atacurile de sincronizare, ar putea fi de dorit ca Alice să precalculeze și să stocheze $H^{b'}(e)$ pentru diverse valori ale $b'$ corespunzând, să zicem, vârstei ei în zile la începutul fiecărui an de până acum. În acest fel, va trebui doar să efectueze cel mult 365 de evaluări hash la fața locului pentru a calcula $H^b(e)$ pentru orice $b$.

Pentru a reduce cererea de calcul a lui Bob, ar putea fi de dorit ca guvernul să emită Alice mai multe declarații semnate de forma de mai sus, dar cu date diferite și valori corespunzătoare de $a$, astfel încât Alice să îi poată trimite lui Bob o declarație semnată pentru, de exemplu, 2004-01-01 în loc de 2050-01-01. Apoi, din nou, câteva mii de evaluări SHA-256 chiar nu sunt prea multe în zilele noastre, iar Bob nu trebuie să-și facă griji cu privire la atacurile pe canale laterale.

Cu toate acestea, emiterea mai multor declarații semnate ajută, de asemenea, la păstrarea proprietății zero-cunoștințe în prezența transferului. De exemplu, să ne imaginăm că guvernul a ales inițial 2030-01-01 ca dată fixă ​​pentru declarațiile semnate, dar apoi a decis în urmă cu câțiva ani să o mute în 2050, deoarece au început să elibereze pașapoarte valabile până în 2030 și mai târziu. Acest lucru ar însemna că, cel puțin, Bob ar putea afla de la data din declarația lui Alice dacă pașaportul ei a fost eliberat înainte sau după tranziție, ceea ce s-ar putea corela cu alte informații, inclusiv vârsta ei. Dându-i lui Alice declarații semnate pentru ambii 2030-01-01 și 2050-01-01 (și posibil alte date aplicabile), această scurgere poate fi evitată, deoarece Alice poate alege doar declarația cu data potrivită anterioară pentru cererea lui Bob (dar nu, evident, mai devreme decât data) ea dorește să demonstreze că s-a născut la sau înainte).


Ps. După cum se notează în răspunsul meu la întrebarea de mai sus, același protocol poate fi folosit și pentru a-i permite Alicei să-și demonstreze vârsta exactă. Pentru a face acest lucru, Alice trebuie să știe nu doar $s = H(r)$ dar și jetonul aleatoriu original $r$, care ar trebui să fie aleasă de guvern astfel încât să fie nu o ieșire validă a $H$.

Apoi, dacă Alice vrea să-i demonstreze lui Bob că s-a născut pe 1975-05-04 și nu mai devreme, poate dezvălui acea dată împreună cu $r$ și cel puțin o declarație semnată din formularul de mai sus. Bob poate calcula apoi vârsta pretinsă a lui Alice în zile $a$ la data indicată în decont, se calculează $H^a(s) = H^{a+1}(r)$ și comparați-l cu hașul din declarația semnată.

Desigur, cu această variantă a protocolului, Bob trebuie să verifice și formatul $s$ sau $r$ jeton trimis de Alice (adică că este o ieșire validă a $H$ pentru afirmațiile „născut la sau înainte” și nu o ieșire validă a $H$ pentru afirmațiile „născut la această dată”).

Toate acestea fiind spuse, în scenariul tău, o semnătură guvernamentală separată pentru „Alice s-a născut pe 1975-05-04” ar servi la fel de bine acestui scop.


Note de subsol:

*) Descrierea dvs. conform căreia „[fiecare proprietate este semnată separat” este de fapt puțin problematică dacă este luată la valoarea nominală, deoarece atragerea guvernului să semneze o proprietate individuală, cum ar fi „prenume: Alice” înseamnă că oricine a văzut semnul lui Alice. prenumele poate face o copie a semnăturii și o poate folosi pentru a pretinde că prenumele lor este de asemenea Alice. De asemenea, de exemplu, dacă Alice Andrews și Bob Barker aveau pașapoarte cu astfel de nume și prenume semnate separat, le-ar putea combina pentru a crea un pașaport fals pentru „Alice Barker” sau „Bob Andrews”.

O soluție puțin mai bună ar fi ca una dintre proprietățile de pe pașaport să fie un ID unic și să includă acel ID în toate proprietățile semnate. Astfel, de exemplu, cineva care a văzut o declarație semnată de forma „ID: #123456789; prenume: Alice” ar putea verifica acum că Alice, purtând un pașaport cu ID #123456789, are într-adevăr prenumele „Alice”, dar nu pot folosi semnătura pentru a revendica pe nimeni a altuia prenumele să fie Alice.

Desigur, această schemă are încă propriile neajunsuri: de exemplu, Alice ar putea dori să-i demonstreze lui Bob că o cheamă Alice fără Bob fiind capabil să demonstreze acest fapt oricui altcuiva. Implementarea unui astfel de autentificare refuzată schema pare în afara domeniului de aplicare al acestui răspuns, deși ați putea dori să vă uitați la, de ex. aceasta de mai devreme.

**) Aici folosesc „Alice” ca substitut pentru ID-ul unic al lui Alice emis de guvern, așa cum este descris în nota de subsol anterioară de mai sus.

fgrieu avatar
drapel ng
Problemă fundamentală: dacă un dispozitiv poate testa Alice are â¥18 ani acum interacționând cu pașaportul ei, iar pașaportul nu are amintiri despre astfel de încercări anterioare, nimic nu-l împiedică pe acel dispozitiv să găsească data nașterii lui Alice prin dihotomie. Chiar dacă dispozitivul nu o va face, atâta timp cât noțiunea de „acum” nu este sigură (de exemplu, există o modalitate de a-și seta ceasul după bunul plac), poate fi abuzat pentru a găsi data nașterii lui Alice. S-ar putea să dorim ca pașaportul însuși să verifice un marcaj de timp pentru prospețime folosind provocarea/răspunsul și să certificăm că Alice nu este în prezent minoră (cel 18 nu trebuie să fie ajustabil, cel puțin fin).
drapel ar
@fgrieu: Adevărat. Presupuneam implicit că (cel puțin o parte din) informațiile de pe pașaportul Alicei sunt de ex. criptată cu o cheie stocată în afara pașaportului, astfel încât să poată alege ce piese să dezvăluie. În caz contrar, alte părți ale întrebării (cum ar fi semnarea câmpurilor pentru pașapoarte separat) nu au niciun sens pentru mine.
Maarten Bodewes avatar
drapel in
În IEC 18013-5 (Permis de conducere mobil / mDL), elementele de date sunt combinate cu un cod aleatoriu și apoi hashing. Hashurile randomizate sunt apoi combinate și semnate într-un MSO (fără aleatoriu, evident). În acest fel, puteți verifica MSO și elementul de date. Trebuie să acordați permisiunea în aplicație pentru a răspunde la orice solicitare de date. Ați putea fi interesat de faptul că cazurile de utilizare > 18 și > 21 au fost implementate în acel standard (permite două solicitări, ceea ce înseamnă că puteți determina totuși că cineva are între 18 și 21 de ani).
deb avatar
drapel cn
deb
Acesta este un răspuns excelent, vă mulțumesc foarte mult pentru timpul acordat.
deb avatar
drapel cn
deb
Această soluție nu presupune că Alice spune adevărul despre vârsta ei în primul rând atunci când generează `Hb(s)`? Simt că nu am înțeles corect asta.
drapel ar
@deb: Observația cheie este că Alice nu poate genera $H^b(s)$ pentru $b$ negativ (cel puțin nu fără informații suplimentare), deoarece asta le-ar cere să găsească o preimagine $H^{-1}( s)$ pentru funcția hash. Presupunând că $H$ este o [funcție hash criptografică](https://en.wikipedia.org/wiki/Cryptographic_hash_function) sigură, acest lucru nu este posibil, deoarece rezistența preimagine este una dintre ipotezele lor fundamentale de securitate.Dacă Alice ar fi găsit o modalitate de a calcula preimagini pentru, de exemplu, SHA-256, ar fi spart hash-ul și ar fi putut deveni instantaneu celebre, indiferent de vârsta lor.
drapel ar
@deb: În ceea ce privește întrebarea ta anterioară despre autentificarea refuzată în acest context, aceasta este de fapt una foarte bună și nu am un răspuns la ea. M-am gândit că *ar trebui* să fie posibil cumva când am scris răspunsul, dar acum că mă gândesc mai mult la asta, nu văd cum. Dar poate că există un truc inteligent ZKP care îmi lipsește. S-ar putea să pun o întrebare separată despre asta, dacă nu o faci.
deb avatar
drapel cn
deb
@IlmariKaronen: Oh, cred că înțeleg puțin mai bine răspunsul tău acum (l-am citit de mai multe ori decât aș recunoaște și totuși nu sunt sigur dacă am înțeles totul bine!). Nu sunt obișnuit cu acel nivel de criptografie, așa că mă voi gândi mai mult la asta când voi avea o foaie de hârtie pe care să scriu... Dacă vorbim despre întrebarea așa cum mi-o amintesc, am șters-o comentariul pentru ca poate am gasit raspunsul. Probabil voi crea un Q&A pe site, voi distribui linkul aici.
deb avatar
drapel cn
deb
Aceasta este întrebarea pe care am pus-o.În comparație cu răspunsul pe care l-ați dat aici, soluția a fost destul de simplă; discutam despre aceeasi problema? https://crypto.stackexchange.com/q/97803/88017
deb avatar
drapel cn
deb
Bine: O lună mai târziu, iată-mă și înțeleg în sfârșit răspunsul tău. Nu pot decât să apreciez inteligența acelui răspuns, mulțumesc mult.
Puncte:2
drapel es

Folosind o curbă eliptică: pașaportul poate conține un marcaj de timp Unix ca angajament Pedersen sub forma $C = bG + tH$, Unde $b$ este un factor de orbire scalar, $t$ este data de naștere a deținătorului pașaportului ca marcaj temporal Unix (secunde de la epocă) și $G$ și $H$ sunt puncte de bază bine cunoscute alese astfel încât logul lor discret unul față de celălalt este necunoscut și de necunoscut.

$C$ este semnat de guvern. Pașaportul face cunoscut deținătorului pașaportului marca temporală și factorul orbitor.

Pentru a dovedi că titularul pașaportului este mai în vârstă de 18 ani, mai întâi calculăm $s$ ca cea mai recentă ștampilă de timp posibilă pe care titularul pașaportului se poate fi născut pentru a avea în prezent 18 ani sau peste.

Deținătorul pașaportului trebuie să demonstreze acest lucru $s>=t$. Putem face asta demonstrând asta $C' = sH - C == (s-t)H - bG$ este un angajament față de un număr pozitiv. Din cauza naturii aritmetice modulare a algebrei EC, aceasta înseamnă că trebuie să ne asigurăm că angajamentul este față de un număr relativ mic și nu față de un număr mare care ar rezulta din $s-t$ fiind „negativ”.

Pentru a realiza acest lucru, avem nevoie de ceva numit o dovadă de interval.

Dovada intervalului va dovedi asta $C'$ poate fi construit printr-o secvență de 43 de biți (ceea ce va permite schemei să funcționeze în următorii 200 de ani). Fiecare „bit” va fi fie zero, fie o putere de 2.

În primul rând, vom declara 43 de angajamente Pedersen $C_i$ pentru valori de $i$ între 0 și 42 inclusiv, unde fiecare angajament va avea propriul factor de orbire $b_i$ iar fiecare angajament va fi fie la valoarea zero, fie $2^i$.

Acum, trebuie să dovedim asta $C'$ este un angajament față de același număr ca $\sum_{i=0}^{42} C_i$. Acest lucru se poate face prin calcularea cheii publice $C'' = C' - \sum_{i=0}^{42} C_i$. Din moment ce numărul angajat de către $C'$ va fi egal cu suma numerelor angajate prin cele 43 de angajamente, rezultatul va fi de forma $C'' == b'G$ Unde $b' == -b - \sum_{i=0}^{42} b_i$. Prin urmare, furnizarea unei semnături pe $C''$ folosind cheia privată $b'$ va dovedi că nu poate exista un non-zero $H$ componentă a $C''$, deoarece o semnătură folosind punctul de bază $G$ nu este posibil decât dacă jurnalul discret al $H$ w.r.t. $G$ este cunoscut (și $H$ a fost ales în mod special astfel încât să fie de necunoscut).

În cele din urmă, trebuie să demonstrăm că fiecare dintre componente $C_i$ sunt fie angajamente la zero, fie angajamente către $2^i$. Facem acest lucru furnizând o semnătură de apel pentru fiecare angajament pentru cele două chei publice $(C_i - 0H, C_i - 2^iH)$. O semnătură de inel va fi posibilă numai dacă una dintre aceste două posibilități produce un punct EC cu nr $H$ componentă, demonstrând astfel că $C_i$ este un angajament fie la zero, fie $2^i$.

Pe scurt, noi am dovedit asta $s>=t$ pentru că noi am dovedit asta $sH -C$ este un angajament față de un număr pozitiv. Am demonstrat că este un număr pozitiv, demonstrând că poate fi construit ca o serie de 43 de biți, în care fiecare bit este fie zero, fie o putere specificată de 2.

deb avatar
drapel cn
deb
Mă tem că nu știu suficient despre curbele eliptice/„Angajamentele Pedersen” pentru a înțelege pe deplin răspunsul tău, dar cu siguranță apreciez efortul. Ce este un factor de legare scalar?
knaccc avatar
drapel es
@deb Este doar un număr aleatoriu care ascunde valoarea Angajamentului Pedersen. Dacă angajamentul a fost de doar $tH$, ai putea forța brută o mulțime de valori ale marcajului de timp pentru a descoperi data de naștere a titularului. Factorul orbitor face ca angajamentul să pară total aleatoriu și îl împiedică să fie forțat. Ceea ce am descris este modul în care sumele sunt ascunse în criptomonede precum Monero, unde dovezile de interval sunt folosite pentru a se asigura că cineva nu încearcă să creeze o sumă pe blockchain cu o valoare negativă.

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.