Cryptography Reference
In-Depth Information
By simplification, we consider that the polynomial
Q
is quasi-random. However,
to obtain a quasi-random polynomial, we would have to add
Q
to a quasi-random
polynomial of
IK
2
k−
2
[
X
]
whose constant term is zero. The resulting polynomial
would be quasi-random (see Lemma 1) and could be considered as a polyno-
mial generated by Shamir's (
2
k
−
1
,
m
)-threshold scheme to share the secret
i
=1
ω
i
×
ϕ
i
.
Proof
(i) From Theorem 2(i),
F
i
×
G
i
∈
IK
2
k−
2
[
X
](1
≤
i
≤
n
). Then, by generalization
of Theorem 1(i),
i
=1
F
i
×
G
i
∈
IK
2
k−
2
[
X
]. Consequently,
Q
∈
IK
2
k−
2
[
X
].
(ii) From Theorems 2(ii) and 1(ii), it holds
Q
(
x
)=
i
=1
F
i
(
x
)
×
G
i
(
x
)for
x
∈
IK . I n p a r t i c u l a r ,
Q
(0) =
i
=1
F
i
(0)
G
i
(0) =
i
=1
ω
i
×
×
ϕ
i
.Ofcourse,
∈I
m
, i.e.,
Q
(
)=
i
=1
F
i
(
)
the relationship is also true for
×
G
i
(
).
As
F
i
(
)=
F
i
and
G
i
(
)=
G
i
for
i
∈I
m
and 1
≤
≤
n
, it follows
Q
(
)=
i
=1
F
i
×
G
i
.
Notations
The Kronecker's symbol,
δ
ij
,isequalto0if
i
=
j
and equal to 1 if
i
=
j
.
By
α
∈
R
IK , w e m e a n t h a t
α
is chosen randomly from all possible elements
of IK.
Addition and multiplication of vectors (of the same variety) are defined nat-
urally. For example, if
U
=(
u
1
,...,u
n
)and
V
=(
v
1
,...,v
n
), then
U
+
V
=
(
u
1
+
v
1
,...,u
n
+
v
n
)and
U
×
V
=(
u
1
×
v
1
,...,u
n
×
v
n
). Similarly, the product
α
×
U
between an element
α
of IK and a vector
U
=(
u
1
,...,u
n
)of
n
elements
of IK is defined as the vector (
α
u
n
).
Each server participating in the protocol is identified by an index selected in
I
m
=
×
u
1
,...,α
×
{
1
,...,m
}
. Thus, the server associated with index
i
∈I
m
is identified
as
S
i
.
4 Our Model
The setting of our model is similar to the setting of DOT protocols in [8,3,4],
i.e., it encompasses a sender
S
who owns
n
secrets
ω
1
,...,ω
n
(
n>
1), a re-
ceiver
R
who wishes to learn a secret
ω
σ
(
σ ∈{
1
,...n}
), and
m
servers. In
addition to these parties, we also need to take into account an adversary whose
characteristics are defined below.
Like other DOT protocols, our protocol is composed of two phases: a setup
phase and an oblivious transfer phase. During the setup step, the sender gen-
erates shares of the
n
secrets he holds and distributes them to the
m
servers.
The sender does not intervene in the rest of the protocol. During the oblivious
transfer phase, the receiver has to contact
k
servers (1
<k
≤
m
) to collect
enough shares to construct
ω
σ
.
In our scheme, however, the inequality
m
1 must be satisfied. This is
because, condition
C
4 allows the receiver to corrupt up to
k
≥
2
k
−
1 servers, in addition
to the
k
servers chosen by the receiver for gaining shares of the chosen secret.
−
Search WWH ::
Custom Search