Secret sharing system and storage medium

Details Secret sharing system and storage medium Secret sharing system and storage medium

2000-01-20

2004-10-26

Vu, Kim (Department: 2135)

Cryptography

Particular algorithmic function encoding

Public key

C380S042000, C380S277000, C380S283000, C380S285000, C380S286000

Reexamination Certificate

active

06810122

ABSTRACT:

BACKGROUND OF THE INVENTION
This invention relates to a secret sharing system and a storage medium for a crypto system based on the problem of factorization into prime factors, and more particularly to a crypto system and a storage device which shares a secret key secretly to n shareholders and enable t of the n shareholders to perform shared decryption and signature without computing the secret key.
One known crypto system based on the problem of factorization into prime factors is a secret sharing scheme called a threshold scheme in the field of secret sharing using, for example, an RSA crypto system. The threshold scheme has a secret information recovery characteristic with a threshold of t as a boundary line. The secret information recovery characteristic is such that, when secret information is shared into n share, the secret information is recovered completely from t out of the n share but cannot be recovered at all from t−1 share (where 1<t<n).
One known secret sharing scheme of this type is a (t, n) secret sharing scheme where the concept of the threshold scheme has been introduced into the RSA crypto system and a secret key has been shared secretly in the (t, n) type (Y. Frankel, P. Gemmell, P. D.
MacKenzie and M. Yung, “Optimal-resilience proactive public-key cryptosystems,” 38
th
Annual Symposium on Foundations of Computer Science, pp. 384-393, 1997, which is hereinafter referred to as reference [FGMY97]), and T. Okamoto, “Threshold key-recovery systems for RSA,” Security Protocols, LNCS 1361, pp. 191-200, 1997, which is hereinafter referred as reference [Oka97]).
Reference [FGMY97] has described a method of enabling any t shareholders to perform decryption and signature without computing a secret key d in an environment where dealers (distributors) exist. That is, it is a method of enabling a secret key d capable of decryption and signature to be created from any t share even if shareholders do not know prime factors of composite number N.
On the other hand, in an environment where no dealer exists, one known secret sharing scheme is a (n, n) secret sharing scheme, not a threshold scheme. In the (n, n) secret sharing scheme, all the shareholders create a key where nobody knows the secret(D. Boneh and M. Franklin, “Efficient generation of shared RSA keys,” Advances in Cryptology-CRYPTO '97, LNCS 1294, pp. 425-439, 1997, which is hereinafter referred to as reference [BF97]).
In the scheme of reference [BF97], when a key is generated, (n, n) secret sharing is performed simultaneously. In addition, by combining the partial outputs from all the shareholders using the held share, the ciphertext can be decrypted without computing the secret key d.
In reference [BF97], a method of constructing (2, n) secret sharing (n≧3) from (2, 2) secret sharing has been described as shown in the following algorithm.
To simplify explanation, it is assumed that a user knows a secret key d and the user performs (2, n) secret sharing of the secret key d. It is also assumed that the number of secret sharing polynomials expressing combinations of share is r+1 where r=┌log n┘ for the total number of shareholders P being n (in the present specification, ┌┘ means that the smallest integer equal to or larger than the value in the parentheses).
To perform the (2, 2) secret sharing r+1 times, the user creates r+1 independent polynomials d=d
0,0
+d
0,1
=d
1,0
+d
1,1
= . . . =d
r,0
+d
r,1
separately.
Next, it is assumed that the identification number of each shareholder in a total of n shareholders is z (z∈[0, n]) and a binary representation of identification number z is z(2)=&bgr;
r
&bgr;
r−1
. . . &bgr;
0
. The user takes all the 0-th to n-th shareholders P
0
to P
n
into account and sends r+1 share {d
r
, &bgr;
r
, d
r−1
, &bgr;
r−1
, . . . , d
0
, &bgr;
0
} to the z-th shareholder P
Z
.
As a result, a set of shares corresponding to a binary representation of identification number z is sent to all the shareholders P
0
to P
n
.
When the number of an shareholder is set uniquely after the set has been sent, any two shareholders Pi, Pj (i≠j) can recover the secret key d (d
i,0
+d
i,1
=d) from the shares (d
i,0
, d
i,1
) in the same digit differing in bit &bgr; at number z(2) of the r+1 share of (2, 2).
Next, related techniques for expanding the type of secret sharing as the method of constructing the (2, n) secret sharing from the (2, 2) one will be explained.
One of the techniques of this type is a (t, 1
m
) secret sharing scheme using the (t, 1) type (S. R. Blackburm, M. Burmester, Y. Desmedt and P. R. Wild, “Efficient multiplicative sharing schemes,” Advances in Cryptology-EURO-CRYPT '96, pp. 107-118, 1996, which is hereinafter referred to as reference [BBDW96]). The scheme of reference [BBDW96] is related to 1 that satisfies the following equation (1) for a positive integer m.
1
≥
(
t
2
)
⁢
(
m
-
1
)
if
⁢
 
⁢
b
=
(
t
2
)
⁢
(
m
-
1
)
(
1
)
then
t
=2
b
≧1→≧1
t
=3
b
≧3→1 ≧3
t
=4
b
≧6→1≧6
When t≧4, then t<1. Specifically, when t≧4, it is impossible to construct a (t, n) secret sharing scheme using the (t, t) type.
For this reason, a (3, 3
2
) secret sharing scheme using the (3, 3) type in reference [BBDW96] will be explained hereinafter. Let m=2, 1=3, and t=3, and calculate b using equation (2).
b
=
(
t
2
)
⁢
(
m
-
1
)
=
3
(
2
)
First, (3, 3) secret sharing is performed b+1=4 times and four independent polynomials for the secret key d using equations (3) are formulated:
d=d
0
,0
+d
0
,1
+d
0
,2 (fist time)=
d
1
,0
+d
1
,1
+d
1
,2 (second time)=
d
2
,0
+d
2
,1
+d
2
,2 (third time)=
d
3
,0
+d
3
,1
+d
3
,2 (fourth time)  (3)
In addition, let f(x)=a
0
+a
1
X (mod 3).
In reference [BBDW96], if a set of the final shareholders (in this case, 3
2
shareholders) is P′, f(X) is expressed by equation (4) (the first line on page 113, “d” in the equation is replaced with “m”, in the present specification).
f
⁡
(
x
)
=
∑
i
=
0
d
-
1
⁢
a
i
⁢
X
i
∈
P
′
(
4
)
Equation (4), however, is mistaken for the following equation (5).
f
⁡
(
x
)
=
∑
i
=
0
d
-
1
⁢
a
i
⁢
X
i
⁡
(
mod
⁢
 
⁢
l
)
(
5
)
where a
0
, a
1
∈F
3
and f(
)=a
1
.
f
1
(
x
)=0 (mod 3)
f
2
(
x
)=1 (mod 3)
f
3
(
x
)=2 (mod 3)
f
4
(
x
)=0
+X
(mod 3)
f
5
(
x
)=1
+X
(mod 3)
f
6
(
x
)=2
+X
(mod 3)
f
7
(
x
)=0+2
X
(mod 3)
f
8
(
x
)=1+2
X
(mod 3)
f
9
(
x
)=2+2
X
(mod 3)
Each shareholder fj has (d
0
,f
j
(
), d
1
,f
j
(0), d
2
,f
j(1)
, d
3
,f
j(2)
).
FIG. 1
concretely shows the sets of shares held in the individual shareholders.
FIG. 2
shows combinations of shareholders and relevant share.
As shown in
FIG. 1
, for example when shareholders f
1
, f
4
, and f
8
(second row) perform shared decryption, they extract the share corresponding to X=
. Each of them can compute the output corresponding to the secret key d by doing calculations using (d
0,0
, d
0,1
, d
0,2
).
In
FIG. 2
, a combination with one of the alphabetic characters a to l means that there are three types of computation routes for the output corresponding to the secret key d in the same combination in each shareholder (in
FIG. 2
, “d” is merely an alphabetic character, not the secret key d). For example, in the combination (f
1
, f
2
, f
3
) with character b, it is possible to collect three shares to recover the secret key d using any of X=0, 1, and 2.
In connection with the (n, n) secret sharing scheme in reference [BF97], there is a scheme that has introduced the concept of threshold scheme (Y. F

Affiliated with

Also associated with

Rating

Secret sharing system and storage medium does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Secret sharing system and storage medium, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Secret sharing system and storage medium will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3328057