Cryptography Reference
In-Depth Information
-
If R = P + Q, then the corresponding polynomial functions satisfy the rela-
tionship
R
(
x
)=
P
(
x
)+
Q
(
x
)
,
-
Similarly, if
R
=
P
Q
, then the corresponding polynomial functions satisfy
the relationship
R
(
x
)=
P
(
x
)
×
×
Q
(
x
)
.
Definition 5.
Let
Φ
=(
F
1
,...,F
n
)
be a vector of polynomials of
IK
t
[
X
]
.
We define
Φ
(
x
)
=(
F
1
(
x
)
,...,F
n
(
x
))
as the vector of corresponding polynomial
functions.
)
=
(
F
1
(
α
)
,...,F
n
(
α
))
the vector of polynomial functions
F
1
(
x
)
,...,F
n
(
x
)
evalu-
ated for the argument
x
=
α
. By homogeneity, we denote
F
α
the value of a
polynomial function
F
applied to the argument
x
=
α
.
For
any
element
α
∈
IK
,wedenote
Φ
α
=
Φ
(
α
Definition 6.
Let
=(
Z
1
,...,Z
n
)
be two vectors of
polynomials of
IK
k−
1
[
X
]
. We define the scalar product between
Φ
=(
F
1
,...,F
n
)
and
Ω
Φ
and
Ω
as
n
Φ
Ω
F
i
×
Z
i
.
=
i
=1
Note that we assume
p ≥
2
k −
1, and thus
F
i
× Z
i
is a polynomial of IK
2
k−
2
[
X
].
Lemma 1.
Let
F
be a quasi-random polynomial of
IK
k
[
X
]
and
G
a(quasi-
random) polynomial of
IK
k
[
X
]
.Then,
P
=
F
+
G
is a quasi-random polynomial
of
IK
k
[
X
]
.
Proof.
The degree of the sum of two polynomials is lower or equal to the maxi-
mum degree of the two original polynomials. Thus deg
P
≤
max(deg
F,
deg
G
)
≤
k
. It follows
P
IK
k
[
X
].
The quasi-random polynomials
F
,
G
, and their sum,
P
, may be written under
the form:
∈
k
k
k
f
i
X
i
,
g
i
X
i
,
(
f
i
+
g
i
)
X
i
,
F
=
G
=
and
P
=
i
=0
i
=0
i
=0
where
f
i
∈
R
IK a n d
g
i
∈
R
IK ( 1
k
, the coecient
f
i
+
g
i
is random (the sum of a random element of IK with another element of
IK is random) and the constant term
f
0
+
g
0
has a predetermined value. Thus,
P
is a quasi-random polynomial.
≤
i
≤
k
). Therefore, for 1
≤
i
≤
Theorem 1 (Addition of shares).
Let
F
and
G
be two quasi-random polyno-
mials of
IK
k−
1
[
X
]
generated by Shamir's (
k
,
m
)-threshold schemes (see Sect. 5.1)
to share respectively the secret
α
and the secret
β
amongst
m
users. We also as-
sume that
I
k
⊂{
1
,...,m
}
is a set of
k
indices. For each index
i
∈I
k
, we define
the shares
F
i
and
G
i
.If
P
is the sum of
F
and
G
,then:
(i)
P
is a quasi-random polynomial of
IK
k−
1
[
X
]
,
(ii)
P
(0) =
α
+
β
and for
i
∈I
k
,
P
(
i
)=
F
i
+
G
i
.
In other words,
P
may be considered as a polynomial generated by Shamir's
(
k
,
m
)-threshold scheme to share the secret
α
+
β
.
Search WWH ::
Custom Search