US 9,432,188 B2Granted

Secret sharing system, data distribution apparatus, distributed data transform apparatus, secret sharing method and program

AssigneeNippon Telegraph and Telephone Corporation

InventorsKoji Chida, Dai Ikarashi, Koki Hamada, Ryo Kikuchi

Life of this patent

Estimating the term…

Loading patent…

Abstract

A secret sharing system transforms computational secret shares to homomorphic secret shares. On a data distribution apparatus, a key selector selects K′−1 keys. A pseudorandom number generator generates pseudorandom numbers from the keys. An encryption part generates a ciphertext from information using the pseudorandom numbers. A key division part divides the keys into N shares fg(n) using an arbitrary sharing. A ciphertext division part divides the ciphertext into N shares fc(n) using an arbitrary sharing. When K shares fsj(i) are input into distributed data transform apparatuses, a reconstruction part generates a reconstructed value Uj by reconstructing shares fsj(i) using the secret sharing, and when K shares fc(i) are input, generates the reconstructed value Uj by reconstructing shares fc(i) using the arbitrary sharing. A redivision part divides reconstructed value Uj into N shares fUj(n) using a homomorphic secret sharing. A transformer generates share ga(i) of the information from K′ shares fUj.

Claims16

Dependent claims

A secret sharing system comprising a data distribution apparatus and N distributed data transform apparatuses,

the data distribution apparatus comprising:
circuitry configured to
receive an electronic information file a as an input;
select K−1 keys s1, . . . , sK−1εS;
compute rj=P(sj) from the keys s1, . . . , sK−1 to generate pseudorandom numbers r1, . . . , rK−1, where j=1, . . . , K−1;
generate a ciphertext c from the electronic information file aεR by using the pseudorandom numbers r1, . . . , rK−1;
divide each of the keys s1, . . . , sK−1 into N shares fs1(n), . . . , fsK−1(n) by using an arbitrary secret sharing scheme S1;
and
divide the ciphertext c into N shares fc(n) by using an arbitrary secret sharing scheme S0;
each of the distributed data transform apparatuses comprising:
circuitry configured to
compute a reconstructed value Uj=P(uj) from a value uj generated by reconstruction of shares fsj(i) by using the secret sharing scheme S1 when K shares fsj(i) are input into the distributed data transform apparatuses, and generate the reconstructed value Uj (j=K) by reconstruction of shares fc(i) by using the secret sharing scheme S0 when K shares fc(i) are input into the distributed data transform apparatuses;
divide the reconstructed value Uj into N shares fUj(n) by using an arbitrary homomorphic secret sharing scheme S2;
and
generate a share ga(i) of the electronic information file a from K shares fU1(i), . . . , fUK(i);
where N and K are integers greater than or equal to 2, N≧K, n=1, . . . , N, λ represents K different integers greater than or equal to 1 and less than or equal to N, i is an integer, iελ, fx(n) represents N shares of x, R is a ring, S is a key space, and P(x) is a mapping that maps xεS to the ring R,
wherein at least K distributed data transform apparatuses are configured to reproduce the original electronic information file a when at least K reconstructed values Uj are reconstructed separately respectively by the at least K distributed data transform apparatuses, and none of the original electronic information file a can be obtained when less than K reconstructed values Uj are reconstructed by less than K distributed data transform apparatuses.

14 more elements

A secret sharing system comprising a data distribution apparatus and N distributed data transform apparatuses,

the data distribution apparatus comprising:
circuitry configured to
receive an electronic information file a as an input;
select K′−1 keys s1, . . . , sK′−1εS;
compute rj=P(sj) from the keys s1, . . . , sK′−1 to generate pseudorandom numbers r1, . . . , rK′−1, where j=1, . . . , K′−1;
generate a ciphertext c from the electronic information file aεR by using the pseudorandom numbers r1, . . . , rK′−1;
divide each of the keys s1, . . . , sK′−1 into N shares fs1(n), . . . , fsK′−1(n) by using an arbitrary secret sharing scheme S1;
and
divide the ciphertext c into N shares fc(n) by using an arbitrary sharing scheme S0;
each of the distributed data transform apparatuses comprising:
circuitry configured to
compute a reconstructed value Uj=P(uj) from a value uj generated by reconstruction of shares fsj(i) by using the secret sharing scheme S1 when K shares fsj(i) are input into the distributed data transform apparatuses, and generate the reconstructed value Uj (j=K′) by reconstruction of shares fc(i) by using the secret sharing scheme S0 when K shares fc(i) are input into the distributed data transform apparatuses;
divide the reconstructed value Uj into N shares fUj(n) by using an arbitrary homomorphic secret sharing scheme S2;
and
generate a share ga(i) of the electronic information file a from K′ shares fU1(i), . . . , fUK′(i);
where N, K and K′ are integers greater than or equal to 2, N≧K, n=1, . . . , N, λ represents K different integers greater than or equal to 1 and less than or equal to N, i is an integer, iελ, fx(n) represents N shares of x, R is a ring, S is a key space, and P(x) is a mapping that maps xεS to the ring R,
wherein at least K′ distributed data transform apparatuses are configured to reproduce the original electronic information file a, when at least K′ reconstructed values Uj are reconstructed separately respectively by the at least K′ distributed data transform apparatuses, and none of the original electronic information file a can be obtained when less than K′ reconstructed values Uj are reconstructed by less than K′ distributed data transform apparatuses.

