Key establishment method and system using commutative linear function
View Patent ↗Provided are a key establishment method and system using commutative linear functions. In the method, a server defines a set of linear functions that use elements of a first finite field as coefficients and satisfy a commutative rule, selects a first linear function from the set, and selects a predetermined element from a second finite field. Next, the server selects a second linear function corresponding to each of nodes from the set, generates a predetermined combination function based on the first and second linear functions, generates a value of the second linear function using the selected element as a factor, and transmits the combination function and the value of the second linear function to a corresponding node. Each node receives the value of the second linear function from a server, exchanges the received values with the other nodes, computes a value using the exchanged value as a factor of the combination function, and establishes the computed value as a shared key between the nodes. Therefore, each node can perform key establishment with a small amount of computation and low memory consumption, while guaranteeing end-to-end security.
1. A key establishment method comprising:
(a) a server defining a set of linear functions which use elements of a first finite field as coefficients and satisfy a commutative rule, selecting a first linear function from the set, and selecting a predetermined element from a second finite field;
(b) the server, for each of a plurality of nodes, selecting a second linear function from the set; generating a combination function based on the first linear function and the second linear function of the corresponding node; generating a value of the second linear function of the corresponding node using the selected element as a factor; and transmitting the combination function and the value of the second linear function to the corresponding node; and
(c) each node exchanging the value of the second linear function received from the server with the other nodes, computing a value of the combination function using the exchanged value as a factor, and establishing the computed value as a shared key among the nodes wherein (b) comprises generating the combination function ƒ∘h i (x)mod(x 2 m −x) based on the first linear function ƒεF and the second linear function h i εF which are selected from the set
F
=
{
∑
i
=
0
m
-
1
α
i
x
2
i
|
α
i
∈
G
F
(
2
)
}
,
and transmitting the combination function ƒ∘h i (x)mod(x 2 m −x) and the value h i (α) of the second linear function to each node.
2. The method of claim 1 , wherein the first finite field is GF(2), and the second finite field is GF(2 m ).
3. The method of claim 1 , wherein during (a), the set of the linear functions is defined as
F
=
{
∑
i
=
0
m
-
1
α
i
x
2
i
|
α
i
∈
G
F
(
2
)
}
,
and a predetermined element αεGF(2 m ) is selected from the second finite field.
4. The method of claim 1 , wherein during (c), a first node i and a second node j respectively receive the combination function ƒ∘h i (x)mod(x 2 m −x) and the value h i (α) of the second linear function, and the combination function ƒ∘h j (x)mod(x 2 m −x) and the value h j (α) of the second linear function from the server, exchange the values h i (α) and h j (α) with each other, and set ƒ∘h i (h j (α))=ƒ∘h i ∘h j (α)=ƒ∘h j (h i (α)) as a shared key.
5. A key establishment system comprising:
a key generating unit of a server, the key generating unit defining a set of linear functions which use elements of a first finite field as coefficients and satisfy a commutative rule, selecting a first linear function from the set, and selecting a predetermined element from a second finite field; and
a key allocating unit of a server, wherein for each of a plurality of nodes the key allocating unit selecting a second linear function from the set, generating a combination function based on the first linear function and the second linear function of the corresponding node, generating a value of the second linear function of the corresponding node using the selected element as a factor, and transmitting the combination function and the value of the second linear function to the corresponding node wherein the key generating unit defines the set of the linear functions as
F
=
{
∑
i
=
0
m
-
1
α
i
x
2
i
|
α
i
∈
G
F
(
2
)
}
and selects a predetermined element αεGF(2 m ) from the second finite field, and
the key allocating unit generating a combination function ƒ∘h i (x)mod(x 2 m −x) based on the first linear function ƒεF and the second linear function h i εF which are selected from the set
F
=
{
∑
i
=
0
m
-
1
α
i
x
2
i
|
α
i
∈
G
F
(
2
)
}
,
and transmitting the combination function ƒ∘h i (x)mod(x 2 m −x) and a value h i (α) of the second linear function to each node; and
wherein each node exchanges the received value of the second linear function with the other nodes, computes a value using the exchanged value as a factor of the combination function, and sets the computed value as a shared key between the nodes.
6. The system of claim 5 , wherein the first finite field is GF(2), and the second finite field is GF(2 m ).
7. The system of claim 5 , wherein a first node i and a second node j respectively receive the combination function ƒ∘h i (x)mod(x 2 m −x) and the value h i (α) of the second linear function, and the combination function ƒ∘h j (x)mod(x 2 m −x) and the value h j (α) of the second linear function from the server, exchange the values h i (α) and h j (α) with each other, and set ƒ∘h i (h j (α))=ƒ∘h i ∘h j (α)=ƒ∘h j (h i (α)) as a shared key.