Puncte:3

Demonstrați că $x$ este suma numerelor semnate digital fără a dezvălui sumandule

drapel pg

Imaginează-ți asta:

  • Charlie alege două numere întregi $x_1$ și $x_2$ și semnează fiecare dintre aceste numere întregi cu aceeași cheie privată.
  • Charlie îi trimite Alicei următoarele:
    • $x_1$ și $x_2$,
    • cele două semnături și
    • cheia lui publică.
  • Alice calculează $x = x_1 + x_2$ și îi trimite lui Bob următoarele:
    • $x$ și
    • Cheia publică a lui Charlie.

Poate Alice să-i demonstreze lui Bob (fără să-l implice pe Charlie) că? $x$ este suma a două numere care au fost semnate de Charlie, fără a fi dezvăluite $x_1$ și $x_2$ lui Bob?

Un exemplu real ar putea fi: Pot dovedi criptografic că două dintre cărțile mele de credit împreună pot acoperi o debitare fără a dezvălui informații despre cardurile de credit individuale?

Știu foarte puține despre criptografie și nu prea știu unde să caut o soluție.Cred că acest lucru s-ar putea îndrepta în direcția calculului de păstrare a confidențialității și, probabil, a dovezilor de cunoștințe zero? Orice indiciu este binevenit!

Puncte:4
drapel my

După cum a spus Mark, este, în teorie, o problemă rezolvabilă (știm cum să o facem; metodele cunoscute nu sunt simple).

Cu toate acestea, modificând puțin lucrurile, putem face această problemă mai ușoară.

Soluția mea se bazează pe angajamentele Pedersen; acestea se bazează pe un grup mare de dimensiuni prime (unde problema logului discret este dificilă) și doi membri ai grupului $g$ și $h$ (care nu au o relație cunoscută; mai exact, nimeni nu știe soluția $x$ la $g^x = h$).

Un angajament Pedersen față de valoare $x$ este valoarea $g^x h^r$, pentru unii aleatoriu $r$; proprietăți; putem emite angajamentul (prin publicarea valorii $g^x h^r$), și apoi deschideți ulterior angajamentul (prin publicarea valorilor $x, r$; oricine poate verifica că acele valori dau angajamentul.

  • Cineva se uită la $g^x h^r$ nu poate determina ce $x$ este (de fapt, pentru orice valoare posibilă a $x$, există o valoare $r$ care ar da acea valoare a angajamentului)

  • Emitentul nu poate deschide angajamentul în două moduri; adică dacă emite un angajament $g^x h^r$, el nu poate găsi o valoare $r'$ astfel încât $g^{x'} h^{r'}$ evaluează la aceeași valoare.

Având în vedere acest context, el este propunerea mea:

Charlie îi trimite Alicei următoarele valori:

  • $x_1$ și $x_2$

  • Angajamente semnate față de acele valori, adică copii semnate ale $g^{x_1} h^{r_1}$ și $g^{x_2}h^{r_2}$

  • Valorile aleatorii $r_1$ și $r_2$ (pentru că a dat deja valorile pentru care s-a angajat, să-i dea aceste valori aleatorii este inofensiv)

  • Cheia lui publică

Alice calculează apoi $x = x_1 + x_2$, și generează o dovadă de cunoștințe zero că suma celor două valori angajate de către $g^{x_1} h^{r_1}$ și $g^{x_2}h^{r_2}$ este $x$. Acest lucru se poate face prin generarea unei dovezi a cunoașterii faptului că Alice cunoaște valoarea $s$ astfel încât $h^s = g^{x_1} h^{r_1} \cdot g^{x_2}h^{r_2} \cdot g^{-x}$; Alice poate genera o astfel de dovadă numai dacă $x_1 + x_2 = x$

Alice îi transmite apoi lui Bob valoarea $x$, cele două angajamente semnate, cheia publică (pentru ca Bob să poată verifica semnăturile) și dovada zero-knowledge (pe care Bob o poate verifica și el).

Acest lucru pare să abordeze obiectivul final (și destul de simplu; există câteva detalii la care am fluturat doar vag, totuși un pic de cercetare le va ridica).

Elias Strehle avatar
drapel pg
Multumesc, asta poate fi exact ceea ce caut! Se poate face ca abordarea să funcționeze și pentru $x_1 * x_2$? Și este posibil să extindem acest lucru la tuplurile cu semn $(c, x_1), (c, x_2)$ și să demonstrăm nu numai că $x = x_1 + x_2$, ci și că constantele $c$ sunt identice fără a dezvălui $c$ ? ... pentru ultima extensie, interpretarea din lumea reală ar fi că pot folosi doar carduri de credit emise pe nume propriu (= c).
poncho avatar
drapel my
@EliasStrehle: tuplurile semnate ar fi ușor; generați angajamente la $c$ și $x_1$ separat (și semnați ambele angajamente ca un singur mesaj); același pentru $c$ și $x_2$. Apoi, generează dovezi că ambele $x = x_1 + x_2$ și că cele două $c$ au aceeași valoare. În ceea ce privește produsul, este mai complicat. Nu numai că nu vă vine în minte un mod imediat ușor, dar aveți și problema că (dacă înmulțiți în $\mathbb{Z}$), puteți factoriza produsul $x_1 \times x_2$ pentru a apărea cu doar o mână de posibilități pentru $x_1, x_2$ (și dacă produsul nu este destul de mare, este ușor)
Elias Strehle avatar
drapel pg
De fapt, ar fi o multiplicare în $\mathbb{R}$...deci presupun că asta rezolvă o problemă cu prețul uneia mai mari ;-) Dar mulțumesc mult pentru comentarii! Este uimitor ce se poate realiza cu criptografie.
Elias Strehle avatar
drapel pg
Ar funcționa o transformare a jurnalului pentru înmulțire? Adică, Charlie se angajează la $\log x_1$ și $\log x_2$ iar Alice îi trimite $x = x_1 * x_2$ lui Bob și demonstrează că $\log x = \log(x_1 * x_2) = \log x_1 + \log x_2$. Totuși, nu sunt sigur dacă acest lucru este practic, gândindu-mă la erori de rotunjire...
poncho avatar
drapel my
@EliasStrehle: sună funcțional (având în vedere că $\log$ este calculat în afara cripto). Desigur, ar trebui să inserați un factor de scalare; cu toate acestea, având în vedere că dimensiunile grupurilor (și, prin urmare, dimensiunile valorilor la care ne putem angaja) sunt destul de mari (cel puțin 256 de biți, posibil mai mari), există * o mulțime * de spațiu pentru a face acest lucru...
Puncte:1
drapel ng

Cauți noțiunea de a semnătură aditiv-omomorfă. În general, un homomorfism este o funcție care „respectă o operație”, adică:

$$f : A\la B,\qquad f(a_0+a_1) = f(a_0)\oplus f(a_1)$$

aici, folosesc $+, \oplus$ a scrie două (potenţial diferite) „operaţii de adunare”. Deci un homomorfism aditiv se comportă bine în ceea ce privește înmulțirea. În mod similar,

$$f : A\la B,\qquad f(a_0\times a_1) = f(a_0) \otimes f(a_1)$$

ar fi un homomorfism multiplicativ (deși acest lucru nu este important aici).

În acest limbaj, tot ce vrei este o semnătură homomorfă aditiv. Multe există, vezi de exemplu această hârtie. Din nefericire, nu știu despre niciun fel care să fie deosebit de simplu (aceasta este oarecum diferită de criptarea aditiv homomorfă --- există o serie de scheme simple). Dar ceea ce vrei este cel puțin un concept teoretic binecunoscut.

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.