14 more elements

computes rj=P(sj) from the keys s1, . . . , sK−1 to generate pseudorandom numbers r1, . . . , rK−1, where j=1, . . . , K−1;
generates a ciphertext c from the electronic information file aεR by using the pseudorandom numbers r1, . . . , rK−1;
divides each of the keys s1, . . . , sK−1 into N shares fs1(n), . . . , fsK−1(n) by using an arbitrary secret sharing scheme S1;
and divides the ciphertext c into N shares fc(n) by using an arbitrary secret sharing scheme S0, the distributed data transform apparatus comprising:
circuitry configured to
compute a reconstructed value Uj=P(uj) from a value uj generated by reconstruction of shares fsj(i) by using the secret sharing scheme S1 when K shares fsj(i) are input, and generate the reconstructed value Uj (j=K) by reconstruction of shares fc(i) by using the secret sharing scheme S0 when K shares fc(i) are input;
divide the reconstructed value Uj into N shares fUj(n) by using an arbitrary homomorphic secret sharing scheme S2;
and
generate a share ga(i) of the electronic information file a from K shares fU1(i), . . . , fUK(i);
and
where N and K are integers greater than or equal to 2, N≧K, n=1, . . . , N, λ represents K different integers greater than or equal to 1 and less than or equal to N, i is an integer, iελ, fx(n) represents N shares of x, R is a ring, S is a key space, and P(x) is a mapping that maps xεS to the ring R,
wherein at least K distributed data transform apparatuses of the N distributed data transform apparatuses are configured to reproduce the original electronic information file a, when at least K reconstructed values Uj are reconstructed separately respectively by the at least K distributed data transform apparatuses, and none of the original electronic information file a can be obtained when less than K reconstructed values Uj are reconstructed by less than K distributed data transform apparatuses.

9 more elements

A distributed data transform apparatus, in a secret sharing system comprising a data distribution apparatus and N distributed data transform apparatuses, wherein the data distribution apparatus receives an electronic information file a as an input, selects K′−1 keys s1, . . . , sK′−1εS, computes rj=P(sj) from the keys s1, . . . , sK′−1 to generate pseudorandom numbers r1, . . . , rK′−1, where j=1, . . . , K′−1;

generates a ciphertext c from information aεR by using the pseudorandom numbers r1, . . . , rK′−1, divides each of the keys s1, . . . , sK′−1 into N shares fs1(n), . . . , fsK′−1(n) by using an arbitrary secret sharing scheme S1, and divides the ciphertext c into N shares fc(n) by using an arbitrary sharing scheme S0, the distributed data transform apparatus comprising:
circuitry configured to
compute a reconstructed value Uj=P(uj) from a value uj generated by reconstructing of shares fsj(i) by using the secret sharing scheme S1 when K shares fsj(i) are input, and generate the reconstructed value Uj (j=K′) by reconstruction of shares fc(i) by using the secret sharing scheme S0 when K shares fc(i) are input;
divide the reconstructed value Uj into N shares fUj(n) by using an arbitrary homomorphic secret sharing scheme S2;
and
generate a share ga(i) of the electronic information file a from K′ shares fU1(i), . . . , fUK′(i);
where N, K and K′ are integers greater than or equal to 2, N≧K, n=1, . . . , N, λ represents K different integers greater than or equal to 1 and less than or equal to N, i is an integer, iελ, fx(n) represents N shares of x, R is a ring, S is a key space, and P(x) is a mapping that maps xεS to the ring R,
wherein at least K′ distributed data transform apparatuses are configured to reproduce the original electronic information file a, when at least K′ reconstructed values Uj are reconstructed separately respectively by the at least K′ distributed data transform apparatuses, and none of the original electronic information file a can be obtained when less than K′ reconstructed values Uj are reconstructed by less than K′ distributed data transform apparatuses.

