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

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.
1
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):
s=f(0)=
∑
∈Aj
f(j)
λ
j,A
=
∑
∈Aj
sj
λ
j,A
λ
j,A

=
∏
−∈
−
}{ 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

α
k
x
k
where
α
0
= s and
α
1
, …,
α
t

∈
Zp. The polynomial is kept secret and the commitment
C
k
=G
αk
, 0
≤
k
≤
t as well as the encrypted shares Hj=h
j
p(j)
, j= 1, 2, …, N are published.
Moreover, the dealer shows that the encrypted shares are consistent:
Let Xj=

∏

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

S
j
= H
j/Zj
j
. Aj also proves that log
G
hj = - log
Hj
Sj (again the proof from the section 4). Further,
suppose that t+1 authorities Aj, j
∈
A. The secret g
s
is reconstructed by Lagrange
interpolation
∏
∈Aj
Aj
j
S
,
λ
=
∏
∈Aj
Ajjp
g
,)(
λ

= 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

satisfying x= g
α
and y = h
α
. The protocol is depicted in the figure. Security properties of
this protocol can be found for instance in [CGS97].
Prover Verifier
|(x, y) = (g
α
, h
α
)|
w
∈
R
Zp
(a,b)  (g
w
, h
w
) c
R
∈
Zp
r  w +
c
α
g
r


=
?

α
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

conversation with the right distribution. However, the prover sends a, b before he receives
the challenge c, without the knowledge of
α
he cannot compute the respond r that meets
verifier’s requirements.
Prover Verifier
3
r
c
a, b
d, r
c
a, b
(x
1
, y
1
), …, (x
L
, y
L
)
(x, y), …, (x
t
g
v
, y
t
h
v

)
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

= (
y
yi
)
di
h
ri

d
t
 c -
∑
≠ jij
d
c
?
=
d
1
+ …+ d
L

a
i

?
=
(
x
xi

)
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

–c
|| h
r
y
–c
|| x ||y)
Notice that instead of four group elements that are communicated in the interactive
protocol, the non – interactive version needs to store only two group elements.
5. Ensuring the Knowledge of the Secret – key
The following protocol is use to verify that the voter really knows his secret key z
v
corresponding to the public key h
v
=g
z v
. Even if the voter does not know his secret key and
he acts according to the coercer’s orders (the coercer knows the secret – key), he finally
gets to know his secret key.
4
The voter’s knowledge of the z
v
is verified by the N authorities. It is assumed that at
least t of them are honest. The untappable channel between the voter and the authorieties is
needed.
- The voter shares his secret key z
v
among the authorieties using (t+1, N) secret
sharing scheme:
• He chooses a random polynomial of degree t: f
v

(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

committed polynomial:
g
sj

?
=
h
v
C
j
1
C
2
2
j
…C
jt
t
(= g
z v
g
α
1j
g
α
2j
… g
α
tj t
=g

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