WO2015107952A1 - 秘密計算方法、秘密計算システム、ランダム置換装置及びプログラム - Google Patents

秘密計算方法、秘密計算システム、ランダム置換装置及びプログラム Download PDF

Info

Publication number
WO2015107952A1
WO2015107952A1 PCT/JP2015/050231 JP2015050231W WO2015107952A1 WO 2015107952 A1 WO2015107952 A1 WO 2015107952A1 JP 2015050231 W JP2015050231 W JP 2015050231W WO 2015107952 A1 WO2015107952 A1 WO 2015107952A1
Authority
WO
WIPO (PCT)
Prior art keywords
random
secret sharing
random replacement
replacement device
value
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/JP2015/050231
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 JP2015557797A priority Critical patent/JP6009698B2/ja
Priority to US15/110,886 priority patent/US10002547B2/en
Priority to EP15737344.0A priority patent/EP3096310B1/en
Priority to CN201580004210.0A priority patent/CN105900165B/zh
Publication of WO2015107952A1 publication Critical patent/WO2015107952A1/ja
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G09—EDUCATION; CRYPTOGRAPHY; DISPLAY; ADVERTISING; SEALS
    • G09C—CIPHERING OR DECIPHERING APPARATUS FOR CRYPTOGRAPHIC OR OTHER PURPOSES INVOLVING THE NEED FOR SECRECY
    • G09C1/00—Apparatus or methods whereby a given sequence of signs, e.g. an intelligible text, is transformed into an unintelligible sequence of signs by transposing the signs or groups of signs or by replacing them by others according to a predetermined system
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F21/00—Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
    • G06F21/60—Protecting data
    • 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
    • H04L2209/00—Additional information or applications relating to cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
    • H04L2209/46—Secure multiparty computation, e.g. millionaire problem