5 more elements

A secret sharing method, implemented by a secret sharing system comprising a data distribution apparatus and N distributed data transform apparatuses, comprising:

by circuitry of the data distribution apparatus:
receiving an electronic information file a as an input;
selecting K−1 keys s1 . . . , sK−1εS,
computing rj=P(sj) from the keys s1, . . . , sK−1 to generate pseudorandom numbers r1, . . . , rK−1, where j=1, . . . , K−1,
generating a ciphertext c from the electronic information file aεR by using the pseudorandom numbers r1, . . . , rK−1,
dividing each of the keys s1, . . . , sK−1 into N shares fs1(n), . . . , fsK−1(n) by using an arbitrary secret sharing scheme S1, and
dividing the ciphertext c into N shares fc(n) by using an arbitrary secret sharing scheme S0;
and
by circuitry of each of the distributed data transform apparatuses:
computing a reconstructed value Uj=P(uj) from a value uj generated by reconstruction of shares fsj(i) by using the secret sharing scheme S1 when K shares fsj(i) are input into the distributed data transform apparatuses, and generate the reconstructed value Uj (j=K) by reconstruction of shares fc(i) by using the secret sharing scheme S0 when K shares fc(i) are input into the distributed data transform apparatuses;
dividing the reconstructed value Uj into N shares fUj(n) by using an arbitrary homomorphic secret sharing scheme S2;
and
generating a share ga(i) of the electronic information file a from K shares fU1(i), . . . , fUK(i);
where N and K are integers greater than or equal to 2, N≧K, n=1, . . . , N, λ represents K different integers greater than or equal to 1 and less than or equal to N, i is an integer, iελ, fx(n) represents N shares of x, R is a ring, S is a key space, and P(x) is a mapping that maps xεS to the ring R, and
wherein at least K distributed data transform apparatuses are configured to reproduce the original electronic information file a, when at least K reconstructed values Uj are reconstructed separately respectively by the at least K distributed data transform apparatuses, and none of the original electronic information file a can be obtained when less than K reconstructed values Uj are reconstructed by less than K distributed data transform apparatuses.

12 more elements

A secret sharing method, implemented by a secret sharing system comprising a data distribution apparatus and N distributed data transform apparatuses, comprising:

by circuitry of the data distribution apparatus:
receiving an electronic information file a as an input;
selecting K′−1 keys s1, . . . , sK′−1εS;
computing rj=P(sj) from the keys s1, . . . , sK′−1 to generate pseudorandom numbers r1, . . . , rK′−1, where j=1, . . . , K′−1;
generating a ciphertext c from the electronic information file aεR by using the pseudorandom numbers r1, . . . , rK′−1;
dividing each of the keys s1, . . . , sK′−1 into N shares fs1(n), . . . , fsK′−1(n) by using an arbitrary secret sharing scheme S1;
and
dividing the ciphertext c into N shares fc(n) by using an arbitrary sharing scheme S0;
by circuitry of each of the distributed data transform apparatuses:
computing a reconstructed value Uj=P(uj) from a value uj generated by reconstruction of shares fsj(i) by using the secret sharing scheme S1 when K shares fsj(i) are input into the distributed data transform apparatuses, and generate the reconstructed value Uj (j=K′) by reconstruction of shares fc(i) by using the secret sharing scheme S0 when K shares fc(i) are input into the distributed data transform apparatuses;
dividing the reconstructed value Uj into N shares fUj(n) by using an arbitrary homomorphic secret sharing scheme S2, and
generating a share ga(i) of the electronic information file a from K′ shares fU1(i), . . . , fUK′(i);
where N, K and K′ are integers greater than or equal to 2, N≧K, n=1, . . . , N, λ represents K different integers greater than or equal to 1 and less than or equal to N, i is an integer, iελ, fx(n) represents N shares of x, R is a ring, S is a key space, and P(x) is a mapping that maps xεS to the ring R,
wherein at least K′ distributed data transform apparatuses are configured to reproduce the original electronic information file a, when at least K′ reconstructed values Uj are reconstructed separately respectively by the at least K′ distributed data transform apparatuses, and none of the original electronic information file a can be obtained when less than K′ reconstructed values Uj are reconstructed by less than K′ distributed data transform apparatuses.

11 more elements

A non-transitory computer readable medium including computer executable instructions that make a data distribution apparatus, in a secret sharing system comprising a data distribution apparatus and N distributed data transform apparatuses, wherein the data distribution apparatus receives an electronic information file a as an input;

