WO2012046692A1 - 秘密分散システム、秘密分散装置、秘密分散方法、秘密ソート方法、秘密分散プログラム - Google Patents

秘密分散システム、秘密分散装置、秘密分散方法、秘密ソート方法、秘密分散プログラム Download PDF

Info

Publication number
WO2012046692A1
WO2012046692A1 PCT/JP2011/072770 JP2011072770W WO2012046692A1 WO 2012046692 A1 WO2012046692 A1 WO 2012046692A1 JP 2011072770 W JP2011072770 W JP 2011072770W WO 2012046692 A1 WO2012046692 A1 WO 2012046692A1
Authority
WO
WIPO (PCT)
Prior art keywords
secret sharing
sharing apparatus
fragment
secret
fragments
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/JP2011/072770
Other languages
English (en)
French (fr)
Inventor
浩気 濱田
大 五十嵐
千田　浩司
高橋　克巳
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
NTT Inc
Original Assignee
Nippon Telegraph and Telephone Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Nippon Telegraph and Telephone Corp filed Critical Nippon Telegraph and Telephone Corp
Priority to EP11830624.0A priority Critical patent/EP2608190B1/en
Priority to CN201180047430.3A priority patent/CN103141056B/zh
Priority to US13/876,110 priority patent/US8989391B2/en
Priority to JP2012537700A priority patent/JP5411994B2/ja
Publication of WO2012046692A1 publication Critical patent/WO2012046692A1/ja
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
    • H04L9/0816—Key establishment, i.e. cryptographic processes or cryptographic protocols whereby a shared secret becomes available to two or more parties, for subsequent use
    • H04L9/085—Secret sharing or secret splitting, e.g. threshold schemes
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/08—Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords
    • H04L9/0891—Revocation or update of secret information, e.g. encryption key update or rekeying
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
    • H04L2209/42—Anonymization, e.g. involving pseudonyms

