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