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
∈
R
X: x is a random element of the set X (uniformly distributed)
X
∈
R
Y: 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

=
∏
−∈
−
}{ jat
jt
t
Information that t or less authorities have about the polynomial f reveals nothing about
the value f(0)=s. Whatever value for f(0)=r they choose, using their shares they can
compute possible polynomial g satisfying g(0)= r.
3. Publicly Verifiable Secret Sharing
Publicly Verifiable Secret Sharing scheme is the secret sharing scheme allowing
verifying that the dealer has distributed valid shares (any set of t+1 authorities will obtain
the same secret) and allowing catching the dishonest authority in forging its share. The
following publicly verifiable secret sharing comes from [Sch99].
Initialization. The group Zp and the generators G, g are selected. The authority Aj
choose its secret key zj and publishes its public key hj=g
zj
. The dealer wants to share a
secret g
s
to the authorities
1.

Distribution of the shares. The dealer picks a random polynomial of degree t over Zp:
p(x)=
∑
=
t
k 0

∏

t
k=0
C
jk
k

= G
∑
t
k=0
α
k
j
k
= G
p(j)
,
the dealer proves that:
2
log
G
Xj=log
hj
Hj
using the non – interactive proof from the section 4.
Reconstruction of the secret. The authority Aj decrypts its share Sj= g
p(j)
by computing

= g
AjAj
jp
,
)(
λ
∑
∈
= g
p(0)
= g
s
Where
λ
j,A
=
∏
−
−∈
jt
t
jAt }{
is a Lagrange coefficient.
4. Equality of Discrete Logarithms
In this secsion, we present protocol that shows equality of discrete logarithms. The
prover has an 4 – tuple (g, x, h, y), g, x, h, p
∈
Zp, and he shows possession of an α
∈
Zp

=
?

α
x
c

h
r

=
?

α
y
c
Figure: Proof of knowledge for log
g
x = log
h
y
For random c, r anyone can construct (g
r
x
–c
, h
r
y
–c
, c, r), which is the accepting

)
d
i
∈
R
Zp, i = 1, …, L
r
i
∈
R
Zp, i = 1, …, L
w  v d
t
+ r
t
a
i
= (
x
xi
)
di
g
ri
c
∈
R
Zp
b
i

)
di
g
ri

b
i

?
=
(
y
yi
)
di
h
ri

Figure: 1 – out – of – L re – encryption proof
Non – interactive version
• The prover’s computations are the same as in the interactive proof, but he generates
the challenge c for himself as c= H(a || b|| x || y), where H is a secure hash function.
The prover stores c, r as a proof.
• The verification can be performed by checking whether
c
?
=
H(g
r
x

(x) = z
v
+
x
1
α
+ …+
t
t
x
α
• He sends s
j
= f
v
(j) through the untappable channel to the authority A
j
, j = 1, …, N
• He commits to the coefficients of the polynomial by sending G
j
= g
α
j
to the
bulletin board.
- Each authority A
j
verifies whether the receiver share s
j
corresponds to the

f v(j)
)
- If the authority A
j
detects an error, it complains and the voter is asked to publish its
share to the bulletin board. If the posted share does not correspond to the
commitments, the voter is discarded.
- Finally, every authority not complaining in the previous stage sends her share
through the untappable channel to the voter.
At least t honest authorities either complain (and their shares are published in the
bulletin board ), or send their shares secretly to the voter. The voter can interpolate the
received shares to obtain the secret key z
v
.
5