Cryptography Reference
In-Depth Information
Proof
(i) Immediate with the application of Lemma 1.
(ii) From the definition 4 of the additive law of composition in IK[
X
], it holds
P
(
x
)=
F
(
x
)+
G
(
x
), for
x
IK . C o n s e q u e n t l y, f o r
x
=0,
P
(0) =
F
(0)+
G
(0).
As
F
and
G
are the sharing polynomials for the secrets
α
and
β
,wehave
F
(0) =
α
and
G
(0) =
β
. It follows
P
(0) =
α
+
β
.
Still from the relationship
P
(
x
)=
F
(
x
)+
G
(
x
), we obtain for
i
∈
∈I
k
,
P
(
i
)=
F
(
i
)+
G
(
i
). From the definition 5 of shares, it follows
P
(
i
)=
F
i
+
G
i
.
Theorem 2 (Product of shares).
Let
F
and
G
be two quasi-random poly-
nomials of
IK
k−
1
[
X
]
generated by Shamir's (
k
,
m
)-threshold schemes to share
respectively the secret
α
and the secret
β
. We assume that
m
≥
2
k
−
1
.Foreach
index
i
∈I
m
,wedefinetheshares
F
i
and
G
i
.If
Q
is the product of
F
and
G
,
then:
IK
2
k−
2
[
X
]
,
(ii)
Q
(0) =
α
(i)
Q
∈
×
β
and for
i
∈I
m
,
Q
(
i
)=
F
i
×
G
i
.
Proof.
(i) If
F
=
k−
1
1) and
G
=
k−
1
i
=0
f
i
X
i
(
f
0
=
α
and
f
i
∈
R
IK , 1
i
=0
g
i
X
i
≤
i
≤
k
−
(
g
0
=
β
and
g
i
∈
R
1), then from the explicit form of the
multiplicative law of composition in IK[
X
], it follows
IK , 1
≤
i
≤
k
−
f
i
g
j
X
2
k−
2
Q
=
=0
i
+
j
=
where
f
i
=0if
i
≥
k
and
g
j
=0if
j
≥
k
. The degree of
Q
is at most 2
k
−
2,
IK
2
k−
2
[
X
].
(ii) Using the definition 4 of the multiplicative law of composition in IK[
X
], we
can write
Q
(
x
)=
F
(
x
)
so
Q
∈
×
G
(
x
)for
x
∈
IK . I n p a r t i c u l a r ,
Q
(0) =
F
(0)
×
G
(0) =
α
×
β
. Of course, the relationship is also true for
x
∈I
m
.
The polynomial
Q
cannot be considered as quasi-random because it is not irre-
ducible. However, if we add
Q
to a quasi-random polynomial of IK
2
k−
2
[
X
]whose
constant term is zero, the resulting polynomial is quasi-random (see Lemma 1)
and may be considered as a polynomial generated by Shamir's (2
k
−
1,
m
)-
threshold scheme to share the secret
α
×
β
.
Corollary 1.
Let
=(
G
1
,...,G
n
)
be two vectors of
quasi-random polynomials of
IK
k−
1
[
X
]
, each polynomial being generated by a
Shamir's (
k
,
m
)-threshold scheme to share secrets (
ω
1
,...,ω
n
)and(
ϕ
1
,...,ϕ
n
).
We assume that
m
Ω
=(
F
1
,...,F
n
)
and
Φ
∈I
m
,wedefinetheshares
(
F
1
i
,...,F
ni
)
and
(
G
1
i
,...,G
ni
)
.If
Q
is the scalar product of
≥
2
k
−
1
. For each index
i
Ω
and
Φ
,then:
(i)
Q
∈
IK
2
k−
2
[
X
]
,
(ii)
Q
(0) =
i
=1
ω
i
×
∈I
m
,
Q
(
)=
i
=1
F
i
×
ϕ
i
and for
G
i
.
Search WWH ::
Custom Search