US 8,275,124 B2Granted

Threshold secret sharing apparatus, threshold secret sharing scheme, secret information decryption method, and program for the same

AssigneeKddi Corporation

InventorsJun Kurihara, Shinsaku Kiyomoto, Toshiaki Tanaka

Life of this patent

Estimating the term…

Loading patent…

Abstract

A threshold secret sharing apparatus, a threshold secret sharing scheme, a secret information recovery apparatus a secret information recovery method, and a program thereof are provided using XOR computation, thereby offering a general (k,n) threshold secret sharing scheme with high computation speed. Secret information K is divided into (np−1) divided pieces of secret information Kq (np is a prime number which is equal to or greater than a secret distribution number n). Furthermore, dummy secret information K0 is generated. Moreover, random numbers R, which are mutually independent are generated. Then, pieces of shares are created using exclusive-OR (XOR) operations based upon the dummy secret information K0, the divided piece of secret information Kq, and the random numbers R. The pieces of shares thus generated are concatenated so as to generate n shares Si, thereby providing a (k,n) threshold secret sharing scheme.

Claims6

Dependent claims

A threshold secret sharing apparatus configured by a computer comprising:

a dividing means which divides inputted secret information K into same size (np−1) divided pieces of secret information Kq (np is a prime number which is equal to or greater than a secret distribution number) according to a program loaded into the computer, the secret information K being divided according to a first expression
K=K1∥K2∥ . . . ∥Knp-1
whose operators and symbols are defined according to a set of definitions including
{circle around (x)}:
Bitwise exclusive-or (XOR) operation
∥:
Concatenation of binary sequence
n:
The number of participants (nεN, 2≦n)
k:
Threshold (kεN,2≦k≦n)
np:
A prime number such that (np≧n)
d:
Data bit length in each processing (dεN)
pi:
Participant (i-εN0, 0≦i≦n−1)
K:
Secret information (Kε{0,1}d(np−1))
Kq:
A divided piece of secret information such that
Kqε{0,1}d,qεN,1≦q≦np−1,K1∥K2∥ . . . Knp-1=K
K0:
A dummy divided piece of secret information (K0ε{0}d)
Rlt:
A random number (Rltε{0,1}d,0≦t≦k−2, 0≦l≦np−1)
Si:
A share which is sent to the participant Pi
S(i,m):
A piece of share Si which is sent to the participant Pi,
(S(i,0)∥S(i,1)∥Λ∥S(i,np-2)=S,0≦m≦np−2);
a dummy information generating means which generates dummy partial secret information K0 according to a program loaded into the computer, the symbol K0 being defined according to the set of definitions;
(k−1) random number generating means which generate respective sets of random numbers Rtl which are mutually independent according to a program loaded into the computer, the symbols k and Rtl being defined according to the set of definitions;
a generating means of pieces of shares, which generates pieces of shares by exclusive-OR (XOR) operations based upon the dummy partial secret information K0, the divided pieces of secret information Kq, and the random numbers Rtl according to a program loaded into the computer, the pieces of shares being generated according to a second expression
S
(
i
,
m
)
=
{
⊕
t
=
0
k
-
2
⁢
R
t
·
i
+
m
t
}
⊕
K
m
-
i
,
(
0
≤
i
≤
n
-
1
,
0
≤
m
≤
n
p
-
2
)
whose operators and symbols are defined according to the set of definitions;
and
a concatenating means which concatenates the pieces of shares so as to generate n shares Si according to a program loaded into the computer, the pieces of shares being concatenated according to a third expression
Si=S(i,0)∥S(i,1)∥ . . . ∥S(i,np-3)∥S(i,np-2)
whose operators and symbols are defined according to the set of definitions.

84 more elements

A threshold secret sharing method executed by operation of a computer comprising:

