înregistrare Logare
Puncte:3
einsteinwein avatar Crypto

Cerințe pentru funcția hash pentru semnătura Schnorr scurtă

drapel st
einsteinwein

Neven și colab. afirmat în lucrarea lor Cerințe pentru funcția Hash pentru semnăturile Schnorr următoarea teoremă (folosind lema de bifurcare): $\mathbb{G}$ este grupul generic (secțiunea 2), $s \aproximativ \log_2q$, funcție hash $H: \lbrace 0,1 \rbrace^* \rightarrow \lbrace 0,1 \rbrace^n$.

Teorema 1 Dacă problema logaritmului discret în $\mathbb{G}$ este $(t_\text{dlog}, \epsilon_\text{dlog}$-greu, atunci semnătura Schnorr este $(t_\text{uf-cma}, q_S,q_H, \epsilon_\text{uf-cma})$-sigur pentru $ \epsilon_\text{uf-cma} = \sqrt{(q_H+q_S+1)\epsilon_\text{dlog}} + \frac{q_H+q_S+1}{2^n} + \frac{q_S( q_H+q_S+1)}{q}$ și $t_\text{uf-cma}= t_\text{tdlog}/2 â q_S t_\text{exp} + \mathcal{O}(q_H + q_S + 1)$, Unde $t_\text{exp}$ este costul unei exponențieri în grup $\mathbb{G}$.

Ei ajung la concluzia că această limită indică în mod clar că o funcție hash cu $n = s/2$ biți de ieșire ar trebui să fie suficient pentru a obține un nivel de securitate de $s/2$ biți. Un termen al formei $q_H^2/2^n$ ar fi recomandat o funcție hash s-bit.

Poate cineva să-mi explice acest lucru un pic mai detaliat?

169
0 + 0
Puncte:2
Ievgeni avatar Crypto
drapel cn
Ievgeni

Aici, $k$ biți de securitate înseamnă că avantajul este cel mult $O\left(\frac{T^\alpha}{2^{\alpha k}}\right)$, după ce a făcut $T$ operațiuni (de toate tipurile) făcute de adversar. Cu acest formalism, ne permite să concluzionam că adversarul trebuie să facă $O(2^k)$ „operații” pentru a sparge sistemul ($T^\alpha \approx2^{\alpha k}\implies T \aprox 2^k$).

Apoi, am analizat în detaliu toți termenii din suma.

Când ne uităm la al treilea termen: $\frac{q_S(q_H+q_S+1)}{q}\leq\frac{T}{q}$, este ok.

Al doilea termen $\frac{q_H+q_S+1}{2^n}=O(T2^{-n})$: Și dacă vrem să avem acest termen în $O(T2^{-s/2})$, trebuie să avem $n\geq s/2$, (reamintim $n$ este dimensiunea de ieșire a funcției hash).

Despre primul termen, este puțin mai complex: $\sqrt{(q_H+q_S+1)\epsilon_\text{dlog}}\leq\sqrt{T2^{-s/2}}$, dar este și în regulă (cu $\alpha=\frac{1}{2}$).

0 + 0
einsteinwein avatar
drapel st
einsteinwein
Și poate știi unde pot găsi o dovadă a acestei teoreme? Lucrarea spune doar că nu este un rezultat nou, dar nu este dată nicio sursă.
0
Răspunde
Ievgeni avatar
drapel cn
Ievgeni
Ei spun că este un corolar al semnăturilor multiple în cheia publică simplă model și o lemă generală de bifurcare.
1
Răspunde
einsteinwein avatar
drapel st
einsteinwein
În regulă. Vă mulțumesc foarte mult pentru răspunsurile voastre!
0
Răspunde
drapel romania
SEF 777
întrebarea această in alte limbi:

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.