Definitions

  • the present invention relates to a secret calculation technique, and more particularly to a technique for performing secret random replacement.
  • Secret calculation is a technology that performs data processing while keeping data secret by secret sharing.
  • Secret sharing is a technology that converts data into a plurality of distributed values and restores the original data by using more than a certain number of distributed values, and makes it impossible to restore the original data from less than a certain number of distributed values.
  • Secret sharing can be classified into several types, for example, (k, n) -secret sharing, additive secret sharing, and replacement data secret sharing.
  • the secret sharing is such that if the number of shares is complete, plaintext can be restored, and no information about the plaintext can be obtained from less than k shares.
  • Specific examples of (k, n) -secret sharing include Shamir secret sharing and duplicate secret sharing.
  • Additive secret sharing is (k, k) -secret sharing by duplicate secret sharing.
  • plaintext cannot be restored unless the shares of all parties gather.
  • Additive secret sharing is the simplest secret sharing in which plaintext is restored simply by adding k shares.
  • Replacement data secret sharing is secret sharing performed by concealing replacement data.
  • the replacement data is data representing how to rearrange the data string.
  • the replacement data ⁇ having the size m is data representing a bijection map ⁇ : N m ⁇ N m .
  • N m is a set of non-negative integers less than m.
  • data whose elements are different from each other in the vector x ⁇ ⁇ (N m ) m can be regarded as random replacement data of size m.
  • move 7 to the second and 10 to the first
  • each k party set ⁇ i is a set of party p 0 and party p 1 (p 0 , p 1 ) or a set of party p 0 and party p 2 (p 0 , p 2 ).
  • Etc. It is assumed that all parties in each k-party set ⁇ i share the replacement data ⁇ ⁇ i with each other and do not know the complement ⁇ ⁇ i .
  • the corresponding plaintext is assumed to be ⁇ 0 ( ⁇ 1 (... ( ⁇ N-1 (I)).
  • Secret random replacement is a technique that replaces an input data string at random so that the execution person does not know in what order the replacement is performed. There is a technique described in Non-Patent Document 1 as a conventional technique for performing secret random replacement.
  • the following three types of secret random replacement can be considered due to differences in input / output types.
  • the first case is when both input and output are (k, n) -secret sharing values.
  • the second case is when the input is a (k, n) -secret sharing value and the output is a public value.
  • the third is the case where the input is a public value and the output is a (k, n) -secret sharing value.
  • the input is a public value
  • the basic value is processed after the public value is secretly shared to obtain a secret sharing value.
  • the output is a public value
  • the public processing is performed after the basic processing described above is performed.
  • the public value is a value known to all parties.
  • the public process is, for example, that all parties transmit their shares to all other parties and restore secret sharing from the shares received by all parties.
  • Non-Patent Document 1 repeats the replacement and redistribution processes using the (k, n) -secret sharing value.
  • each party has to communicate with all the parties, and there is a problem that the amount of communication and the number of communication stages are large.
  • An object of the present invention is to reduce the amount of communication and the number of communication steps required for secret random replacement, and to perform secret calculation including secret random replacement at high speed.
  • a random replacement apparatus included in the set [rho i + 1 of the unsubstituted, random replacement devices p j (j 1, ... , k-1) of the i-th random permutation device set [rho i and i + 1 th As k ⁇ 1 random replacement devices included in any of the random replacement device sets ⁇ i + 1 , the random replacement devices p 0 ,..., P k-1 subshare the additive secret sharing value ⁇ a >> ⁇ i.
  • random replacement device p 0 is a random replacement devices p 1, ..., a random number r 1 to share the p k-1, ..., additive secret sharing values with r k-1 send to the random replacement device p k to generate «a» ⁇ i + 1 pk, respectively random replacement device p j generates an additive secret sharing value «a» ⁇ i + 1 pj using the random number r j redispersed Steps.
  • secret calculation technique of the present invention it is possible to reduce the amount of communication and the number of communication stages when performing secret random replacement. Therefore, secret calculation including secret random replacement can be executed at high speed.
  • FIG. 1 is a diagram illustrating a functional configuration of a secret calculation system.
  • FIG. 2 is a diagram illustrating a functional configuration of the random replacement device of the first embodiment.
  • FIG. 3 is a diagram illustrating a processing flow of the secret calculation method according to the first embodiment.
  • FIG. 4 is a diagram illustrating a processing flow of the secret calculation method according to the second embodiment.
  • FIG. 5 is a diagram illustrating a processing flow of the secret calculation method according to the third embodiment.
  • FIG. 6 is a diagram illustrating a functional configuration of the random replacement device of the fourth embodiment.
  • FIG. 7 is a diagram illustrating a processing flow of the secret calculation method according to the fourth embodiment.
  • notation methods and terms used in this specification are defined.
  • p represents the party that owns the share.
  • P (p 0 ,..., P n ⁇ 1 ) represents a set of all n parties possessing a share.
  • ⁇ (p 0 ,..., p k ⁇ 1 ) represents a set of k party sets that perform the replacement process.
  • ⁇ ( ⁇ 0 ,..., ⁇ N ⁇ 1 ) represents the order of the k party group that executes each replacement process.
  • N n C k is the number of executions of replacement processing, and is the number of all combinations for selecting k parties from n parties.
  • [x] represents the (k, n) -secret sharing value of plaintext x ⁇ G.
  • G is a commutative group.
  • the (k, n) -secret sharing value is a set obtained by collecting all shares in which plaintext x is distributed by (k, n) -secret sharing. Since the secret sharing value [x] is usually distributed and held in the n party set P, it is not held in one place and is virtual.
  • [x] p represents a share possessed by the party p ⁇ P among (k, n) -secret sharing value [x].
  • [x ⁇ ] represents a column of (k, n) -secret sharing values in which the plaintext column becomes x ⁇ .
  • [G] represents a set of all (k, n) -secret sharing values on the commutative group G.
  • ⁇ x >> ⁇ is an additive secret sharing value of plaintext x ⁇ G, and represents what the k party set ⁇ owns a share.
  • the additive secret sharing value represents a set of all shares obtained by distributing plaintext x by additive secret sharing.
  • «X» ⁇ p represents the share possessed by the party p ⁇ among the additive secret sharing values «x» ⁇ .
  • «X ⁇ » ⁇ represents a sequence of additive secret sharing values where the plaintext sequence is x ⁇ .
  • ⁇ G >> ⁇ represents a set of all additive secret sharing values on the commutative group G.
  • ⁇ > represents a replacement data secret sharing value of replacement data ⁇ .
  • ⁇ represents the entire set of replacement data of size m.
  • ⁇ > represents a set of all replacement data secret sharing values of size m.
  • Step 1 Convert input from (k, n) -secret sharing value or public value to additive secret sharing value.
  • one iteration is referred to as unit replacement, and the entire repeated process is referred to as iterative replacement.
  • Step 3 Convert the output from an additive secret sharing value to a (k, n) -secret sharing value or public value.
  • the point in unit replacement is to select the k party set ⁇ i so that
  • 1 in the i-th unit replacement.
  • the k-party set ⁇ i to perform unit replacement of the i-th in the k-party set ⁇ i + 1 to carry out the unit replacement (i + 1) th time, the rest of the k-1 party only one party is different from that same party That is.
  • Such unit replacement is called a 1-additive redistribution protocol because there is only one party.
  • Non-Patent Document 1 requires a communication amount of (n-1) (k-1) G elements.
  • the communication volume of k-1 G elements is sufficient.
  • the communication amount is only one G element. In this case, the amount of communication becomes a constant, which is very efficient.
  • k party set ⁇ p 0 , ..., p k-1 as secret sharing value ⁇ a >> ⁇ ⁇ ⁇ G >> ⁇ , and performs data processing according to the following procedure.
  • other k-party set ⁇ ' p 1
  • ..., p k is secret dispersion value «a» ⁇ possession' to output a ⁇ «G» ⁇ '.
  • the role of the party shall be changed appropriately.
  • the party p 0 calculates the secret sharing value ⁇ a >> ⁇ ′ pk according to the following equation and transmits it to the party p k .
  • the party p k outputs the received ⁇ a >> ⁇ ′ pk .
  • the iterative replacement is a repetition of replacement ⁇ redistribution ⁇ replacement ⁇ redistribution ⁇ . If this is simply performed, the number of communication stages is the number of re-distribution as it is, which is N-1 stages.
  • unit replacement with 1-additive redistribution protocol can be parallelized for communication. This is because there is only one party waiting for data reception, that is, a party that has not participated in the previous unit replacement, and the other unit performs only the offline processing without waiting for any data reception, and the next unit replacement processing. It is because it can shift to.
  • the unit replacement can be executed a maximum of k times in one stage. As a result, the number of communication stages can be reduced to (N-1) / k stages.
  • the order of the k party group increases the number of communication stages by making the order of the communication stages of the path from the party p i equal to each other or the smallest difference between the maximum and minimum values for any i ⁇ k. can do.
  • the number of communication stages of the route is the number of ⁇ s that need to be communicated as the party changes in the route, that is,
  • the communication of 1-additive redispersion protocol, except that party p k waits for transmission from the party p 0 is the communication of the random number does not depend on the previous stage of redispersion results.
  • Communication number of paths represents the number of stages that can not be executed in parallel are arranged in series in the communication party p k from the party p 0. Since the number of communication stages of the entire iterative replacement is as shown in the following equation, it is efficient if the number of communication stages of each path is equal.
  • the secret calculation system includes n ( ⁇ 2) random replacement devices 1 1 ,..., 1 n and a network 9.
  • the random replacement devices 1 1 ,..., 1 n are connected to the network 9 respectively.
  • the network 9 only needs to be configured so that the random replacement devices 1 1 ,..., 1 n can communicate with each other, and can be configured by the Internet, a LAN, a WAN, or the like, for example.
  • each of the random replacement devices 1 1 ,..., 1 n does not necessarily need to be able to communicate online via the network 9.
  • information output from a random replacement device 1 i (1 ⁇ i ⁇ n) is stored in a portable recording medium such as a USB memory, and the random replacement device 1 j (1 ⁇ j ⁇ n) different from the portable recording medium. , I ⁇ j) may be input offline.
  • the random replacement device 1 includes a pre-conversion unit 10, a unit replacement unit 12, a redistribution unit 14, a post-conversion unit 16, and a storage unit 18.
  • the random replacement device 1 is, for example, a special configuration in which a special program is read into a known or dedicated computer having a central processing unit (Central processing unit, CPU), a main storage device (Random access memory, RAM), and the like. Device.
  • the random replacement device 1 executes each process under the control of the central processing unit.
  • the storage unit 18 included in the random replacement device 1 includes, for example, a main storage device such as a RAM (Random Access Memory), an auxiliary storage device configured by a semiconductor memory element such as a hard disk, an optical disk, or a flash memory (Flash Memory), or It can be configured with middleware such as a relational database or key-value store.
  • a main storage device such as a RAM (Random Access Memory)
  • auxiliary storage device configured by a semiconductor memory element such as a hard disk, an optical disk, or a flash memory (Flash Memory)
  • middleware such as a relational database or key-value store.
  • the random replacement device 1 p corresponding to the party p stores the (k, n) -secret sharing value [a] p of the plaintext a or the public value a and the k party set ⁇ including the party p.
  • the sub-share ⁇ ⁇ of the corresponding replacement data ⁇ and N ⁇ k seeds s 0,1 ,..., S N ⁇ 1, k are stored.
  • the seeds s 0,1 ,..., S N ⁇ 1, k are stored in advance so as to be performed without communication when generating random numbers in the processing of the redistribution unit 14 described later. When the random number generation is performed cooperatively, it may not be stored.
  • step S10 the pre-conversion unit 10 included in the k random replacement devices 1 ⁇ 0 adds (k, n) -secret sharing value [a] pi or public value a stored in the storage unit 18 to the additive secret sharing. Convert to value ⁇ a >> ⁇ 0 .
  • conversion to an additive secret sharing value can be performed as follows, for example. Assume that ⁇ is a set of k random replacement devices 1 p0 ,..., 1 pk ⁇ 1 , a ⁇ G is an input public value, and the random replacement device 1 p0 knows the public value a.
  • the conversion to the additive secret sharing value can be performed by, for example, the methods described in Reference Document 1 and Reference Document 2 below.
  • Reference 1 describes a method of conversion from linear secret sharing including Shamir secret sharing to additive secret sharing without communication. Since Reference 2 describes a method for conversion from duplicate secret sharing to linear secret sharing without communication, conversion from duplicate secret sharing to additive secret sharing is performed using the method and reference described in Reference 2. 1 is implemented without communication by combining the methods described in 1.
  • step S1a the k random replacement devices 1 ⁇ 0 initialize a counter i indicating the number of executions of replacement processing to 0.
  • step S12 the unit replacement unit 12 included in the k random replacement devices 1 ⁇ i replaces the additive secret sharing value ⁇ a >> ⁇ i using the subshare ⁇ i of the replacement data stored in the storage unit 18.
  • the replacement method may be performed by a conventional replacement data secret sharing method.
  • step S14 the redistribution unit 14 included in the k random replacement devices 1 ⁇ i + 1 performs redistribution of the additive secret sharing value ⁇ a >> ⁇ i using the 1-additive redistribution protocol.
  • a random permutation device 1 p0 is included in the random permutation device 1 .rho.i a random permutation device not included in the random permutation device 1 .rho.i + 1, the random replacement device 1 pk, not included in the random replacement device 1 .rho.i
  • the random replacement device 1 is a random replacement device included in ⁇ i + 1 .
  • the redistribution unit 14 included in the random replacement device 1 ⁇ i + 1 generates k random numbers r 1 ,..., R k ⁇ G.
  • Random number r 1, ..., r k is a random number r 1 of the shared random permutation device 1 .rho.i + 1 of k base is coordinated, ..., may generate an r k, stored in the storage unit 18 seed s i, 1, ..., s i, the pseudo-random number r 1 by using the k, ..., may generate a r k. If pseudo random numbers are generated using seeds s i, 1 ,..., S i, k shared in advance, random numbers can be generated without communication between random replacement devices, which is very efficient.
  • the redistribution unit 14 included in the random replacement device 1 p0 uses the additive secret sharing value ⁇ a >> ⁇ i + 1 pk for the random replacement device 1 pk , the additive secret sharing value ⁇ a >> ⁇ i p0, and the random number.
  • r 0 ,..., r k ⁇ 1 it is generated by the following equation and transmitted to the random replacement device 1 pk .
  • the redistribution unit 14 included in the random replacement device 1 pj uses the additive secret sharing value ⁇ a >> ⁇ i pj and the random number r j to obtain the additive secret sharing value ⁇ a >> ⁇ i + 1 pj by the following equation: Generate.
  • step S1c the k random replacement devices 1 ⁇ i + 1 add 1 to a counter i representing the number of executions of the replacement process. Thereafter, the unit replacement in step S12 and the redistribution in step S14 are repeated until it is determined in step S1b that the counter i has reached N-1.
  • step S16 the a posteriori conversion unit 16 included in the k random replacement devices 1 ⁇ N-1 converts the additive secret sharing value into (k, n) -secret sharing value or a public value.
  • the method of converting from an additive secret sharing value to another format can be performed relatively lightly. It should be noted that the following conversion method is an example, and does not mean that it cannot be applied to other conversion methods.
  • the k random replacement devices 1 ⁇ N ⁇ 1 that have executed the replacement processing last for the random replacement device 1 p (1 ⁇ p ⁇ n) whose output is to be obtained are additive secret sharing
  • the output is a (k, n) -secret sharing value
  • it has additive homomorphism such as linear secret sharing and duplicate secret sharing, that is, for secret sharing that can be added without communication on the secret sharing value. It can be converted by the following procedure.
  • the n random replacement devices 1 P add all the received k (k, n) -secret sharing values [ ⁇ a >> ⁇ N ⁇ 1 pj ] p .
  • the secret calculation system can reduce the amount of communication in the re-distribution process by converting the input into an additive secret sharing value, which is more efficient than the conventional random replacement. Processing can be performed.
  • a public value a is stored in the storage unit 18 included in at least one random replacement device 1 p0 . It is sufficient that at least one public value a is possessed, and any number of random replacement devices may be possessed.
  • the storage unit 18 included in the n ⁇ 1 random replacement devices 1 p1 ,..., 1 pn-1 excluding the random replacement device 1 p0 has replacement data ⁇ corresponding to the k party set ⁇ i including the party p i. , ⁇ ⁇ i and N ⁇ k seeds s 0,1 ,..., S N ⁇ 1, k are stored.
  • N is n-1 Ck .
  • the seeds s 0,1 ,..., S N ⁇ 1, k may not necessarily be stored.
  • step S12 p0 the unit replacement unit 12 included in the random replacement device 1 p0 generates random replacement data ⁇ , and replaces the public value a with the replacement data ⁇ .
  • the replacement method is the same as the conventional replacement method.
  • step S10 p0 pre-translation unit 10 that random substitution apparatus 1 p0 is provided converts the public value a after the replacement to the additive secret variance «a» ⁇ -1.
  • the conversion method is the same as step S10 of the first embodiment.
  • the additive secret sharing value ⁇ a >> ⁇ 1 is distributed to k ⁇ 1 arbitrarily selected random replacement devices 1 ⁇ 0 .
  • the random replacement devices 1 p1 ,..., 1 pk-1 are distributed.
  • step S14 p0 the redistribution unit 14 included in the k random replacement devices 1 ⁇ 0 performs redistribution of the additive secret sharing value ⁇ a >> ⁇ -1 using the 1-additive redistribution protocol.
  • the redispersion method is the same as step S14 of the first embodiment.
  • step S1a to S16 are executed by n ⁇ 1 random replacement devices 1 p1 ,..., 1 pn ⁇ 1 excluding the random replacement device 1 p0 .
  • the number of replacement processes is n ⁇ . 1 C k +1, and it is possible to perform processing more efficiently than the secret calculation system of the first embodiment.
  • the storage unit 18 included in the n ⁇ 1 random replacement devices 1 p1 ,..., 1 pn-1 excluding the random replacement device 1 p0 has replacement data ⁇ corresponding to the k party set ⁇ i including the party p i. , ⁇ ⁇ i and N ⁇ k seeds s 0,1 ,..., S N ⁇ 1, k are stored.
  • N is n-1 Ck .
  • the seeds s 0,1 ,..., S N ⁇ 1, k may not necessarily be stored.
  • step S10 The processing from step S10 to S1b until i ⁇ N ⁇ 1 is executed by n ⁇ 1 random replacement devices 1 p1 ,..., 1 pn ⁇ 1 excluding the random replacement device 1 p0 .
  • step S16 p0 the posterior conversion unit 16 included in the random replacement device 1 p0 converts the additive secret sharing value into a public value.
  • the conversion method is the same as step S16 in the first embodiment.
  • step S12 p0 the unit replacement unit 12 included in the random replacement device 1 p0 generates random replacement data ⁇ and replaces the restored public value.
  • the replacement method is the same as the conventional replacement method.
  • the number of replacement processes is n ⁇ . 1 C k +1, and it is possible to perform processing more efficiently than the secret calculation system of the first embodiment.
  • the fourth embodiment is an embodiment that makes it possible to detect tampering during secret calculation for the secret random replacement of the present invention.
  • a secret tampering detection method for detecting tampering during secret calculation a method described in Reference Document 3 below has been proposed.
  • tampering detection during secret calculation is performed in three phases.
  • the randomization phase the variance value is converted into a randomized variance value that can be verified for validity.
  • a desired secret calculation is executed using an operation for a randomized variance value configured by a semi-honest operation. At this time, the calculation is performed while collecting the randomized variance values necessary for calculating the checksum in the subsequent correctness proof phase.
  • the fourth embodiment shows a configuration example in which the secret falsification detection method described in Reference 3 is applied to the secret random replacement of the first embodiment so as to satisfy the above-described conditions.
  • the example applied to 1st embodiment below is shown, it is also possible to apply to 2nd embodiment and 3rd embodiment by the same view.
  • the random replacement device 2 includes a pre-conversion unit 10, a unit replacement unit 12, a re-distribution unit 14, a post-conversion unit 16, and a storage unit 18.
  • the unit conversion unit 22 and the validity verification unit 24 are further included.
  • step S20 the randomizing unit 20 included in the k random replacement devices 1 ⁇ 0 converts the stored (k, n) -secret shared value [a] pi into a randomized distributed value.
  • the public value a is stored in the storage unit 18, the public value a is converted into (k, n) -secret shared value [a] pi and then converted into a randomized distributed value.
  • the randomized variance value is a set of a variance value [a] pi of a value a ⁇ R and a variance value [ar] pi of an integrated value ar of a value a ⁇ R and a random number r ⁇ A ([a] pi , [ar] pi ).
  • R is a ring
  • A is a bonded multiple ring on the ring R.
  • a bond multiple ring is a bond ring and has a structure of a linear space on the body that is compatible with the ring. It can be said that the combined multi-ring is that the value handled in the vector space is not a field but a ring.
  • the 0th component ([a] pi ) of the randomized variance value is also called the R component, and the first component ([ar] pi ) is also called the A component.
  • the random number used when generating the randomized sharing value converts the sharing value for one secret sharing into the sharing value for the other secret sharing.
  • the random numbers are generated so as to have the same value.
  • alteration detection must be possible or impossible.
  • the above-mentioned reference 2 describes a method that cannot be tampered with to convert from replicated secret sharing to linear secret sharing.
  • step S22 the unit conversion unit 22 included in the k random replacement devices 1 ⁇ i performs randomized distribution by using (k, n) -secret sharing for the additive secret sharing value ⁇ a >> ⁇ i replaced by the unit replacing unit 12 It is converted into a value and accumulated in the storage unit 18.
  • the stored randomized variance value is used for calculating a checksum in the correctness proving unit 24 described later.
  • the accumulation of randomized variance values is not necessarily performed after all unit replacements, but may be performed only at the time of partial unit replacements.
  • step S24 the validity proving unit 24 executes a synchronization process (SYNC) that waits until all secret calculations are completed for all secret sharing.
  • SYNC a synchronization process
  • the dispersion value after conversion [phi alpha] with the checksum C variance value calculated in the same manner from beta [phi beta] and summed dispersion value and [ ⁇ ⁇ + ⁇ ⁇ ]] the dispersion value after conversion [[psi alpha ]
  • the dispersion value [ ⁇ ] ([ ⁇ ⁇ ] + [ ⁇ ⁇ ])-([ ⁇ ⁇ ] + [ ⁇ ⁇ ]) is restored, and if the restored value ⁇ is 0, it is determined that no alteration has occurred.
  • step S16 the posterior conversion unit 16 converts the additive secret sharing value into a (k, n) -secret sharing value or a public value.
  • the additive secret sharing value ⁇ a >> ⁇ N ⁇ 1 after the last replacement process is transmitted to the random replacement device 1 p , and the random replacement device 1
  • the p is constructed to obtain the public value a by the method of restoring additive secret sharing.
  • the additive secret sharing value is once converted into (k, n) -secret sharing value, and then the public value is obtained by the (k, n) -secret sharing restoration method. Configure to get a.
  • the random replacement device 1 p receives the (k, n) -secret sharing value obtained by converting the form of the additive secret sharing value ⁇ a >> ⁇ N-1 from any k ⁇ 1 random replacement devices. Further, the remaining nk random replacement devices receive a checksum such as a hash value of (k, n) -secret sharing value obtained by format-converting the additive secret sharing value ⁇ a >> ⁇ N-1 .
  • the checksum does not have to be a hash value, and a safer information-theoretic checksum can be used.
  • An information-theoretic checksum is, for example, a set of random numbers r and a i r i + 1 where a checksum calculation target is a i .
  • the random permutation apparatus 1 p restores nk (k, n) -secret sharing values from k (k, n) -secret sharing values obtained by adding its own (k, n) -secret sharing values.
  • the checksum is calculated from each restored (k, n) -secret sharing value. Note that recovery is a method to reconstruct nk distributed values that have become unusable from k available distributed values without losing confidentiality when some distributed values are lost. .
  • the random replacement device 1 p matches the checksum of the (k, n) -secret sharing value received from the nk random replacement devices with the checksum of the restored (k, n) -secret sharing value. Confirm whether or not to do. If all checksums match, it is determined that there has been no tampering, and (k, n) -secret sharing value or public value is output. If any of the checksums is different, it is determined that the falsification has occurred, and information indicating that (for example, “ ⁇ ”) is output.
  • tampering detection is possible in the secret random replacement of the present invention, and safety is improved.
  • the first viewpoint is the viewpoint of the input / output type. From this viewpoint, four configuration methods are conceivable.
  • the first configuration is a case where the input is a linear secret sharing value and the output is a linear secret sharing value.
  • the second configuration is when the input is a linear secret sharing value and the output is a duplicate secret sharing value, or vice versa, when the input is a replica secret sharing value and the output is a linear secret sharing value.
  • the third configuration is a case where the input is a public value and the output is a secret sharing value.
  • the fourth configuration is a case where the input is a linear secret sharing value and the output is a public value.
  • the second viewpoint is a random number generation method. From this viewpoint, two configuration methods are conceivable.
  • the first configuration is a case of pseudo-random numbers generated from seeds in which random numbers are shared in advance.
  • the second configuration is a case where random numbers are shared during protocol execution.
  • the third point of view is the type of random substitution. From this viewpoint, two configuration methods are conceivable.
  • the first configuration is a case where replacement data is arbitrary, and a case where it is desired to shuffle completely randomly.
  • the fourth point of view is a point of view of a specific example of iterative substitution with k and n limited.
  • the vertical axis represents the party
  • the horizontal axis represents the number of unit replacements.
  • a circle indicates a party that performs processing in unit replacement.
  • the solid arrow indicates the direction of the party to which the secret sharing value is transmitted in the re-distribution. Dotted arrows indicate that the same party continues to hold the secret sharing value during redistribution.
  • FIG. 6 the vertical axis represents the party, and the horizontal axis represents the number of unit replacements.
  • a circle indicates a party that performs processing in unit replacement.
  • the solid arrow indicates the direction of the party to which the secret sharing value is transmitted in the re-distribution. Dotted arrows indicate that the same party continues to hold the secret sharing value during redistribution.
  • the parties p 0 and p 1 perform processing, and in the first redistribution, the secret sharing value is transmitted from the party p 0 to the party p 2 .
  • the parties p 1 and p 2 perform processing, and in the second redistribution, the secret sharing value is transmitted from the party p 1 to the party p 0 .
  • the parties p 0 and p 2 perform processing, and the repeated replacement is completed.
  • the repeated replacement of this specific example will be described.
  • the notation of the figure is the same as in FIG.
  • the parties p 0 , p 1 and p 2 perform processing, and in the first redistribution, the secret sharing value is transmitted from the party p 0 to the party p 3 .
  • the parties p 1 , p 2 , and p 3 perform processing, and in the second redistribution, the secret sharing value is transmitted from the party p 1 to the party p 4 .
  • the parties p 2 , p 3 , and p 4 perform processing, and in the third redistribution, the secret sharing value is transmitted from the party p 2 to the party p 0 .
  • the parties p 0 , p 3 and p 4 perform processing, and in the fourth redistribution, the secret sharing value is transmitted from the party p 3 to the party p 1 .
  • the secret sharing value transmitted from the party p 3 to the party p 1 is the secret sharing value transmitted from the party p 0 to the party p 3 in the first re-distribution, before the fifth re-distribution.
  • Party p 1 waits for reception. Therefore, it becomes the first stage of communication until the fourth redistribution. Thereafter, the replacement and redistribution are repeated in the same manner, and in this specific example, the repeated replacement is completed with three communication stages.
  • the repeated replacement of this specific example will be described.
  • the notation of the figure is the same as in FIG.
  • the first and second unit replacement only the party p 0 performs processing. This unit substitution may be simply repeated twice, or two substitutions may be performed together.
  • the secret sharing value is transmitted from the party p 0 to the parties p 1 and p 2 .
  • the parties p 1 and p 2 perform processing, and the repeated replacement is completed.
  • the repeated replacement of this specific example will be described.
  • the notation of the figure is the same as in FIG. In the example of FIG.
  • the secret sharing value is transmitted from the party p 0 to the parties p 2 , p 3 , and p 4 .
  • the parties p 2 , p 3 , and p 4 perform processing, and in the seventh redistribution, the secret sharing value is transmitted from the party p 2 to the party p 1 .
  • the parties p 1 , p 3 and p 4 perform processing, and in the eighth redistribution, the secret sharing value is transmitted from the party p 3 to the party p 2 .
  • the parties p 1 , p 2 , and p 4 perform processing, and in the ninth redistribution, the secret sharing value is transmitted from the party p 4 to the party p 3 .
  • the parties p 1 , p 2 , and p 3 perform processing, and the repeated replacement is completed. As shown in FIG. 7, in this specific example, the repeated replacement is completed with two communication stages.
  • the repeated replacement of this specific example will be described.
  • the notation of the figure is the same as in FIG.
  • the parties p 1 and p 2 perform processing, and the secret sharing value is transmitted from the parties p 1 and p 2 to the party p 0 .
  • Party p 0 restores the secret sharing value and performs the second and third unit replacement. This unit substitution may be simply repeated twice, or two substitutions may be performed together. This completes the repeated replacement.
  • the repeated replacement of this specific example will be described.
  • the notation of the figure is the same as in FIG.
  • the secret sharing value is transmitted to p 0 .
  • Party p 0 restores the secret sharing value and performs unit replacement from the fifth time to the tenth time. This unit substitution may be simply repeated six times, or six substitutions may be performed together. This completes the repeated replacement.
  • the program describing the processing contents can be recorded on a computer-readable recording medium.
  • a computer-readable recording medium any recording medium such as a magnetic recording device, an optical disk, a magneto-optical recording medium, and a semiconductor memory may be used.
  • 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 a program stored in its own recording medium and executes a 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)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Computer Security & Cryptography (AREA)
  • General Physics & Mathematics (AREA)
  • Signal Processing (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • General Health & Medical Sciences (AREA)
  • Computer Hardware Design (AREA)
  • Software Systems (AREA)
  • Bioethics (AREA)
  • General Engineering & Computer Science (AREA)
  • Health & Medical Sciences (AREA)
  • Storage Device Security (AREA)

Abstract

　秘密ランダム置換が含まれる秘密計算を高速に行う。単位置換ステップＳ１２は、ランダム置換装置p0,…,pk-1が、平文aの加法的秘密分散値≪a≫ρiを置換データπのサブシェアπρiにより置換する。再分散ステップＳ１４は、ランダム置換装置p0が、ランダム置換装置pj（j=1,…,k-1）それぞれと共有する乱数r1,…,rk-1を用いて加法的秘密分散値≪a≫ρi+1 pkを生成してランダム置換装置pkへ送信し、ランダム置換装置pjそれぞれが乱数rjを用いて加法的秘密分散値≪a≫ρi+1 pjを生成する。

Description

秘密計算方法、秘密計算システム、ランダム置換装置及びプログラム
　この発明は、秘密計算技術に関し、特に、秘密ランダム置換を行う技術に関する。
　秘密計算とは、秘密分散によりデータを秘匿しつつデータ処理を行う技術である。秘密分散は、データを複数の分散値に変換し、一定個数以上の分散値を用いれば元のデータを復元でき、一定個数未満の分散値からは元のデータを一切復元できなくする技術である。秘密分散はいくつかの種類に分類でき、例えば、(k,n)-秘密分散、加法的秘密分散、置換データ秘密分散などがある。
　(k,n)-秘密分散とは、入力された平文をn個のシェアに分割し、n個のパーティP=(p0,…,pn-1)に分散しておき、任意のk個のシェアが揃えば平文を復元でき、k個未満のシェアからは平文に関する一切の情報を得られないような秘密分散である。(k,n)-秘密分散の具体的な方式には、例えば、Shamir秘密分散、複製秘密分散などがある。
　加法的秘密分散とは、複製秘密分散による(k,k)-秘密分散である。(k,k)-秘密分散とは、(k,n)-秘密分散において、n=kとした場合である。(k,k)-秘密分散では、全パーティのシェアが集まらない限り平文を復元することはできない。加法的秘密分散は、k個のシェアを加算するだけで平文が復元される最もシンプルな秘密分散である。
　置換データ秘密分散は、置換データを秘匿して行う秘密分散である。置換データとは、データ列を並び替えるときの並び替え方を表すデータである。m個のデータ列を並び替えるとき、大きさmの置換データπは全単射写像π:Nm→Nmを表すデータである。ただし、任意の整数mに対して、Nmはm未満の非負整数の集合である。例えば、ベクトルx→∈(Nm)mで各要素が互いに異なるデータは大きさmのランダム置換データと見なせる。
　より具体的には、ベクトルx→=(3,0,2,1)を大きさ4のランダム置換データと見なすことができる。例えば、データ列y→=(1,5,7,10)をベクトルx→によって並び替えるとする。データ列y→の0番目の要素である1を、ベクトルx→の0番目の要素が示す3番目に移動する。データ列y→の1番目の要素である5を、ベクトルx→の1番目の要素が示す0番目に移動する。同様に、7を2番目に移動し、10を1番目に移動する。結果として、置換後のデータ列z→=(5,10,7,1)が得られる。
　置換データ秘密分散は、以下の手順により置換データを秘匿する。N個のkパーティ組の列Ρ=ρ0,…,ρN-1があるとする。例えば、k=2のとき、各kパーティ組ρiは、パーティp0とパーティp1の組(p0,p1)や、パーティp0とパーティp2の組(p0,p2)などである。各kパーティ組ρi内の全パーティが互いに置換データπρiを共有し、補集合ρ￣ iには知らさないものとする。そして、対応する平文をπ0(π1(…(πN-1(I))…))とする。ただし、Iは入力と同じ並びでそのまま出力する置換、つまり恒等置換である。このとき、kパーティ組の列Ρ=ρ0,…,ρN-1を、「（条件１）任意のk-1パーティ組ρに対して、いずれかの補集合ρ￣ iがρ⊆ρ￣ iを満たす」ように設定すれば、どのようにk-1パーティが結託しても、いずれかの置換データπρiを知らないことになる。
　例えば、パーティ数nがn≧2k-1を満たすとき、kパーティ組の列Ρをすべてのkパーティ組を含む集合とすれば上記の条件１を満たす。また、パーティ数nがn>2k-1を満たすときは、すべてのkパーティ組を含まなくても上記の条件１が実現されることがある。例えば、k=2, n=4のとき、{(p0,p1),(p2,p3)}はすべてのkパーティ組を含みはしないが条件１を満たす。
　秘密ランダム置換とは、どのような順番に置換したのかを処理実行者にもわからないように、入力されたデータ列をランダムに置換する技術である。秘密ランダム置換を行う従来技術として非特許文献１に記載の技術がある。
　非特許文献１に記載の秘密ランダム置換の基本形は、(k,n)-秘密分散値の列[a→]を入力とし、置換データ秘密分散値<π>を生成し、(k,n)-秘密分散値の列[b→]=([aπ(0)],…,[aπ(m-1)])を出力する。このとき、置換データ秘密分散値<π>の平文π、つまりデータ列をどのような順序で入れ替えたのかがいずれのパーティにもわからないことが特徴である。具体的な処理としては、置換データ秘密分散の各サブシェアπρiに対して、kパーティ集合ρiに属するパーティp∈ρiが秘密計算ではない通常の置換処理により、入力[a→]=([a0],…,[am-1])から([aπρi(0)],…,[aπρi(m-1)])を生成し、これを再分散と呼ばれる処理により秘密分散し直すことを繰り返す。
　秘密ランダム置換は入出力の型の違いから以下の三種類が考えられる。一つ目は、入力も出力も(k,n)-秘密分散値である場合である。二つ目は、入力が(k,n)-秘密分散値であり、出力は公開値の場合である。三つ目は、入力が公開値であり、出力は(k,n)-秘密分散値の場合である。入力が公開値の場合、公開値を秘密分散して秘密分散値としてから上記の基本形の処理を行う。また、出力が公開値の場合、上記の基本形の処理を行った後に公開処理を行う。公開値とは全パーティが知っている値である。公開処理とは、例えば、全パーティが自身のシェアを他の全パーティに送信し、全パーティが受信したシェアから秘密分散の復元を行うことである。
濱田浩気、五十嵐大、千田浩司、高橋克巳、"3パーティ秘匿関数計算のランダム置換プロトコル"、コンピュータセキュリティシンポジウム2010、2010年
　非特許文献１に記載の秘密ランダム置換は、(k,n)-秘密分散値を用いて置換と再分散の処理を繰り返す。(k,n)-秘密分散値を再分散するためには、各パーティが全パーティと相互に通信を行わなければならず、通信量及び通信段数が大きいという問題がある。
　この発明の目的は、秘密ランダム置換に要する通信量及び通信段数を低減し、秘密ランダム置換が含まれる秘密計算を高速に行うことである。
　上記の課題を解決するために、この発明の秘密計算方法は、n,kを2以上の整数とし、n>kとし、N=nCkとし、ρをn台のランダム置換装置から選択したk台のランダム置換装置の組とし、ρ0,…,ρN-1はi=0,…,N-2について|ρi＼ρi+1|=1となるように構成されており、≪a≫ρiをi番目のランダム置換装置の組ρiが保持する平文aの加法的秘密分散値とし、≪a≫ρi pを加法的秘密分散値≪a≫ρiのうちランダム置換装置pが保持する加法的秘密分散値とし、πρiをi番目のランダム置換装置の組ρiに対応する置換データπのサブシェアとし、ランダム置換装置p0をi番目のランダム置換装置の組ρiに含まれi+1番目のランダム置換装置の組ρi+1に含まれないランダム置換装置とし、ランダム置換装置pkをi番目のランダム置換装置の組ρiに含まれずi+1番目のランダム置換装置の組ρi+1に含まれるランダム置換装置とし、ランダム置換装置pj（j=1,…,k-1）をi番目のランダム置換装置の組ρi及びi+1番目のランダム置換装置の組ρi+1のいずれにも含まれるk-1台のランダム置換装置として、ランダム置換装置p0,…,pk-1が、加法的秘密分散値≪a≫ρiをサブシェアπρiにより置換する単位置換ステップと、ランダム置換装置p0が、ランダム置換装置p1,…,pk-1と共有する乱数r1,…,rk-1を用いて加法的秘密分散値≪a≫ρi+1 pkを生成してランダム置換装置pkへ送信し、ランダム置換装置pjそれぞれが乱数rjを用いて加法的秘密分散値≪a≫ρi+1 pjを生成する再分散ステップと、を含む。
　この発明の秘密計算技術によれば、秘密ランダム置換を行う際の通信量及び通信段数を低減することができる。したがって、秘密ランダム置換が含まれる秘密計算を高速に実行できる。
図１は、秘密計算システムの機能構成を例示する図である。 図２は、第一実施形態のランダム置換装置の機能構成を例示する図である。 図３は、第一実施形態の秘密計算方法の処理フローを例示する図である。 図４は、第二実施形態の秘密計算方法の処理フローを例示する図である。 図５は、第三実施形態の秘密計算方法の処理フローを例示する図である。 図６は、第四実施形態のランダム置換装置の機能構成を例示する図である。 図７は、第四実施形態の秘密計算方法の処理フローを例示する図である。 図８は、第一実施形態におけるk=2,n=3の具体例を示す図である。 図９は、第一実施形態におけるk=3,n=5の具体例を示す図である。 図１０は、第二実施形態におけるk=2,n=3の具体例を示す図である。 図１１は、第二実施形態におけるk=3,n=5の具体例を示す図である。 図１２は、第三実施形態におけるk=2,n=3の具体例を示す図である。 図１３は、第三実施形態におけるk=3,n=5の具体例を示す図である。
　実施形態の説明に先立ち、この明細書で用いる表記方法及び用語を定義する。
［表記方法］
　pは、シェアを所持するパーティを表す。
　P=(p0,…,pn-1)は、シェアを所持するnパーティ全体の集合を表す。
　ρ=(p0,…,pk-1)は、置換処理を実行するkパーティ組の集合を表す。
　Ρ=(ρ0,…,ρN-1)は、各置換処理を実行するkパーティ組の順番を表す。ただし、N=nCkは、置換処理の実行回数であり、nパーティからkパーティを選択するすべての組み合わせの数である。
　[x]は、平文x∈Gの(k,n)-秘密分散値を表す。ここで、Gは可換群である。(k,n)-秘密分散値とは、平文xを(k,n)-秘密分散で分散したシェアすべてを集めた組である。秘密分散値[x]は、普段はnパーティ集合Pに分散されて所持されているため、一か所ですべてを所持されることはなく、仮想的である。
　[x]pは、(k,n)-秘密分散値[x]のうち、パーティp∈Pが所持するシェアを表す。
　[x→]は、平文の列がx→となる(k,n)-秘密分散値の列を表す。
　[G]は、可換群G上の(k,n)-秘密分散値全体の集合を表す。
　≪x≫ρは、平文x∈Gの加法的秘密分散値で、kパーティ組ρがシェアを所持するものを表す。加法的秘密分散値とは、平文xを加法的秘密分散で分散したシェアすべてを集めた組を表す。
　≪x≫ρ pは、加法的秘密分散値≪x≫ρのうち、パーティp∈ρが所持するシェアを表す。
　≪x→≫ρは、平文の列がx→となる加法的秘密分散値の列を表す。
　≪G≫ρは、可換群G上の加法的秘密分散値全体の集合を表す。
　<π>は、置換データπの置換データ秘密分散値を表す。
　Πは、大きさmの置換データ全体の集合を表す。
　<Π>は、大きさmの置換データ秘密分散値全体の集合を表す。
［発明のポイント］
　この発明の秘密ランダム置換の概要は以下の通りである。
ステップ１．入力を(k,n)-秘密分散値または公開値から加法的秘密分散値に変換する。
ステップ２．加法的秘密分散値上で、シェアを持つkパーティ集合ρに属する各パーティが置換データ秘密分散値<π>のサブシェアπρによる通常の置換を行い、再分散することを繰り返す。ただし、最終回は再分散しない。以下、反復の一回を単位置換と呼び、繰り返す処理全体を反復置換と呼ぶ。
ステップ３．出力を加法的秘密分散値から(k,n)-秘密分散値または公開値に変換する。
　ステップ１及びステップ３は、既存の手法を適用できる。以下では、ステップ２の処理におけるポイントについて説明する。
＜単位置換＞
　単位置換におけるポイントは、i回目の単位置換で、|ρi＼ρi+1|=1となるようにkパーティ集合ρiを選択することである。つまり、i回目の単位置換を行うkパーティ集合ρiと、i+1回目の単位置換を行うkパーティ集合ρi+1とでは、1パーティだけが異なり残りのk-1パーティは同じパーティということである。このような単位置換を、パーティが一つしか異ならない場合であることから、1-加法的再分散プロトコルと呼ぶ。
　非特許文献１に記載の秘密ランダム置換における再分散では、(n-1)(k-1)個のG要素の通信量を要する。一方、1-加法的再分散プロトコルでは、k-1個のG要素の通信量で済む。特に、シードを予め共有して疑似乱数を共有すれば、通信量は1個のG要素の通信量で済む。この場合は、通信量が定数となり、非常に効率的である。
　1-加法的再分散プロトコルは、入力をkパーティ組ρ=p0,…,pk-1が所持する秘密分散値≪a≫ρ∈≪G≫ρとし、以下の手順でデータ処理を行い、他のkパーティ組ρ’=p1,…,pkが所持する秘密分散値≪a≫ρ’∈≪G≫ρ’を出力する。ただし、パーティの役割は適切に変更されるものとする。
　まず、パーティp0は、i=1,…,k-1について、パーティpiと乱数ri∈Gを共有する。次に、パーティp0は、次式により秘密分散値≪a≫ρ' pkを計算して、パーティpkに送信する。パーティpkは、受信した≪a≫ρ' pkを出力する。
Figure JPOXMLDOC01-appb-M000003
　続いて、パーティpi（i=1,…,k-1）は、次式により秘密分散値≪a≫ρ' piを計算して出力する。
Figure JPOXMLDOC01-appb-M000004
＜反復置換の中の単位置換の並列化＞
　反復置換は、置換→再分散→置換→再分散→…→置換という繰り返しであり、置換をN回、再分散をN-1回実行する。これを単純に行うと、通信の段数はそのまま再分散の回数であり、N-1段となる。しかし、1-加法的再分散プロトコルによる単位置換は、通信に関して並列化することができる。データ受信を待つパーティが1パーティ、すなわち前回の単位置換に参加していないパーティだけだからであり、他のパーティは何らのデータ受信を待つことなく、オフライン処理だけを実行して次の単位置換処理に移行できるからである。加法的秘密分散のシェアはk個であるから、kパーティ組の順番Ρを適切に設定すれば、最大k回の単位置換を1段で実行することができる。これにより、通信段数を(N-1)/k段に低減することができる。
　kパーティ組の順番Ρは、任意のi<kについて、パーティpiからの経路の通信段数が互いに等しいか、最大値と最小値の差が最も小さい順番にすることで、通信段数を効率化することができる。
　パーティpiからの経路とは、長さLのkパーティ組の列Ρ=(ρ0,…,ρL-1)に対して、パーティの列(pj0,pj1,…,pjL-1)であって、次式により帰納的に定められる列である。
Figure JPOXMLDOC01-appb-M000005
　経路の通信段数とは、経路の中でパーティが変化することで通信が必要となるλの数、すなわち|{λ∈NL|pjλ≠pjλ+1}|である。1-加法的再分散プロトコルの通信では、パーティpkがパーティp0からの送信を待つ以外は乱数の通信であり、前段の再分散の結果に依存していない。経路の通信段数は、このパーティp0からパーティpkの通信のうち直列に並んでおり並列に実行できない段数を表している。反復置換全体の通信段数は、次式に示すとおりであるため、各経路の通信段数が均等になっていると効率的である。
Figure JPOXMLDOC01-appb-M000006
　以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
［第一実施形態］
　図１を参照して、第一実施形態に係る秘密計算システムの構成例を説明する。秘密計算システムは、n（≧2）台のランダム置換装置１1,…,１nとネットワーク９を含む。ランダム置換装置１1,…,１nはネットワーク９にそれぞれ接続される。ネットワーク９はランダム置換装置１1,…,１nそれぞれが相互に通信可能なように構成されていればよく、例えばインターネットやＬＡＮ、ＷＡＮなどで構成することができる。また、ランダム置換装置１1,…,１nそれぞれは必ずしもネットワーク９を介してオンラインで通信可能である必要はない。例えば、あるランダム置換装置１i（1≦i≦n）が出力する情報をＵＳＢメモリなどの可搬型記録媒体に記憶し、その可搬型記録媒体から異なるランダム置換装置１j（1≦j≦n、i≠j）へオフラインで入力するように構成してもよい。
　図２を参照して、秘密計算システムに含まれるランダム置換装置１の構成例を説明する。ランダム置換装置１は、事前変換部１０、単位置換部１２、再分散部１４、事後変換部１６及び記憶部１８を含む。ランダム置換装置１は、例えば、中央演算処理装置（Central Processing Unit、ＣＰＵ）、主記憶装置（Random Access Memory、ＲＡＭ）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。ランダム置換装置１は、例えば、中央演算処理装置の制御のもとで各処理を実行する。ランダム置換装置１に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて読み出されて他の処理に利用される。ランダム置換装置１が備える記憶部１８は、例えば、ＲＡＭ（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリ（Flash Memory）のような半導体メモリ素子により構成される補助記憶装置、またはリレーショナルデータベースやキーバリューストアなどのミドルウェアにより構成することができる。
　パーティpに対応するランダム置換装置１pが備える記憶部１８には、平文aの(k,n)-秘密分散値[a]pもしくは公開値a、パーティpが含まれるkパーティの組ρに対応する置換データπのサブシェアπρ及びN×k個のシードs0,1,…,sN-1,kが記憶されている。なお、シードs0,1,…,sN-1,kは、後述する再分散部１４の処理において乱数を生成する際に通信無しで行うために予め記憶しておくものであるが、都度協調して乱数生成を行う場合には記憶していなくても構わない。
　図３を参照しながら、第一実施形態に係る秘密計算システムが実行する秘密計算方法の処理フローの一例を、実際に行われる手続きの順に従って説明する。
　ステップＳ１０において、k台のランダム置換装置１ρ0が備える事前変換部１０は、記憶部１８に記憶されている(k,n)-秘密分散値[a]piもしくは公開値aを加法的秘密分散値≪a≫ρ0へ変換する。ρ0はkパーティ組の列Ρ=(ρ0,…,ρN-1)の0番目の要素であり、ランダム置換装置１ρ0は、ρ0=(p0,…,pk-1)に対応するk台のランダム置換装置１p0,…,１pk-1である。
　(k,n)-秘密分散値もしくは公開値から加法的秘密分散値へ変換する方法は、既知の方法により行えばよい。
　入力が公開値である場合、加法的秘密分散値への変換は、例えば以下のように行うことができる。ρをk台のランダム置換装置１p0,…,１pk-1の組とし、a∈Gを入力された公開値とし、ランダム置換装置１p0が公開値aを知っているとする。公開値aから加法的秘密分散値≪a≫ρへの変換は、i=0,…,k-1について、次式により行えばよい。
Figure JPOXMLDOC01-appb-M000007
　入力が(k,n)-秘密分散値である場合、加法的秘密分散値への変換は、例えば下記の参考文献１及び参考文献２に記載された方法により行うことができる。参考文献１には、Shamir秘密分散を含む線形秘密分散から加法的秘密分散へ通信無しで変換する方法が記述されている。参考文献２には、複製秘密分散から線形秘密分散へ通信無しで変換する方法が記述されているため、複製秘密分散から加法的秘密分散への変換は、参考文献２に記載の方法と参考文献１に記載の方法を組み合わせることで通信無しで実現される。
〔参考文献１〕五十嵐大、濱田浩気、菊池亮、千田浩司、“少パーティの秘密分散ベース秘密計算のためのO(l)ビット通信ビット分解およびO(|p'|)ビット通信Modulus変換法”、コンピュータセキュリティシンポジウム2013、2013年
〔参考文献２〕R. Cramer, I. Damgard, and Y. Ishai, “Share conversion, pseudorandom secret-sharing and applications to secure computation”, TCC 2005, Vol. 3378 of Lecture Notes in Computer Science, pp. 342-362, 2005.
　ステップＳ１ａにおいて、k台のランダム置換装置１ρ0は、置換処理の実行回数を表すカウンタiを0に初期化する。
　ステップＳ１２において、k台のランダム置換装置１ρiが備える単位置換部１２は、記憶部１８に記憶されている置換データのサブシェアπρiを用いて加法的秘密分散値≪a≫ρiを置換する。ρiはkパーティ組の列Ρ=(ρ0,…,ρN-1)のi番目の要素であり、ランダム置換装置１ρiは、ρi=(p0,…,pk-1)に対応するk台のランダム置換装置１p0,…,１pk-1である。置換の方法は、従来の置換データ秘密分散の方法により行えばよい。
　ステップＳ１ｂにおいて、k台のランダム置換装置１ρiは、所定回数の置換処理が実行されたか否かを判定する。具体的には、N=nCkを単位置換の総実行回数として、カウンタiの値がN-1に達したか否かを判定する。i<N-1であれば、ステップＳ１４へ処理を進める。i≧N-1であれば、ステップＳ１６へ処理を進める。
　ステップＳ１４において、k台のランダム置換装置１ρi+1が備える再分散部１４は、1-加法的再分散プロトコルにより加法的秘密分散値≪a≫ρiの再分散を行う。以下、ランダム置換装置１p0を、ランダム置換装置１ρiに含まれてランダム置換装置１ρi+1には含まれないランダム置換装置とし、ランダム置換装置１pkを、ランダム置換装置１ρiに含まれずランダム置換装置１ρi+1に含まれるランダム置換装置とする。また、ランダム置換装置１pj（j=1,…,k-1）を、ランダム置換装置１pkを除くランダム置換装置１ρi+1に含まれるk-1台のランダム置換装置を表すものとする。
　まず、ランダム置換装置１ρi+1が備える再分散部１４は、k個の乱数r1,…,rk∈Gを生成する。乱数r1,…,rkは、k台のランダム置換装置１ρi+1が協調して共有の乱数r1,…,rkを生成してもよいし、記憶部１８に記憶されているシードsi,1,…,si,kを用いて疑似乱数r1,…,rkを生成してもよい。予め共有したシードsi,1,…,si,kを用いて疑似乱数を生成すればランダム置換装置間の通信無く乱数生成ができるので非常に効率的である。
　次に、ランダム置換装置１p0が備える再分散部１４は、ランダム置換装置１pkのための加法的秘密分散値≪a≫ρi+1 pkを、加法的秘密分散値≪a≫ρi p0及び乱数r0,…,rk-1を用いて次式により生成し、ランダム置換装置１pkへ送信する。
Figure JPOXMLDOC01-appb-M000008
　そして、ランダム置換装置１pjが備える再分散部１４は、加法的秘密分散値≪a≫ρi pj及び乱数rjを用いて、加法的秘密分散値≪a≫ρi+1 pjを、次式により生成する。
Figure JPOXMLDOC01-appb-M000009
　ステップＳ１ｃにおいて、k台のランダム置換装置１ρi+1は、置換処理の実行回数を表すカウンタiへ1を加算する。以降、ステップＳ１ｂにおいてカウンタiがN-1に達したと判定されるまで、ステップＳ１２の単位置換とステップＳ１４の再分散を繰り返す。
　ステップＳ１６において、k台のランダム置換装置１ρN-1が備える事後変換部１６は、加法的秘密分散値を(k,n)-秘密分散値もしくは公開値へ変換する。加法的秘密分散値から他の形式へ変換する方法は、比較的軽量に行うことができる。なお、下記の変換方法は一例であり、他の変換方法では適用できないということを意味するものではない。
　出力が公開値である場合、出力を得たいランダム置換装置１p（1≦p≦n）に対して、最後に置換処理を実行したk台のランダム置換装置１ρN-1が加法的秘密分散値≪a≫ρN-1 pj（j=0,…,k-1）を送信し、ランダム置換装置１pが復元を行う方法がある。その他に、出力を得たい複数台のランダム置換装置１ρ（ρ⊆{1,…,n}）から選択した一台のランダム置換装置１p（p∈ρ）に対して、最後に置換処理を実行したk台のランダム置換装置１ρN-1が加法的秘密分散値≪a≫ρN-1 pj(j=0,…,k-1）を送信し、ランダム置換装置１pが復元を行い、他のランダム置換装置１ρへ復元結果を送信する方法もある。
　出力が(k,n)-秘密分散値である場合、線形秘密分散、複製秘密分散など加法準同型性を持つ、つまり秘密分散値上で通信無しで加法を行える秘密分散に対しては、例えば、以下の手順により変換することができる。まず、k台のランダム置換装置１ρN-1は変換先の(k,n)-秘密分散によって加法的秘密分散値≪a≫ρN-1 pjを秘密分散し、n台のランダム置換装置１Pへ(k,n)-秘密分散値[≪a≫ρN-1 pj]p（p=1,…,n）を配信する。そして、n台のランダム置換装置１Pは受信したk個の(k,n)-秘密分散値[≪a≫ρN-1 pj]pをすべて加算する。
　このように、第一実施形態の秘密計算システムは、入力を加法的秘密分散値に変換することで、再分散の処理における通信量を低減させることができ、従来のランダム置換よりも効率的に処理を行うことが可能である。
［第二実施形態］
　秘密ランダム置換の入力が公開値である場合には第一実施形態よりもさらに効率化することができる。非特許文献１や第一実施形態の方法でランダム置換の置換データを秘密にするためには、任意のk-1パーティ組ρに対して、いずれかの補集合ρ￣ iがρ⊆ρ￣ iを満たすようなkパーティ組の列Ρの要素数だけ、単位置換を行う必要がある。しかし、あるパーティpがもつ公開値が入力の場合、もっと少ない回数の単位置換でよい。入力が公開値であるため、最初はパーティpが1パーティで置換を行うことができ、パーティpが知っている分の置換をすべてまとめて行うことができるからである。
　少なくとも1台のランダム置換装置１p0が備える記憶部１８には、公開値aが記憶されている。公開値aは少なくとも1台が所持していればよく、何台のランダム置換装置が所持していても構わない。
　ランダム置換装置１p0を除くn-1台のランダム置換装置１p1,…,１pn-1が備える記憶部１８には、パーティpiが含まれるkパーティの組ρiに対応する置換データπのサブシェアπρi及びN×k個のシードs0,1,…,sN-1,kが記憶されているものとする。ただし、Nはn-1Ckである。第一実施形態と同様に、シードs0,1,…,sN-1,kは必ずしも記憶していなくても構わない。
　図４を参照しながら、第二実施形態に係る秘密計算システムが実行する秘密計算方法の処理フローの一例を、実際に行われる手続きの順に従って説明する。
　ステップＳ１２p0において、ランダム置換装置１p0が備える単位置換部１２は、ランダムな置換データπを生成し、置換データπにより公開値aを置換する。置換の方法は、従来の置換方法と同様である。
　ステップＳ１０p0において、ランダム置換装置１p0が備える事前変換部１０は、置換後の公開値aを加法的秘密分散値≪a≫ρ-1へ変換する。変換の方法は、第一実施形態のステップＳ１０と同様である。加法的秘密分散値≪a≫ρ-1は、ランダム置換装置１ρ0のうち、任意に選択したk-1台に配信される。ここでは、ランダム置換装置１p1,…,１pk-1に配信されたものとする。
　ステップＳ１４p0において、k台のランダム置換装置１ρ0が備える再分散部１４は、1-加法的再分散プロトコルにより加法的秘密分散値≪a≫ρ-1の再分散を行う。再分散の方法は、第一実施形態のステップＳ１４と同様である。
　以降、ランダム置換装置１p0を除くn-1台のランダム置換装置１p1,…,１pn-1により、ステップＳ１ａからＳ１６までの処理を実行する。
　このように、第二実施形態の秘密計算システムでは、1台のランダム置換装置によりまとめて置換を行った後にn-1台のランダム置換装置によりランダム置換を行うため、置換処理の回数がn-1Ck+1となり、第一実施形態の秘密計算システムよりも効率的に処理を行うことが可能である。
［第三実施形態］
　秘密ランダム置換の入力が公開値の場合と同様に、秘密ランダム置換の出力が公開値の場合にも、第一実施形態よりもさらに効率化ができる。出力が公開値であるため、n-1パーティがランダム置換を行った後に、残りの1パーティに秘密分散値を送信し、復元した公開値に対してまとめて置換を行うことができるからである。
　ランダム置換装置１p0を除くn-1台のランダム置換装置１p1,…,１pn-1が備える記憶部１８には、パーティpiが含まれるkパーティの組ρiに対応する置換データπのサブシェアπρi及びN×k個のシードs0,1,…,sN-1,kが記憶されているものとする。ただし、Nはn-1Ckである。第一実施形態と同様に、シードs0,1,…,sN-1,kは必ずしも記憶していなくても構わない。
　図５を参照しながら、第三実施形態に係る秘密計算システムが実行する秘密計算方法の処理フローの一例を、実際に行われる手続きの順に従って説明する。
　ステップＳ１０からＳ１ｂにおいてi≧N-1と判定されるまでの処理を、ランダム置換装置１p0を除くn-1台のランダム置換装置１p1,…,１pn-1により実行する。
　ステップＳ１６p0において、ランダム置換装置１p0が備える事後変換部１６は、加法的秘密分散値を公開値へ変換する。変換の方法は第一実施形態のステップＳ１６と同様である。具体的には、ランダム置換装置１p0に対して、最後に置換処理を実行したk台のランダム置換装置１ρN-1が加法的秘密分散値≪a≫ρN-1 pj（j=0,…,k-1）を送信し、ランダム置換装置１p0が備える事後変換部１６が加法的秘密分散値≪a≫ρN-1を復元する。
　ステップＳ１２p0において、ランダム置換装置１p0が備える単位置換部１２は、ランダムな置換データπを生成し、復元された公開値を置換する。置換の方法は、従来の置換方法と同様である。
　このように、第三実施形態の秘密計算システムでは、n-1台のランダム置換装置によりランダム置換を行った後に1台のランダム置換装置によりまとめて置換を行うため、置換処理の回数がn-1Ck+1となり、第一実施形態の秘密計算システムよりも効率的に処理を行うことが可能である。
［第四実施形態］
　第四実施形態は、この発明の秘密ランダム置換に対して秘密計算中の改ざんを検知することを可能とする実施形態である。秘密計算中の改ざんを検知する秘密改ざん検知方法として、下記参考文献３に記載の方法が提案されている。参考文献３では、３つのフェーズで秘密計算中の改ざん検知を行う。ランダム化フェーズでは、分散値を正当性検証可能なランダム化分散値へと変換する。計算フェーズでは、semi-honestの演算により構成されるランダム化分散値用の演算を用いて所望の秘密計算を実行する。このとき、後続の正当性証明フェーズでチェックサムを計算するために必要となるランダム化分散値を収集しながら計算が行われる。正当性証明フェーズでは、計算フェーズで収集されたランダム化分散値に対して、一括でチェックサムを計算し正当性証明を行う。チェックサムが正当であれば計算フェーズによる計算結果を出力し、正当でなければ計算結果は出力せずに正当でない旨のみを出力する。
〔参考文献３〕五十嵐大、千田浩司、濱田浩気、菊池亮、“非常に高効率なn≧2k-1 malicious モデル上秘密分散ベースマルチパーティ計算の構成法”、SCIS2013、2013年
　しかしながら、参考文献３に記載の方法を適用するためには、秘密計算で実行する各演算がtamper-simulatableである必要がある（参考文献４）。
〔参考文献４〕D. Ikarashi, R. Kikuchi, K. Hamada, and K. Chida, “Actively Private and Correct MPC Scheme in t<n/2 from Passively Secure Schemes with Small Overhead”, IACR Cryptology ePrint Archive, vol. 2014, p. 304, 2014
　そこで、第四実施形態では、参考文献３に記載の秘密改ざん検知方法を上記の条件を満たすように第一実施形態の秘密ランダム置換に適用した構成例を示す。なお、以下では第一実施形態に適用した例を示すが、同様の考え方により、第二実施形態及び第三実施形態に適用することも可能である。
　図６を参照して、第四実施形態に係るランダム置換装置２の構成例を説明する。ランダム置換装置２は、上述の実施形態に係るランダム置換装置１と同様に、事前変換部１０、単位置換部１２、再分散部１４、事後変換部１６及び記憶部１８を含み、ランダム化部２０、単位変換部２２及び正当性証明部２４をさらに含む。
　図７を参照しながら、第四実施形態に係る秘密計算システムが実行する秘密計算方法の処理フローの一例を、実際に行われる手続きの順に従って説明する。
　ステップＳ２０において、k台のランダム置換装置１ρ0が備えるランダム化部２０は、記憶されている(k,n)-秘密分散値[a]piをランダム化分散値へ変換する。記憶部１８に公開値aが記憶されている場合には、公開値aを(k,n)-秘密分散値[a]piへ変換した上で、ランダム化分散値へ変換する。ランダム化分散値とは、値a∈Rの分散値[a]piと、値a∈Rと乱数r∈Aとの積算値arの分散値[ar]piとの組([a]pi,[ar]pi)である。ここで、Rは環であり、Aは環R上の結合多元環である。結合多元環とは、結合的な環であって、かつそれと両立するような、何らかの体上の線型空間の構造を備えたものである。結合多元環は、ベクトル空間で扱う値が体ではなく環でよくなったものと言える。ランダム化分散値の第０成分（[a]pi）はR成分、第１成分（[ar]pi）はA成分とも呼ぶ。
　ランダム化分散値を生成する際に用いる乱数は、同一の環上の秘密分散を複数利用する場合には、一方の秘密分散のための分散値を他方の秘密分散のための分散値に変換することで、乱数の値が同一となるように生成する。この形式変換においても、改ざん検知が可能もしくは改ざんが不可能でなければならない。例えば、複製型秘密分散（replicated secret sharing）から線形秘密分散（linear secret sharing）へ変換する改ざん不可能な方法は上記参考文献２に記載されている。
　ステップＳ２２において、k台のランダム置換装置１ρiが備える単位変換部２２は、単位置換部１２により置換された加法的秘密分散値≪a≫ρiを(k,n)-秘密分散によるランダム化分散値に変換して記憶部１８に蓄積する。蓄積したランダム化分散値は後述の正当性証明部２４においてチェックサムを計算するために利用される。ランダム化分散値の蓄積は、すべての単位置換の後に必ず行わなくともよく、一部の単位置換の際にのみ行うようにしてもよい。
　ステップＳ２４において、正当性証明部２４は、すべての秘密分散についてすべての秘密計算が終了するまで待機する同期処理（SYNC）を実行する。すべての秘密分散についてすべての秘密計算が終了したことを検知すると、ランダム化部２０で用いた乱数r0,…,rJ-1の分散値[r0],…,[rJ-1]を用いてチェックサムC0,…,CJ-1を検証し、秘密ランダム置換の結果として得られる(k,n)-秘密分散値もしくは公開値の正当性を検証する。チェックサムC0,…,CJ-1を検証した結果、改ざんがないと判定した場合はステップＳ１６へ処理を進める。改ざんがあったと判断した場合はその旨を示す情報（例えば、「⊥」など）を出力する。
　チェックサムの検証は、j=0,…,J-1について、チェックサムCjに含まれるランダム化分散値のR成分の総和に分散値[rj]を乗じた分散値[φj]と、チェックサムCjに含まれるランダム化分散値のA成分の総和である分散値[ψj]とを計算し、分散値[φj]と分散値[ψj]を減算した分散値[δj]=[φj]-[ψj]を復元して、値δ0,…,δJ-1がすべて0であれば秘密ランダム置換全体を通して改ざんがなかったものと判定する。いずれかの値δjが0以外であれば、秘密ランダム置換のいずれかの演算において改ざんがあったものと判定する。
　J個の秘密分散のうち同一の環上の秘密分散が存在する場合には、可能な限りまとめて正当性証明を行うと、公開される値の数が少なくなるため、より秘匿性を向上することができる。例えば、α（α=0,…,J-1）番目の秘密分散とβ（β=0,…,J-1、α≠β）番目の秘密分散が同一の環上の秘密分散である場合には、以下のように正当性証明を行う。まず、チェックサムCαから上述のように算出した分散値[φα]と、チェックサムCαから上述のように算出した分散値[ψα]とをそれぞれβ番目の秘密分散へ変換する。そして、変換後の分散値[φα]とチェックサムCβから同様に算出した分散値[φβ]とを合算した分散値[φα+φβ]と、変換後の分散値[ψα]とβ番目のチェックサムCβから同様に算出した分散値[ψβ]とを合算した分散値[ψα+ψβ]とを減算した分散値[δ]=([φα]+[φβ])-([ψα]+[ψβ])を復元し、復元値δが0であれば改ざんがなかったものと判定し、復元値δが0以外であれば改ざんがあったものと判定する。このようにして、すべての同一の環上の秘密分散の組み合わせについて検証し、秘密ランダム置換全体で改ざんがなかったことを検証する。本形態では２個の秘密分散が同一の環上の秘密分散である例を説明したが、３個以上の秘密分散が同一の環上の秘密分散である場合でも、同様の方法により正当性証明を行うことができる。
　ステップＳ１６において、事後変換部１６は、加法的秘密分散値を(k,n)-秘密分散値もしくは公開値へ変換する。上述の実施形態では、出力が公開値の場合には、最後の置換処理を行った後の加法的秘密分散値≪a≫ρN-1をランダム置換装置１pへ送信し、そのランダム置換装置１pが加法的秘密分散の復元方法により公開値aを得るように構成した。本形態では、公開時の改ざんを検知するために、加法的秘密分散値を(k,n)-秘密分散値に一旦変換した上で、(k,n)-秘密分散の復元方法により公開値aを得るように構成する。
　(k,n)-秘密分散値から公開値を得る際には、改ざん検知が可能な公開方法による必要がある。改ざん検知が可能な公開方法としては、上記参考文献４のappendixに記載の方法がある。もしくは、以下のようにして公開を行うことで改ざん検知が可能である。
　ランダム置換装置１pは、任意のk-1台のランダム置換装置から、加法的秘密分散値≪a≫ρN-1を形式変換した(k,n)-秘密分散値を受信する。また、残りのn-k台のランダム置換装置からは、加法的秘密分散値≪a≫ρN-1を形式変換した(k,n)-秘密分散値のハッシュ値などのチェックサムを受信する。チェックサムはハッシュ値でなくてもよく、より安全な情報理論的なチェックサムを用いることもできる。情報理論的なチェックサムは、例えば、チェックサムの計算対象をaiとして、乱数rとairi+1の組である。ランダム置換装置１pは、自らの持つ(k,n)-秘密分散値を加えたk個の(k,n)-秘密分散値からn-k個の(k,n)-秘密分散値を復旧し、復旧した(k,n)-秘密分散値それぞれからチェックサムを計算する。なお、復旧とは、一部の分散値が失われた際に、利用可能なk個の分散値から利用不能となったn-k個の分散値を秘匿性を失わずに再構築する方法である。
　続いて、ランダム置換装置１pは、n-k台のランダム置換装置から受信した(k,n)-秘密分散値のチェックサムと、復旧した(k,n)-秘密分散値のチェックサムとが一致するか否かを確認する。すべてのチェックサムが一致した場合には改ざんがなかったものと判定し、(k,n)-秘密分散値もしくは公開値を出力する。いずれかのチェックサムが異なっていた場合には改ざんがあったものと判定し、その旨を示す情報（例えば、「⊥」など）を出力する。
　本形態のように構成すれば、この発明の秘密ランダム置換において、改ざん検知が可能となり、安全性が向上する。
［構成例の組み合わせ］
　この発明は、上述の実施形態の他にも、四つの独立した観点の組み合わせにより、様々な構成とすることが可能である。
　一つ目の観点は、入出力の型の観点である。この観点では、四つの構成方法が考えられる。一つ目の構成は、入力が線形秘密分散値であり出力が線形秘密分散値の場合である。二つ目の構成は、入力が線形秘密分散値であり出力が複製秘密分散値の場合、もしくはその逆に入力が複製秘密分散値であり出力が線形秘密分散値の場合である。三つ目の構成は、入力が公開値であり出力が秘密分散値の場合である。四つ目の構成は、入力が線形秘密分散値であり出力が公開値の場合である。
　二つ目の観点は、乱数生成方法の観点である。この観点では、二つの構成方法が考えられる。一つ目の構成は、乱数があらかじめ共有されたシードから生成される疑似乱数の場合である。二つ目の構成は、乱数がプロトコル実行時に共有される場合である。
　三つ目の観点は、ランダム置換の種類の観点である。この観点では、二つの構成方法が考えられる。一つ目の構成は、置換データが任意の場合であり、完全にランダムにシャッフルしたい場合である。二つ目の構成は、置換データがローテーションに制限される場合、つまり置換データがあるr∈Nmで表現され、π(i)=i+r mod mとなっており、絶対的な位置は秘匿したいが相対的な並び順は秘匿しなくてよい場合である。
　四つ目の観点は、k,nを限定した反復置換の具体例の観点である。一つ目の構成は、k=2, n=3の構成である。二つ目の構成は、k=3, n=5の構成である。この観点では、各構成に対して、さらに入出力の観点を加えた計六つの具体例が考えられる。
　一つ目の具体例は、k=2, n=3の構成において、入出力とも秘密分散値の場合である。図６を参照しながら、この具体例の反復置換について説明する。図６において、縦軸はパーティを表し、横軸は単位置換の回数を表している。丸印は単位置換において処理を行うパーティを示している。実線の矢印は再分散において秘密分散値が送信されるパーティの方向を示している。点線の矢印は再分散において同一のパーティが引き続き秘密分散値を保持することを示している。図６の例では、kパーティ組の順番Ρ=(ρ0,ρ1,ρ2)は、ρ0=(p0,p1)、ρ1=(p1,p2)、ρ2=(p0,p2)と設定される。一回目の単位置換ではパーティp0,p1が処理を行い、一回目の再分散ではパーティp0からパーティp2へ秘密分散値が送信される。二回目の単位置換ではパーティp1,p2が処理を行い、二回目の再分散ではパーティp1からパーティp0へ秘密分散値が送信される。三回目の単位置換でパーティp0,p2が処理を行い、反復置換が完了する。
　二つ目の具体例は、k=3, n=5の構成において、入出力とも秘密分散値の場合である。図７を参照しながら、この具体例の反復置換について説明する。図の記法は、図６と同様である。図７の例では、kパーティ組の順番Ρ=(ρ0,…,ρ9)は、ρ0=(p0,p1,p2)、ρ1=(p1,p2,p3)、ρ2=(p2,p3,p4)、ρ3=(p0,p3,p4)、ρ4=(p0,p1,p4)、ρ5=(p1,p3,p4)、ρ6=(p0,p1,p3)、ρ7=(p0,p2,p3)、ρ8=(p0,p2,p4)、ρ9=(p1,p2,p4)と設定される。一回目の単位置換ではパーティp0,p1,p2が処理を行い、一回目の再分散ではパーティp0からパーティp3へ秘密分散値が送信される。二回目の単位置換ではパーティp1,p2,p3が処理を行い、二回目の再分散ではパーティp1からパーティp4へ秘密分散値が送信される。三回目の単位置換ではパーティp2,p3,p4が処理を行い、三回目の再分散ではパーティp2からパーティp0へ秘密分散値が送信される。四回目の単位置換ではパーティp0,p3,p4が処理を行い、四回目の再分散ではパーティp3からパーティp1へ秘密分散値が送信される。ここで、パーティp3からパーティp1へ送信される秘密分散値は、一回目の再分散でパーティp0からパーティp3へ送信された秘密分散値であるから、五回目の再分散の前にパーティp1は受信待ちが発生する。したがって、四回目の再分散までは通信の一段目となる。以降、同様に置換と再分散を繰り返すことで、この具体例では三段の通信段数で反復置換が完了する。
　三つ目の具体例は、k=2, n=3の構成において、入力が公開値であり出力が秘密分散値の場合である。図８を参照しながら、この具体例の反復置換について説明する。図の記法は、図６と同様である。図８の例では、kパーティ組の順番Ρ=(ρ0,ρ1,ρ2)は、ρ0=ρ1=(p0)、ρ2=(p1,p2)と設定される。一回目と二回目の単位置換ではパーティp0のみが処理を行う。この単位置換は単純に二回繰り返してもよいし、二回分の置換をまとめて行うこともできる。二回目の再分散ではパーティp0からパーティp1,p2へ秘密分散値が送信される。三回目の単位置換でパーティp1,p2が処理を行い、反復置換が完了する。
　四つ目の具体例は、k=3, n=5の構成において、入力が公開値であり出力が秘密分散値の場合である。図９を参照しながら、この具体例の反復置換について説明する。図の記法は、図６と同様である。図９の例では、kパーティ組の順番Ρ=(ρ0,…,ρ9)は、ρ0=ρ1=ρ2=ρ3=ρ4=ρ5=(p0)、ρ6=(p2,p3,p4)、ρ7=(p1,p3,p4)、ρ8=(p1,p2,p4)、ρ9=(p1,p2,p3)と設定される。一回目から六回目の単位置換ではパーティp0のみが処理を行う。この単位置換は単純に六回繰り返してもよいし、六回分の置換をまとめて行うこともできる。六回目の再分散ではパーティp0からパーティp2,p3,p4へ秘密分散値が送信される。七回目の単位置換ではパーティp2,p3,p4が処理を行い、七回目の再分散ではパーティp2からパーティp1へ秘密分散値が送信される。八回目の単位置換ではパーティp1,p3,p4が処理を行い、八回目の再分散ではパーティp3からパーティp2へ秘密分散値が送信される。九回目の単位置換ではパーティp1,p2,p4が処理を行い、九回目の再分散ではパーティp4からパーティp3へ秘密分散値が送信される。十回目の単位置換ではパーティp1,p2,p3が処理を行い、反復置換が完了する。図７に示すとおり、この具体例では二段の通信段数で反復置換が完了する。
　五つ目の具体例は、k=2, n=3の構成において、入力が秘密分散値であり出力が公開値の場合である。図１０を参照しながら、この具体例の反復置換について説明する。図の記法は、図６と同様である。図１０の例では、kパーティ組の順番Ρ=(ρ0,ρ1,ρ2)は、ρ0=(p1,p2)、ρ1=ρ2=(p0)と設定される。一回目の単位置換ではパーティp1,p2が処理を行い、パーティp1,p2からパーティp0へ秘密分散値が送信される。パーティp0は秘密分散値の復元を行い、二回目と三回目の単位置換を行う。この単位置換は単純に二回繰り返してもよいし、二回分の置換をまとめて行うこともできる。以上で反復置換が完了する。
　六つ目の具体例は、k=3, n=5の構成において、入力が秘密分散値であり出力が公開値の場合である。図１１を参照しながら、この具体例の反復置換について説明する。図の記法は、図６と同様である。図１１の例では、kパーティ組の順番Ρ=(ρ0,…,ρ9)は、ρ0=(p2,p3,p4)、ρ1=(p1,p3,p4)、ρ2=(p1,p2,p4)、ρ3=(p1,p2,p3)、ρ4=ρ5=ρ6=ρ7=ρ8=ρ9=(p0)と設定される。一回目の単位置換ではパーティp2,p3,p4が処理を行い、一回目の再分散ではパーティp2からパーティp1へ秘密分散値が送信される。以降、パーティp1,p2,p3,p4により置換と再分散を繰り返し、N（=4C3=4）回目の置換が完了した後、パーティp1,p2,p3からパーティp0へ秘密分散値が送信される。パーティp0は秘密分散値の復元を行い、五回目から十回目の単位置換を行う。この単位置換は単純に六回繰り返してもよいし、六回分の置換をまとめて行うこともできる。以上で反復置換が完了する。
　この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
［プログラム、記録媒体］
　上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
　この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
　また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ－ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
　このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
　また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。

Claims (10)

  1. 　n,kを2以上の整数とし、n>kとし、N=nCkとし、ρをn台のランダム置換装置から選択したk台のランダム置換装置の組とし、ρ0,…,ρN-1はi=0,…,N-2について|ρi＼ρi+1|=1となるように構成されており、≪a≫ρiをi番目のランダム置換装置の組ρiが保持する平文aの加法的秘密分散値とし、≪a≫ρi pを加法的秘密分散値≪a≫ρiのうちランダム置換装置pが保持する加法的秘密分散値とし、πρiをi番目のランダム置換装置の組ρiに対応する置換データπのサブシェアとし、ランダム置換装置p0をi番目のランダム置換装置の組ρiに含まれi+1番目のランダム置換装置の組ρi+1に含まれないランダム置換装置とし、ランダム置換装置pkをi番目のランダム置換装置の組ρiに含まれずi+1番目のランダム置換装置の組ρi+1に含まれるランダム置換装置とし、ランダム置換装置pj（j=1,…,k-1）をi番目のランダム置換装置の組ρi及びi+1番目のランダム置換装置の組ρi+1のいずれにも含まれるk-1台のランダム置換装置とし、
    　上記ランダム置換装置p0,…,pk-1が、上記加法的秘密分散値≪a≫ρiを上記サブシェアπρiにより置換する単位置換ステップと、
    　上記ランダム置換装置p0が、上記ランダム置換装置pjそれぞれと共有する乱数r1,…,rk-1を用いて加法的秘密分散値≪a≫ρi+1 pkを生成して上記ランダム置換装置pkへ送信し、上記ランダム置換装置pjそれぞれが上記乱数rjを用いて加法的秘密分散値≪a≫ρi+1 pjを生成する再分散ステップと、
    　を含む秘密計算方法。
  2. 　請求項１に記載の秘密計算方法であって、
    　上記再分散ステップは、上記ランダム置換装置p0が次式により上記加法的秘密分散値≪a≫ρi+1 pkを生成し、
    Figure JPOXMLDOC01-appb-M000001
    上記ランダム置換装置pjそれぞれが次式により上記加法的秘密分散値≪a≫ρi+1 pjを生成する
    Figure JPOXMLDOC01-appb-M000002
    　秘密計算方法。
  3. 　請求項２に記載の秘密計算方法であって、
    　ρ0,…,ρN-1は、0番目のランダム置換装置の組ρ0に含まれるk台のランダム置換装置からN-1番目のランダム置換装置の組ρN-1に含まれるk台のランダム置換装置への経路の通信段数が、最大値と最小値の差が最も小さくなるように構成されている
    　秘密計算方法。
  4. 　請求項１から３のいずれかに記載の秘密計算方法であって、
    　上記平文aの(k,n)-秘密分散による秘密分散値[a]を上記加法的秘密分散値≪a≫ρ0に変換する事前変換ステップと、
    　上記加法的秘密分散値≪a≫ρN-1を上記秘密分散値[a]に変換して出力する事後変換ステップと、
    　をさらに含む秘密計算方法。
  5. 　請求項１から３のいずれかに記載の秘密計算方法であって、
    　N=n-1Ckとし、ρをn台のランダム置換装置から所定のランダム置換装置qを除いて選択したk台のランダム置換装置の組とし、
    　上記平文aを上記加法的秘密分散値≪a≫ρ0に変換する事前変換ステップと、
    　上記加法的秘密分散値≪a≫ρN-1を(k,n)-秘密分散による秘密分散値[a]に変換して出力する事後変換ステップと、
    　をさらに含み、
    　上記単位置換ステップは、
    　　i≦nCk-n-1Ckであれば、上記ランダム置換装置qが、上記平文aを上記サブシェアπρiにより置換し、
    　　i>nCk-n-1Ckであれば、上記ランダム置換装置p1,…,pk-1が、上記加法的秘密分散値≪a≫ρiを上記サブシェアπρiにより置換する
    　秘密計算方法。
  6. 　請求項１から３のいずれかに記載の秘密計算方法であって、
    　N=n-1Ckとし、ρをn台のランダム置換装置から所定のランダム置換装置qを除いて選択したk台のランダム置換装置の組とし、
    　上記平文aの(k,n)-秘密分散による秘密分散値[a]を上記加法的秘密分散値≪a≫ρ0に変換する事前変換ステップと、
    　上記加法的秘密分散値≪a≫ρN-1を復元して上記平文aを出力する事後変換ステップと、
    　をさらに含み、
    　上記単位置換ステップは、
    　　i≦n-1Ckであれば、上記ランダム置換装置p1,…,pk-1が、上記加法的秘密分散値≪a≫ρiを上記サブシェアπρiにより置換し、
    　　i>n-1Ckであれば、上記ランダム置換装置qが、上記平文aを上記サブシェアπρiにより置換する
    　秘密計算方法。
  7. 　請求項１から６のいずれかに記載の秘密計算方法であって、
    　上記単位置換ステップにより置換された上記加法的秘密分散値≪a≫ρiを(k,n)-秘密分散による秘密分散値[a]に変換して記憶部に蓄積する単位変換ステップ
    　をさらに含む秘密計算方法。
  8. 　nを2以上の整数とし、n台のランダム置換装置を含む秘密計算システムであって、
    　kを2以上の整数とし、n>kとし、N=nCkとし、ρをn台のランダム置換装置から選択したk台のランダム置換装置の組とし、ρ0,…,ρN-1はi=0,…,N-2について|ρi＼ρi+1|=1となるように構成されており、≪a≫ρiをi番目のランダム置換装置の組ρiが保持する平文aの加法的秘密分散値とし、≪a≫ρi pを加法的秘密分散値≪a≫ρiのうちランダム置換装置pが保持する加法的秘密分散値とし、πρiをi番目のランダム置換装置の組ρiに対応する置換データπのサブシェアとし、ランダム置換装置p0をi番目のランダム置換装置の組ρiに含まれi+1番目のランダム置換装置の組ρi+1に含まれないランダム置換装置とし、ランダム置換装置pkをi番目のランダム置換装置の組ρiに含まれずi+1番目のランダム置換装置の組ρi+1に含まれるランダム置換装置とし、ランダム置換装置pj（j=1,…,k-1）をi番目のランダム置換装置の組ρi及びi+1番目のランダム置換装置の組ρi+1のいずれにも含まれるk-1台のランダム置換装置とし、
    　上記ランダム置換装置は、
    　　上記加法的秘密分散値≪a≫ρiを上記サブシェアπρiにより置換する単位置換部と、
    　　当該ランダム置換装置が上記ランダム置換装置p0であれば、上記ランダム置換装置pjそれぞれと共有する乱数r1,…,rk-1を用いて加法的秘密分散値≪a≫ρi+1 pkを生成して上記ランダム置換装置pkへ送信し、当該ランダム置換装置が上記ランダム置換装置pjのいずれかであれば、上記乱数rjを用いて加法的秘密分散値≪a≫ρi+1 pjを生成する再分散部と、
    　を含む秘密計算システム。
  9. 　n,kを2以上の整数とし、n>kとし、N=nCkとし、ρをn台のランダム置換装置から選択したk台のランダム置換装置の組とし、ρ0,…,ρN-1はi=0,…,N-2について|ρi＼ρi+1|=1となるように構成されており、≪a≫ρiをi番目のランダム置換装置の組ρiが保持する平文aの加法的秘密分散値とし、≪a≫ρi pを加法的秘密分散値≪a≫ρiのうちランダム置換装置pが保持する加法的秘密分散値とし、πρiをi番目のランダム置換装置の組ρiに対応する置換データπのサブシェアとし、ランダム置換装置p0をi番目のランダム置換装置の組ρiに含まれi+1番目のランダム置換装置の組ρi+1に含まれないランダム置換装置とし、ランダム置換装置pkをi番目のランダム置換装置の組ρiに含まれずi+1番目のランダム置換装置の組ρi+1に含まれるランダム置換装置とし、ランダム置換装置pj（j=1,…,k-1）をi番目のランダム置換装置の組ρi及びi+1番目のランダム置換装置の組ρi+1のいずれにも含まれるk-1台のランダム置換装置とし、
    　上記加法的秘密分散値≪a≫ρiを上記サブシェアπρiにより置換する単位置換部と、
    　当該ランダム置換装置が上記ランダム置換装置p0であれば、上記ランダム置換装置pjそれぞれと共有する乱数r1,…,rk-1を用いて加法的秘密分散値≪a≫ρi+1 pkを生成して上記ランダム置換装置pkへ送信し、当該ランダム置換装置が上記ランダム置換装置pjのいずれかであれば、上記乱数rjを用いて加法的秘密分散値≪a≫ρi+1 pjを生成する再分散部と、
    　を含むランダム置換装置。
  10. 　請求項９に記載のランダム置換装置としてコンピュータを機能させるためのプログラム。
PCT/JP2015/050231 2014-01-17 2015-01-07 秘密計算方法、秘密計算システム、ランダム置換装置及びプログラム Ceased WO2015107952A1 (ja)

Priority Applications (4)

Application Number Priority Date Filing Date Title
JP2015557797A JP6009698B2 (ja) 2014-01-17 2015-01-07 秘密計算方法、秘密計算システム、ランダム置換装置及びプログラム
US15/110,886 US10002547B2 (en) 2014-01-17 2015-01-07 Secret calculation method, secret calculation system, random permutation device, and program
EP15737344.0A EP3096310B1 (en) 2014-01-17 2015-01-07 Secret calculation method, secret calculation system, random permutation device, and program
CN201580004210.0A CN105900165B (zh) 2014-01-17 2015-01-07 秘密计算方法、秘密计算系统、随机置换装置及记录介质

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP2014-006694 2014-01-17
JP2014006694 2014-01-17

Publications (1)

Publication Number Publication Date
WO2015107952A1 true WO2015107952A1 (ja) 2015-07-23

Family

ID=53542842

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2015/050231 Ceased WO2015107952A1 (ja) 2014-01-17 2015-01-07 秘密計算方法、秘密計算システム、ランダム置換装置及びプログラム

Country Status (5)

Country Link
US (1) US10002547B2 (ja)
EP (1) EP3096310B1 (ja)
JP (1) JP6009698B2 (ja)
CN (1) CN105900165B (ja)
WO (1) WO2015107952A1 (ja)

Cited By (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN105204782A (zh) * 2015-10-13 2015-12-30 中国联合网络通信集团有限公司 一种实现数据存储的方法及装置
WO2019087317A1 (ja) * 2017-10-31 2019-05-09 日本電気株式会社 秘密計算装置、システム、方法、プログラム
JPWO2021106133A1 (ja) * 2019-11-28 2021-06-03
US11334353B2 (en) 2017-05-18 2022-05-17 Nec Corporation Multiparty computation method, apparatus and program
WO2022195799A1 (ja) * 2021-03-18 2022-09-22 日本電気株式会社 秘密計算システム、秘密計算サーバ装置、秘密計算方法および秘密計算プログラム
CN117157690A (zh) * 2021-04-19 2023-12-01 日本电信电话株式会社 秘密计算系统、秘密计算装置、方法及程序
US12160506B2 (en) 2019-11-28 2024-12-03 Nec Corporation Shuffling shares among nodes to detect incorrectness or frauds

Families Citing this family (30)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2015107951A1 (ja) * 2014-01-17 2015-07-23 日本電信電話株式会社 秘密計算方法、秘密計算システム、ソート装置及びプログラム
IL278834B2 (en) 2016-02-23 2023-09-01 Nchain Holdings Ltd Automatic registration and management method for smart contracts based on 'block chain'
EP3754901A1 (en) 2016-02-23 2020-12-23 Nchain Holdings Limited Blockchain implemented counting system and method for use in secure voting and distribution
KR102777896B1 (ko) 2016-02-23 2025-03-10 엔체인 홀딩스 리미티드 토큰화를 이용한 블록체인 기반 교환 방법
US12107952B2 (en) 2016-02-23 2024-10-01 Nchain Licensing Ag Methods and systems for efficient transfer of entities on a peer-to-peer distributed ledger using the blockchain
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
US10652014B2 (en) 2016-02-23 2020-05-12 nChain Holdings Limited Determining a common secret for the secure exchange of information and hierarchical, deterministic cryptographic keys
MX2018010058A (es) 2016-02-23 2019-01-21 Nchain Holdings Ltd Metodo y sistema para la transferencia eficiente de criptomoneda asociada con un pago de nomina en una cadena de bloques que lleva a un metodo y sistema de pago de nomina automatico con base en contratos inteligentes.
CN109074580B (zh) 2016-02-23 2022-09-30 区块链控股有限公司 在区块链上安全转移实体的方法和系统
GB2560274C (en) 2016-02-23 2022-06-15 Nchain Holdings Ltd Personal device security using elliptic curve cryptography for secret sharing
CN109155036B (zh) 2016-02-23 2023-05-23 区块链控股有限公司 用于经由区块链控制资产有关的动作的系统及方法
JP7249148B2 (ja) 2016-02-23 2023-03-30 エヌチェーン ライセンシング アーゲー ブロックチェーンベースユニバーサルトークン化システム
JP6995762B2 (ja) 2016-02-23 2022-01-17 エヌチェーン ホールディングス リミテッド ブロックチェーンからのデータのセキュアな抽出のための暗号方法及びシステム
SG10202007907PA (en) 2016-02-23 2020-09-29 Nchain Holdings Ltd Blockchain-implemented method for control and distribution of digital content
MX2018010056A (es) 2016-02-23 2019-01-21 Nchain Holdings Ltd Un metodo y sistema para asegurar software de computadora usando un cuadro hash distribuido y una cadena de bloques.
KR102753021B1 (ko) 2016-02-23 2025-01-14 엔체인 홀딩스 리미티드 블록체인에서 교환을 구현하기 위한 토큰화 방법 및 시스템
JP7047838B2 (ja) * 2017-05-18 2022-04-05 日本電気株式会社 秘密計算装置、比較方法、比較プログラム、および秘密計算システム
JP6777816B2 (ja) * 2017-05-25 2020-10-28 日本電信電話株式会社 秘密改ざん検知システム、秘密改ざん検知装置、秘密改ざん検知方法、およびプログラム
WO2019009180A1 (ja) * 2017-07-05 2019-01-10 日本電信電話株式会社 秘密計算システム、秘密計算装置、秘密計算方法、プログラム、および記録媒体
US11374743B2 (en) * 2017-08-22 2022-06-28 Nippon Telegraph And Telephone Corporation Share generating device, share converting device, secure computation system, share generation method, share conversion method, program, and recording medium
JP6901004B2 (ja) * 2017-10-12 2021-07-14 日本電信電話株式会社 置換装置、置換方法、およびプログラム
CN111183469B (zh) * 2017-10-13 2023-02-28 日本电信电话株式会社 隐匿分类系统以及方法
GB201720753D0 (en) 2017-12-13 2018-01-24 Nchain Holdings Ltd Computer-implemented system and method
CN111902854B (zh) * 2018-03-26 2023-08-01 日本电信电话株式会社 秘密重复排除滤波器生成系统、秘密重复排除系统、它们的方法、秘密计算装置以及记录介质
CN112313728B (zh) * 2018-06-20 2024-04-19 日本电信电话株式会社 秘密结合系统、方法、秘密计算装置以及记录介质
EP3839923B1 (en) * 2018-08-13 2023-11-22 Nippon Telegraph And Telephone Corporation Secret strong mapping calculation system, method therefor, secret calculation device, and program
WO2020165931A1 (ja) * 2019-02-12 2020-08-20 日本電気株式会社 情報処理装置、秘密計算方法及びプログラム
JP7801842B2 (ja) * 2020-02-14 2026-01-19 株式会社野村総合研究所 秘密分散ベースのマルチパーティ計算のための装置
JP7494931B2 (ja) * 2020-10-16 2024-06-04 日本電信電話株式会社 秘密計算システム、秘密計算方法、およびプログラム
AU2020472388B2 (en) * 2020-10-16 2024-02-15 Ntt, Inc. Secure computation system, secure computation apparatus, secure computation method, and program

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20030046547A1 (en) * 2001-05-30 2003-03-06 Jakobsson Bjorn Markus Secure distributed computation in cryptographic applications
US6772339B1 (en) * 2000-03-13 2004-08-03 Lucent Technologies Inc. Mix and match: a new approach to secure multiparty computation
JP5411994B2 (ja) * 2010-10-06 2014-02-12 日本電信電話株式会社 秘密分散システム、秘密分散装置、秘密分散方法、秘密ソート方法、秘密分散プログラム

Family Cites Families (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6035041A (en) * 1997-04-28 2000-03-07 Certco, Inc. Optimal-resilience, proactive, public-key cryptographic system and method
EP1249963B1 (en) * 2001-04-11 2013-01-16 Hitachi, Ltd. Method of a public key encryption and a cypher communication both secure against a chosen-ciphertext attack
US7725730B2 (en) * 2002-08-09 2010-05-25 Emc Corporation Cryptographic methods and apparatus for secure authentication
EP1646174A1 (en) * 2004-10-07 2006-04-12 Axalto SA Method and apparatus for generating cryptographic sets of instructions automatically and code generation
US8050411B2 (en) * 2005-09-29 2011-11-01 Hewlett-Packard Development Company, L.P. Method of managing one-time pad data and device implementing this method

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6772339B1 (en) * 2000-03-13 2004-08-03 Lucent Technologies Inc. Mix and match: a new approach to secure multiparty computation
US20030046547A1 (en) * 2001-05-30 2003-03-06 Jakobsson Bjorn Markus Secure distributed computation in cryptographic applications
JP5411994B2 (ja) * 2010-10-06 2014-02-12 日本電信電話株式会社 秘密分散システム、秘密分散装置、秘密分散方法、秘密ソート方法、秘密分散プログラム

Non-Patent Citations (7)

* Cited by examiner, † Cited by third party
Title
D. IKARASHI; R. KIKUCHI; K. HAMADA; K. CHIDA: "Actively Private and Correct MPC Scheme in t<n/2 from Passively Secure Schemes with Small Overhead", IACR CRYPTOLOGY EPRINT ARCHIVE, vol. 2014, 2014, pages 304
DAI IKARASHI ET AL.: "Internet Kankyo Response 1 Byo no Tokei Shori o Mezashita, Himitsu Keisan Kisu Sort no Kairyo", 2014 NEN SYMPOSIUM ON CRYPTOGRAPHY AND INFORMATION SECURITY KOEN RONBUNSHU, 21 January 2014 (2014-01-21), XP008184896 *
DAI IKARASHI; KOJI CHIDA; KOKI HAMADA; RYO KIKUCHI: "An Extremely Efficient Secret-sharing-based Multi-Party Computation against Malicious Adversary", SCIS 2013, 2013
DAI IKARASHI; KOLCI HAMADA; RYO KIKUCHI; KOJI CHIDA: "0(1) Bits Communication Bit Decomposition and O(|p'|) Bits Communication Modulus Conversion for Small k Secret-Sharing-Based Secure Computation", COMPUTER SECURITY SYMPOSIUM 2013, 2013
KOKI HAMADA; DAI IKARASHI; KOJI CHIDA; KATSUMI TAKAHASHI: "A Random Permutation Protocol on Three-Party Secure Function Evaluation", COMPUTER SECURITY SYMPOSIUM, 2010
LAUR, S. ET AL.: "Round-efficient Oblivious Database Manipulation,", INFORMATION SECURITY, 1 January 2011 (2011-01-01), BERLIN, pages 262 - 277, XP019167784, ISSN: 0302-9743, Retrieved from the Internet <URL:https://eprint.iacr.org/2011/429> [retrieved on 20150127] *
R. CRAMER; I. DAMGARD; Y. ISHAI: "Share conversion, pseudorandom secret-sharing and applications to secure computation", TCC 2005, VOL. 3378 OF LECTURE NOTES IN COMPUTER SCIENCE, vol. 3378, 2005, pages 342 - 362, XP047029379

Cited By (14)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN105204782A (zh) * 2015-10-13 2015-12-30 中国联合网络通信集团有限公司 一种实现数据存储的方法及装置
US11334353B2 (en) 2017-05-18 2022-05-17 Nec Corporation Multiparty computation method, apparatus and program
US11381390B2 (en) 2017-10-31 2022-07-05 Nec Corporation Secure computation apparatus, system, method and program
WO2019087317A1 (ja) * 2017-10-31 2019-05-09 日本電気株式会社 秘密計算装置、システム、方法、プログラム
JPWO2019087317A1 (ja) * 2017-10-31 2020-11-12 日本電気株式会社 秘密計算装置、システム、方法、プログラム
JP7031682B2 (ja) 2017-10-31 2022-03-08 日本電気株式会社 秘密計算装置、システム、方法、プログラム
JPWO2021106133A1 (ja) * 2019-11-28 2021-06-03
JP7420147B2 (ja) 2019-11-28 2024-01-23 日本電気株式会社 シャッフルシステム、シャッフル方法及びプログラム
US12143420B2 (en) 2019-11-28 2024-11-12 Nec Corporation Shuffling shares among nodes to detect incorrectness or frauds
US12160506B2 (en) 2019-11-28 2024-12-03 Nec Corporation Shuffling shares among nodes to detect incorrectness or frauds
WO2022195799A1 (ja) * 2021-03-18 2022-09-22 日本電気株式会社 秘密計算システム、秘密計算サーバ装置、秘密計算方法および秘密計算プログラム
JP7552863B2 (ja) 2021-03-18 2024-09-18 日本電気株式会社 秘密計算システム、秘密計算サーバ装置、秘密計算方法および秘密計算プログラム
US12468857B2 (en) 2021-03-18 2025-11-11 Nec Corporation Secure computation system, secure computation server apparatus, secure computation method, and secure computation program
CN117157690A (zh) * 2021-04-19 2023-12-01 日本电信电话株式会社 秘密计算系统、秘密计算装置、方法及程序

Also Published As

Publication number Publication date
EP3096310A4 (en) 2017-09-27
EP3096310B1 (en) 2018-08-01
JPWO2015107952A1 (ja) 2017-03-23
US20160335924A1 (en) 2016-11-17
CN105900165A (zh) 2016-08-24
US10002547B2 (en) 2018-06-19
JP6009698B2 (ja) 2016-10-19
EP3096310A1 (en) 2016-11-23
CN105900165B (zh) 2019-03-08

Similar Documents

Publication Publication Date Title
JP6009698B2 (ja) 秘密計算方法、秘密計算システム、ランダム置換装置及びプログラム
JP6009697B2 (ja) 秘密計算方法、秘密計算システム、ソート装置及びプログラム
JP5885840B2 (ja) 秘密分散システム、データ分散装置、分散データ変換装置、秘密分散方法、およびプログラム
JP5860556B1 (ja) 不整合検知方法、不整合検知システム、不整合検知装置、およびプログラム
US10003460B2 (en) Secret quotient transfer device, secret bit decomposition device, secret modulus conversion device, secret quotient transfer method, secret bit decomposition method, secret modulus conversion method, and programs therefor
JP6016948B2 (ja) 秘匿計算システム、演算装置、秘匿計算方法、およびプログラム
JP5944841B2 (ja) 秘密分散システム、データ分散装置、分散データ保有装置、秘密分散方法、およびプログラム
JP6040320B2 (ja) 秘密並列処理装置、秘密並列処理方法、プログラム
Mansouri et al. Learning from failures: Secure and fault-tolerant aggregation for federated learning
WO2016104476A1 (ja) 秘密改ざん検知システム、秘密計算装置、秘密改ざん検知方法、およびプログラム
JP5860557B1 (ja) 秘密公開方法、秘密公開システム、秘密公開装置、およびプログラム
US11599681B2 (en) Bit decomposition secure computation apparatus, bit combining secure computation apparatus, method and program
JP5864004B1 (ja) 分散値変換システム、分散値変換装置、分散値変換方法、およびプログラム
JP2016173532A (ja) 分散値変換システム、分散値変換装置、分散値変換方法、およびプログラム
JP5872084B1 (ja) 分散値変換システム、分散値変換装置、分散値変換方法、およびプログラム
WO2016148281A1 (ja) 秘匿文字列計算システム及び方法と装置並びにプログラム
JP6053238B2 (ja) 秘密改ざん検知システム、秘密計算装置、秘密改ざん検知方法、およびプログラム
WO2013136235A1 (en) Byzantine fault tolerance and threshold coin tossing
JP5889454B1 (ja) 分散値変換システム、分散値変換装置、分散値変換方法、およびプログラム
JP2014137516A (ja) 分散管理装置、復元装置、パーティ装置、およびプログラム
WO2018216512A1 (ja) 秘密改ざん検知システム、秘密改ざん検知装置、秘密改ざん検知方法、およびプログラム
Omote et al. DD-POR: Dynamic operations and direct repair in network coding-based proof of retrievability
WO2024233499A1 (en) Single server multi-client message shuffling
CN120930730A (zh) 一种具有全周期安全性的新型联邦学习框架运行方法

Legal Events

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

Ref document number: 15737344

Country of ref document: EP

Kind code of ref document: A1

ENP Entry into the national phase

Ref document number: 2015557797

Country of ref document: JP

Kind code of ref document: A

REEP Request for entry into the european phase

Ref document number: 2015737344

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 2015737344

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 15110886

Country of ref document: US

NENP Non-entry into the national phase

Ref country code: DE