Secret sharing method, secret sharing system, distributing apparatus and program

1. A secret sharing method in which x is an element X of an irreducible polynomial f[X] that generates an extension field GF(x q ), n and k are integers equal to or larger than 2 and satisfy n≥2k−1, p 0 to p k−1 are different integers equal to or larger than 0 and smaller than n, and A is an n−by−k matrix defined by a formula given below:

A

ij

=

{

1

if

⁢

⁢

i

=

j

⁢

⁢

and

⁢

⁢

i

<

k

-

1

0

if

⁢

⁢

i

≠

j

⁢

⁢

and

⁢

⁢

i

<

k

-

1

x

(

i

-

k

-

1

)

⁢

j

if

⁢

⁢

i

≥

k

-

1

where

iϵ{0, . . . ,n−1}, jϵ{0, . . . , k−1},

the secret sharing method comprising:

generating, by circuitry of a distributing apparatus, random numbers r 0 , . . . , r k−2 ϵ GF(x q );

generates, by the circuitry of the distributing apparatus, shares b 0 to b n−1 by calculating a product of a vector a=(r 0 , . . . , r k−2 , s), having the random numbers r 0 to r k−2 and plaintext sϵ GF(x q ) as its elements, and the matrix A; the generating of the shares b 0 to b n−1 requiring fewer than (k−1)n multiplications;

distributing, by the circuitry of the distributing apparatus, the shares b 0 to b n−1 to a plurality of devices;

receiving, by circuitry of a restoring apparatus and from the plurality of devices, k shares b p0 to b pk−1 of the shares b 0 to b n−1 distributed by the distributing apparatus to the plurality of devices;

generating, by the circuitry of the restoring apparatus, a vector b′=(b p0 , . . . ,b pk−1 ) having, as its elements, the k shares b p0 , . . . ,b pk−1 of the shares b 0 to b n−1 ;

generating, by the circuitry of the restoring apparatus, an inverse matrix A′ −1 of a k-degree square matrix having the p 0 -th to p k−1 -th rows of the matrix A; and

restoring, by the circuitry of the restoring apparatus, the plaintext s by multiplying the k-th row of the inverse matrix A′ 1 and the vector b′.

2. The secret sharing method according to claim 1 ,

wherein q is the degree of field extension of the extension field GF(x q ), d is the degree of a term of the highest degree of a polynomial f′ obtained by excluding a term of the highest degree from the irreducible polynomial f[X], m=n−k, and (m−1)(k−1)≤q−d,

the secret sharing method comprising:

calculating, by the circuitry of the distributing apparatus, a value c i for iϵ{0, . . . , m−1}as expressed by a formula given below:

c

i

=

∑

0

≤

j

<

k

-

1

⁢

r

j

⁢

x

ij

+

sx

i

⁡

(

k

-

1

)

updating the value c i by calculating g i −h i f′ by using a polynomial h i obtained by dividing a part of degree q or higher of the value c i by X q and a polynomial g i which is a part of degree below q of the value c i , and setting the values c 0 to c m−1 as the shares b 0 to b n−1 .

3. The secret sharing method according to claim 1 ,

wherein q is the degree of field extension of the extension field GF(x q ), d is the degree of a term of the highest degree of a polynomial f 40 obtained by excluding a term of the highest degree from the irreducible polynomial f[X], and m=n −k,

the secret sharing method comprising:

setting a′ j =a j and d j =0 for j ϵ{0, . . . , k−1}, calculating a value c 1 for iϵ{0, . . . , m−1} as expressed by a formula given below,

c

i

=

∑

0

≤

j

<

k

⁢

a

j

′

⁢

x

ij

-

d

j

calculating g i −h i f′ by using a polynomial h i obtained by dividing a part of degree q or higher of the value c i by X q and a polynomial g i which is a part of degree below q of the value c i , the value c i is updated, if i≠m−1 and (i+1)j−d≥q−d for iϵ{0, . . . , m−1}and jϵ{0, . . . , k−1}, updating a′ j :=a′ j X α and d j :=d j +α, and setting the values c 0 to c m−1 , as the shares b 0 to b n−1 .

4. The secret sharing method according to claim 1 , wherein a number of multiplications performed in the generating of the shares b 0 to b n−1 is (k−1)(n−k+1).

5. A secret sharing system comprising a distributing apparatus and a restoring apparatus;

wherein x is an element X of an irreducible polynomial f[X] that generates an extension field GF(x q ), n and k are integers equal to or larger than 2 and satisfy n≥2k−1, p 0 to p k−1 , are different integers equal to or larger than 0 and smaller than n, and A is an n−by−k matrix defined by a formula given below:

A

ij

=

{

1

if

⁢

⁢

i

=

j

⁢

⁢

and

⁢

⁢

i

<

k

-

1

0

if

⁢

⁢

i

≠

j

⁢

⁢

and

⁢

⁢

i

<

k

-

1

x

(

i

-

k

-

1

)

⁢

j

if

⁢

⁢

i

≥

k

-

1

where

iϵ{0, . . . , n −1},jϵ{0, . . . ,k−1},

the distributing apparatus comprising:

circuitry configured to:

generate random numbers r 0 , . . . , r k−2 ϵ GF(x q ),

generate shares b o to b n−1 by calculating a product of a vector a=(r 0 . . . , r k−2 , s), having the random numbers r 0 to r k−2 and plaintext sϵ GF(x q ) as its elements, and the matrix A, the generating of the shares b 0 to b n−1 requiring fewer than (k−1)n multiplications, and

distribute the shares b 0 to b n−1 to a plurality of devices;

the restoring apparatus comprising:

another circuitry configured to:

receive, from the plurality of devices, b p0 to b pk−1 of the shares b 0 to b n−1 distributed by the distributing apparatus to the plurality of devices,

generate a vector b′=(b p0 , . . . b pk−1 ) having, as its elements, k shares b p0 to b pk−1 selected from the shares b 0 to b n−1 ,

generate an inverse matrix A′ −1 of a k-degree square matrix having the p 0 -th to p k−1 -th rows of the matrix A, and

restore the plaintext s by multiplying the k-th row of the inverse matrix A′ −1 and the vector b′.

6. A distributing apparatus in which x is an element X of an irreducible polynomial f[X] that generates an extension field GF(x q ), n and k are integers equal to or larger than 2 and satisfy n≥2k−1, p 0 to p k−1 are different integers equal to or larger than 0 and smaller than n; and A is an n−by−k matrix defined by a formula given below:

A

ij

=

{

1

if

⁢

⁢

i

=

j

⁢

⁢

and

⁢

⁢

i

<

k

-

1

0

if

⁢

⁢

i

≠

j

⁢

⁢

and

⁢

⁢

i

<

k

-

1

x

(

i

-

k

-

1

)

⁢

j

if

⁢

⁢

i

≥

k

-

1

where

iϵ{0, . . . , n−1},jϵ{0, . . . ,k −1},

the distributing apparatus comprising:

circuitry configured to:

generate random numbers r 0 , . . . , r k−2 ϵ GF(x q );

generate shares b 0 to b n−1 by calculating a product of a vector a=(r 0 , . . . , r k−2 , s), having the random numbers r 0 to r k−2 and plaintext sϵ GF(x q ) as its elements, and the matrix A, the generating of the shares b 0 to b n−1 requiring fewer than (k−1)n multiplications; and

distribute the shares b 0 to b n−1 to a plurality of devices.

7. A non-transitory computer readable medium including computer executable instructions that make a distributing apparatus, wherein x is an element X of an irreducible polynomial f[X] that generates an extension field GF(x q ), n and k are integers equal to or larger than 2 and satisfy n≥2k −1, p 0 to p k−1 are different integers equal to or larger than 0 and smaller than n; and A is an n−by−k matrix defined by a formula given below:

A

ij

=

{

1

if

⁢

⁢

i

=

j

⁢

⁢

and

⁢

⁢

i

<

k

-

1

0

if

⁢

⁢

i

≠

j

⁢

⁢

and

⁢

⁢

i

<

k

-

1

x

(

i

-

k

-

1

)

⁢

j

if

⁢

⁢

i

≥

k

-

1

where

iϵ{0, . . . , n−1},jϵ{0, . . . ,k −1},

perform a method comprising:

generating random numbers r 0 , . . . , r k−2 ϵ GF(x q ); and

generating shares b 0 to b n−1 by calculating a product of a vector a=(r 0 , . . . , r k−2 , s), having the random numbers r 0 to r k−2 and plaintext sϵ GF(x q ) as its elements, and the matrix A, the generating of the shares b 0 to b n−1 requiring fewer than (k−1)n multiplications; and

distributing the shares b 0 to b n−1 to a plurality of devices.