Tài liệu Secret key sharing

1. Notation
N : number of authorities
A1, A2, , An: N authorities
t: maximum number of malicious and dishonest authorities
A: any set of t+1 authorities
M: number of eligible voters
m: number of voters participating in the voting; m<=M
V1, V2, , Vm: M voters
v1, v2, , vm: intentions (voters) of the voters
Zp: field of positive integers modulo p, where p is prime number
Zn: set of integers modulo, i.e. {0, 1, , n-1}
Zn*: set of integers from Zn relatively prime to n
a|b: an integer a is a divisor of an integer b
gcd(a,b): greatest comon divisor of the integer a,b
a||b: concatenation of the string a, b
a b: bitwise exclusive or
x RX: x is a random element of the set X (uniformly distributed)
X RY: X is a random subset of the set Y (uniformly distributed)
x ?= y: check whether x=y


2. Secret Sharing Scheme
Purpose of secret sharing scheme is to share a secret among N authorities. In such away that only some predefined coalitions of authorities can later reconstruct the secret. Other coalitions of authorities should get no knowledge about the secret. We introdure Shamir’s (t+1, N) secret sharing scheme from [Sha 79] that alows any coalition of t+1 from N authorities to get the secret. Any set of at most t authorities knows noting about the secret.
Let the set of possible secrets forms a field F(for instants, F could be set of real numbers, or Zp). F should have a least N+1 distinct elements – we will denote them 0, 1, 2, , N.
Distribution of the shares. A secret s F is distributed among the N authorities; each authority gets it share sj F. The idea behind is simple: Choose a random polynomial f of degree t over the field F satisfying f(0)=s. Give the authority Aj its share sj = f(j).
Reconstruction of the secret. Set of t+1 authorities A gains the secret s by reconstructing the polynomial f (using Lagrange interpolation) and computing s=f(0):