Ist es möglich, Zufallszahlen zu generieren, wenn wir uns nicht vertrauen? Teil 2

Hallo Habr!

Im ersten Teil des Artikels haben wir diskutiert, warum es möglicherweise erforderlich ist, Zufallszahlen für Teilnehmer zu generieren, die sich nicht vertrauen, welche Anforderungen an solche Zufallszahlengeneratoren gestellt werden, und zwei Ansätze für ihre Implementierung in Betracht gezogen.

, .

, , , . : , , (x, y) , .

, :

1. ( xG, G^x ). -- .

2. G xG x.

p(x) k-1. , : p(x) k x ( p(x)), p(x) x.

, p(x) G, p(x)G k x, p(x)G x.

, , , .

n , , k , , k-1 , .

p(x) k-1, p(1), p(2), (n- p(n)). , G p(x)G x. p(i) “ ” i- ( i- ), p(i)G “ ” i- ( ). , p(i)G p(i).

, i- – , . , , .

, ? , . h -- . , h seed. h :

H = scalarToPoint(h)

i H_i = p(i)H, , p(i) H. H_i i- , . , , , .

k H_i = p(i)H, H_x = p(x)H x , . H₀ = p(0)H, . , p(0), p(0)H – p(x)H, k p(i)H . p(i)H p(0)H.

, : , k-1 , , , k , k seed.

, . , H_i i p(i)H. i- p(i), i- H_i , - H_i H_i, :

H_i, , .

, p(x) k-1 i p(i), . G p(x)G x.

, x_i, X_i.

:

1. i p_i(x) k-1. j p_i(j), X_j. i- j- p_i(j). i p_i(j)G j 1 k .

2. k , . , n . – Z k , (1).

3. , p_i(j) p_i(j)G. Z , p_i(j) p_i(j)G.

4. j p(j) p_i(j) i Z. p(x)G p_i(x)G i Z.

, p(x) – k-1, p_i(x), – k-1. , , j p(j), p(x) x ≠ j. , , p_i(x), j , p(x).

, . 1, 2 4 . 3 .

, , p_i(j) p_i(j)G. , i p_i(j) j, j p_i(j), .

, proof_i(j), , e, proof_i(j) p_i(j)G, , e – p_i(j), j. , , O(nk) , .

, , p_i(j) p_i(j)G , p_i(j), p_i(j)G, , . , p_i(G) , , . , , , , , , .

, , . , , , k , , .

H_i

, , H_i, H_i = p(i)H, p(i).

, H, G, p(i)G . p(i) p(i)G G , dlog, , :

dlog(p(i)G, G) = dlog(H_i, H)

p(i). , Schnorr Protocol.

, H_i .

, , , . H_i .

: – H₀, p(0)G – , Hi, ,

dlog(p(0)G, G) = dlog(H₀, H)

, Schnorr Protocol , p(0), , , , . H_i , H₀.

, - , , H₀ , ,

H₀ × G = p(0)G × H

elliptic curve pairings, . H₀ – , , G, H p(0)G. H₀ – , seed, , k n . , seed – , H₀ – - , .

– NEAR. NEAR – , .

, Rust, .

NEAR, -IDE .

, .

!