Definitions

  • the present invention relates to cryptographic application technology, and more particularly to a secret sharing system, a secret sharing device, a secret sharing method, a secret sorting method, and a secret sharing program that perform function calculation without revealing input data.
  • Non-Patent Document 1 As a method for obtaining a specific calculation result without restoring the encrypted numerical value, there is a method called secret calculation (for example, a method described in Non-Patent Document 1).
  • secret calculation for example, a method described in Non-Patent Document 1
  • numerical fragments are distributed to three secret computing devices, and addition / subtraction, constant sum, multiplication, constant multiplication, logical operation (negative, logical product, logical sum, exclusive) are performed without restoring the numerical value.
  • the result of data format conversion integer, binary
  • An object of the present invention is to provide a secret calculation technique for outputting data that cannot be associated with a plurality of input data.
  • the present invention relates to secret sharing.
  • the secret sharing system in (k, n) -secret sharing, the secret sharing system has two parameters k and n.
  • the value to be kept secret is divided into n, and even if less than k are collected, the original value is related. Information is not leaked, but the original value can be restored by collecting more than k.
  • Secret sharing system of the present invention N number of secret sharing apparatus R 1, ..., constituted by R N.
  • N is an integer of 3 or more
  • n is an integer of 1 to N
  • M is an integer of 1 or more
  • m is an integer of 1 to M
  • K is an integer of 2 or more
  • k is an integer of 1 to K
  • ..., K ⁇ M pieces of numerical values each secret sharing device a K (M) is recorded in a distributed fragment
  • the secret sharing system of the present invention includes a selection unit, a fragment replacement unit, and a re-distribution unit.
  • the selection means selects a number of secret sharing apparatuses that is greater than or equal to 2 and less than N.
  • the fragment replacement means creates a bijection ⁇ of ⁇ 1,..., K ⁇ ⁇ ⁇ 1,..., K ⁇ between the selected secret sharing apparatuses, and selects the selected secret sharing apparatus R i (where i Is the number of the associated ⁇ (k) -th numerical group a ⁇ (k) i (1) ,..., A ⁇ (k) i (M) recorded by the number indicating the selected secret sharing apparatus.
  • Each is a fragment of the kth numerical group associated with each other.
  • Redispersion means, numerical substituted by segment substitution means A ⁇ (k) (1) , ..., A ⁇ (k) fragment corresponding to (M) a ⁇ (k) i (1), ..., a ⁇ (k) i (M) redispersion to new fragment b k1 (1) using a, ..., b kN (1) , ..., b k1 (M), ..., b kN Request (M) (hereinafter, This is called “redistribution”).
  • This is called “redistribution”.
  • the secret sharing system of the present invention may also include initial information distribution means, initial multiplication means, confirmation distribution means, confirmation multiplication means, and falsification detection means.
  • Initial information distribution means, secret sharing apparatus R 1, ..., K-number of numerical P 1 does not know any of R N, ..., P K each fragment p 1n, ..., determined by secure computing the p Kn, secret sharing It is recorded in the apparatus R n.
  • the initial multiplication means, secret sharing apparatus R 1, ..., with R N, determined S k P k ⁇ A k (1) a is numeric S k fragment s k1 of, ..., a s kN by secure computing, secret sharing device R 1, ..., and records the distributed R N.
  • the m-th numerical value A k (m) a k ⁇ (m) + a k ⁇ (m) + a k ⁇ (m) of the k- th associated numerical group.
  • ( ⁇ , ⁇ , ⁇ ) is one of (1, 2, 3), (2, 3, 1), (3, 1, 2)), and (a k ⁇ (m) , A k ⁇ (m) ), (a k ⁇ (m) , a k ⁇ (m) ), (a k ⁇ (m) , a k ⁇ (m) ).
  • Each secret sharing apparatus may include a fragment replacement unit, a first random number generation unit, a second random number generation unit, a first calculation unit, a second calculation unit, a third calculation unit, and a fragment update unit.
  • the fragment replacement unit When the fragment replacement unit is selected as the first secret sharing device or the second secret sharing device, it generates a bijection ⁇ of ⁇ 1,..., K ⁇ ⁇ ⁇ 1,.
  • K A piece of each numerical value in the k-th associated numerical group is made a piece of each numerical value in the k-th associated numerical group.
  • the first random number generation unit when the first secret sharing device, for re-dispersion of the fragments of each value of the k-th corresponding Lighted numerical value group after movement, b k31 (1 a random value ), ..., and generates a b k31 (M), and transmits the third secret sharing device.
  • the second random number generator is the second secret sharing apparatus, b k23 (1) ,..., Which are random values, are used for redistributing the numerical value fragments of the k-th associated numerical value group.
  • B k23 (M) are generated and transmitted to the third secret sharing apparatus.
  • k31 (m) ⁇ a ⁇ (k) 31 (m) is calculated and transmitted to the second secret sharing apparatus.
  • k23 (m) ⁇ a ⁇ (k) 23 (m) is calculated and transmitted to the first secret sharing apparatus.
  • b k12 (m) a ⁇ (k) 12 (m) ⁇ x k (m) ⁇ y k (m) is calculated.
  • the fragment update unit sets (b k31 (m) , b k12 (m) ) to fragment b k1 (m) when the first secret sharing apparatus is used, and (b k12 (m) , b k23 (m)) (a m), at the time of the third secret sharing device (b k23 (m) fragments b k2 and a, b k31 (m)) a fragment b k3 (m).
  • the fragment replacement unit of the secret sharing system is configured by the fragment replacement unit of all secret sharing apparatuses.
  • the first random number generation unit, the second random number generation unit, the first calculation unit, the second calculation unit, the third calculation unit, and the fragment update unit constitute a redistribution unit of the secret sharing system.
  • secret sharing device not selected in segment substitution unit does not know the BC [pi, numerical A 1 (1), ..., A K (1), ..., A 1 (M) , ..., AK (M) and the numerical values B 1 (1) , ..., B K (1) , ..., B 1 (M) , ..., B K (M) are not known.
  • a sorting algorithm based on comparison such as quick sort can be realized on a secret calculation without increasing the number of comparisons.
  • FIG. 10 is a diagram illustrating an example of a detailed configuration of a redistribution unit according to third and fourth embodiments.
  • FIG. 10 is a diagram illustrating a detailed structure of a falsification detection unit according to a fourth embodiment.
  • each of the secret sharing devices distributes the numerical values A 1 (1) , ..., A K (1) , ..., A 1 (M) , ..., A K (M).
  • K ⁇ M numerical values to be recorded, the k th numerical value group associated with the numerical values A k (1) ,..., A k (M), and the numerical values recorded by the n th secret sharing apparatus with a kn (m). It was explained as a fragment of A k (m) .
  • a k (1) is expressed as A k and a kn (1) is expressed as a kn .
  • FIG. 1 shows a functional configuration example of the secret sharing system according to the first embodiment.
  • FIG. 2 shows a secret sharing process flow in the secret sharing system according to the first embodiment.
  • Secret sharing system of the present embodiment connected N-number to the network 1000 (N is an integer of 3 or more, n represents an integer 1 or more N) secret sharing apparatus 100 1, ..., the selection means 105 and 100 N Composed.
  • a 1 ,..., A K are K numbers (K is an integer equal to or larger than 2) that each secret sharing apparatus 100 n distributes and records fragments, and the number A k is the kth number (k is 1). An integer of K or less), and a kn is the k-th fragment recorded by the secret sharing apparatus 100 n .
  • the numerical values A 1 ,..., AK are numerical values to be concealed, for example, numerical values to be sorted.
  • the numerical value group as the sorting subject, for example, numerical A k are considered numeric group shown an annual income of each person.
  • the selection unit 105 may be arranged inside any secret sharing apparatus or may be a single apparatus.
  • the secret sharing system includes a selection unit, a fragment replacement unit, and a redistribution unit.
  • the secret sharing apparatus 100 n includes at least a fragment replacement unit 110 n , a re-distribution unit 120 n, and a recording unit 190 n .
  • the recording unit 190 n records fragments a 1n ,..., A Kn, and the like.
  • the recording unit 190 n also records information on the number a fragment of the numerical value A k that the fragment a kn recorded by itself is.
  • the selection means 105 selects a number of secret sharing devices less than N (S105). For example, if secret sharing can be performed by collecting N ′ out of N fragments, the secret sharing apparatus having fragment replacement means of N ′ or more and less than N may be selected.
  • the fragment replacement means includes at least the fragment replacement units 110 1 ,..., 110 N. Then, ⁇ 1,..., K ⁇ ⁇ ⁇ 1,..., Between the fragment replacement units 110 i of the secret sharing apparatus 100 i selected by the selection unit 105 (where i is a number indicating the selected secret sharing apparatus). create a bijective [pi of K ⁇ , the recording unit 190 i of the secret sharing device 100 i to the selected fragment a ⁇ (k) i to k-th fragment to be recorded (S110).
  • the bijection ⁇ may be obtained by simply rearranging 1 to K at random. Note that the bijection ⁇ is preferably rearranged uniformly and randomly.
  • the bijection ⁇ may be generated between the selected secret sharing apparatuses 100 i or may be generated by one secret sharing apparatus among the selected secret sharing apparatuses 100 i to select the selected secret sharing apparatus. It may be shared between the devices 100 i .
  • Redispersion means at least re-dispersing section 120 1, ..., configured to include a 120 N.
  • secret sharing device not selected in segment substitution unit does not know the BC [pi, numerical A 1, ..., A K and number B 1, ..., I do not know the correspondence between the B K. That is, numerical values A 1 from a specific secret sharing device, ..., A K and number B 1, ..., If you wish to state that corresponds is not known with B K, choose a secret distribution apparatus in segment substitution unit Thus, the secret sharing apparatus to be selected may be determined in advance. Further, if this process is repeated while changing the secret sharing device selected by the fragment replacement unit and all secret sharing devices have not been selected, all secret sharing devices have numerical values A 1 ,. numerical B 1 that can not be assigned corresponding to the K, ..., can be obtained B K.
  • redispersion was not described in detail.
  • the redispersion method will be described.
  • the method of redispersion is described in Reference 2 (Amir Herzberg, Stanislaw Jarecki, Hugo Krawczyk, and Moti Yung, “Proactive secret sharing or: How to cope with perpetual leakage”, In Don Coppersmith, editor, CRYPTO 1995, volume 963 of LNCS, pages 339-352.
  • N ′ secret sharing apparatuses I and j are numbers indicating the selected secret sharing apparatus (any one of N ′ numbers selected from 1 to N), where j ⁇ i.
  • the values z 1 ,..., Z N are predetermined values and are shared among all secret sharing apparatuses.
  • All secret sharing apparatuses 100 i create N′ ⁇ 1 random numbers u i, 1 , u i, 2 ,..., U i, N′ ⁇ 1 .
  • All secret sharing apparatuses 100 i transmit the values of Z i (z j ) to all the other selected secret sharing apparatuses 100 j (N′ ⁇ 1).
  • All secret sharing apparatuses 100 i calculate the sum of all Z j (z i ) received from other selected secret sharing apparatuses 100 j (N′ ⁇ 1) as Z (z i ).
  • b ki a ⁇ (k) i + Z (z i ) Seek like.
  • h is a number indicating any secret sharing apparatus that has not been selected (any one of NN ′ numbers not selected from 1 to N).
  • L ij (z) (z ⁇ z j ) / (z i ⁇ z j ), and L i (z) is the product of L ij (z) for all j.
  • All secret sharing apparatuses 100 i generate random numbers v i, j (h) for all combinations of j where i ⁇ j and the secret sharing apparatus 100 h that has not been selected.
  • All secret sharing apparatuses 100 i transmit v i, j (h) to the secret sharing apparatus 100 j .
  • All secret sharing apparatuses 100 h use the sum of all received values w hi as a new fragment b kh .
  • the processing speed can be increased. Specifically, the processes (1), (2), and (5) are performed first, the processes (3) and (6) are performed simultaneously, and the processes (4), (7), and (8) are performed. .
  • FIG. 3 shows a processing flow for sorting numerical values in the secret sharing system according to the first embodiment.
  • the initial numbers A 1 by the method described above, ..., new number A 1 can not be assigned corresponding to A K, ..., to obtain a A K (S101).
  • the secret sharing apparatus 100 n also includes a comparison unit 210 n and an exchange unit 220 n .
  • the comparison units 210 1 ,..., 210 N select two numerical values and compare the magnitudes of the two numerical values by a secret calculation (S210).
  • Exchange unit 220 1, ..., 220 N respectively comparing unit 210 1, ..., based on the comparison result in 210 N, replace the 0 set or one or more sets of pieces of numerical (S220). Then, steps S210 and S220 (necessary processes such as comparison, exchange, and change of combination) may be repeated until the sorting process for all numerical values is completed (S211 and S212).
  • the comparison result in step S210 is information that all secret sharing apparatuses know because it is information necessary for the next processing of all secret sharing apparatuses.
  • numerical A 1 all the secret sharing device early in step S101, ..., A K new value no longer corresponds with the A 1, ..., since the processing to A K, the initial numbers A 1, ..., information on the a K is not leaking.
  • the comparison result is also information that can be calculated from public information such as sort output. Therefore, even if it sees in the whole protocol of a present Example, disclosure of a comparison result does not mean that information more than necessary was leaked.
  • the quick sort algorithm shown in FIG. 4 may be applied to the sort portion (steps S210, S220, S211, and S212). Also in this case, the process of comparing A [i] and A [j] is performed while keeping the values of A [i] and A [j] secret, and the comparison result is disclosed. In the case of this method, the number of comparisons is the same as that of the original quick sort, and the average is O (N ⁇ logN) times.
  • the present embodiment can also be applied to a sorting algorithm that can be configured by a numerical value comparison process and a process of exchanging two elements of an array.
  • M is an integer of 1 or more
  • m is an integer of 1 or more and M or less.
  • a kn ( m) be a fragment of the numerical value A k (m) recorded by the secret sharing apparatus 100 n .
  • the configuration of the secret sharing system is the same as in FIG. 1, and the secret sharing process flow is the same as in FIG.
  • the secret sharing apparatus 100 n includes at least a fragment replacement unit 110 n , a re-distribution unit 120 n, and a recording unit 190 n .
  • each component and its processing are as follows.
  • Recording unit 190 n fragments a 1n (1), ..., a Kn (1), ..., a 1n (M), ..., to record such a Kn (M).
  • the recording unit 190 n also records information on the number a fragment of the numerical value A k that the fragment a kn recorded by itself is.
  • the selection means 105 selects a number of secret sharing devices less than N (S105). For example, if secret sharing can be performed by collecting N ′ out of N fragments, the secret sharing apparatus having fragment replacement means of N ′ or more and less than N may be selected. This process is the same.
  • the fragment replacement means includes at least the fragment replacement units 110 1 ,..., 110 N. Then, ⁇ 1,..., K ⁇ ⁇ ⁇ 1,..., Between the fragment replacement units 110 i of the secret sharing apparatus 100 i selected by the selection unit 105 (where i is a number indicating the selected secret sharing apparatus). K ⁇ bijection ⁇ is created, and fragments a ⁇ (k) i (1) ,..., A ⁇ (k) i (M) recorded by the recording unit 190 i of the selected secret sharing apparatus 100 i A fragment of the k-th numerical value group associated is made (S110).
  • Redispersion means at least re-dispersing section 120 1, ..., configured to include a 120 N.
  • the re-distribution means is a fragment a ⁇ (k) i (1) ,..., A corresponding to the numerical group A ⁇ (k) (1) ,..., A ⁇ (k) (M) replaced by the fragment replacement means. re-distributed using ⁇ (k) i (M) (kth substituted) and new fragments b k1 (1) ,..., b kN (1) ,..., b k1 (M) ,. b kN (M) is obtained and set as a fragment of numerical values B k (1) ,..., B k (M) (S120).
  • numerical value B 1 (1), ..., B K (1), ..., B 1 (M), ..., B K (M) a new value A 1 (1), ..., A K (1), ... , A 1 (M) ,..., A K (M) and the combination of secret sharing apparatuses selected by the fragment replacement means is changed, this process can be repeated (S111, S112).
  • each row is random in the column direction as one element (a group of associated numerical values). Substitution can be made.
  • FIG. 5 shows a secret sharing process flow in the secret sharing system according to the second embodiment.
  • Secret sharing system of the present embodiment connected N-number to the network 1000 (N is an integer of 3 or more, n represents an integer 1 or more N) secret sharing apparatus 100 1, ..., the selection means 105 and 100 N Composed.
  • a 1 ,..., A K are K numerical values (K is an integer of 2 or more) in which each secret sharing apparatus 100 n records the fragments, and the numerical value A k is the kth numerical value (k is 1).
  • a kn is a fragment of a numerical value A k recorded by the secret sharing apparatus 100 n .
  • the secret sharing system includes a selection unit 105, an initial information distribution unit, an initial multiplication unit, a fragment replacement unit, a redistribution unit, a confirmation distribution unit, a confirmation multiplication unit, and a falsification detection unit.
  • the secret sharing apparatus 100 n includes an initial information distribution unit 130 n , an initial multiplication unit 140 n , a fragment replacement unit 110 n , a redistribution unit 120 n , a confirmation distribution unit 150 n , a confirmation multiplication unit 160 n , and a tampering detection unit 170.
  • n and a recording unit 190 n .
  • the recording unit 190 n records fragments a 1n ,..., A Kn, and the like.
  • the recording unit 190 n also records information on the number a fragment of the numerical value A k that the fragment a kn recorded by itself is.
  • the selection means 105 is the same as that in the first embodiment.
  • the initial information distribution unit 130 i of the secure computing apparatus 100 i selected by the selecting means 105, the secret sharing apparatus 100 1, ..., 100 K pieces of numerical P 1 does not know any of N, ..., P K respectively It fragments p 11, ..., p K1, ..., p 1n, ..., p Kn, ..., p 1N, ..., a p KN determined by secure computing, fragments p 1n the secret sharing apparatus 100 n, ..., a p Kn Recording is performed (S130).
  • two or more secret sharing apparatuses are selected from the secret sharing apparatuses selected by the selection unit 105. Then, based on the value created by the selected secret sharing apparatus, a fragment of a value unknown to any apparatus may be created. For example, two secret sharing apparatuses 100 i and 100 j are selected (where i ⁇ j), and a numerical fragment generated by the secret sharing apparatus 100 i and a numerical fragment generated by the secret sharing apparatus 100 j are distributed. Record. Then, if the sum of the two numerical values is obtained by secret calculation and the fragments are distributed and recorded so that the result is not known, it is possible to distribute and record numerical fragments that are not known by all the secret sharing apparatuses. In this example, the number of selected secret computing devices is two, but two or more may be used.
  • the initial multiplication means the initial multiplier 140 1, ..., and a 140 N.
  • the fragment replacement unit and the redispersion unit are the same as those in the first embodiment.
  • the confirmation distribution means is composed of confirmation distribution units 150 1 ,..., 150 N.
  • the data are distributed and recorded in the devices 100 1 ,..., 100 N (S150). Specifically, another fragment having a value unknown to any device may be created based on the value created by the secret sharing device selected in step S130.
  • another fragment (new fragment) of the numerical value generated by the secret sharing apparatus 100 i selected in step S130 for the numerical value P ⁇ (k) and the secret sharing apparatus 100 j selected in step S130 are the numerical value P ⁇ .
  • the number of selected secret computing devices is two, but two or more may be used as in step S130.
  • Check multiplying means check multiplying unit 160 1, ..., and a 160 N.
  • Tampering detection means the falsification detection unit 170 1, ..., and a 170 N.
  • the secret sharing apparatus 100 n also includes a comparison unit 210 n and an exchange unit 220 n .
  • the specific sorting process is the same as in the first embodiment.
  • the number of secret sharing apparatuses is N (N is an integer of 3 or more).
  • N is an integer of 3 or more.
  • the number of secret sharing apparatuses constituting the secret sharing system will be limited to 3, and a more specific description will be given.
  • FIG. 6 shows a functional configuration example of the secret sharing system according to the third embodiment.
  • FIG. 7 shows an example of a detailed configuration of the redistribution unit of the third embodiment.
  • FIG. 8 shows a secret sharing process flow in the secret sharing system according to the third embodiment.
  • the secret sharing system according to the present embodiment includes three secret sharing apparatuses 100 ⁇ , 100 ⁇ , 100 ⁇ connected to the network 1000 and a selection unit 105.
  • the selection unit 105 may be arranged inside any secret sharing apparatus or may be a single apparatus.
  • the secret sharing system includes a selection unit 105, a fragment replacement unit, and a redistribution unit.
  • Each secret sharing apparatus 100 n includes a fragment replacement unit 110 n , a re-distribution unit 120 n , and a recording unit 190 n (where n is any one of ⁇ , ⁇ , and ⁇ ).
  • Recording unit 190 n has numerical A 1, ..., it records the like fragment A K.
  • the selection unit 105 selects two secret sharing apparatuses.
  • One of the secret sharing apparatuses selected by the selection means 105 is the first secret sharing apparatus 100 1
  • the other is the second secret sharing apparatus 100 2
  • the secret sharing apparatus that has not been selected is the third secret sharing apparatus 100. 3 (S105).
  • k-th fragment a k1 the first secret sharing apparatus 100 1 records (a k31, a k12)
  • the k-th fragment a k2 the second secret distribution apparatus 100 2 for recording ( a k12, a k23)
  • the fragment replacement means includes at least the fragment replacement units 110 ⁇ , 110 ⁇ , 110 ⁇ .
  • the bijection ⁇ may be obtained by simply rearranging 1 to K at random.
  • the bijection ⁇ is preferably rearranged uniformly and randomly, and may be created using, for example, Fisher-Yates shuffle.
  • the redispersion means includes at least the redispersion parts 120 ⁇ , 120 ⁇ , 120 ⁇ .
  • the redistribution unit 120 n includes a first random number generation unit 121 n , a second random number generation unit 122 n , a first calculation unit 123 n , a second calculation unit 124 n , a third calculation unit 125 n , A fragment update unit 126 n is provided.
  • First first random number generation unit 121 1 of the secret sharing apparatus 100 1, for the redispersion of the k-th fragment, to generate b k31 is a random value
  • the third secret sharing apparatus 100 3 Transmit (S121).
  • Second second random number generation unit 122 2 of the secret sharing apparatus 100 2, for the redispersion of the k-th fragment, to generate b k23 is a random value
  • the third secret sharing apparatus 100 3 Transmit (S122).
  • First first calculation unit 123 1 of the secret sharing apparatus 100 1, for the redispersion of the k-th fragment, calculate the x k b k31 -a ⁇ ( k) 31, a second secret distribution and it transmits to the device 100 2 (S123).
  • the first fragment updating unit 126 1 of the secret sharing device 100 1 (b k31, b k12) was used as a fragment b k1, fragment updating unit 126 2 of the second secret sharing device 100 2 (b k12, b k23) It was a fragment b k2, the third secret sharing apparatus 100 3 fragment updating unit 126 3 and fragment b k3 and (b k23, b k31) ( S126).
  • the information that the recording unit 190 n secret sharing apparatus 100 n can not only record the fragment b kn, a fragment of fragment b kn numerical B k is the k-th fragment itself is recorded Also record.
  • the fragments b k1 , b k2 , and b k3 are fragments of the numerical value B k . That is, steps S121 to S126 correspond to step S120.
  • the secret sharing system can obtain the same effects as those of the first embodiment.
  • the secret sharing apparatus 100 n also includes a comparison unit 210 n and an exchange unit 220 n .
  • the specific sorting process is the same as in the first embodiment.
  • M is an integer of 1 or more, and m is an integer of 1 or more and M or less.
  • a k (m) a k ⁇ (m) + a k ⁇ (m) + a k ⁇ (m) (where k is an integer from 1 to K, m is an integer from 1 to M, ( ⁇ , ⁇ , ( ⁇ ) is (1, 2, 3), (2, 3, 1), (3, 1, 2)), and the three fragments are (a k ⁇ (m) , a k ⁇ (m) ), (A k ⁇ (m) , a k ⁇ (m) ), (a k ⁇ (m) , a k ⁇ (m) ).
  • M 1
  • M the following description is a more general limited shuffle.
  • a functional configuration example of the secret sharing system is the same as in FIG. 6, a detailed configuration example of the re-distribution unit is the same as in FIG. 7, and a secret sharing processing flow is the same as in FIG.
  • the secret sharing system includes a selection unit 105, a fragment replacement unit, and a redistribution unit.
  • the secret sharing apparatus 100 n includes at least a fragment replacement unit 110 n , a re-distribution unit 120 n, and a recording unit 190 n (where n is any one of ⁇ , ⁇ , and ⁇ ).
  • each component and its processing are as follows.
  • Recording unit 190 n fragments a 1n (1), ..., a Kn (1), ..., a 1n (M), ..., to record such a Kn (M).
  • the recording unit 190 n also records information on the number a fragment of the numerical value A k that the fragment a kn recorded by itself is.
  • the selection unit 105 selects two secret sharing apparatuses.
  • One of the secret sharing apparatuses selected by the selection means 105 is the first secret sharing apparatus 100 1
  • the other is the second secret sharing apparatus 100 2
  • the secret sharing apparatus that has not been selected is the third secret sharing apparatus 100. 3 (S105).
  • the fragment replacement means includes at least the fragment replacement units 110 ⁇ , 110 ⁇ , 110 ⁇ .
  • Segment substitution means ⁇ 1, ..., K ⁇ in the first secret sharing apparatus 100 1 and the second secret sharing apparatus 100 2 ⁇ ⁇ 1, ..., K ⁇ to create a bijection ⁇ , the first The fragment a ⁇ (k) 1 (1) ,..., A ⁇ (k) 1 (M) recorded by the secret sharing apparatus 100 1 is made a fragment of the k-th numerical value group, and the second secret sharing apparatus 100 2 fragments records a ⁇ (k) 2 (1 ), ..., a ⁇ (k) 2 (M) to the k-th numerical value group of fragments associated with (S110).
  • the redispersion means includes at least the redispersion parts 120 ⁇ , 120 ⁇ , 120 ⁇ .
  • the redistribution unit 120 n includes a first random number generation unit 121 n , a second random number generation unit 122 n , a first calculation unit 123 n , a second calculation unit 124 n , a third calculation unit 125 n , A fragment update unit 126 n is provided.
  • First random number generation unit 121 1 of the first secret sharing apparatus 100 for the redispersion of the associated k-th numerical value group of fragments, a random value b k31 (1), ..., b k31 (M) is generated and transmitted to the third secret sharing apparatus 1003 ( S121).
  • Second second random number generation unit 122 2 of the secret sharing apparatus 100 2 for the redispersion of the associated k-th numerical value group of fragments, a random value b k23 (1), ..., b k23 (M) is generated and transmitted to the third secret sharing apparatus 1003 ( S122).
  • the fragment updating unit 126 1 of the first secret sharing apparatus 100 1 uses (b k31 (m) , b k12 (m) ) as the fragment b k1 (m), and the fragment updating unit 126 of the second secret sharing apparatus 100 2.
  • the fragments b k1 (m) , b k2 (m) , and b k3 (m) are fragments of the numerical value B k (m) . That is, steps S121 to S126 correspond to step S120.
  • each row is randomized in the column direction as one element (a numerical group associated). Substitution can be made.
  • the number of secret sharing apparatuses constituting the secret sharing system will be limited to 3, and will be described more specifically.
  • an example in which a fraud detection function is provided as in the second embodiment will be described.
  • the configuration of the secret sharing system of the fourth embodiment is also shown in FIG. Note that the secret sharing apparatus 100 n according to the present embodiment also includes a component indicated by a dotted line.
  • FIG. 9 shows a detailed structure of the alteration detection unit.
  • FIG. 10 shows a secret sharing process flow in the secret sharing system according to the fourth embodiment.
  • the secret sharing system according to the present embodiment includes three secret sharing apparatuses 100 ⁇ , 100 ⁇ , 100 ⁇ connected to the network 1000 and a selection unit 105.
  • the secret sharing system includes a selection unit 105, an initial information distribution unit, an initial multiplication unit, a fragment replacement unit, a redistribution unit, a confirmation distribution unit, a confirmation multiplication unit, and a falsification detection unit.
  • the secret sharing apparatus 100 n includes an initial information distribution unit 130 n , an initial multiplication unit 140 n , a fragment replacement unit 110 n , a redistribution unit 120 n , a confirmation distribution unit 150 n , a confirmation multiplication unit 160 n , a falsification detection unit 170 n ,
  • a recording unit 190 n is provided (where n is any one of ⁇ , ⁇ , and ⁇ ). Recording unit 190 n has numerical A 1, ..., it records the like fragment A K.
  • the selection unit 105 selects two secret sharing apparatuses.
  • One of the secret sharing apparatuses selected by the selection means 105 is the first secret sharing apparatus 100 1
  • the other is the second secret sharing apparatus 100 2
  • the secret sharing apparatus that has not been selected is the third secret sharing apparatus 100. 3 (S105).
  • k-th fragment a k1 the first secret sharing apparatus 100 1 records (a k31, a k12)
  • the k-th fragment a k2 the second secret distribution apparatus 100 2 for recording ( a k12, a k23)
  • the initial information dispersal means includes initial information dispersers 130 ⁇ , 130 ⁇ , and 130 ⁇ .
  • the initial information distribution units 130 ⁇ , 130 ⁇ , and 130 ⁇ perform secret computation on K pieces of numerical values P 1 ,..., P K that none of the secret distribution devices 100 ⁇ , 100 ⁇ , 100 ⁇ know. It is obtained and recorded in the secret sharing apparatus 100 n (S130). For example, K random values R (1) 1 ,..., R (1) K are generated by the first secret sharing apparatus 100 1 , and K random values R are generated by the second secret sharing apparatus 100 2. (2) 1 ,..., R (2) K is generated.
  • R (1) k fragments (r (1) k31 , r (1) k12 ), (r (1) k12 , r (1) k23 ), (R (1) k23 , r (1) k31 ) and R (2) k fragments (r (2) k31 , r (2) k12 ), (r (2) k12 , r (2) k23 ), (R (2) k23 , r (2) k31 ) are secretly distributed and recorded.
  • the initial multiplication means includes initial multiplication units 140 ⁇ , 140 ⁇ , and 140 ⁇ .
  • a k is a numerical value S k fragment (s k ⁇ , s k ⁇ ), (s k ⁇ , s k ⁇ ), (s k ⁇ , s k ⁇ ) Is obtained by secret calculation, and distributed and recorded in secret sharing apparatuses 100 ⁇ , 100 ⁇ , 100 ⁇ (S140).
  • the fragment replacement unit and the redispersion unit are the same as those in the third embodiment. Fragments b k1 , b k2 , and b k3 are recorded as fragments of the numerical value B k in the secret sharing apparatuses 100 ⁇ , 100 ⁇ , and 100 ⁇ by the fragment replacement unit and the redistribution unit.
  • the confirmation dispersion unit includes confirmation dispersion units 150 ⁇ , 150 ⁇ , and 150 ⁇ .
  • (Q k ⁇ , q k ⁇ ) are generated by secret calculation, and are distributed and recorded in the secret sharing apparatuses 100 ⁇ , 100 ⁇ , 100 ⁇ (S150).
  • Q k R (1) ⁇ (k) + R (2) ⁇ (k) a is numeric Q k fragment (q k31, q k12), ( q k12 , q k23 ), (q k23 , q k31 ) are obtained by secret calculation using another fragment, and are distributed and recorded in the secret sharing apparatuses 100 1 , 100 2 , 100 3 .
  • Q k P ⁇ (k) and that are not known by all the secret sharing apparatuses 100 ⁇ , 100 ⁇ , and 100 ⁇ .
  • the confirmation multiplication means is composed of confirmation multiplication units 160 ⁇ , 160 ⁇ , and 160 ⁇ .
  • T k Q k ⁇
  • B k is a numerical value T k fragment (t k ⁇ , t k ⁇ ), (t k ⁇ , t k ⁇ ), (t k ⁇ , t k ⁇ )
  • the tampering detection means includes tampering detection units 170 ⁇ , 170 ⁇ , and 170 ⁇ .
  • the falsification detection unit 170 n includes a third random number generation unit 171 n , a fourth random number generation unit 172 n , a fourth calculation unit 173 n , a fifth calculation unit 174 n , and a first confirmation unit. 175 n , a sixth calculation unit 176 n , a seventh calculation unit 177 n , and a second confirmation unit 178 n .
  • the secret sharing apparatuses 100 ⁇ , 100 ⁇ , 100 ⁇ operate as any one of the first secret sharing apparatus 100 1 , the second secret sharing apparatus 100 2 , and the third secret sharing apparatus 100 3. Depending on whether or not, processing is performed as follows.
  • the third random number generation unit 171 1 of the first secret sharing apparatus 100 1 generates a u k is a random value, and transmits the second secret distribution apparatus 100 2 (S171).
  • Second fourth random number generation unit 172 2 of the secret sharing device 100 2 may generate v k is a random value, and transmits first the secret sharing device 100 1 (S172).
  • the secret sharing apparatus 100 n also includes a comparison unit 210 n and an exchange unit 220 n .
  • the specific sorting process is the same as in the first embodiment.
  • the fragments of the numerical value A that are distributed and recorded by the secret sharing apparatuses 100 ⁇ , 100 ⁇ , 100 ⁇ are (a ⁇ , a ⁇ ), (a ⁇ , a ⁇ ), (a ⁇ , a ⁇ ), the fragments of the numerical value B are (b ⁇ , b ⁇ ), (b ⁇ , b ⁇ ), (b ⁇ , b ⁇ ), the fragments of the numerical value C are (c ⁇ , c ⁇ ), (c ⁇ , c ⁇ ), (c ⁇ , c ⁇ ).
  • a ⁇ computes the A-a ⁇ -a ⁇ , the fragment (a ⁇ , a ⁇ ), and (a ⁇ , a ⁇ ), (a ⁇ , a ⁇ ), secret sharing apparatus 100 alpha, Recorded in a dispersed manner at 100 ⁇ and 100 ⁇ .
  • a (1) secret sharing apparatus 100 alpha sends a Ganmaarufa the secret sharing apparatus 100 beta, and transmits the a .alpha..beta the secret sharing apparatus 100 gamma.
  • the secret sharing apparatus 100 ⁇ transmits a ⁇ to the secret sharing apparatus 100 ⁇ , and transmits a ⁇ to the secret sharing apparatus 100 ⁇ .
  • the secret sharing apparatus 100 ⁇ transmits a ⁇ to the secret sharing apparatus 100 ⁇ , and transmits a ⁇ to the secret sharing apparatus 100 ⁇ .
  • C AS secret calculation (where S is a known constant) (1)
  • the secret sharing apparatus 100 alpha is the secret sharing apparatus 100 beta the (r 1, c ⁇ ), and transmits the secret sharing apparatus 100 gamma a (r 2, c ⁇ ).
  • the secret sharing apparatus 100 ⁇ records (c ⁇ , c ⁇ ), the secret sharing apparatus 100 ⁇ records (c ⁇ , c ⁇ ), and the secret sharing apparatus 100 ⁇ is (c ⁇ , c ⁇ ). Record.
  • the program describing the processing contents can be recorded on a computer-readable recording medium.
  • the computer-readable recording medium may be any recording medium such as a magnetic recording device, an optical disk, a magneto-optical recording medium, and a semiconductor memory.
  • this program is distributed by selling, transferring, or lending a portable recording medium such as a DVD or CD-ROM in which the program is recorded. Furthermore, the program may be distributed by storing the program in a storage device of the server computer and transferring the program from the server computer to another computer via a network.
  • a computer that executes such a program first stores a program recorded on a portable recording medium or a program transferred from a server computer in its own storage device.
  • the computer reads the program stored in its own recording medium and executes the process according to the read program.
  • the computer may directly read the program from a portable recording medium and execute processing according to the program, and the program is transferred from the server computer to the computer.
  • the processing according to the received program may be executed sequentially.
  • the program is not transferred from the server computer to the computer, and the above-described processing is executed by a so-called ASP (Application Service Provider) type service that realizes a processing function only by an execution instruction and result acquisition. It is good.
  • the program in this embodiment includes information that is used for processing by an electronic computer and that conforms to the program (data that is not a direct command to the computer but has a property that defines the processing of the computer).
  • the present apparatus is configured by executing a predetermined program on a computer.
  • a predetermined program on a computer.
  • at least a part of these processing contents may be realized by hardware.

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Storage Device Security (AREA)

Abstract

　本発明の秘密分散システムは、Ｎ個の秘密分散装置で構成される。本発明の秘密分散システムは、断片置換手段と再分散手段を備える。断片置換手段は、Ｎ未満の数の秘密分散装置を選択し、選択された秘密分散装置の間で｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、選択された秘密分散装置が記録する断片ａπ（ｋ）ｉをｋ番目の断片にする（ただし、ｉは選択された秘密分散装置を示す番号）。再分散手段は、断片置換手段によって置換された数値に対応する断片を用いて再分散化して新しい断片を求める。

Description

秘密分散システム、秘密分散装置、秘密分散方法、秘密ソート方法、秘密分散プログラム
　本発明は、暗号応用技術に関するものであり、特に入力データを明かすことなく関数計算を行う秘密分散システム、秘密分散装置、秘密分散方法、秘密ソート方法、秘密分散プログラムに関する。
　暗号化された数値を復元すること無く特定の演算結果を得る方法として、秘密計算と呼ばれる方法がある(例えば、非特許文献１に記載された方法)。非特許文献１の方法では、３つの秘密計算装置に数値の断片を分散させ、数値を復元すること無く、加減算、定数和、乗算、定数倍、論理演算(否定，論理積，論理和，排他的論理和)、データ形式変換(整数,二進数)の結果を３つの秘密計算装置に分散保持させることができる。
千田浩司，五十嵐大，高橋克巳，"効率的な３パーティ秘匿関数計算の提案とその運用モデルの考察"，第48回情報処理学会研究報告，CSEC, pp.1-7, 2010，3月.
　しかしながら、従来技術はデータの対応を隠したまま複数のデータをランダムに置換できないという課題がある。本発明の目的は、入力された複数のデータと対応つけることができないデータを出力する秘密計算技術を提供することである。
　本発明は秘密分散に関する。一般に、（ｋ，ｎ）－秘密分散では、秘密分散システムが２つのパラメータｋ，ｎを持っており、秘密にしたい値をｎ個に分割し、そのうちｋ個未満を集めても元の値に関する情報は漏れないが、ｋ個以上を集めると元の値を復元できる。本発明の秘密分散システムは、Ｎ個の秘密分散装置Ｒ１，…，ＲＮで構成される。ここで、Ｎを３以上の整数、ｎを１以上Ｎ以下の整数、Ｍを１以上の整数、ｍを1以上Ｍ以下の整数、Ｋを２以上の整数、ｋを１以上Ｋ以下の整数、数値Ａ１ （１），…，ＡＫ （１），…，Ａ１ （Ｍ），…，ＡＫ （Ｍ）を各秘密分散装置が断片を分散して記録するＫ×Ｍ個の数値、数値Ａｋ （１），…，Ａｋ （Ｍ）を対応付けられたｋ番目の数値群、ａｋｎ （ｍ）をｎ番目の秘密分散装置が記録する数値Ａｋ （ｍ）の断片とする。本発明の秘密分散システムは、選択手段と断片置換手段と再分散手段を備える。選択手段は、２以上Ｎ未満の数の秘密分散装置を選択する。断片置換手段は、選択された秘密分散装置の間で｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、選択された秘密分散装置Ｒｉ（ただし、ｉは選択された秘密分散装置を示す番号）が記録する対応付けられたπ（ｋ）番目の数値群の断片ａπ（ｋ）ｉ （１），…，ａπ（ｋ）ｉ （Ｍ）をそれぞれ対応付けられたｋ番目の数値群の断片にする。再分散手段は、断片置換手段によって置換された数値Ａπ（ｋ） （１），…，Ａπ（ｋ） （Ｍ）に対応する断片ａπ（ｋ）ｉ （１），…，ａπ（ｋ）ｉ （Ｍ）を用いて再分散化して新しい断片ｂｋ１ （１），…，ｂｋＮ （１），…，ｂｋ１ （Ｍ），…，ｂｋＮ （Ｍ）を求める（以下、これを「再分散化」と呼ぶ）。なお、対応つけられた数値群の対応を維持したまま数値群を再分散化する場合は、同一の全単射πを用いて、対応つけられた数値群の各数値の断片を置換すればよい。
　また、本発明の秘密分散システムは、初期情報分散手段、初期乗算手段、確認分散手段、確認乗算手段、改ざん検出手段も備えてもよい。初期情報分散手段は、秘密分散装置Ｒ１，…，ＲＮのどれも知らないＫ個の数値Ｐ１，…，ＰＫそれぞれの断片ｐ１ｎ，…，ｐＫｎを秘密計算によって求め、秘密分散装置Ｒｎに記録させる。初期乗算手段は、秘密分散装置Ｒ１，…，ＲＮで、Ｓｋ＝Ｐｋ×Ａｋ （１）である数値Ｓｋの断片ｓｋ１，…，ｓｋＮを秘密計算によって求め、秘密分散装置Ｒ１，…，ＲＮに分散して記録する。確認分散手段は、ｋ＝１～Ｋについて、Ｑｋ＝Ｐπ（ｋ）である数値Ｑｋの断片ｑｋ１，…，ｑｋＮを秘密計算によって生成し、秘密分散装置Ｒ１，…，ＲＮに分散して記録させる。確認乗算手段は、秘密分散装置Ｒ１，…，ＲＮで、Ｔｋ＝Ｑｋ×Ｂｋ （１）である数値Ｔｋの断片ｔｋ１，…，ｔｋＮを秘密計算によって求め、秘密分散装置Ｒ１，…，ＲＮに分散して記録する。改ざん検出手段は、ｋ＝１～Ｋについて、Ｔｋ＝Ｓπ（ｋ）であることを確認する。
　例えば、３つの秘密分散装置で構成する場合であれば、ｋ番目の対応つけられた数値群のｍ番目の数値Ａｋ （ｍ）＝ａｋαβ （ｍ）＋ａｋβγ （ｍ）＋ａｋγα （ｍ）（ただし、（α，β，γ）は、（１，２，３）、（２，３，１）、（３，１，２）のいずれか）の３つの断片を（ａｋγα （ｍ），ａｋαβ （ｍ））、（ａｋαβ （ｍ），ａｋβγ （ｍ））、（ａｋβγ （ｍ），ａｋγα （ｍ））とする。秘密分散装置が、第１の秘密分散装置として選ばれたときには記録する断片をａｋ１ （ｍ）＝（ａｋ３１ （ｍ），ａｋ１２ （ｍ））、第２の秘密分散装置として選ばれたときには記録する断片をａｋ２ （ｍ）＝（ａｋ１２ （ｍ），ａｋ２３ （ｍ））、第３の秘密分散装置として選ばれたときには記録する断片をａｋ３ （ｍ）＝（ａｋ２３ （ｍ），ａｋ３１ （ｍ））とする。そして、各秘密分散装置は、断片置換部、第１乱数生成部、第２乱数生成部、第１計算部、第２計算部、第３計算部、断片更新部を備えればよい。断片置換部は、第１の秘密分散装置または第２の秘密分散装置として選ばれたときは、｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、π（ｋ）番目の対応つけられた数値群の各数値の断片をｋ番目の対応つけられた数値群の各数値の断片にする。第１乱数生成部は、第１の秘密分散装置のときには、移動後のｋ番目の対応つけられた数値群の各数値の断片の再分散化のために、ランダムな値であるｂｋ３１ （１），…，ｂｋ３１ （Ｍ）を生成し、第３の秘密分散装置に送信する。第２乱数生成部は、第２の秘密分散装置のときには、ｋ番目の対応つけられた数値群の各数値の断片の再分散化のために、ランダムな値であるｂｋ２３ （１），…，ｂｋ２３ （Ｍ）を生成し、第３の秘密分散装置に送信する。第１計算部は、第１の秘密分散装置のときには、ｋ番目の対応つけられた数値群の各数値の断片の再分散化のために、ｍ＝１～Ｍについてｘｋ （ｍ）＝ｂｋ３１ （ｍ）－ａπ（ｋ）３１ （ｍ）を計算し、第２の秘密分散装置に送信する。第２計算部は、第２の秘密分散装置のときには、ｋ番目の対応つけられた数値群の各数値の断片の再分散化のために、ｍ＝１～Ｍについてｙｋ （ｍ）＝ｂｋ２３ （ｍ）－ａπ（ｋ）２３ （ｍ）を計算し、第１の秘密分散装置に送信する。第３計算部は、第１の秘密分散装置または第２の秘密分散装置のときには、ｋ番目の対応つけられた数値群の各数値の断片の再分散化のために、ｍ＝１～Ｍについてｂｋ１２ （ｍ）＝ａπ（ｋ）１２ （ｍ）－ｘｋ （ｍ）－ｙｋ （ｍ）を計算する。断片更新部は、第１の秘密分散装置のときには（ｂｋ３１ （ｍ），ｂｋ１２ （ｍ））を断片ｂｋ１ （ｍ）とし、第２の秘密分散装置のときには（ｂｋ１２ （ｍ），ｂｋ２３ （ｍ））を断片ｂｋ２ （ｍ）とし、第３の秘密分散装置のときには（ｂｋ２３ （ｍ），ｂｋ３１ （ｍ））を断片ｂｋ３ （ｍ）とする。なお、全ての秘密分散装置の断片置換部で、秘密分散システムの断片置換手段が構成される。また、第１乱数生成部、第２乱数生成部、第１計算部、第２計算部、第３計算部、断片更新部で、秘密分散システムの再分散手段が構成される。
　本発明の秘密分散システムによれば、断片置換部に選ばれなかった秘密分散装置は、全単射πを知らないので、数値Ａ１ （１），…，ＡＫ （１），…，Ａ１ （Ｍ），…，ＡＫ （Ｍ）と数値Ｂ１ （１），…，ＢＫ （１），…，Ｂ１ （Ｍ），…，ＢＫ （Ｍ）との対応が分からない。本発明を用いることにより、クイックソートなどの比較に基づくソーティングアルゴリズムを、比較回数を増やすことなく秘密計算上で実現できる。
実施例１，２の秘密分散システムの機能構成例を示す図。 実施例１の秘密分散システムでの秘密分散の処理フローを示す図。 本発明の秘密分散システムでの数値のソートの処理フローを示す図。 クイックソートのアルゴリズムを示す図。 実施例２の秘密分散システムでの秘密分散の処理フローを示す図。 実施例３，４の秘密分散システムの機能構成例を示す図。 実施例３，４の再分散部の詳細な構成の例を示す図。 実施例３の秘密分散システムでの秘密分散の処理フローを示す図。 実施例４の改ざん検出部の詳細な構造を示す図。 実施例４の秘密分散システムでの秘密分散の処理フローを示す図。
　以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
　課題を解決するための手段では、数値Ａ１ （１），…，ＡＫ （１），…，Ａ１ （Ｍ），…，ＡＫ （Ｍ）を各秘密分散装置が断片を分散して記録するＫ×Ｍ個の数値、数値Ａｋ （１），…，Ａｋ （Ｍ）を対応付けられたｋ番目の数値群、ａｋｎ （ｍ）をｎ番目の秘密分散装置が記録する数値Ａｋ （ｍ）の断片として説明した。本実施例では、まず本発明の理解を助けるために、Ｍ＝１の場合について説明し、その後Ｍを１に限定しない場合について説明する。また、Ｍ＝１の場合の説明では、Ａｋ （１）をＡｋと、ａｋｎ （１）をａｋｎと表現する。
［限定シャッフル］
　図１に実施例１の秘密分散システムの機能構成例を示す。図２に実施例１の秘密分散システムでの秘密分散の処理フローを示す。本実施例の秘密分散システムは、ネットワーク１０００に接続されたＮ個（Ｎは３以上の整数、ｎは１以上Ｎ以下の整数）の秘密分散装置１００１，…，１００Ｎと選択手段１０５で構成される。ここで、Ａ１，…，ＡＫを各秘密分散装置１００ｎが断片を分散して記録するＫ個の数値（Ｋは２以上の整数）、数値Ａｋをｋ番目の数値（ｋは１以上Ｋ以下の整数）、ａｋｎを秘密分散装置１００ｎが記録するｋ番目の断片とする。なお、数値Ａ１，…，ＡＫが、秘匿化したい数値群であって、例えば、ソートの対象となる数値群である。ソートの対象となる数値群としては、例えば、数値Ａｋが各々の人の年収を示すような数値群が考えられる。選択手段１０５は、いずれかの秘密分散装置の内部に配置されてもよいし、単独の装置であってもよい。
　本実施例の秘密分散システムは、選択手段と断片置換手段と再分散手段を備える。また、秘密分散装置１００ｎは、少なくとも断片置換部１１０ｎと再分散部１２０ｎと記録部１９０ｎを備える。記録部１９０ｎは断片ａ１ｎ，…，ａＫｎなどを記録する。また、記録部１９０ｎは、自身が記録している断片ａｋｎが数値Ａｋの何番目の断片なのかに関する情報も記録する。
　選択手段１０５は、Ｎ未満の数の秘密分散装置を選択する（Ｓ１０５）。例えば、Ｎ個の断片のうちＮ’個を集めれば数値を復元できる秘密分散であれば、断片置換手段がＮ’個以上Ｎ未満の秘密分散装置を選べばよい。
　断片置換手段は、少なくとも断片置換部１１０１，…，１１０Ｎを含んで構成される。そして、選択手段１０５に選択された秘密分散装置１００ｉ（ただし、ｉは選択された秘密分散装置を示す番号）の断片置換部１１０ｉ間で｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、選択された秘密分散装置１００ｉの記録部１９０ｉが記録する断片ａπ（ｋ）ｉをｋ番目の断片にする（Ｓ１１０）。全単射πは、１～Ｋを単にランダムに並べ替えたものであってもよい。なお、全単射πは、望ましくは一様にランダムに並び替えられたものであり、例えばFisher-Yates shuffle（参考文献１：Richard Durstenfeld, “Algorithm 235: Random permutation”, Communications of the ACM archive, Volume 7, Issue 7, 1964.）などを用いて作成すればよい。また、全単射πは選択された秘密分散装置１００ｉ間で生成してもよいし、選択された秘密分散装置１００ｉのうちの１つの秘密分散装置が生成して、選択された秘密分散装置１００ｉ間で共有してもよい。
　再分散手段は、少なくとも再分散部１２０１，…，１２０Ｎを含んで構成される。再分散手段は、断片置換手段によって置換された数値Ａπ（ｋ）に対応する断片ａπ（ｋ）ｉ（ｋ番目に置換されている）を用いて再分散化して新しい断片ｂｋ１，…，ｂｋＮを求め、数値Ｂｋの断片とする（Ｓ１２０）。つまり、Ａπ（ｋ）＝Ｂｋの関係が成り立つが、選ばれなかった秘密分散装置は全単射πを知らないので、Ａπ（ｋ）＝Ｂｋであることを知らない。なお、各秘密分散装置１００ｎの記録部１９０ｎは、断片ｂｋｎを記録するだけでなく、自身が記録しているｋ番目の断片である断片ｂｋｎが数値Ｂｋの断片であるという情報も記録する。また、数値Ｂ１，…，ＢＫを新しい数値Ａ１，…，ＡＫとし、断片置換手段で選択する秘密分散装置の組み合わせを変更すれば、この処理を繰り返すことができる（Ｓ１１１，Ｓ１１２）。
　本発明の秘密分散システムによれば、限定された秘密分散装置間で断片をシャッフルする。したがって、断片置換部に選ばれなかった秘密分散装置は、全単射πを知らないので、数値Ａ１，…，ＡＫと数値Ｂ１，…，ＢＫとの対応が分からない。つまり、特定の秘密分散装置からは数値Ａ１，…，ＡＫと数値Ｂ１，…，ＢＫとの対応が分からない状態にしたいのであれば、その秘密分散装置を断片置換部で選ばないように、選択する秘密分散装置をあらかじめ定めればよい。また、断片置換部が選ぶ秘密分散装置を変更しながらこの処理を繰り返し、全ての秘密分散装置が選ばれなかったことがある状態にすれば、全ての秘密分散装置が数値Ａ１，…，ＡＫと対応つけることができない数値Ｂ１，…，ＢＫを得ることができる。
［再分散］
　上述の限定シャッフルの説明では、再分散については詳しく説明しなかった。ここでは、再分散の方法について説明する。再分散の方法としては、参考文献２（Amir Herzberg, Stanislaw Jarecki, Hugo Krawczyk, and Moti Yung, “Proactive secret sharing or: How to cope with perpetual leakage”, In Don Coppersmith, editor, CRYPTO 1995, volume 963 of LNCS, pages 339-352. Springer, 1995.）の3.3節に示された更新方法と、参考文献３（Haiyun Luo and Songwu Lu, “Ubiquitous and robust authentication services for ad hoc wireless networks”, In UCLA-CSD-TR-200030, 2000.）の6.1節に示された再作成方法を用いる。選択手段１０５が選択した秘密計算装置間で参考文献２の更新方法を用いて新しい断片を生成し、その後、参考文献３の再作成方法を用いて選択手段１０５が選択しなかった秘密計算装置の新しい断片を生成する。
　参考文献２の更新方法を、本件に適用したアルゴリズムを以下に示す。選択手段１０５がＮ’個の秘密分散装置を選択したとする。そして、ｉとｊは選択された秘密分散装置を示す番号（１～Ｎの中から選ばれたＮ’個の数の中のいずれか）であって、ｊ≠ｉとする。また、値ｚ１，…，ｚＮはあらかじめ決められた値であり、すべての秘密分散装置間で共有されているとする。
（１）すべての秘密分散装置１００ｉは、Ｎ’－１個の乱数ｕｉ，１，ｕｉ，２，…，ｕｉ，Ｎ’－１を作成する。
（２）すべての秘密分散装置１００ｉは、Ｚｉ（ｚ）：＝０＋ｕｉ，１ｚ＋ｕｉ，２ｚ２＋…＋ｕｉ，Ｎ’－１ｚＮ’－１を定める。
（３）すべての秘密分散装置１００ｉは、選択された他の秘密分散装置１００ｊ（Ｎ’－１個存在する）のすべてに対して、それぞれＺｉ（ｚｊ）の値を送信する。
（４）すべての秘密分散装置１００ｉは、選択された他の秘密分散装置１００ｊ（Ｎ’－１個存在する）から受け取ったすべてのＺｊ（ｚｉ）の和をＺ（ｚｉ）とし、新しい断片ｂｋｉを置換された断片ａπ（ｋ）ｉを用いて、
　ｂｋｉ＝ａπ（ｋ）ｉ＋Ｚ（ｚｉ）
のように求める。
　次に、参考文献３の再作成方法を、本件に適用したアルゴリズムを以下に示す。ｈは選択されなかった秘密分散装置を示す番号（１～Ｎの中から選ばれなかったＮ－Ｎ’個の数のなかのいずれか）とする。また、Ｌｉｊ（ｚ）＝（ｚ－ｚｊ）／（ｚｉ－ｚｊ）とし、Ｌｉ（ｚ）は、すべてのｊについてのＬｉｊ（ｚ）の積とする。
（５）すべての秘密分散装置１００ｉは、ｉ＜ｊであるｊと、選択されなかった秘密分散装置１００ｈのすべての組み合わせに対して、乱数ｖｉ，ｊ （ｈ）を生成する。
（６）すべての秘密分散装置１００ｉは、ｖｉ，ｊ （ｈ）を秘密分散装置１００ｊに送信する。
（７）すべての秘密分散装置１００ｉは、すべての選択されなかった秘密分散装置１００ｈについて、ｊ＜ｉのすべての乱数ｖｉ，ｊ （ｈ）の和をＶ（ｈ＋）とし、ｉ＜ｊのすべての乱数ｖｉ，ｊ （ｈ）の和をＶ（ｈ－）とし、値ｗｈｉを、
　ｗｈｉ＝ｂｋｉＬｉ（ｚｈ）＋Ｖ（ｈ＋）－Ｖ（ｈ－）
のように求め、秘密分散装置１００ｈに値ｗｈｉを送信する。
（８）すべての秘密分散装置１００ｈは、受信したすべての値ｗｈｉの和を新しい断片ｂｋｈとする。
　上述のように、（１）～（４）の処理で、すべての選択された秘密分散装置が、新しい断片を記録する。（５）～（８）の処理で、すべての選択されなかった秘密分散装置が、新しい断片を記録する。
　なお、（３）と（６）の処理を同時に行えば、処理の高速化を図ることができる。具体的には、（１）、（２）、（５）の処理をまず行い、（３）と（６）を同時に行い、（４）、（７）、（８）の処理を行えばよい。
［ソート］
　図３に実施例１の秘密分散システムでの数値のソートの処理フローを示す。上述の方法によって初期の数値Ａ１，…，ＡＫと対応つけることができない新しい数値Ａ１，…，ＡＫを得ている（Ｓ１０１）。ソートも行う場合は、秘密分散装置１００ｎは、比較部２１０ｎと交換部２２０ｎも備える。比較部２１０１，…，２１０Ｎは、２つの数値を選択し、当該２つの数値の大小を秘密計算によって比較する（Ｓ２１０）。
　交換部２２０１，…，２２０Ｎは、それぞれ比較部２１０１，…，２１０Ｎでの比較結果に基づいて、０組または１組または複数組の数値の断片を入れ替える（Ｓ２２０）。そして、全ての数値に対するソート処理が終わるまで、ステップＳ２１０とＳ２２０（比較、交換、組合せの変更などの必要な処理）を繰り返せばよい（Ｓ２１１，Ｓ２１２）。
　ステップＳ２１０の比較結果は、全ての秘密分散装置の次の処理に必要な情報なので全ての秘密分散装置が知る情報である。しかし、ステップＳ１０１によって全ての秘密分散装置が初期の数値Ａ１，…，ＡＫと対応できなくなった新しい数値Ａ１，…，ＡＫに対して処理しているので、初期の数値Ａ１，…，ＡＫに関する情報は漏れない。さらに、比較結果は、ソートの出力という公開情報から計算可能な情報でもある。そのため、本実施例のプロトコル全体で見ても、比較結果が開示されることは必要以上の情報を漏らしたことにはならない。
　なお、より具体的には、ソートの部分（ステップＳ２１０，Ｓ２２０，Ｓ２１１，Ｓ２１２）には図４に示すクイックソートのアルゴリズムを適用すればよい。この場合もＡ［ｉ］とＡ［ｊ］とを比較する処理はＡ［ｉ］とＡ［ｊ］の値を秘匿したままで行い、比較結果は公開される。この方法の場合、比較回数は元のクイックソートと同じであり、平均Ｏ（Ｎ・ｌｏｇＮ）回である。また、この他にも、数値の大小比較の処理と配列の２つの要素を入れ替える処理で構成できるソーティングアルゴリズムにも本実施例は適用できる。
　このように、本実施例の秘密分散システムを用いれば、比較と要素の入れ替えからなるソーティングアルゴリズムを比較回数を増やすことなく秘密計算で実現できる。
［限定シャッフルの変形例］
　次に、Ｍを１に限定しない場合について説明する。Ｍは１以上の整数、ｍは１以上Ｍ以下の整数とする。Ａ（１），…，Ａ（Ｍ）はそれぞれＫ個の要素を持つベクトルであり、Ａ（ｍ）＝(Ａ１ （ｍ），…，ＡＫ （ｍ）)とする。また、ベクトルＡ（１），…，Ａ（Ｍ）の各要素は対応付けられているとする。言い換えると、Ａｋ （１），…，Ａｋ （Ｍ）は対応付けられたｋ番目の数値群とする。本変形例では、対応つけられた数値群の対応を維持したまま数値群を限定シャッフルする。また、ａｋｎ （ｍ）を秘密分散装置１００ｎが記録する数値Ａｋ （ｍ）の断片とする。なお、上述の限定シャッフルはＭ＝１の場合に相当するので、以下の説明はより一般的な限定シャッフルである。
　秘密分散システムの構成は図１と同じであり、秘密分散の処理フローは図２と同じである。秘密分散装置１００ｎは、少なくとも断片置換部１１０ｎと再分散部１２０ｎと記録部１９０ｎを備える。ただし、各構成部とその処理は以下のようになる。
　記録部１９０ｎは断片ａ１ｎ （１），…，ａＫｎ （１），…，ａ１ｎ （Ｍ），…，ａＫｎ （Ｍ）などを記録する。また、記録部１９０ｎは、自身が記録している断片ａｋｎが数値Ａｋの何番目の断片なのかに関する情報も記録する。
　選択手段１０５は、Ｎ未満の数の秘密分散装置を選択する（Ｓ１０５）。例えば、Ｎ個の断片のうちＮ’個を集めれば数値を復元できる秘密分散であれば、断片置換手段がＮ’個以上Ｎ未満の秘密分散装置を選べばよい。この処理は同じである。
　断片置換手段は、少なくとも断片置換部１１０１，…，１１０Ｎを含んで構成される。そして、選択手段１０５に選択された秘密分散装置１００ｉ（ただし、ｉは選択された秘密分散装置を示す番号）の断片置換部１１０ｉ間で｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、選択された秘密分散装置１００ｉの記録部１９０ｉが記録する断片ａπ（ｋ）ｉ （１），…，ａπ（ｋ）ｉ （Ｍ）を対応付けられたｋ番目の数値群の断片にする（Ｓ１１０）。
　再分散手段は、少なくとも再分散部１２０１，…，１２０Ｎを含んで構成される。再分散手段は、断片置換手段によって置換された数値群Ａπ（ｋ） （１），…，Ａπ（ｋ） （Ｍ）に対応する断片ａπ（ｋ）ｉ （１），…，ａπ（ｋ）ｉ （Ｍ）（ｋ番目に置換されている）を用いて再分散化して新しい断片ｂｋ１ （１），…，ｂｋＮ （１），…，ｂｋ１ （Ｍ），…，ｂｋＮ （Ｍ）を求め、数値Ｂｋ （１），…，Ｂｋ （Ｍ）の断片とする（Ｓ１２０）。つまり、Ａπ（ｋ） （ｍ）＝Ｂｋ （ｍ）の関係が成り立つが、選ばれなかった秘密分散装置は全単射πを知らないので、Ａπ（ｋ） （ｍ）＝Ｂｋ （ｍ）であることを知らない。なお、各秘密分散装置１００ｎの記録部１９０ｎは、断片ｂｋｎ （ｍ）を記録するだけでなく、自身が記録しているｋ番目の断片である断片ｂｋｎ （ｍ）が数値Ｂｋ （ｍ）の断片であるという情報も記録する。また、数値Ｂ１ （１），…，ＢＫ （１），…，Ｂ１ （Ｍ），…，ＢＫ （Ｍ）を新しい数値Ａ１ （１），…，ＡＫ （１），…，Ａ１ （Ｍ），…，ＡＫ （Ｍ）とし、断片置換手段で選択する秘密分散装置の組み合わせを変更すれば、この処理を繰り返すことができる（Ｓ１１１，Ｓ１１２）。
　このように、ベクトルの各要素の対応を維持した限定シャッフルを利用すれば、例えば、表形式をしたデータの秘密分散から、各行を１つの要素（対応付けられた数値群）として列方向のランダム置換を行うことができる。
［限定シャッフル］
　実施例２の秘密分散システムの構成も図１に示す。なお、本実施例の秘密分散装置１００ｎは、点線で示された構成部も備えている。図５に実施例２の秘密分散システムでの秘密分散の処理フローを示す。本実施例の秘密分散システムは、ネットワーク１０００に接続されたＮ個（Ｎは３以上の整数、ｎは１以上Ｎ以下の整数）の秘密分散装置１００１，…，１００Ｎと選択手段１０５で構成される。ここで、Ａ１，…，ＡＫを各秘密分散装置１００ｎが断片を分散して記録するＫ個の数値（Ｋは２以上の整数）、数値Ａｋをｋ番目の数値（ｋは１以上Ｋ以下の整数）、ａｋｎを秘密分散装置１００ｎが記録する数値Ａｋの断片とする。
　本実施例の秘密分散システムは、選択手段１０５、初期情報分散手段、初期乗算手段、断片置換手段、再分散手段、確認分散手段、確認乗算手段、改ざん検出手段を備える。また、秘密分散装置１００ｎは、初期情報分散部１３０ｎ、初期乗算部１４０ｎ、断片置換部１１０ｎ、再分散部１２０ｎ、確認分散部１５０ｎ、確認乗算部１６０ｎ、改ざん検出部１７０ｎ、記録部１９０ｎを備える。記録部１９０ｎは断片ａ１ｎ，…，ａＫｎなどを記録する。また、記録部１９０ｎは、自身が記録している断片ａｋｎが数値Ａｋの何番目の断片なのかに関する情報も記録する。
　選択手段１０５は実施例１と同じである。初期情報分散手段は、初期情報分散部１３０１，…，１３０Ｎで構成される。そして、選択手段１０５に選択された秘密計算装置１００ｉの初期情報分散部１３０ｉは、秘密分散装置１００１，…，１００Ｎのどれも知らないＫ個の数値Ｐ１，…，ＰＫそれぞれの断片ｐ１１，…，ｐＫ１，…，ｐ１ｎ，…，ｐＫｎ，…，ｐ１Ｎ，…，ｐＫＮを秘密計算によって求め、秘密分散装置１００ｎに断片ｐ１ｎ，…，ｐＫｎを記録する（Ｓ１３０）。具体的には、選択手段１０５に選択された秘密分散装置から、２つ以上の秘密分散装置を選定する。そして、選定された秘密分散装置が作った値に基づいて、どの装置も知らない値の断片を作ればよい。例えば、２つの秘密分散装置１００ｉ，１００ｊを選定し（ただし、ｉ≠ｊ）、秘密分散装置１００ｉが生成した数値の断片と、秘密分散装置１００ｊが生成した数値の断片を分散して記録する。そして、その２つの数値の和を秘密計算によって求め、結果が分からないように断片を分散して記録すれば、全ての秘密分散装置が知らない数値の断片を分散して記録できる。この例では、選定した秘密計算装置を２つとしたが、２つ以上でもかまわない。
　初期乗算手段は、初期乗算部１４０１，…，１４０Ｎで構成される。初期乗算部１４０１，…，１４０Ｎは、Ｓｋ＝Ｐｋ×Ａｋである数値Ｓｋの断片ｓｋ１，…，ｓｋＮを秘密計算によって求め、秘密分散装置１００１，…，１００Ｎに分散して記録する（Ｓ１４０）。
　断片置換手段と再分散手段は、実施例１と同じである。確認分散手段は、確認分散部１５０１，…，１５０Ｎで構成される。確認分散部１５０１，…，１５０Ｎは、ｋ＝１～Ｋについて、Ｑｋ＝Ｐπ（ｋ）である数値Ｑｋの断片ｑｋ１，…，ｑｋＮを秘密計算によって生成し、秘密分散装置１００１，…，１００Ｎに分散して記録する（Ｓ１５０）。具体的には、ステップＳ１３０で選定された秘密分散装置が作った値に基づいて、どの装置も知らない値の別の断片を作ればよい。例えば、ステップＳ１３０で選定された秘密分散装置１００ｉが数値Ｐπ（ｋ）用に生成した数値の別の断片（新しい断片）と、ステップＳ１３０で選定された秘密分散装置１００ｊが数値Ｐπ（ｋ）用に生成した数値の別の断片（新しい断片）を分散して記録する。そして、その２つの数値の和を秘密計算によって求め、結果が分からないように断片を分散して記録すれば、Ｑｋ＝Ｐπ（ｋ）であり、かつ、全ての秘密分散装置が知らない数値の断片を分散して記録できる。この例では、選定した秘密計算装置を２つとしたが、ステップＳ１３０と同じように２つ以上でもかまわない。
　確認乗算手段は、確認乗算部１６０１，…，１６０Ｎで構成される。確認乗算部１６０１，…，１６０Ｎは、Ｔｋ＝Ｑｋ×Ｂｋである数値Ｔｋの断片ｔｋ１，…，ｔｋＮを秘密計算によって求め、秘密分散装置１００１，…，１００Ｎに分散して記録する（Ｓ１６０）。
　改ざん検出手段は、改ざん検出部１７０１，…，１７０Ｎで構成される。改ざん検出部１７０１，…，１７０Ｎは、ｋ＝１～Ｋについて、Ｔｋ＝Ｓπ（ｋ）であることを確認する（Ｓ１７０）。ｔｋｎ≠ｓπ（ｋ）ｎの場合には、改ざんがあったとして異常終了する。また、数値Ｂ１，…，ＢＫを新しい数値Ａ１，…，ＡＫとし、断片置換手段で選択する秘密分散装置の組み合わせを変更すれば、この処理を繰り返すことができる（Ｓ１１１，Ｓ１１２）。
　実施例２の秘密分散システムによれば、実施例１の秘密分散装置と同じ効果が得られると共に、数値Ａ１，…，ＡＫと数値Ｂ１，…，ＢＫとの対応を分からなくする処理の途中に、他の秘密分散装置に改ざんした値を送信する不正がないことも確認できる。なお、ソートも行う場合は、秘密分散装置１００ｎは、比較部２１０ｎと交換部２２０ｎも備える。具体的なソートの処理については実施例１と同じである。
　実施例１、２では、秘密分散装置の数をＮ（Ｎは３以上の整数）としていた。実施例３では、秘密分散システムを構成する秘密分散装置の数を３に限定し、より具体的に説明する。
［限定シャッフル］
　図６に実施例３の秘密分散システムの機能構成例を示す。図７に実施例３の再分散部の詳細な構成の例を示す。図８に実施例３の秘密分散システムでの秘密分散の処理フローを示す。本実施例の秘密分散システムは、ネットワーク１０００に接続された３つの秘密分散装置１００α，１００β，１００γと選択手段１０５で構成される。ここで、Ｋ個の数値のｋ番目を数値Ａｋ＝ａｋαβ＋ａｋβγ＋ａｋγα（ただし、Ｋは２以上の整数、ｋは１以上Ｋ以下の整数、（α，β，γ）は、（１，２，３）、（２，３，１）、（３，１，２）のいずれか）とし、その３つの断片を（ａｋγα，ａｋαβ）、（ａｋαβ，ａｋβγ）、（ａｋβγ，ａｋγα）とする。なお、選択手段１０５は、いずれかの秘密分散装置の内部に配置されてもよいし、単独の装置であってもよい。
　本実施例の秘密分散システムは、選択手段１０５と断片置換手段と再分散手段を備える。各秘密分散装置１００ｎは、断片置換部１１０ｎ、再分散部１２０ｎ、記録部１９０ｎを備えている（ただし、ｎはα、β、γのいずれか）。記録部１９０ｎは、数値Ａ１，…，ＡＫの断片などを記録する。
　選択手段１０５は、２つの秘密分散装置を選択する。そして、選択手段１０５に選択された秘密分散装置の一方を第１の秘密分散装置１００１、他方を第２の秘密分散装置１００２、選択されなかった秘密分散装置を第３の秘密分散装置１００３とする（Ｓ１０５）。ここで、第１の秘密分散装置１００１が記録するｋ番目の断片をａｋ１＝（ａｋ３１，ａｋ１２）、第２の秘密分散装置１００２が記録するｋ番目の断片をａｋ２＝（ａｋ１２，ａｋ２３）、第３の秘密分散装置１００３が記録するｋ番目の断片をａｋ３＝（ａｋ２３，ａｋ３１）とする。
　断片置換手段は、少なくとも断片置換部１１０α，１１０β，１１０γを含んで構成される。断片置換手段は、第１の秘密分散装置１００１または第２の秘密分散装置１００２で｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、第１の秘密分散装置１００１が記録する断片ａπ（ｋ）１をｋ番目の断片にし、第２の秘密分散装置１００２が記録する断片ａπ（ｋ）２をｋ番目の断片にする（Ｓ１１０）。実施例１で説明した通り、全単射πは、１～Ｋを単にランダムに並べ替えたものであってもよい。なお、全単射πは、望ましくは一様にランダムに並び替えられたものであり、例えばFisher-Yates shuffleなどを用いて作成すればよい。
　再分散手段は、少なくとも再分散部１２０α，１２０β，１２０γを含んで構成される。図７に示すように再分散部１２０ｎは、第１乱数生成部１２１ｎ、第２乱数生成部１２２ｎ、第１計算部１２３ｎ、第２計算部１２４ｎ、第３計算部１２５ｎ、断片更新部１２６ｎを備えている。
　第１の秘密分散装置１００１の第１乱数生成部１２１１は、ｋ番目の断片の再分散化のために、ランダムな値であるｂｋ３１を生成し、第３の秘密分散装置１００３に送信する（Ｓ１２１）。第２の秘密分散装置１００２の第２乱数生成部１２２２は、ｋ番目の断片の再分散化のために、ランダムな値であるｂｋ２３を生成し、第３の秘密分散装置１００３に送信する（Ｓ１２２）。第１の秘密分散装置１００１の第１計算部１２３１は、ｋ番目の断片の再分散化のために、ｘｋ＝ｂｋ３１－ａπ（ｋ）３１を計算し、第２の秘密分散装置１００２に送信する（Ｓ１２３）。
　第２の秘密分散装置１００２の第２計算部１２４２は、ｋ番目の断片の再分散化のために、ｙｋ＝ｂｋ２３－ａπ（ｋ）２３を計算し、第１の秘密分散装置１００１に送信する（Ｓ１２４）。第１の秘密分散装置１００１の第３計算部１２５１と第２の秘密分散装置１００２の第３計算部１２５２は、ｋ番目の断片の再分散化のために、それぞれｂｋ１２＝ａπ（ｋ）１２－ｘｋ－ｙｋを計算する（Ｓ１２５）。第１の秘密分散装置１００１の断片更新部１２６１は（ｂｋ３１，ｂｋ１２）を断片ｂｋ１とし、第２の秘密分散装置１００２の断片更新部１２６２は（ｂｋ１２，ｂｋ２３）を断片ｂｋ２とし、第３の秘密分散装置１００３の断片更新部１２６３は（ｂｋ２３，ｂｋ３１）を断片ｂｋ３とする（Ｓ１２６）。なお、各秘密分散装置１００ｎの記録部１９０ｎは、断片ｂｋｎを記録するだけでなく、自身が記録しているｋ番目の断片である断片ｂｋｎが数値Ｂｋの断片であるという情報も記録する。実施例１と同じように、断片ｂｋ１，ｂｋ２，ｂｋ３は、数値Ｂｋの断片である。つまり、ステップＳ１２１～Ｓ１２６が、ステップＳ１２０に相当する。
　また、数値Ｂ１，…，ＢＫを新しい数値Ａ１，…，ＡＫとし、断片置換手段で選択する秘密分散装置の組み合わせを変更すれば、この処理を繰り返すことができる（Ｓ１１１，Ｓ１１２）。そして、断片置換部が選ぶ秘密分散装置を変更しながらこの処理を繰り返し、全ての秘密分散装置が選ばれなかったことがある状態にすれば、全ての秘密分散装置が数値Ａ１，…，ＡＫと対応つけることができない数値Ｂ１，…，ＢＫを得ることができる。本実施例では、断片置換手段が選択する秘密分散装置を、｛１００α，１００β｝，｛１００β，１００γ｝，｛１００γ，１００α｝のように選択すれば、全ての秘密分散装置が選ばれなかったことがある状態にできる。
　したがって、実施例３の秘密分散システムは、実施例１と同様の効果が得られる。なお、ソートも行う場合は、秘密分散装置１００ｎは、比較部２１０ｎと交換部２２０ｎも備える。具体的なソートの処理については実施例１と同じである。
［限定シャッフルの変形例］
　Ｍは１以上の整数、ｍは１以上Ｍ以下の整数とする。Ａ（１），…，Ａ（Ｍ）はそれぞれＫ個の要素を持つベクトルであり、Ａ（ｍ）＝(Ａ１ （ｍ），…，ＡＫ （ｍ）)とする。また、ベクトルＡ（１），…，Ａ（Ｍ）の各要素は対応付けられているとする。言い換えると、Ａｋ （１），…，Ａｋ （Ｍ）は対応付けられたｋ番目の数値群である。本変形例では、対応つけられた数値群の対応を維持したまま数値群を限定シャッフルする。また、数値Ａｋ （ｍ）＝ａｋαβ （ｍ）＋ａｋβγ （ｍ）＋ａｋγα （ｍ）（ただし、ｋは１以上Ｋ以下の整数、ｍは１以上Ｍ以下の整数、（α，β，γ）は、（１，２，３）、（２，３，１）、（３，１，２）のいずれか）とし、の３つの断片を（ａｋγα （ｍ），ａｋαβ （ｍ））、（ａｋαβ （ｍ），ａｋβγ （ｍ））、（ａｋβγ （ｍ），ａｋγα （ｍ））とする。なお、上述の限定シャッフルはＭ＝１の場合に相当するので、以下の説明はより一般的な限定シャッフルである。
　秘密分散システムの機能構成例は図６と同じであり、再分散部の詳細な構成例は図７と同じであり、秘密分散の処理フローは図８と同じである。秘密分散システムは、選択手段１０５と断片置換手段と再分散手段を備える。秘密分散装置１００ｎは、少なくとも断片置換部１１０ｎと再分散部１２０ｎと記録部１９０ｎを備える（ただし、ｎはα、β、γのいずれか）。ただし、各構成部とその処理は以下のようになる。
　記録部１９０ｎは断片ａ１ｎ （１），…，ａＫｎ （１），…，ａ１ｎ （Ｍ），…，ａＫｎ （Ｍ）などを記録する。また、記録部１９０ｎは、自身が記録している断片ａｋｎが数値Ａｋの何番目の断片なのかに関する情報も記録する。
　選択手段１０５は、２つの秘密分散装置を選択する。そして、選択手段１０５に選択された秘密分散装置の一方を第１の秘密分散装置１００１、他方を第２の秘密分散装置１００２、選択されなかった秘密分散装置を第３の秘密分散装置１００３とする（Ｓ１０５）。ここで、第１の秘密分散装置１００１が記録する数値Ａｋ （ｍ）の断片をａｋ１ （ｍ）＝（ａｋ３１ （ｍ），ａｋ１２ （ｍ））、第２の秘密分散装置１００２が記録する数値Ａｋ （ｍ）の断片をａｋ２ （ｍ）＝（ａｋ１２ （ｍ），ａｋ２３ （ｍ））、第３の秘密分散装置１００３が記録する数値Ａｋ （ｍ）の断片をａｋ３ （ｍ）＝（ａｋ２３ （ｍ），ａｋ３１ （ｍ））とする。
　断片置換手段は、少なくとも断片置換部１１０α，１１０β，１１０γを含んで構成される。断片置換手段は、第１の秘密分散装置１００１または第２の秘密分散装置１００２で｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、第１の秘密分散装置１００１が記録する断片ａπ（ｋ）１ （１），…，ａπ（ｋ）１ （Ｍ）を対応付けられたｋ番目の数値群の断片にし、第２の秘密分散装置１００２が記録する断片ａπ（ｋ）２ （１），…，ａπ（ｋ）２ （Ｍ）を対応付けられたｋ番目の数値群の断片にする（Ｓ１１０）。
　再分散手段は、少なくとも再分散部１２０α，１２０β，１２０γを含んで構成される。図７に示すように再分散部１２０ｎは、第１乱数生成部１２１ｎ、第２乱数生成部１２２ｎ、第１計算部１２３ｎ、第２計算部１２４ｎ、第３計算部１２５ｎ、断片更新部１２６ｎを備えている。
　第１の秘密分散装置１００１の第１乱数生成部１２１１は、対応付けられたｋ番目の数値群の断片の再分散化のために、ランダムな値であるｂｋ３１ （１），…，ｂｋ３１ （Ｍ）を生成し、第３の秘密分散装置１００３に送信する（Ｓ１２１）。第２の秘密分散装置１００２の第２乱数生成部１２２２は、対応付けられたｋ番目の数値群の断片の再分散化のために、ランダムな値であるｂｋ２３ （１），…，ｂｋ２３ （Ｍ）を生成し、第３の秘密分散装置１００３に送信する（Ｓ１２２）。第１の秘密分散装置１００１の第１計算部１２３１は、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１～Ｍについてｘｋ （ｍ）＝ｂｋ３１ （ｍ）－ａπ（ｋ）３１ （ｍ）を計算し、ｘｋ （１），…，ｘｋ （Ｍ）を第２の秘密分散装置１００２に送信する（Ｓ１２３）。
　第２の秘密分散装置１００２の第２計算部１２４２は、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１～Ｍについてｙｋ （ｍ）＝ｂｋ２３ （ｍ）－ａπ（ｋ）２３ （ｍ）を計算し、ｙｋ （１），…，ｙｋ （Ｍ）を第１の秘密分散装置１００１に送信する（Ｓ１２４）。第１の秘密分散装置１００１の第３計算部１２５１と第２の秘密分散装置１００２の第３計算部１２５２は、対応付けられたｋ番目の数値群の断片の再分散化のために、それぞれｍ＝１～Ｍについてｂｋ１２ （ｍ）＝ａπ（ｋ）１２ （ｍ）－ｘｋ （ｍ）－ｙｋ （ｍ）を計算する（Ｓ１２５）。第１の秘密分散装置１００１の断片更新部１２６１は（ｂｋ３１ （ｍ），ｂｋ１２ （ｍ））を断片ｂｋ１ （ｍ）とし、第２の秘密分散装置１００２の断片更新部１２６２は（ｂｋ１２ （ｍ），ｂｋ２３ （ｍ））を断片ｂｋ２ （ｍ）とし、第３の秘密分散装置１００３の断片更新部１２６３は（ｂｋ２３ （ｍ），ｂｋ３１ （ｍ））を断片ｂｋ３ （ｍ）とする（Ｓ１２６）。なお、各秘密分散装置１００ｎの記録部１９０ｎは、断片ｂｋｎ （ｍ）を記録するだけでなく、自身が記録しているｋ番目の断片である断片ｂｋｎ （ｍ）が数値Ｂｋ （ｍ）の断片であるという情報も記録する。実施例１と同じように、断片ｂｋ１ （ｍ），ｂｋ２ （ｍ），ｂｋ３ （ｍ）は、数値Ｂｋ （ｍ）の断片である。つまり、ステップＳ１２１～Ｓ１２６が、ステップＳ１２０に相当する。
　また、数値Ｂ１ （１），…，ＢＫ （１），…，Ｂ１ （Ｍ），…，ＢＫ （Ｍ）を新しい数値Ａ１ （１），…，ＡＫ （１），…，Ａ１ （Ｍ），…，ＡＫ （Ｍ）とし、断片置換手段で選択する秘密分散装置の組み合わせを変更すれば、この処理を繰り返すことができる（Ｓ１１１，Ｓ１１２）。
　このように、ベクトルの各要素の対応を維持した限定シャッフルを利用すれば、例えば、表形式をしたデータの秘密分散から、各行を１つの要素（対応付けられた数値群）として列方向のランダム置換を行うことができる。
　実施例４でも、秘密分散システムを構成する秘密分散装置の数を３に限定し、より具体的に説明する。また、実施例４では、実施例２と同じように不正検出機能を具備した例を説明する。
［限定シャッフル］
　実施例４の秘密分散システムの構成も図６に示す。なお、本実施例の秘密分散装置１００ｎは、点線で示された構成部も備えている。図９に改ざん検出部の詳細な構造を示す。図１０に実施例４の秘密分散システムでの秘密分散の処理フローを示す。本実施例の秘密分散システムは、ネットワーク１０００に接続された３つの秘密分散装置１００α，１００β，１００γと選択手段１０５で構成される。ここで、Ｋ個の数値のｋ番目を数値Ａｋ＝ａｋαβ＋ａｋβγ＋ａｋγα（ただし、Ｋは２以上の整数、ｋは１以上Ｋ以下の整数、（α，β，γ）は、（１，２，３）、（２，３，１）、（３，１，２）のいずれか）とし、その３つの断片を（ａｋγα，ａｋαβ）、（ａｋαβ，ａｋβγ）、（ａｋβγ，ａｋγα）とする。
　本実施例の秘密分散システムは、選択手段１０５、初期情報分散手段、初期乗算手段、断片置換手段、再分散手段、確認分散手段、確認乗算手段、改ざん検出手段を備える。秘密分散装置１００ｎは、初期情報分散部１３０ｎ、初期乗算部１４０ｎ、断片置換部１１０ｎ、再分散部１２０ｎ、確認分散部１５０ｎ、確認乗算部１６０ｎ、改ざん検出部１７０ｎ、記録部１９０ｎを備える（ただし、ｎはα、β、γのいずれか）。記録部１９０ｎは、数値Ａ１，…，ＡＫの断片などを記録する。
　選択手段１０５は、２つの秘密分散装置を選択する。そして、選択手段１０５に選択された秘密分散装置の一方を第１の秘密分散装置１００１、他方を第２の秘密分散装置１００２、選択されなかった秘密分散装置を第３の秘密分散装置１００３とする（Ｓ１０５）。ここで、第１の秘密分散装置１００１が記録するｋ番目の断片をａｋ１＝（ａｋ３１，ａｋ１２）、第２の秘密分散装置１００２が記録するｋ番目の断片をａｋ２＝（ａｋ１２，ａｋ２３）、第３の秘密分散装置１００３が記録するｋ番目の断片をａｋ３＝（ａｋ２３，ａｋ３１）とする。
　初期情報分散手段は、初期情報分散部１３０α，１３０β，１３０γで構成される。初期情報分散部１３０α，１３０β，１３０γは、秘密分散装置１００α，１００β，１００γのどれも知らないＫ個の数値Ｐ１，…，ＰＫそれぞれの断片ｐｋｎを秘密計算によって求め、秘密分散装置１００ｎに記録する（Ｓ１３０）。例えば、第１の秘密分散装置１００１でＫ個のランダムな値Ｒ（１） １，…，Ｒ（１） Ｋを生成し、第２の秘密分散装置１００２でＫ個のランダムな値Ｒ（２） １，…，Ｒ（２） Ｋを生成する。そして、秘密分散装置１００１，１００２，１００３で、Ｒ（１） ｋの断片（ｒ（１） ｋ３１，ｒ（１） ｋ１２）、（ｒ（１） ｋ１２，ｒ（１） ｋ２３）、（ｒ（１） ｋ２３，ｒ（１） ｋ３１）と、Ｒ（２） ｋの断片（ｒ（２） ｋ３１，ｒ（２） ｋ１２）、（ｒ（２） ｋ１２，ｒ（２） ｋ２３）、（ｒ（２） ｋ２３，ｒ（２） ｋ３１）とを秘密分散して記録する。その後、秘密分散装置１００１，１００２，１００３で、Ｐｋ＝Ｒ（１） ｋ＋Ｒ（２） ｋである数値Ｐｋの断片（ｐｋ３１，ｐｋ１２）、（ｐｋ１２，ｐｋ２３）、（ｐｋ２３，ｐｋ３１）を秘密計算によって求め、秘密分散装置１００１，１００２，１００３に分散して記録する。このような処理によって、全ての秘密分散装置１００α，１００β，１００γが知らない数値の断片を分散して記録できる。
　初期乗算手段は、初期乗算部１４０α，１４０β，１４０γで構成される。初期乗算部１４０α，１４０β，１４０γは、Ｓｋ＝Ｐｋ×Ａｋである数値Ｓｋの断片（ｓｋγα，ｓｋαβ）、（ｓｋαβ，ｓｋβγ）、（ｓｋβγ，ｓｋγα）を秘密計算によって求め、秘密分散装置１００α，１００β，１００γに分散して記録する（Ｓ１４０）。
　断片置換手段と再分散手段は、実施例３と同じである。断片置換手段と再分散手段によって、秘密分散装置１００α，１００β，１００γに数値Ｂｋの断片として断片ｂｋ１、ｂｋ２、ｂｋ３が記録される。確認分散手段は、確認分散部１５０α，１５０β，１５０γで構成される。確認分散部１５０α，１５０β，１５０γは、ｋ＝１～Ｋについて、Ｑｋ＝Ｐπ（ｋ）である数値Ｑｋの断片（ｑｋγα，ｑｋαβ）、（ｑｋαβ，ｑｋβγ）、（ｑｋβγ，ｑｋγα）を秘密計算によって生成し、秘密分散装置１００α，１００β，１００γに分散して記録する（Ｓ１５０）。例えば、ステップＳ１３０で第１の秘密分散装置１００１が生成した数値Ｒ（１） π（ｋ）の別の断片（ｒ’（１） π（ｋ）３１，ｒ’（１） π（ｋ）１２）、（ｒ’（１） π（ｋ）１２，ｒ’（１） π（ｋ）２３）、（ｒ’（１） π（ｋ）２３，ｒ’（１） π（ｋ）３１）と、第２の秘密分散装置１００２が生成した数値Ｒ（２） π（ｋ）の別の断片（ｒ’（２） π（ｋ）３１，ｒ’（２） π（ｋ）１２）、（ｒ’（２） π（ｋ）１２，ｒ’（２） π（ｋ）２３）、（ｒ’（２） π（ｋ）２３，ｒ’（２） π（ｋ）３１）とを秘密分散して記録する。その後、秘密分散装置１００１，１００２，１００３で、Ｑｋ＝Ｒ（１） π（ｋ）＋Ｒ（２） π（ｋ）である数値Ｑｋの断片（ｑｋ３１，ｑｋ１２）、（ｑｋ１２，ｑｋ２３）、（ｑｋ２３，ｑｋ３１）を別の断片を用いて秘密計算によって求め、秘密分散装置１００１，１００２，１００３に分散して記録する。このような処理によって、Ｑｋ＝Ｐπ（ｋ）であり、かつ、全ての秘密分散装置１００α，１００β，１００γが知らない数値の断片を分散して記録できる。
　確認乗算手段は、確認乗算部１６０α，１６０β，１６０γで構成される。確認乗算部１６０α，１６０β，１６０γは、Ｔｋ＝Ｑｋ×Ｂｋである数値Ｔｋの断片（ｔｋγα，ｔｋαβ）、（ｔｋαβ，ｔｋβγ）、（ｔｋβγ，ｔｋγα）を秘密計算によって求め、秘密分散装置１００α，１００β，１００γに分散して記録する（Ｓ１６０）。
　改ざん検出手段は、改ざん検出部１７０α，１７０β，１７０γで構成される。また、図９に示すように、改ざん検出部１７０ｎは、第３乱数生成部１７１ｎ、第４乱数生成部１７２ｎ、第４計算部１７３ｎ、第５計算部１７４ｎ、第１確認部１７５ｎ、第６計算部１７６ｎ、第７計算部１７７ｎ、第２確認部１７８ｎを備える。改ざん検出手段は、秘密分散装置１００α，１００β，１００γが第１の秘密分散装置１００１、第２の秘密分散装置１００２、第３の秘密分散装置１００３のいずれの装置として動作するかにしたがって、以下のように処理を行う。
　第１の秘密分散装置１００１の第３乱数生成部１７１１は、ランダムな値であるｕｋを生成し、第２の秘密分散装置１００２に送信する（Ｓ１７１）。第２の秘密分散装置１００２の第４乱数生成部１７２２は、ランダムな値であるｖｋを生成し、第１の秘密分散装置１００１に送信する（Ｓ１７２）。第１の秘密分散装置１００１の第４計算部１７３１は、ｄｋ＝ｓπ（ｋ）１２－ｔｋ１２－ｕｋ－ｖｋを計算し、第３の秘密分散装置１００３に送信する（Ｓ１７３）。
　第２の秘密分散装置１００２の第５計算部１７４２は、ｅｋ＝ｓπ（ｋ）１２－ｔｋ１２－ｕｋ－ｖｋを計算し、第３の秘密分散装置１００３に送信する（Ｓ１７４）。第３の秘密分散装置１００３の第１確認部１７５３は、ｄｋ＝ｅｋであることを確認し、異なっていれば処理を中止する（Ｓ１７５）。
　第１の秘密分散装置１００１の第６計算部１７６１は、ｆｋ＝ｓπ（ｋ）３１－ｔｋ３１＋ｕｋを計算し、第３の秘密分散装置１００３に送信する（Ｓ１７６）。第２の秘密分散装置１００２の第７計算部１７７２は、ｇｋ＝ｓπ（ｋ）２３－ｔｋ２３＋ｖｋを計算し、第３の秘密分散装置１００３に送信する（Ｓ１７７）。第３の秘密分散装置１００３の第２確認部１７８３は、ｆｋ＋ｇｋ＋ｄｋ＝０であることを確認し、異なっていれば処理を中止する（Ｓ１７８）。また、数値Ｂ１，…，ＢＫを新しい数値Ａ１，…，ＡＫとし、断片置換手段で選択する秘密分散装置の組み合わせを変更すれば、この処理を繰り返すことができる（Ｓ１１１，Ｓ１１２）。
　実施例４の秘密分散システムによれば、実施例３の秘密分散装置と同じ効果が得られると共に、数値Ａ１，…，ＡＫと数値Ｂ１，…，ＢＫとの対応を分からなくする処理の途中に、他の秘密分散装置に改ざんした値を送信する不正がないことも確認できる。なお、ソートも行う場合は、秘密分散装置１００ｎは、比較部２１０ｎと交換部２２０ｎも備える。具体的なソートの処理については実施例１と同じである。
［秘密計算］
　上述の説明では、秘密計算については１つの方法に限定しないことを前提としており、具体例は示さなかった。以下では、実施例３、４の秘密分散システムの各構成部が利用できる基本的な秘密計算の具体例を示す。なお、以下の説明では、秘密分散装置１００α，１００β，１００γが分散して記録する数値Ａの断片を（ａγα，ａαβ）、（ａαβ，ａβγ）、（ａβγ，ａγα）、数値Ｂの断片を（ｂγα，ｂαβ）、（ｂαβ，ｂβγ）、（ｂβγ，ｂγα）、数値Ｃの断片を（ｃγα，ｃαβ）、（ｃαβ，ｃβγ）、（ｃβγ，ｃγα）とする。
数値Ａの秘密分散
（１）乱数ａαβ，ａβγを生成する。
（２）ａγα＝Ａ－ａαβ－ａβγを計算し、断片を（ａγα，ａαβ）、（ａαβ，ａβγ）、（ａβγ，ａγα）とし、秘密分散装置１００α，１００β，１００γに分散して記録する。
数値Ａの復元
（１）秘密分散装置１００αは秘密分散装置１００βにａγαを送信し、秘密分散装置１００γにａαβを送信する。秘密分散装置１００βは秘密分散装置１００γにａαβを送信し、秘密分散装置１００αにａβγを送信する。秘密分散装置１００γは秘密分散装置１００αにａβγを送信し、秘密分散装置１００βにａγαを送信する。
（２）秘密分散装置１００αは秘密分散装置１００βから受信したａβγと秘密分散装置１００γから受信したａβγとが一致していれば、ａαβ＋ａβγ＋ａγαを計算して数値Ａを復元する。秘密分散装置１００βは秘密分散装置１００γから受信したａγαと秘密分散装置１００αから受信したａγαとが一致していれば、ａαβ＋ａβγ＋ａγαを計算して数値Ａを復元する。秘密分散装置１００γは秘密分散装置１００αから受信したａαβと秘密分散装置１００βから受信したａαβとが一致していれば、ａαβ＋ａβγ＋ａγαを計算して数値Ａを復元する。
Ｃ＝Ａ＋Ｂの秘密計算
（１）秘密分散装置１００αは（ｃγα，ｃαβ）＝（ａγα＋ｂγα，ａαβ＋ｂαβ）を計算して記録し、秘密分散装置１００βは（ｃαβ，ｃβγ）＝（ａαβ＋ｂαβ，ａβγ＋ｂβγ）を計算して記録し、秘密分散装置１００γは（ｃβγ，ｃγα）＝（ａβγ＋ｂβγ，ａγα＋ｂγα）を計算して記録する。
Ｃ＝Ａ－Ｂの秘密計算
（１）秘密分散装置１００αは（ｃγα，ｃαβ）＝（ａγα－ｂγα，ａαβ－ｂαβ）を計算して記録し、秘密分散装置１００βは（ｃαβ，ｃβγ）＝（ａαβ－ｂαβ，ａβγ－ｂβγ）を計算して記録し、秘密分散装置１００γは（ｃβγ，ｃγα）＝（ａβγ－ｂβγ，ａγα－ｂγα）を計算して記録する。
Ｃ＝Ａ＋Ｓの秘密計算（ただし、Ｓは既知の定数）
（１）秘密分散装置１００αは（ｃγα，ｃαβ）＝（ａγα＋Ｓ，ａαβ）を計算して記録し、秘密分散装置１００γは（ｃβγ，ｃγα）＝（ａβγ，ａγα＋Ｓ）を計算して記録する。秘密分散装置１００βの処理はない。
Ｃ＝ＡＳの秘密計算（ただし、Ｓは既知の定数）
（１）秘密分散装置１００αは（ｃγα，ｃαβ）＝（ａγαＳ，ａαβＳ）を計算して記録し、秘密分散装置１００βは（ｃαβ，ｃβγ）＝（ａαβＳ，ａβγＳ）を計算して記録し、秘密分散装置１００γは（ｃβγ，ｃγα）＝（ａβγＳ，ａγαＳ）を計算して記録する。
Ｃ＝ＡＢの秘密計算
（１）秘密分散装置１００αは、乱数ｒ１，ｒ２，ｃγαを生成し、ｃαβ＝（ａγα＋ａαβ）（ｂγα＋ｂαβ）－ｒ１－ｒ２－ｃγαを計算する。そして、秘密分散装置１００αは、秘密分散装置１００βに（ｒ１，ｃαβ）を、秘密分散装置１００γに（ｒ２，ｃγα）を送信する。
（２）秘密分散装置１００βは、ｙ＝ａαβｂβγ＋ａβγｂαβ＋ｒ１を計算し、秘密分散装置１００γに送信する。
（３）秘密分散装置１００γは、ｚ＝ａβγｂγα＋ａγαｂβγ＋ｒ２を計算し、秘密分散装置１００αに送信する。
（４）秘密分散装置１００βと秘密分散装置１００γは、それぞれｃβγ＝ｙ＋ｚ＋ａβγｂβγを計算する。
（５）秘密分散装置１００αは（ｃγα，ｃαβ）を記録し、秘密分散装置１００βは（ｃαβ，ｃβγ）を記録し、秘密分散装置１００γは（ｃβγ，ｃγα）を記録する。
［プログラム、記録媒体］
　上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
　また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
　この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
　また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ－ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
　このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
　また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。

Claims (14)

  1. 　Ｎ個の秘密分散装置で構成された秘密分散システムであって、
    　Ｎを３以上の整数、ｎを１以上Ｎ以下の整数、Ｍを１以上の整数、ｍを1以上Ｍ以下の整数、Ｋを２以上の整数、ｋを１以上Ｋ以下の整数、数値Ａ１ （１），…，ＡＫ （１），…，Ａ１ （Ｍ），…，ＡＫ （Ｍ）を各秘密分散装置が断片を分散して記録するＫ×Ｍ個の数値、数値Ａｋ （１），…，Ａｋ （Ｍ）を対応付けられたｋ番目の数値群、ａｋｎ （ｍ）をｎ番目の秘密分散装置が記録する数値Ａｋ （ｍ）の断片、ｉをＮ個の秘密分散装置の中から選択された秘密分散装置を示すための１以上Ｎ以下の中の一部の整数とし、
    　２以上Ｎ未満の数の秘密分散装置を選択する選択手段と、
    　前記選択手段で選択された秘密分散装置の間で｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、選択されたｉ番目の秘密分散装置が記録する対応付けられたπ（ｋ）番目の数値群の断片ａπ（ｋ）ｉ （１），…，ａπ（ｋ）ｉ （Ｍ）をそれぞれ対応付けられたｋ番目の数値群の断片にする断片置換手段と、
    　前記断片置換手段によって置換された数値Ａπ（ｋ） （１），…，Ａπ（ｋ） （Ｍ）に対応する断片ａπ（ｋ）ｉ （１），…，ａπ（ｋ）ｉ （Ｍ）を用いて再分散化して新しい断片ｂｋ１ （１），…，ｂｋＮ （１），…，ｂｋ１ （Ｍ），…，ｂｋＮ （Ｍ）を求め、数値Ｂｋ （１），…，Ｂｋ （Ｍ）の断片とする再分散手段と、
    　を備える秘密分散システム。
  2. 　請求項１記載の秘密分散システムであって、
    　Ｍ＝１である秘密分散システム。
  3. 　請求項２記載の秘密分散システムであって、
    　Ｎ個の秘密分散装置のどれも知らないＫ個の数値Ｐ１，…，ＰＫそれぞれの断片を秘密計算によって求め、ｎ番目の秘密分散装置に断片ｐ１ｎ，…，ｐＫｎを記録する初期情報分散手段と、
    　Ｎ個の秘密分散装置で、Ｓｋ＝Ｐｋ×Ａｋ （１）である数値Ｓｋの断片ｓｋ１，…，ｓｋＮを秘密計算によって求め、Ｎ個の秘密分散装置に分散して記録する初期乗算手段と、
    　ｋ＝１～Ｋについて、Ｑｋ＝Ｐπ（ｋ）である数値Ｑｋの断片ｑｋ１，…，ｑｋＮを秘密計算によって生成し、Ｎ個の秘密分散装置に分散して記録する確認分散手段と、
    　Ｎ個の秘密分散装置で、Ｔｋ＝Ｑｋ×Ｂｋ （１）である数値Ｔｋの断片ｔｋ１，…，ｔｋＮを秘密計算によって求め、Ｎ個の秘密分散装置に分散して記録する確認乗算手段と、
    　ｋ＝１～Ｋについて、Ｔｋ＝Ｓπ（ｋ）であることを確認する改ざん検出手段、
    　も備える秘密分散システム。
  4. 　請求項１記載の秘密分散システムであって、
    　Ｎ＝３、（α，β，γ）を（１，２，３）と（２，３，１）と（３，１，２）のいずれかの組み合わせ、数値Ａｋ （ｍ）＝ａｋαβ （ｍ）＋ａｋβγ （ｍ）＋ａｋγα （ｍ）の３つの断片を（ａｋγα （ｍ），ａｋαβ （ｍ））と（ａｋαβ （ｍ），ａｋβγ （ｍ））と（ａｋβγ （ｍ），ａｋγα （ｍ））、前記の３つの断片は３つの秘密分散装置に分散して記録されているとし、
    　前記選択手段は、２つの秘密分散装置を選択し、選択された秘密分散装置の一方を第１の秘密分散装置、他方を第２の秘密分散装置、選択されなかった秘密分散装置を第３の秘密分散装置とし、
    　前記断片置換手段は、第１の秘密分散装置が記録する数値Ａｋ （ｍ）の断片をａｋ１ （ｍ）＝（ａｋ３１ （ｍ），ａｋ１２ （ｍ））、第２の秘密分散装置が記録する数値Ａｋ （ｍ）の断片をａｋ２ （ｍ）＝（ａｋ１２ （ｍ），ａｋ２３ （ｍ））、第３の秘密分散装置が記録する数値Ａｋ （ｍ）の断片をａｋ３ （ｍ）＝（ａｋ２３ （ｍ），ａｋ３１ （ｍ））とし、第１の秘密分散装置または第２の秘密分散装置で｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、第１の秘密分散装置が記録する対応付けられたπ（ｋ）番目の数値群の断片ａπ（ｋ）１ （１），…，ａπ（ｋ）１ （Ｍ）を対応付けられたｋ番目の数値群の断片にし、第２の秘密分散装置が記録する対応付けられたπ（ｋ）番目の数値群の断片ａπ（ｋ）２ （１），…，ａπ（ｋ）２ （Ｍ）を対応付けられたｋ番目の数値群の断片にし、
    　前記再分散手段として、各秘密分散装置が、
    　第１の秘密分散装置のときには、対応付けられたｋ番目の数値群の断片の再分散化のために、ランダムな値であるｂｋ３１ （１），…，ｂｋ３１ （Ｍ）を生成し、第３の秘密分散装置に送信する第１乱数生成部と、
    　第２の秘密分散装置のときには、対応付けられたｋ番目の数値群の断片の再分散化のために、ランダムな値であるｂｋ２３ （１），…，ｂｋ２３ （Ｍ）を生成し、第３の秘密分散装置に送信する第２乱数生成部と、
    　第１の秘密分散装置のときには、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１～Ｍについてｘｋ （ｍ）＝ｂｋ３１ （ｍ）－ａπ（ｋ）３１ （ｍ）を計算し、ｘｋ （１），…，ｘｋ （Ｍ）を第２の秘密分散装置に送信する第１計算部と、
    　第２の秘密分散装置のときには、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１～Ｍについてｙｋ （ｍ）＝ｂｋ２３ （ｍ）－ａπ（ｋ）２３ （ｍ）を計算し、ｙｋ （１），…，ｙｋ （Ｍ）を第１の秘密分散装置に送信する第２計算部と、
    　第１の秘密分散装置または第２の秘密分散装置のときには、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１～Ｍについてｂｋ１２ （ｍ）＝ａπ（ｋ）１２ （ｍ）－ｘｋ （ｍ）－ｙｋ （ｍ）を計算する第３計算部と、
    　第１の秘密分散装置のときには（ｂｋ３１ （ｍ），ｂｋ１２ （ｍ））を断片ｂｋ１ （ｍ）とし、第２の秘密分散装置のときには（ｂｋ１２ （ｍ），ｂｋ２３ （ｍ））を断片ｂｋ２ （ｍ）とし、第３の秘密分散装置のときには（ｂｋ２３ （ｍ），ｂｋ３１ （ｍ））を断片ｂｋ３ （ｍ）とする断片更新部と、
    　を備え、断片ｂｋ１ （ｍ）、ｂｋ２ （ｍ）、ｂｋ３ （ｍ）を数値Ｂｋ （ｍ）の断片として記録する
    　秘密分散システム。
  5. 　請求項４記載の秘密分散システムであって、
    　Ｍ＝１である秘密分散システム。
  6. 　請求項５記載の秘密分散システムであって、
    　第１の秘密分散装置でＫ個のランダムな値Ｒ（１） １，…，Ｒ（１） Ｋを生成し、第２の秘密分散装置でＫ個のランダムな値Ｒ（２） １，…，Ｒ（２） Ｋを生成し、前記３つの秘密分散装置で、Ｒ（１） ｋの断片（ｒ（１） ｋ３１，ｒ（１） ｋ１２）、（ｒ（１） ｋ１２，ｒ（１） ｋ２３）、（ｒ（１） ｋ２３，ｒ（１） ｋ３１）と、Ｒ（２） ｋの断片（ｒ（２） ｋ３１，ｒ（２） ｋ１２）、（ｒ（２） ｋ１２，ｒ（２） ｋ２３）、（ｒ（２） ｋ２３，ｒ（２） ｋ３１）とを秘密分散して記録し、前記３つの秘密分散装置で、Ｐｋ＝Ｒ（１） ｋ＋Ｒ（２） ｋである数値Ｐｋの断片（ｐｋ３１，ｐｋ１２）、（ｐｋ１２，ｐｋ２３）、（ｐｋ２３，ｐｋ３１）を秘密計算によって求め、前記３つの秘密分散装置に分散して記録する初期情報分散手段と、
    　前記３つの秘密分散装置で、Ｓｋ＝Ｐｋ×Ａｋ （１）である数値Ｓｋの断片（ｓｋ３１，ｓｋ１２）、（ｓｋ１２，ｓｋ２３）、（ｓｋ２３，ｓｋ３１）を秘密計算によって求め、前記３つの秘密分散装置に分散して記録する初期乗算手段と、
    　前記の数値Ｒ（１） π（ｋ）の別の断片（ｒ’（１） π（ｋ）３１，ｒ’（１） π（ｋ）１２）、（ｒ’（１） π（ｋ）１２，ｒ’（１） π（ｋ）２３）、（ｒ’（１） π（ｋ）２３，ｒ’（１） π（ｋ）３１）と、前記の数値Ｒ（２） π（ｋ）の別の断片（ｒ’（２） π（ｋ）３１，ｒ’（２） π（ｋ）１２）、（ｒ’（２） π（ｋ）１２，ｒ’（２） π（ｋ）２３）、（ｒ’（２） π（ｋ）２３，ｒ’（２） π（ｋ）３１）とを前記３つの秘密分散装置に分散して記録し、前記３つの秘密分散装置で、Ｑｋ＝Ｒ（１） π（ｋ）＋Ｒ（２） π（ｋ）である数値Ｑｋの断片（ｑｋ３１，ｑｋ１２）、（ｑｋ１２，ｑｋ２３）、（ｑｋ２３，ｑｋ３１）を当該別の断片を用いて秘密計算によって求め、前記３つの秘密分散装置に分散して記録する確認分散手段と、
    　前記３つの秘密分散装置で、Ｔｋ＝Ｑｋ×Ｂｋ （１）である数値Ｔｋの断片（ｔｋ３１，ｔｋ１２）、（ｔｋ１２，ｔｋ２３）、（ｔｋ２３，ｔｋ３１）を秘密計算によって求め、前記３つの秘密分散装置に分散して記録する確認乗算手段と、
    　第１の秘密分散装置が記録する断片をｓｋ１＝（ｓｋ３１，ｓｋ１２）、ｔｋ１＝（ｔｋ３１，ｔｋ１２）とし、第２の秘密分散装置が記録する断片をｓｋ２＝（ｓｋ１２，ｓｋ２３）、ｔｋ２＝（ｔｋ１２，ｔｋ２３）とし、第３の秘密分散装置が記録する断片をｓｋ３＝（ｓｋ２３，ｓｋ３１）、ｔｋ３＝（ｔｋ２３，ｔｋ３１）とし、
    各秘密分散装置が、
    　第１の秘密分散装置のときに、ランダムな値であるｕｋを生成し、第２の秘密分散装置に送信する第３乱数生成部と、
    　第２の秘密分散装置のときに、ランダムな値であるｖｋを生成し、第１の秘密分散装置に送信する第４乱数生成部と、
    　第１の秘密分散装置のときに、ｄｋ＝ｓπ（ｋ）１２－ｔｋ１２－ｕｋ－ｖｋを計算し、第３の秘密分散装置に送信する第４計算部と、
    　第２の秘密分散装置のときに、ｅｋ＝ｓπ（ｋ）１２－ｔｋ１２－ｕｋ－ｖｋを計算し、第３の秘密分散装置に送信する第５計算部と、
    　第３の秘密分散装置のときに、ｄｋ＝ｅｋであることを確認し、異なっていれば処理を中止する第１確認部と、
    　第１の秘密分散装置のときに、ｆｋ＝ｓπ（ｋ）３１－ｔｋ３１＋ｕｋを計算し、第３の秘密分散装置に送信する第６計算部と、
    　第２の秘密分散装置のときに、ｇｋ＝ｓπ（ｋ）２３－ｔｋ２３＋ｖｋを計算し、第３の秘密分散装置に送信する第７計算部と、
    　第３の秘密分散装置のときに、ｆｋ＋ｇｋ＋ｄｋ＝０であることを確認し、異なっていれば処理を中止する第２確認部と、
    　を備える
    　秘密分散システム。
  7. 　請求項４記載の秘密分散システムの中の秘密分散装置であって、
    　第１の秘密分散装置として選ばれたときには記録する数値Ａｋ （ｍ）の断片をａｋ１ （ｍ）＝（ａｋ３１ （ｍ），ａｋ１２ （ｍ））、第２の秘密分散装置として選ばれたときには記録する数値Ａｋ （ｍ）の断片をａｋ２ （ｍ）＝（ａｋ１２ （ｍ），ａｋ２３ （ｍ））、第３の秘密分散装置として選ばれたときには記録する数値Ａｋ （ｍ）の断片をａｋ３ （ｍ）＝（ａｋ２３ （ｍ），ａｋ３１ （ｍ））とし、
    　第１の秘密分散装置または第２の秘密分散装置として選ばれたときは、｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、対応付けられたπ（ｋ）番目の数値群の断片を対応付けられたｋ番目の数値群の断片にする断片置換部と、
    　第１の秘密分散装置のときには、対応付けられたｋ番目の数値群の断片の再分散化のために、ランダムな値であるｂｋ３１ （１），…，ｂｋ３１ （Ｍ）を生成し、第３の秘密分散装置に送信する第１乱数生成部と、
    　第２の秘密分散装置のときには、対応付けられたｋ番目の数値群の断片の再分散化のために、ランダムな値であるｂｋ２３ （１），…，ｂｋ２３ （Ｍ）を生成し、第３の秘密分散装置に送信する第２乱数生成部と、
    　第１の秘密分散装置のときには、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１～Ｍについてｘｋ （ｍ）＝ｂｋ３１ （ｍ）－ａπ（ｋ）３１ （ｍ）を計算し、ｘｋ （１），…，ｘｋ （Ｍ）を第２の秘密分散装置に送信する第１計算部と、
    　第２の秘密分散装置のときには、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１～Ｍについてｙｋ （ｍ）＝ｂｋ２３ （ｍ）－ａπ（ｋ）２３ （ｍ）を計算し、ｙｋ （１），…，ｙｋ （Ｍ）を第１の秘密分散装置に送信する第２計算部と、
    　第１の秘密分散装置または第２の秘密分散装置のときには、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１～Ｍについてｂｋ１２ （ｍ）＝ａπ（ｋ）１２ （ｍ）－ｘｋ （ｍ）－ｙｋ （ｍ）を計算する第３計算部と、
    　第１の秘密分散装置のときには（ｂｋ３１ （ｍ），ｂｋ１２ （ｍ））を断片ｂｋ１ （ｍ）とし、第２の秘密分散装置のときには（ｂｋ１２ （ｍ），ｂｋ２３ （ｍ））を断片ｂｋ２ （ｍ）とし、第３の秘密分散装置のときには（ｂｋ２３ （ｍ），ｂｋ３１ （ｍ））を断片ｂｋ３ （ｍ）とする断片更新部と、
    　を備える秘密分散装置。
  8. 　請求項７記載の秘密分散装置であって、
    　Ｍ＝１である秘密分散装置。
  9. 　Ｋを２以上の整数、ｋを１以上Ｋ以下の整数、Ｍを１以上の整数、ｍを１以上Ｍ以下の整数、Ａ１ （１），…，ＡＫ （１），…，Ａ１ （Ｍ），…，ＡＫ （Ｍ）をＫ×Ｍ個の数値、（α，β，γ）を（１，２，３）と（２，３，１）と（３，１，２）のいずれかの組み合わせ、数値Ａｋ （ｍ）＝ａｋαβ （ｍ）＋ａｋβγ （ｍ）＋ａｋγα （ｍ）の３つの断片を（ａｋγα （ｍ），ａｋαβ （ｍ））と（ａｋαβ （ｍ），ａｋβγ （ｍ））と（ａｋβγ （ｍ），ａｋγα （ｍ））、対応付けられたｋ番目の数値群をＡｋ （１），…，Ａｋ （Ｍ）とし、前記断片を分散して記録する３つの秘密分散装置を用いた秘密分散方法であって、
    　２つの秘密分散装置を選択し、選択された秘密分散装置の一方を第１の秘密分散装置、他方を第２の秘密分散装置、選択されなかった秘密分散装置を第３の秘密分散装置する選択ステップと、
    　第１の秘密分散装置が記録する数値Ａｋ （ｍ）の断片をａｋ１ （ｍ）＝（ａｋ３１ （ｍ），ａｋ１２ （ｍ））、第２の秘密分散装置が記録する数値Ａｋ （ｍ）の断片をａｋ２ （ｍ）＝（ａｋ１２ （ｍ），ａｋ２３ （ｍ））、第３の秘密分散装置が記録する数値Ａｋ （ｍ）の断片をａｋ３ （ｍ）＝（ａｋ２３ （ｍ），ａｋ３１ （ｍ））とし、第１の秘密分散装置または第２の秘密分散装置で｛１，…，Ｋ｝→｛１，…，Ｋ｝の全単射πを作成し、第１の秘密分散装置が記録する対応付けられたπ（ｋ）番目の数値群の断片ａπ（ｋ）１ （１），…，ａπ（ｋ）１ （Ｍ）を対応付けられたｋ番目の数値群の断片にし、第２の秘密分散装置が記録する対応付けられたπ（ｋ）番目の数値群の断片ａπ（ｋ）２ （１），…，ａπ（ｋ）２ （Ｍ）を対応付けられたｋ番目の数値群の断片にする断片置換ステップと、
    　第１の秘密分散装置が、対応付けられたｋ番目の数値群の断片の再分散化のために、ランダムな値であるｂｋ３１ （１），…，ｂｋ３１ （Ｍ）を生成し、第３の秘密分散装置に送信する第１乱数生成ステップと、
    　第２の秘密分散装置が、対応付けられたｋ番目の数値群の断片の再分散化のために、ランダムな値であるｂｋ２３ （１），…，ｂｋ２３ （Ｍ）を生成し、第３の秘密分散装置に送信する第２乱数生成ステップと、
    　第１の秘密分散装置が、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１～Ｍについてｘｋ （ｍ）＝ｂｋ３１ （ｍ）－ａπ（ｋ）３１ （ｍ）を計算し、ｘｋ （１），…，ｘｋ （Ｍ）を第２の秘密分散装置に送信する第１計算ステップと、
    　第２の秘密分散装置が、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１～Ｍについてｙｋ （ｍ）＝ｂｋ２３ （ｍ）－ａπ（ｋ）２３ （ｍ）を計算し、ｙｋ （１），…，ｙｋ （Ｍ）を第１の秘密分散装置に送信する第２計算ステップと、
    　第１の秘密分散装置と第２の秘密分散装置が、対応付けられたｋ番目の数値群の断片の再分散化のために、ｍ＝１～Ｍについてｂｋ１２ （ｍ）＝ａπ（ｋ）１２ （ｍ）－ｘｋ （ｍ）－ｙｋ （ｍ）を計算する第３計算ステップと、
    　第１の秘密分散装置が（ｂｋ３１ （ｍ），ｂｋ１２ （ｍ））を断片ｂｋ１ （ｍ）とし、第２の秘密分散装置が（ｂｋ１２ （ｍ），ｂｋ２３ （ｍ））を断片ｂｋ２ （ｍ）とし、第３の秘密分散装置が（ｂｋ２３ （ｍ），ｂｋ３１ （ｍ））を断片ｂｋ３ （ｍ）とする断片更新ステップと、
    　を有する秘密分散方法。
  10. 　請求項９記載の秘密分散方法であって、
    　Ｍ＝１である秘密分散方法。
  11. 　請求項１０記載の秘密分散方法であって、
    　第１の秘密分散装置がＫ個のランダムな値Ｒ（１） １，…，Ｒ（１） Ｋを生成し、第２の秘密分散装置がＫ個のランダムな値Ｒ（２） １，…，Ｒ（２） Ｋを生成し、前記３つの秘密分散装置がＲ（１） ｋの断片（ｒ（１） ｋ３１，ｒ（１） ｋ１２）、（ｒ（１） ｋ１２，ｒ（１） ｋ２３）、（ｒ（１） ｋ２３，ｒ（１） ｋ３１）とＲ（２） ｋの断片（ｒ（２） ｋ３１，ｒ（２） ｋ１２）、（ｒ（２） ｋ１２，ｒ（２） ｋ２３）、（ｒ（２） ｋ２３，ｒ（２） ｋ３１）とを秘密分散して記録し、前記３つの秘密分散装置がＰｋ＝Ｒ（１） ｋ＋Ｒ（２） ｋである数値Ｐｋの断片（ｐｋ３１，ｐｋ１２）、（ｐｋ１２，ｐｋ２３）、（ｐｋ２３，ｐｋ３１）を秘密計算によって求め、前記３つの秘密分散装置に分散して記録する初期情報分散ステップと、
    　前記３つの秘密分散装置が、Ｓｋ＝Ｐｋ×Ａｋ （１）である数値Ｓｋの断片（ｓｋ３１，ｓｋ１２）、（ｓｋ１２，ｓｋ２３）、（ｓｋ２３，ｓｋ３１）を秘密計算によって求め、前記３つの秘密分散装置に分散して記録する初期乗算ステップと、
    　前記３つの秘密分散装置が、請求項１０記載の秘密分散システムによって得られた断片ｂｋ１、ｂｋ２、ｂｋ３を数値Ｂｋ （１）の断片として記録する秘密分散更新ステップと、
    　前記の数値Ｒ（１） π（ｋ）の別の断片（ｒ’（１） π（ｋ）３１，ｒ’（１） π（ｋ）１２）、（ｒ’（１） π（ｋ）１２，ｒ’（１） π（ｋ）２３）、（ｒ’（１） π（ｋ）２３，ｒ’（１） π（ｋ）３１）と、前記の数値Ｒ（２） π（ｋ）の別の断片（ｒ’（２） π（ｋ）３１，ｒ’（２） π（ｋ）１２）、（ｒ’（２） π（ｋ）１２，ｒ’（２） π（ｋ）２３）、（ｒ’（２） π（ｋ）２３，ｒ’（２） π（ｋ）３１）とを前記３つの秘密分散装置に分散して記録し、前記３つの秘密分散装置で、Ｑｋ＝Ｒ（１） π（ｋ）＋Ｒ（２） π（ｋ）である数値Ｑｋの断片（ｑｋ３１，ｑｋ１２）、（ｑｋ１２，ｑｋ２３）、（ｑｋ２３，ｑｋ３１）を当該別の断片を用いて秘密計算によって求め、前記３つの秘密分散装置に分散して記録する確認分散ステップと、
    　前記３つの秘密分散装置が、Ｔｋ＝Ｑｋ×Ｂｋ （１）である数値Ｔｋの断片（ｔｋ３１，ｔｋ１２）、（ｔｋ１２，ｔｋ２３）、（ｔｋ２３，ｔｋ３１）を秘密計算によって求め、前記３つの秘密分散装置に分散して記録する確認乗算ステップと、
    　第１の秘密分散装置が記録する断片をｓｋ１＝（ｓｋ３１，ｓｋ１２）、ｔｋ１＝（ｔｋ３１，ｔｋ１２）とし、第２の秘密分散装置が記録する断片をｓｋ２＝（ｓｋ１２，ｓｋ２３）、ｔｋ２＝（ｔｋ１２，ｔｋ２３）とし、第３の秘密分散装置が記録する断片をｓｋ３＝（ｓｋ２３，ｓｋ３１）、ｔｋ３＝（ｔｋ２３，ｔｋ３１）とし、
    　第１の秘密分散装置が、ランダムな値であるｕｋを生成し、第２の秘密分散装置に送信する第３乱数生成ステップと、
    　第２の秘密分散装置が、ランダムな値であるｖｋを生成し、第１の秘密分散装置に送信する第４乱数生成ステップと、
    　第１の秘密分散装置が、ｄｋ＝ｓπ（ｋ）１２－ｔｋ１２－ｕｋ－ｖｋを計算し、第３の秘密分散装置に送信する第４計算ステップと、
    　第２の秘密分散装置が、ｅｋ＝ｓπ（ｋ）１２－ｔｋ１２－ｕｋ－ｖｋを計算し、第３の秘密分散装置に送信する第５計算ステップと、
    　第３の秘密分散装置が、ｄｋ＝ｅｋであることを確認し、異なっていれば処理を中止する第１確認ステップと、
    　第１の秘密分散装置が、ｆｋ＝ｓπ（ｋ）３１－ｔｋ３１＋ｕｋを計算し、第３の秘密分散装置に送信する第６計算ステップと、
    　第２の秘密分散装置が、ｇｋ＝ｓπ（ｋ）２３－ｔｋ２３＋ｖｋを計算し、第３の秘密分散装置に送信する第７計算ステップと、
    　第３の秘密分散装置が、ｆｋ＋ｇｋ＋ｄｋ＝０であることを確認し、異なっていれば処理を中止する第２確認ステップと、
    　を有する秘密分散方法。
  12. 　請求項９から１１のいずれかに記載の秘密分散方法であって、
    　前記断片更新ステップで得られた断片ｂｋ１ （ｍ）、ｂｋ２ （ｍ）、ｂｋ３ （ｍ）を新しい断片ａｋ１ （ｍ）、ａｋ２ （ｍ）、ａｋ３ （ｍ）とし、
    　前記断片置換ステップで、あらかじめ定めた全ての組合せで前記秘密分散装置を選択するまで、前記の秘密分散方法を繰り返す
    　ことを特徴とする秘密分散方法。
  13. 　請求項１２記載の秘密分散方法を用いた秘密ソート方法であって、
    　請求項１２記載の秘密分散方法によって断片を分散して記録した複数の数値に対して、
    　３つの秘密分散装置が、２つの数値を選択し、当該２つの数値の大小を秘密計算によって比較する比較ステップと、
    　秘密分散装置のそれぞれが、前記比較ステップの結果に基づいて数値の断片を入れ替える交換ステップと、
    　を有する秘密ソート方法。
  14. 　請求項１から６のいずれかに記載の秘密分散システムの各秘密分散装置としてコンピュータを機能させる秘密分散プログラム。
     
PCT/JP2011/072770 2010-10-06 2011-10-03 秘密分散システム、秘密分散装置、秘密分散方法、秘密ソート方法、秘密分散プログラム Ceased WO2012046692A1 (ja)

Priority Applications (4)

Application Number Priority Date Filing Date Title
EP11830624.0A EP2608190B1 (en) 2010-10-06 2011-10-03 Secret sharing system, secret sharing apparatus, secret sharing method, secret sorting method and secret sharing program
CN201180047430.3A CN103141056B (zh) 2010-10-06 2011-10-03 秘密分散系统、秘密分散装置、秘密分散方法、秘密分类方法、秘密分散程序
US13/876,110 US8989391B2 (en) 2010-10-06 2011-10-03 Secret sharing system, secret sharing apparatus, secret sharing method, secret sorting method and secret sharing program
JP2012537700A JP5411994B2 (ja) 2010-10-06 2011-10-03 秘密分散システム、秘密分散装置、秘密分散方法、秘密ソート方法、秘密分散プログラム

Applications Claiming Priority (4)

Application Number Priority Date Filing Date Title
JP2010-226553 2010-10-06
JP2010226553 2010-10-06
JP2011192844 2011-09-05
JP2011-192844 2011-09-05

Publications (1)

Publication Number Publication Date
WO2012046692A1 true WO2012046692A1 (ja) 2012-04-12

Family

ID=45927688

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2011/072770 Ceased WO2012046692A1 (ja) 2010-10-06 2011-10-03 秘密分散システム、秘密分散装置、秘密分散方法、秘密ソート方法、秘密分散プログラム

Country Status (5)

Country Link
US (1) US8989391B2 (ja)
EP (1) EP2608190B1 (ja)
JP (1) JP5411994B2 (ja)
CN (1) CN103141056B (ja)
WO (1) WO2012046692A1 (ja)

Cited By (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2013225078A (ja) * 2012-04-23 2013-10-31 Panasonic Corp 分散装置、復元装置、分散方法、復元方法及び分散復元システム
JPWO2012102203A1 (ja) * 2011-01-24 2014-06-30 日本電信電話株式会社 秘匿積和計算方法、秘匿積和計算システム、計算装置、及びそれらのプログラム
WO2019074044A1 (ja) * 2017-10-13 2019-04-18 日本電信電話株式会社 秘匿ソートシステム及び方法
JPWO2021106133A1 (ja) * 2019-11-28 2021-06-03
WO2021106143A1 (ja) * 2019-11-28 2021-06-03 日本電気株式会社 シャッフルシステム、シャッフル方法及びプログラム
CN114153808A (zh) * 2022-02-09 2022-03-08 支付宝(杭州)信息技术有限公司 一种基于秘密分享的排序方法和系统
WO2022079895A1 (ja) * 2020-10-16 2022-04-21 日本電信電話株式会社 秘密計算システム、秘密計算装置、秘密計算方法、およびプログラム

Families Citing this family (17)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP2947642B1 (en) * 2013-01-17 2017-09-06 Nippon Telegraph and Telephone Corporation Secret computation system, arithmetic unit, secret computation method and program
EP3096310B1 (en) * 2014-01-17 2018-08-01 Nippon Telegraph And Telephone Corporation Secret calculation method, secret calculation system, random permutation device, and program
WO2015107951A1 (ja) * 2014-01-17 2015-07-23 日本電信電話株式会社 秘密計算方法、秘密計算システム、ソート装置及びプログラム
WO2015114947A1 (ja) * 2014-01-28 2015-08-06 日本電信電話株式会社 秘密計算方法、秘密計算システム、秘密計算サーバ、登録者端末、利用者端末及びプログラム
JP5860556B1 (ja) * 2015-02-06 2016-02-16 日本電信電話株式会社 不整合検知方法、不整合検知システム、不整合検知装置、およびプログラム
JP5968484B1 (ja) * 2015-03-18 2016-08-10 日本電信電話株式会社 シェア復旧システム、シェア復旧方法、およびプログラム
JP5957126B1 (ja) * 2015-06-24 2016-07-27 日本電信電話株式会社 秘密計算装置、秘密計算方法、およびプログラム
CN105204782B (zh) * 2015-10-13 2018-12-11 中国联合网络通信集团有限公司 一种实现数据存储的方法及装置
SG11201805542TA (en) * 2016-02-23 2018-09-27 Nchain Holdings Ltd Secure multiparty loss resistant storage and transfer of cryptographic keys for blockchain based systems in conjunction with a wallet management system
CN109478381B (zh) * 2016-07-06 2021-12-14 日本电信电话株式会社 秘密计算系统、秘密计算装置、秘密计算方法以及程序
WO2018034079A1 (ja) * 2016-08-18 2018-02-22 日本電気株式会社 秘密計算システム、秘密計算方法、秘密計算装置、分散情報生成装置およびそれらの方法とプログラム
WO2019009180A1 (ja) * 2017-07-05 2019-01-10 日本電信電話株式会社 秘密計算システム、秘密計算装置、秘密計算方法、プログラム、および記録媒体
US11514192B2 (en) * 2017-09-21 2022-11-29 Nippon Telegraph And Telephone Corporation Secure reading apparatus, secure writing apparatus, method thereof, and program for reading and writing data in a sequence without revealing an access position
CN111902854B (zh) * 2018-03-26 2023-08-01 日本电信电话株式会社 秘密重复排除滤波器生成系统、秘密重复排除系统、它们的方法、秘密计算装置以及记录介质
JP6973629B2 (ja) * 2018-04-20 2021-12-01 日本電信電話株式会社 秘密集約順位システム、秘密計算装置、秘密集約順位方法、およびプログラム
US11281493B2 (en) 2018-05-30 2022-03-22 Texas Instruments Incorporated Real-time context specific task manager for multi-core communication and control system
CN114282255B (zh) * 2022-03-04 2022-05-31 支付宝(杭州)信息技术有限公司 一种基于秘密分享的排序序列合并方法和系统

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2005227331A (ja) * 2004-02-10 2005-08-25 Ntt Communications Kk 機密情報管理システム、機密情報管理方法、および機密情報管理プログラム
JP2007300157A (ja) * 2006-04-27 2007-11-15 Toshiba Corp 秘密分散システム、装置及びプログラム

Family Cites Families (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6263436B1 (en) * 1996-12-17 2001-07-17 At&T Corp. Method and apparatus for simultaneous electronic exchange using a semi-trusted third party
CA2369304A1 (en) * 2002-01-30 2003-07-30 Cloakware Corporation A protocol to hide cryptographic private keys
JP4602675B2 (ja) * 2004-02-10 2010-12-22 エヌ・ティ・ティ・コミュニケーションズ株式会社 機密情報管理システム、機密情報管理方法、および機密情報管理プログラム、並びに機密情報管理システム用端末プログラム
WO2005076518A1 (en) * 2004-02-10 2005-08-18 Ntt Communications Corporation Secret information management scheme based on secret sharing scheme
WO2008048713A2 (en) * 2006-05-05 2008-04-24 President And Fellows Of Harvard College Practical secrecy-preserving, verifiably correct and trustworthy auctions
EP2122530A2 (en) * 2006-12-15 2009-11-25 Hans Martin Boesgaard Sørensen Digital data authentication
US8930660B2 (en) * 2007-02-16 2015-01-06 Panasonic Corporation Shared information distributing device, holding device, certificate authority device, and system
US8457305B2 (en) * 2009-11-13 2013-06-04 Microsoft Corporation Generating genus 2 curves from invariants

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2005227331A (ja) * 2004-02-10 2005-08-25 Ntt Communications Kk 機密情報管理システム、機密情報管理方法、および機密情報管理プログラム
JP2007300157A (ja) * 2006-04-27 2007-11-15 Toshiba Corp 秘密分散システム、装置及びプログラム

Non-Patent Citations (5)

* Cited by examiner, † Cited by third party
Title
AMIR HERZBERG; STANISLAW JARECKI; HUGO KRAWCZYK; MOTI YUNG: "CRYPTO 1995", vol. 963, 1995, SPRINGER, article "Proactive secret sharing or: How to cope with perpetual leakage", pages: 339 - 352
KOJI CHIDA; DAI IKARASHI; KATSUMI TAKAHASHI: "Efficient 3-Party Secure Function Evaluation and Its Application", 48-TH IPSJ SIG TECHNICAL REPORT, CSEC, 4 March 2010 (2010-03-04), pages 1 - 7
KOKI HAMADA: "A Random Permutation Protocol on Three-Party Secure Function Evaluation", COMPUTER SECURITY SYMPOSIUM 2010 (CSS2010) RONBUNSHU, vol. 2, no. 9, 12 October 2010 (2010-10-12), pages 561 - 566, XP008170364 *
RICHARD DURSTENFELD: "Algorithm 235: Random permutation", COMMUNICATIONS OF THE ACM ARCHIVE, vol. 7, no. 7, 1964
See also references of EP2608190A4

Cited By (22)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPWO2012102203A1 (ja) * 2011-01-24 2014-06-30 日本電信電話株式会社 秘匿積和計算方法、秘匿積和計算システム、計算装置、及びそれらのプログラム
JP2013225078A (ja) * 2012-04-23 2013-10-31 Panasonic Corp 分散装置、復元装置、分散方法、復元方法及び分散復元システム
US9442890B2 (en) 2012-04-23 2016-09-13 Panasonic Intellectual Property Management Co., Ltd. Distribution apparatus, restoration apparatus, distribution method, restoration method, and distribution and restoration system
AU2018349997B2 (en) * 2017-10-13 2021-07-22 Ntt, Inc. Confidential sort system and method
WO2019074044A1 (ja) * 2017-10-13 2019-04-18 日本電信電話株式会社 秘匿ソートシステム及び方法
JPWO2019074044A1 (ja) * 2017-10-13 2020-11-05 日本電信電話株式会社 秘匿ソートシステム及び方法
CN111183469A (zh) * 2017-10-13 2020-05-19 日本电信电话株式会社 隐匿分类系统以及方法
CN111183469B (zh) * 2017-10-13 2023-02-28 日本电信电话株式会社 隐匿分类系统以及方法
JP7420147B2 (ja) 2019-11-28 2024-01-23 日本電気株式会社 シャッフルシステム、シャッフル方法及びプログラム
JPWO2021106133A1 (ja) * 2019-11-28 2021-06-03
WO2021106133A1 (ja) * 2019-11-28 2021-06-03 日本電気株式会社 シャッフルシステム、シャッフル方法及びプログラム
US12160506B2 (en) 2019-11-28 2024-12-03 Nec Corporation Shuffling shares among nodes to detect incorrectness or frauds
JPWO2021106143A1 (ja) * 2019-11-28 2021-06-03
WO2021106143A1 (ja) * 2019-11-28 2021-06-03 日本電気株式会社 シャッフルシステム、シャッフル方法及びプログラム
US12143420B2 (en) 2019-11-28 2024-11-12 Nec Corporation Shuffling shares among nodes to detect incorrectness or frauds
JP7334798B2 (ja) 2019-11-28 2023-08-29 日本電気株式会社 シャッフルシステム、シャッフル方法及びプログラム
WO2022079895A1 (ja) * 2020-10-16 2022-04-21 日本電信電話株式会社 秘密計算システム、秘密計算装置、秘密計算方法、およびプログラム
AU2020472388B2 (en) * 2020-10-16 2024-02-15 Ntt, Inc. Secure computation system, secure computation apparatus, secure computation method, and program
JP7468687B2 (ja) 2020-10-16 2024-04-16 日本電信電話株式会社 秘密計算システム、秘密計算装置、秘密計算方法、およびプログラム
CN116324937A (zh) * 2020-10-16 2023-06-23 日本电信电话株式会社 秘密计算系统、秘密计算装置、秘密计算方法以及程序
AU2020472388A9 (en) * 2020-10-16 2025-03-13 Ntt, Inc. Secure computation system, secure computation apparatus, secure computation method, and program
CN114153808A (zh) * 2022-02-09 2022-03-08 支付宝(杭州)信息技术有限公司 一种基于秘密分享的排序方法和系统

Also Published As

Publication number Publication date
CN103141056A (zh) 2013-06-05
US20130182836A1 (en) 2013-07-18
EP2608190A4 (en) 2014-10-01
CN103141056B (zh) 2015-08-26
EP2608190B1 (en) 2016-05-11
EP2608190A1 (en) 2013-06-26
JP5411994B2 (ja) 2014-02-12
JPWO2012046692A1 (ja) 2014-02-24
US8989391B2 (en) 2015-03-24

Similar Documents

Publication Publication Date Title
JP5411994B2 (ja) 秘密分散システム、秘密分散装置、秘密分散方法、秘密ソート方法、秘密分散プログラム
US11038679B2 (en) Secure multi-party computation method and apparatus, and electronic device
Farah et al. A novel method for designing S-box based on chaotic map and teaching–learning-based optimization
JP6095792B2 (ja) 秘密ビット分解装置、秘密モジュラス変換装置、秘密ビット分解方法、秘密モジュラス変換方法、プログラム
EP2947642A1 (en) Secure-computation system, computing device, secure-computation method, and program
JP2021515271A (ja) コンピュータにより実施される投票処理およびシステム
JP5486520B2 (ja) セキュア集合関数システム、秘密集合関数装置、セキュア集合関数処理方法、セキュア集合関数プログラム
JP5944841B2 (ja) 秘密分散システム、データ分散装置、分散データ保有装置、秘密分散方法、およびプログラム
WO2014007310A1 (ja) 秘密分散システム、データ分散装置、分散データ変換装置、秘密分散方法、およびプログラム
CN107210006A (zh) 不一致检测方法、不一致检测系统、不一致检测装置以及程序
EP3389031A1 (en) Pre-calculation device, method, computer-readable recording medium, vector multiplication device, and method
JP5860557B1 (ja) 秘密公開方法、秘密公開システム、秘密公開装置、およびプログラム
Zhang et al. A blockchain-based privacy-preserving scheme for sealed-bid auction
CN112819058A (zh) 一种具有隐私保护属性的分布式随机森林评估系统与方法
CN112905187A (zh) 编译方法、装置、电子设备及存储介质
Faraoun A genetic strategy to design cellular automata based block ciphers
JP5438650B2 (ja) 不正検知方法、秘密計算システム、計算装置、計算プログラム
He et al. Towards secure weighted aggregation for privacy-preserving federated learning
García-Hernández et al. Multi-objective configuration of a secured distributed cloud data storage
CN116032639A (zh) 基于隐私计算的消息推送方法及装置
CN107210005A (zh) 矩阵/密钥生成装置、矩阵/密钥生成系统、矩阵结合装置、矩阵/密钥生成方法、程序
JPWO2019198516A1 (ja) 鍵配信システム、端末装置、鍵配信方法、及びプログラム
JPWO2018216512A1 (ja) 秘密改ざん検知システム、秘密改ざん検知装置、秘密改ざん検知方法、およびプログラム
JP2015135380A (ja) シェア変換システム、シェア変換方法、プログラム
Juraev et al. Protection of Transaction Data of Financial Information Systems in Communication Networks Based on Sea80 New Stream Encryption Algorithm

Legal Events

Date Code Title Description
WWE Wipo information: entry into national phase

Ref document number: 201180047430.3

Country of ref document: CN

121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 11830624

Country of ref document: EP

Kind code of ref document: A1

ENP Entry into the national phase

Ref document number: 2012537700

Country of ref document: JP

Kind code of ref document: A

WWE Wipo information: entry into national phase

Ref document number: 2011830624

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 13876110

Country of ref document: US

NENP Non-entry into the national phase

Ref country code: DE