dividing inputted secret information K into same size (np−1) divided pieces of secret information Kq (np is a prime number which is equal to or greater than a secret distribution number), the secret information K being divided according to a first expression
K=K1∥K2∥ . . . ∥Knp-1
whose operators and symbols are defined according to a set of definitions including
{circle around (x)}:
Bitwise exclusive-or (XOR) operation
∥:
Concatenation of binary sequence
n:
The number of participants (nεN, 2≦n)
k:
Threshold (kεN, 2≦k≦n)
np:
A prime number such that (np≧n)
d:
Data bit length in each processing (dεN)
pi:
Participant (iεN0, 0≦i≦n−1)
K:
Secret information (Kε{0,1}d(np−1))
Kg:
A divided piece of secret information such that
Kqε{0,1}d, qεN,1≦q≦np−1,K1∥K2∥ . . . Knp-1=K
K0:
A dummy divided piece of secret information (K0ε{0}d)
Rlt:
A random number (Rltε{0,1}d,0≦t≦k−2, 0<l≦np−1)
Si:
A share which is sent to the participant Pi
S(i,m):
A piece of share Si which is sent to the participant Pi,
(S(i,0)∥S(i,1)∥Λ∥S(i,np-2)=S,0≦m≦np−2);
generating dummy partial secret information K0, the symbol K0 being defined according to the set of definitions;
generating sets of random numbers Rtl which are mutually independent, the symbol Rtl being defined according to the set of definitions;
generating pieces of shares using exclusive-OR (XOR) computation based upon the dummy partial secret information K0, the divided pieces of secret information Kq, and the random numbers Rtl, the pieces of shares being generated according to a second expression
S
(
i
,
m
)
=
{
⊕
t
=
0
k
-
2
⁢
R
t
·
i
+
m
t
}
⊕
K
m
-
i
,
(
0
≤
i
≤
n
-
1
,
0
≤
m
≤
n
p
-
2
)
whose operators and symbols are defined according to the set of definitions;
and
concatenating the pieces of shares so as to generate n shares Si, the pieces of shares being concatenated according to a third expression
Si=S(i,0)∥S(i,1)∥ . . . ∥S(i,np-3)∥S(i,np-2)
whose operators and symbols are defined according to the set of definitions.

84 more elements

A computer program product comprising a computer-readable non-transitory storage medium having computer readable instructions recorded thereon, the computer readable instructions being operative, when performed by a computerized device, to cause the computerized device to:

divide inputted secret information K into same size (np−1) divided pieces of secret information Kq (np is a prime number which is equal to or greater than a secret distribution number), the secret information K being divided according to a first expression
K=K1∥K2∥ . . . ∥Knp-1
whose operators and symbols are defined according to a set of definitions including
{circle around (x)}:
Bitwise exclusive-or (XOR) operation
∥:
Concatenation of binary sequence
n:
The number of participants (nεN,2≦n)
k:
Threshold (kεN,2≦k≦n)
np:
A prime number such that (np≧n)
d:
Data bit length in each processing (dεN)
pi:
Participant (iεN0, 0≦i≦n−1)
K:
Secret information (Kε{0,1}d(np−1))
Kq:
A divided piece of secret information such that
Kqε{0,1}d,qεN,1≦q≦np−1,K1∥K2∥ . . . Knp-1=K
K0:
A dummy divided piece of secret information (K0ε{0}d)
Rlt:
A random number (Rltε{0,1}d, 0≦t≦k−2,0≦n≦np−1)
Si:
A share which is sent to the participant Pi
S(i,m):
A piece of share Si which is sent to the participant Pi,
(S(i,0)∥S(i,1)∥Λ∥S(i,np-2)=S,0≦m≦np−2);
generate dummy partial secret information K0, the symbol K0 being defined according to the set of definitions;
generate sets of random numbers Rtl which are mutually independent, the symbol Rtl being defined according to the set of definitions;
generate pieces of shares using exclusive-OR (XOR) computation based upon the dummy partial secret information K0, the divided pieces of secret information Kq, and the random numbers Rtl, the pieces of shares being generated according to a second expression
S
(
i
,
m
)
=
{
⊕
t
=
0
k
-
2
⁢
R
t
·
i
+
m
t
}
⊕
K
m
-
i
,
(
0
≤
i
≤
n
-
1
,
0
≤
m
≤
n
p
-
2
)
whose operators and symbols are defined according to the set of definitions;
and
concatenate the pieces of shares so as to generate n shares Si, the pieces of shares being concatenated according to a third expression
Si=s(i,0)∥S(i,1)∥ . . . ∥S(i,np-3)∥S(i,np-2)
whose operators and symbols are defined according to the set of definitions.

84 more elements

Dependencies are inferred from the claim text.