Cryptography Reference
In-Depth Information
user
u
i
holds the share
f
(
i
). Also, let assume that the users
u
1
,...,u
k
1
wish to
redistribute the secret
ω
over the set of users
V
=
{
v
1
,...,v
m
2
}
usinga(
k
2
,
m
2
)-threshold scheme (
k
2
≤
m
2
). Note that
U
and
V
are two arbitrary groups
of users. Each user
u
i
∈
(
u
1
,...,u
k
1
) generates a polynomial
H
i
such that
k
2
−
1
h
i,r
X
r
+
L
i
×
H
i
=
f
(
i
)
,
r
=1
where
h
i,r
∈
R
IK ( 1
≤
i
≤
k
1
,1
≤
r
≤
k
2
−
1) and
L
i
is the truncated Lagrange
basis polynomial
L
i
mod
X
k
2
where
k
1
X
−
j
L
i
=
.
i
−
j
j
=1
j
=
i
Truncating the polynomial
L
i
(1
≤
i
≤
k
1
) allows each user
u
i
∈
(
u
1
,...,u
k
1
)
to generate a polynomial
H
i
of degree
k
2
−
1(when
k
2
<k
1
), by
application of the technique described by Beaver [1]. Then, for all 1
1 and not
k
1
−
≤
j
≤
m
2
,
the user
u
i
privately sends the value
H
i
(
j
) to the user
v
j
∈V
. Once a user
v
j
∈V
obtains
k
1
partial shares, sent by the users
u
i
∈U
, he computes a new share
ρ
j
=
k
1
i
=1
H
i
(
j
) as his share of the secret
ω
.
With this method, the original sharing polynomial
f
is replaced with a sharing
polynomial
g
such that
k
2
−
1
L
i
k
1
h
i,r
X
r
+
f
(
i
)
g
=
×
i
=1
r
=1
k
1
k
2
−
1
k
1
h
i,r
X
r
+
=
f
(
i
)
×
L
i
r
=1
i
=1
i
=1
k
1
k
2
−
1
h
i,r
X
r
+
f
=
i
=1
r
=1
where
f
is the truncated polynomial
f
mod
X
k
2
.
The degree of the polynomial
g
is at most
k
2
−
1and
g
(0) =
f
(0) =
f
(0) =
ω
.
Therefore, with
k
2
values
ρ
i
=
g
(
i
), any set of
k
2
users in
V
is able to interpolate
g
and to determine the secret
ω
.
Theorem 3.
If
k
2
≤
k
1
, the proposed protocol for transforming a Shamir (
k
1
,
m
1
)-threshold scheme to a Shamir (
k
2
,
m
2
)-threshold scheme is secure.
Proof.
To demonstrate the security of
ω
, we show that after the new shares
have been obtained, no coalition of
k
2
−
1 users or less can infer any information
about
ω
.
After the redistribution of shares, a coalition of
k
2
−
1usersholdsatmost
k
2
−
1shares
f
(
i
)and
k
2
−
1shares
g
(
i
). We analyze the worst case, i.e., when all
Search WWH ::
Custom Search