Cryptography Reference
In-Depth Information
4. Then, the receiver selects a subset
I
k
⊂{
1
,...,m
}
of
k
indices and sends
∈I
k
)arequest(
i, Z
1
(
i
)
,...,Z
n−
1
(
i
)). When a server
S
i
receives such a request, it replies with the share
F
i
(
Z
1
(
i
)
,...,Z
n−
1
(
i
)).
5. After receiving
k
responses, the receiver interpolates a univariate polynomial
R
from the
k
points (
i, F
i
(
Z
1
(
i
)
,...,Z
n−
1
(
i
))) and calculates the chosen
secret:
ω
=
R
(0).
In this scheme, each server
S
j
to each server
S
i
(
i
1) as the
coecient of
y
i
in the polynomial function
F
j
received from the sender. After
execution of the protocol, the receiver who has learned a secret
ω
of her choice
can request the values
ω
i
−
knows the value
ω
i
−
ω
0
(1
≤
i
≤
n
−
1) from a corrupt server and compute
all other secrets. Therefore, a coalition of the receiver and only one dishonest
server enables the receiver to learn all secrets. Indeed, in [3,4], each secret
ω
i
is
masked by multiplying it with a random value
r
i
, but at the end of protocol the
receiver learns all masks as well.
Our observation is that, in [8,3,4], the amount of information given to each
server is too high. A fundamental requirement for achieving condition
C
4isthat
not only each server, but also any coalition of up to
k
ω
0
(1
≤
i
≤
n
−
1 servers, should not
gain a linear combination of any of two secrets. To meet this requirement, a
solution consists, for the sender, in storing the secret values in the servers using
a(
k
,
m
)-threshold scheme (see Sect. 5.1).
−
3 Preliminaries
Definition 1.
A(
k
,
m
)-DOT-
1
protocol is
(k
−
1
)-private
if, after completion
of the protocol, any subset of up to
k
−
1
servers cannot learn which secret has
been chosen by the receiver.
Definition 2.
A(
k
,
m
)-DOT-
1
protocol is
(k
−
1
)-secure
if, after completion
of the protocol, any subset composed of up to
k
1
servers and the receiver cannot
learn information about the secrets in addition to the information already learned
by the receiver.
−
Throughout this paper, all operations are executed in a finite field (IK = IF
p
,
+
,
×
),
where
p
∈
IN is a prime number, + is the additive law of composition, and
×
is the multiplicative law of composition of the field. We assume that
p>
max(
n, ω
1
,...,ω
n
,m
), where
n
is the number of secrets,
m
is the number of
servers, and
ω
1
,...,ω
n
are the
n
secrets in the system.
Definition 3.
If
(IK[
X
]
,
+
,
)
is the ring of polynomials over
IK
and
(IK
t
[
X
]
,
+)
the group of polynomials of degree at most
t
over
IK
, we say that a polynomial
F
=
i
=0
f
i
X
i
of
IK
t
[
X
]
is
quasi-random
, if the coecients
f
i
(
1
×
≤
i
≤
t
)are
randomly selected in
IK
and the constant term
f
0
has a predefined value.
Definition 4.
By an abuse of language, if
F
=
i
=0
f
i
X
i
(
r
∈
IN
,f
i
∈
IK
)
is a polynomial of
IK [
X
]
,wedefinethepolynomialfunction
F
:IK
→
IK
,
x
→
i
=0
f
i
x
i
. Note that the additive and multiplicative laws of composition in
IK [
X
]
are defined such that, for
P
,
Q
,
R
∈
IK [
X
]
and for
x
∈
IK
Search WWH ::
Custom Search