selects K−1 keys s1, . . . , sK−1εS;
computes rj=P(sj) from the keys s1, . . . , sK−1 to generate pseudorandom numbers r1, . . . , rK−1, where j=1, . . . , K−1;
generates a ciphertext c from the electronic information file aεR by using the pseudorandom numbers r1, . . . , rK−1;
divides each of the keys s1, . . . , sK−1 into N shares fs1(n), . . . , fsK−1(n) by using an arbitrary secret sharing scheme S1, and divides the ciphertext c into N shares fc(n) by using an arbitrary secret sharing scheme S0, perform a method comprising:
computing a reconstructed value Uj=P(uj) from a value uj generated by reconstruction of shares fsj(i) by using the secret sharing scheme S1 when K shares fsj(i) are input, and generate the reconstructed value Uj (j=K) by reconstruction of shares fc(i) by using the secret sharing scheme S0 when K shares fc(i) are input;
dividing the reconstructed value Uj into N shares fUj(n) by using an arbitrary homomorphic secret sharing scheme S2;
and
generating a share ga(i) of the electronic information file a from K shares fU1(i), . . . , fUK(i);
and
where N and K are integers greater than or equal to 2, N≧K, n=1, . . . , N, λ represents K different integers greater than or equal to 1 and less than or equal to N, i is an integer, iελ, fx(n) represents N shares of x, R is a ring, S is a key space, and P(x) is a mapping that maps xεS to the ring R,
wherein at least K distributed data transform apparatuses of the N distributed data transform apparatuses are configured to reproduce the original electronic information file a, when at least K reconstructed values Uj are reconstructed separately respectively by the at least K distributed data transform apparatuses, and none of the original electronic information file a can be obtained when less than K reconstructed values Uj are reconstructed by less than K distributed data transform apparatuses.

8 more elements

A non-transitory computer readable medium including computer executable instructions that make a distributed data transform apparatus in a secret sharing system comprising a data distribution apparatus and N distributed data transform apparatuses, wherein the data distribution apparatus receives an electronic information file a as an input, selects K′−1 keys s1, . . . , sK′−1εS, computes rj=P(sj) from the keys s1, . . . , sK′−1 to generate pseudorandom numbers r1, . . . , rK′−1, where j=1, . . . , K′−1;

generates a ciphertext c from the electronic information file aεR by using the pseudorandom numbers r1, . . . , rK′−1, divides each of the keys s1, . . . , sK′−1 into N shares fs1(n), . . . , fsK′−1(n) by using an arbitrary secret sharing scheme S1, and divides the ciphertext c into N shares fc(n) by using an arbitrary sharing scheme S0, perform a method comprising:
computing a reconstructed value Uj=P(uj) from a value uj generated by reconstructing of shares fsj(i) by using the secret sharing scheme S1 when K shares fsj(i) are input, and generate the reconstructed value Uj (j=K′) by reconstruction of shares fc(i) by using the secret sharing scheme S0 when K shares fc(i) are input;
dividing the reconstructed value Uj into N shares fUj(n) by using an arbitrary homomorphic secret sharing scheme S2;
and
generating a share ga(i) of the electronic information file a from K′ shares fU1(i), . . . , fUK′(i);
where N, K and K′ are integers greater than or equal to 2, N≧K, n=1, . . . , N, λ represents K different integers greater than or equal to 1 and less than or equal to N, i is an integer, iελ, fx(n) represents N shares of x, R is a ring, S is a key space, and P(x) is a mapping that maps xεS to the ring R,
wherein at least K′ distributed data transform apparatuses are configured to reproduce the original electronic information file a, when at least K′ reconstructed values Uj are reconstructed separately respectively by the at least K′ distributed data transform apparatuses, and none of the original electronic information file a can be obtained when less than K′ reconstructed values Uj are reconstructed by less than K′ distributed data transform apparatuses.

4 more elements

Dependencies are inferred from the claim text.

Facts

Application: 14/408,426Filed 4 Jul 2013
Priority: JP 2012-1511405 Jul 2012
Published: US 2015/0172049 A118 Jun 2015
Granted: 30 Aug 2016
Term ends: Not estimatedThe source records don’t support an estimate.

Classification6 codes

H04L 9/0869
Generation of secret information including derivation or calculation of cryptographic keys or passwords: involving random numbers or seeds
G06F 21/606
Protecting data: by securing the transmission between two devices or processes
H04L 9/008
Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols: involving homomorphic…
H04L 9/085
Key establishment, i.e. cryptographic processes or cryptographic protocols whereby a shared secret becomes available to two or more parties, for…:…