WO2009093603A1 - 秘密計算システム - Google Patents

秘密計算システム Download PDF

Info

Publication number
WO2009093603A1
WO2009093603A1 PCT/JP2009/050857 JP2009050857W WO2009093603A1 WO 2009093603 A1 WO2009093603 A1 WO 2009093603A1 JP 2009050857 W JP2009050857 W JP 2009050857W WO 2009093603 A1 WO2009093603 A1 WO 2009093603A1
Authority
WO
WIPO (PCT)
Prior art keywords
data
secret
fragment
computing device
logic circuit
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/JP2009/050857
Other languages
English (en)
French (fr)
Inventor
Koji Chida
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
Priority claimed from JP2008010928A external-priority patent/JP5078632B2/ja
Application filed by Nippon Telegraph and Telephone Corp filed Critical Nippon Telegraph and Telephone Corp
Priority to CN200980102192.4A priority Critical patent/CN101911153B/zh
Priority to EP09703675.0A priority patent/EP2242032B1/en
Priority to US12/812,916 priority patent/US9300469B2/en
Publication of WO2009093603A1 publication Critical patent/WO2009093603A1/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/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
    • 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/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
    • H04L9/3218—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs
    • H04L9/3221—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs interactive zero-knowledge proofs
    • 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/12—Details relating to cryptographic hardware or logic circuitry
    • 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/16—Obfuscation or hiding, e.g. involving white box
    • 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/50—Oblivious transfer

Definitions

  • the present invention relates to a cryptographic application technique, and more particularly to a technique for obtaining an operation result for an input value while keeping the input value secret.
  • Non-Patent Document 1 discloses a technique for obtaining a calculation result while keeping an input value secret.
  • FIG. 1 is a block diagram showing a configuration of a secret calculation system using the technique disclosed in Non-Patent Document 1.
  • the secret calculation system includes a secret calculation device 81A and a secret calculation device 81B.
  • the secret computing device 81A has a logic circuit function f (x, y) and a bit string m A that is an input to x.
  • the secret computing device 81B similarly has a logic circuit function f (x, y) and a bit string m B that is an input to y.
  • the secret computing device 81A obtains data that allows the secret computing device 81B to easily restore m A without obtaining data that can easily restore m B.
  • One or both of the secret computing devices 81A and 81B obtain the operation result f (m A , m B ) of the logic circuit function f (x, y).
  • the logic circuit function f (x, y) can be realized by a combination of one or more logic gates g.
  • the logic gate g performs a predetermined logical operation on the input one or two bits and outputs one bit indicating the result. Examples of logic gates are AND gates, OR gates, and the like.
  • the input / output series of each logic gate g is called a wire, the input side wire is called an input wire, and the output side wire is called an output wire.
  • Non-Patent Document 1 The method disclosed in Non-Patent Document 1 will be outlined. As an example, a processing procedure for the secret computing device 81A to obtain f (m A , m B ) will be described below.
  • Step C1-1 The secret computing device B having the logic circuit function f (x, y) and the bit string m B that is input to y has a truth table of each logic gate constituting the logic circuit function f (x, y). By concealing, the logic circuit function f (x, y) is concealed.
  • the secret computing device B When concealing a logic gate, the secret computing device B sets a pair of a fixed-length random number corresponding to the value of each wire and a random bit corresponding to the value of each wire to each input wire and output wire. Associate. Then, the truth table is concealed by reconstructing the truth table using the associated (fixed-length random number, random bit). However, with this alone, even those who do not know the correspondence between the value of each wire and (fixed-length random number, random bit), from the combination of (fixed-length random number, random bit) corresponding to the output wire, The contents of the gate can be guessed. Therefore, further concealment is performed using a pseudo-random function. Thereby, the logic gate can be concealed.
  • the logic circuit function f (x, m B ) can be concealed by executing similar concealment for each logic gate constituting the logic circuit function f (x, m B ).
  • the secret computing device B conceals the logic circuit function f (x, m B ) by executing the following (a) to (d).
  • the secret computing device 81B uses a fixed-length random number for each wire i of the logic circuit function f (x, m B ).
  • the secret computing device 81B generates random bits c i ⁇ ⁇ 0, 1 ⁇ . c i is used as a randomized label.
  • C Furthermore, the secret computing device 81B
  • the secret computing device 81B has four labeled data for the logic gate g having i and j as input wires and k as an output wire.
  • T g as described above is generated for each gate constituting the logic circuit function f (x, m B ), and the set T of the generated T g is concealment of the logic circuit function f (x, m B ).
  • the data is transmitted as data to the secret computing device 81A.
  • Step C1-2 The secret computing device 81A that holds the bit string m A that is input to x executes the 1-out-of-2 Oblivious Transfer protocol with the secret computing device 81B. Thereby, the secret computing device 81A causes the data corresponding to the wire having the bit b ⁇ ⁇ 0, 1 ⁇ of m A as an input.
  • the secret computing device 81A receives the data T g received from the secret computing device 81B,
  • step C1-3 in the procedure secure computing apparatus 81A includes a data
  • the T g corresponds to the input wire i, j, the gate of the output wire k,
  • the secret computing device 81A Take out.
  • the secret computing device 81A performs exclusive OR of the expressions (2) and (3), and the data corresponding to the output wire
  • the secret computing device 81A uses the data corresponding to the output wire as one data of the input wires of the other logic gates, and performs the same processing for the other logic gates.
  • the output of the logic gate g wire is obtained.
  • Non-Patent Document 1 it is necessary for the secret computing device 81A and the secret computing device 81B to execute the 1-out-of-2 Oblivious Transfer protocol in the second step.
  • 1-out-of-2 Oblivious Transfer Protocol secure computing apparatus 81B can hold data d 0, d 1, when the secure computing apparatus 81A's bits b, to be secure computing apparatus 81A can obtain the d b Yes, but
  • the secret computing device 81B is a protocol having such a feature that b cannot be obtained.
  • the secure computing apparatus 81A to the secure computing apparatus 81B it is possible to prevent the bit b of m A is leaked, the logic circuit function f is concealed in T g (x, m B) Can be prevented from leaking to the secret computing device 81A. Details of this protocol are described in Non-Patent Document 2.
  • Non-Patent Document 3 discloses another technique for obtaining a calculation result while keeping an input value secret.
  • FIG. 2 is a block diagram showing a configuration of a secret calculation system using the technique disclosed in Non-Patent Document 3.
  • the secret calculation system includes a plurality of conversion devices 90 1 to 90 N and secret calculation devices 91A and 91B.
  • the secret calculation device group 91 is formed by the two secret calculation devices 91A and 91B.
  • the secret computing device group 91 composed of the secret computing devices 91A and 91B uses data mn (1 ⁇ n ⁇ N) held by each of the conversion devices 90 1 to 90 N to easily restore the input value mn. Without obtaining the calculation result f (m 1 ,..., M N ) of the logic circuit function f (x 1 ,..., X N ).
  • the secret computing device 91B conceals the logic circuit function f by executing the following (a) to (d).
  • the secure computing apparatus 91B transmits the data
  • the T g corresponds to the logic circuit function f, a logic circuit function f (x 1, ⁇ , x N) to the secure computing apparatus 91A as concealing data.
  • the secret computing device 91B uses a fixed-length random number for each wire i of the logic circuit function f (x 1 ,..., X N ).
  • the secret computing device 91B generates random bits c i ⁇ ⁇ 0, 1 ⁇ .
  • the secret computing device 91B Furthermore, the secret computing device 91B
  • the secret computing device 91B has four labeled data for the logic gate g having i and j as input wires and k as an output wire.
  • Step C2-2 When each of the conversion devices 90 1 to 90 N executes the proxy 1-out-of-2 Oblivious Transfer protocol together with the secret calculation devices 91A and 91B, the secret calculation device 91A transmits to the input wire i of each bit b of m. Corresponding data
  • the secret computing device 91A includes data T g and
  • the proxy 1-out-of-2 Oblivious Transfer protocol is used.
  • This protocol is an extended version of the 1-out-of-2 Obvious Transfer protocol.
  • the secret calculation device 91A is used instead of the conversion devices 90 1 to 90 N without the bit b, which is information relating to the data held by the conversion devices 90 1 to 90 N being known to the secret calculation device 91A. But
  • Non-Patent Document 1 it is necessary that the secret computing devices 81A and 81B execute the 1-out-of-2 Oblivious Transfer protocol. Further, in the method disclosed in Patent Document 3, it is necessary for the conversion devices 90 1 to 90 N and the secret calculation devices 91A and 91B to execute the proxy 1-out-of-2 Oblivious Transfer protocol.
  • the amount of calculation required to execute the proxy 1-out-of-2 Oblivious Transfer Protocol which is an extension of the 1-out-of-2 Oblivious Transfer Protocol, is the same as that of the 1-out-of-2 Oblivious Transfer Protocol. Degree.
  • the first aspect of the present invention is executed by the first secret calculation device, the second secret calculation device storing the logic circuit function f, and the third secret calculation device.
  • the third secret computing device transmits the data Wb to the first secret computing device without specifying the correspondence between the bit b and the inverted bit (1-b) and the data Wb and the data W (1-b). , Data Wb and data W including data W (1-b) are transmitted to the second secret computing device.
  • the second secret computing device transmits data T to the first secret computing device.
  • Data T and data Wb are input to the first secret computation device, and an operation result f (mA) is calculated using data T and data Wb.
  • the second aspect of the present invention is executed by the first secret calculation device storing the logic circuit function f (x) and the second secret calculation device.
  • Fragment B out of fragment A and fragment B divided from input value m is input to the first secret computing device.
  • the first secret computing device uses the logic circuit function f (x) and the fragment B, and is the data T in which the logic circuit function f (x) is concealed. Generate what can determine (m). Fragment A and data T are input to the second secret computing device, and calculation result f (m) is calculated using fragment A and data T.
  • the input value information of the logic circuit function f is divided into two fragments, and the two divided fragments are input to different secret computing devices and processed.
  • the processing load on the 1-out-of-2 Obvious Transfer protocol and the proxy 1-out-of-2 Obvious Transfer protocol can be reduced, and the load on the secret computing device can be greatly reduced.
  • FIG. 1 is a block diagram showing a configuration of a secret calculation system using the technique disclosed in Non-Patent Document 1.
  • FIG. 2 is a block diagram showing a configuration of a secret calculation system using the technique disclosed in Non-Patent Document 3.
  • FIG. 3 is a block diagram illustrating a configuration of the secret calculation system according to the first embodiment.
  • 4A, 4B, and 4C are block diagrams illustrating a configuration of a secret calculation device 11A included in the secret calculation system according to the first embodiment.
  • FIG. 5 is a sequence diagram illustrating a specific example of the operation of the secret calculation system according to the first embodiment. It is a block diagram which shows the structure of the secret calculation system of 2nd Embodiment.
  • FIGS. 11A and 11B are block diagrams illustrating the configuration of a secret calculation device included in the secret calculation system according to the third embodiment.
  • FIG. 12 is a sequence diagram illustrating a specific example of the operation of the secret calculation system according to the third embodiment.
  • FIG. 13 is a block diagram illustrating a configuration of a secret calculation system according to the fourth embodiment.
  • FIGS. 14A and 14B are block diagrams showing the configuration of the secret calculation device included in the secret calculation system.
  • FIG. 15 is a block diagram illustrating a configuration of a conversion device included in the secret calculation system.
  • FIG. 16 is a sequence diagram illustrating a specific example of the operation of the secret calculation system according to the fourth embodiment.
  • the secret calculation system of this embodiment is composed of three secret calculation devices. Each of the two secret calculation devices constituting the secret calculation system holds input values that are independent of each other.
  • the secret calculation system of this embodiment calculates the calculation result of the logic circuit function f for the input value held by the secret calculation device without being known to other secret calculation devices.
  • FIG. 3 is a block diagram illustrating a configuration of the secret calculation system 1 according to the first embodiment.
  • 4A, 4B, and 4C are block diagrams illustrating the configuration of the secret computing devices 11A, 11B, and 11C included in the secret computing system 1.
  • the secret calculation system 1 includes secret calculation devices 11A, 11B, and 11C (first, second, and third secret calculation devices).
  • the secret calculation device 11A includes a storage unit 11AA, an input unit 11AB, an output unit 11AC, a division unit 11AD, a bit concealment unit 11AE, and a secret calculation unit 11AF.
  • the secret calculation device 11B includes a storage unit 11BA, an input unit 11BB, an output unit 11BC, a bit concealment unit 11BD, and a function concealment unit 11BF.
  • the secret calculation device 11C includes a storage unit 11CA, an input unit 11CB, an output unit 11CC, a bit concealment unit 11CD, and a selection unit 11CE.
  • examples of the secret computing devices 11A, 11B, and 11C include a known CPU (central processing unit), RAM (random-access memory), ROM (read-only memory), a communication device, an input interface, an output interface, and the like. It is an apparatus configured by reading a predetermined program into a computer. Moreover, the secret computing devices 11A, 11B, and 11C may include an integrated circuit.
  • the processing of this embodiment is an example of the first aspect of the present invention described above.
  • the input value m A is stored in the storage unit 11AA of the secret calculation device 11A by preprocessing
  • the input value m B and the logic circuit function f (x, y) are stored in the storage unit 11BA of the secret calculation device 11B.
  • the secret calculation system 1 according to the present embodiment is such that the input value m A held by the secret calculation device 11A is not known to the secret calculation device, and the input value m B held by the secret calculation device 11B is the secret calculation device.
  • the calculation result f (m A , m B ) of the logic circuit function f (x, y) is calculated without being known.
  • the fragment t is transmitted to the secret computing device 11C (step E1-1).
  • the secret computing device 11C generates each data Wb corresponding to each bit b of the inputted fragment t and each data W (1-b) corresponding to each inverted bit (1-b) of each bit b. . Then, the secret computation device 11C includes the data Wb and the data W (1-b) without specifying the correspondence between the bit b and the inverted bit (1-b), the data Wb and the data W (1-b).
  • the data W is transmitted to the secret computing device 11B, and the data Wb is transmitted to the secret computing device 11A (step E1-2).
  • the secret computing device 11B uses the fragment s, the logic circuit function f (x, y), the data W, and the input value m B , and the fragment s and the input value m B are embedded in the logic circuit function f (x, y).
  • the logic circuit function f (s * X, m B ) is concealed, and the logic circuit function f (x, y) for the input value m A and the input value m B from the data T and the data Wb. That can obtain the calculation result f (m A , m B ) is generated.
  • the secret computing device 11B transmits data T to the secret computing device 11A (step E1-3).
  • Data T and data Wb are input to the secret computing device 11A.
  • the secret computing device 11A calculates the calculation result f (m A , m B ) using the data T and the data Wb (steps E1-4, 5).
  • FIG. 5 is a sequence diagram illustrating a specific example of the operation of the secret calculation system 1 according to the first embodiment.
  • XOR exclusive OR operator
  • the dividing unit 11AD of the secret computing device 11A uses the input value m A stored in the storage unit 11AA.
  • step S101 the output unit 11AC of the secret calculation device 11A transmits the fragment s to the secret calculation device 11B (step S102), and transmits the fragment t to the secret calculation device 11C (step S103).
  • the selection unit 11CE corresponds to the W i generated as described above, each bit b of the real t 'set
  • step S104 are selected (step S104).
  • b ′ means the lower wth bit of the fragment t when the input to the input wire i is the lower wth bit of the fragment t.
  • the output unit 11CC secure computing apparatus 11C transmits the W i to secure computing apparatus 11B (step S105),
  • Step E1-3 By secure computing apparatus 11B executes following the (a) ⁇ (d), the logic circuit function f (x, y) to the fragment s and the input value m B and is embedded logic function f (s * X, m B ) is kept secret.
  • the bit concealment unit 11BD of the secret computing device 11B uses a fixed-length random number for each wire i of f (s * X, m B ).
  • bit concealing part 11BD in the secure computing apparatus 11B generates a random bit c i.
  • the bit concealment unit 11BD of the secret computing device 11B Furthermore, the bit concealment unit 11BD of the secret computing device 11B
  • the function concealment unit 11BF of the secret computing device 11B has four labeled data for each logic gate g having i and j as input wires and k as an output wire.
  • T g data in which they are arranged in a random order is generated.
  • the set T of T g becomes data in which the logic circuit function f (s * X, m B ) is concealed (step S107). Note that ck of T g corresponding to the gate g in the final stage of the logic circuit function f (s * X, m B ) is set to 0.
  • the output unit 11BC of the secret calculation device 11B transmits the set T of T g to the secret calculation device 11A as the concealment data of the logic circuit function f (s * X, m B ) (step S108).
  • the input unit 11AB of the secret computing device 11A has a set T of data T g and
  • the secret calculation unit 11AF of the secret calculation apparatus 11A receives the data T g and
  • step E1-4 of the above processing procedure the secret calculation unit 11AF of the secret calculation device 11A is supplied with T g corresponding to the gates g of the input wires i and j and the output wire k, and
  • the secret calculation unit 11AF first labels from T g
  • the secret calculation unit 11AF performs an exclusive OR of Expression (6) and Expression (7), and data corresponding to the output wire
  • the secret calculation unit 11AF uses the data corresponding to the output wire as one data of the input wire of the other gate, performs the same processing for the other gate, and finally performs the final stage of the logic circuit function f.
  • the output of the wire of the logic gate g is obtained.
  • the 1-out-of-2 Oblivious Transfer protocol that occupies most of the total calculation amount in the secret calculation system using the technique of Non-Patent Document 1 is secret. Since it is not necessary to execute any of the computing devices 11A, 11B, and 11C, the load on the secret computing devices 11A, 11B, and 11C can be greatly reduced.
  • the secret calculation device 11C added in this embodiment is only given the fragment t of the input value m A , the secret calculation device 11C does not impair the confidentiality of the input values m A and m B.
  • the operator * an example in which XOR is used as the operator * is shown, but the present invention is not limited to this. For example, addition / subtraction, multiplication, or any other operator may be used as the operator *.
  • the second embodiment is a modification of the first embodiment.
  • the secret calculation system is composed of three secret calculation devices.
  • a secret calculation system is composed of N conversion devices (N is a positive integer) and three secret calculation devices.
  • N is a positive integer
  • two secret calculation devices each hold an input value, and one secret calculation device divides the input value into two pieces.
  • each converter holds input values that are independent of each other, and each converter divides the input value into two pieces.
  • FIG. 6 is a block diagram illustrating a configuration of the secret calculation system 2 according to the second embodiment.
  • FIGS. 7A, 7B, and 7C are block diagrams showing the configuration of the secret computing devices 21A, 21B, and 21C included in the secret computing system 2.
  • FIG. 8 is a block diagram showing a configuration of the conversion device 20 included in the secret calculation system 2.
  • the conversion devices 20 1 to 20 N are collectively referred to as the conversion device 20.
  • the secret calculation system 2 includes secret calculation devices 21A, 21B, and 21C (first, second, and third secret calculation devices).
  • the secret calculation device 21A includes a storage unit 21AA, an input unit 21AB, an output unit 21AC, a bit concealment unit 21AE, and a secret calculation unit 21AF.
  • the secret calculation device 21B includes a storage unit 21BA, an input unit 21BB, an output unit 21BC, a bit concealment unit 21BD, a selection unit 21BE, and a function concealment unit 21BF.
  • the secret calculation device 21C includes a storage unit 21CA, an input unit 21CB, an output unit 21CC, a bit concealment unit 21CD, and a selection unit 21CE.
  • the conversion device 20 includes a storage unit 20A, an input unit 20B, an output unit 20C, and a dividing unit 20D.
  • examples of the secret computing devices 11A, 11B, and 11C and the conversion device 20 are devices configured by reading a predetermined program into a known computer including a CPU, a RAM, a ROM, a communication device, an input interface, an output interface, and the like. It is. Moreover, the secret calculation devices 21A, 21B, and 21C and the conversion device 20 may include an integrated circuit.
  • the processing of this embodiment is an example of the first aspect of the present invention described above.
  • the input values m 1 to m N are stored in the storage units 20A of the respective conversion devices 20 1 to 20 N by preprocessing, and the logic circuit function f (x (x) is stored in the storage unit 21BA of the secret calculation device 21B. 1 ,..., X N ) are stored.
  • the input values m 1 to m N held by the conversion devices 20 1 to 20 N are not known to other devices, and the input values m n (1 ⁇ n ⁇ N) a logic circuit function f as input to calculate (x 1, ⁇ , x N ) computation result f of (m 1, ⁇ , m N ) a.
  • the secure computing apparatus 21A, 21B, 21C without restoring the input values m n, and without obtaining data that can be easily restored input values m n, the operation result f (m 1, ⁇ ⁇ ⁇ , M N ).
  • the operations of the other conversion devices 20 2 to 20 N are the same as those of the conversion device 20 1 (step E2-1).
  • the secret computing device 21C has each data Wb corresponding to each bit b of the fragment t n transmitted from the converting devices 20 1 to 20 N and each data W corresponding to each inverted bit (1-b) of each bit b. (1-b) is generated. Then, the output unit 21CC of the secret computing device 21C does not specify the correspondence between the bit b and the inverted bit (1-b), the data Wb and the data W (1-b), and the data Wb and the data W (1- The data W including b) is transmitted to the secret computing device 21B, and the data Wb is transmitted to the secret computing device 21A (step E2-2).
  • the secret computing device 21B uses the fragment s n , the logic circuit function f (x 1 ,..., X N ) and the data W transmitted from the conversion devices 20 1 to 20 N , and uses the logic circuit function f (x 1 , , X N ) is data T in which the logic circuit function f (s 1 * X 1 ,..., S N * X N ) in which the fragment s n is embedded is concealed, What can obtain the calculation result f (m 1 ,..., M N ) of the logic circuit function f (x 1 ,..., X N ) for the input values m 1 to m N from the data Wb. Generate.
  • the secret computing device 21B transmits data T to the secret computing device 21A (step E2-3).
  • Data T and data Wb are input to the secret computing device 21A.
  • the secret computing device 21A calculates the calculation result f (m 1 ,..., M N ) using the data T and the data Wb (steps E2-4, 5).
  • FIG. 9 is a sequence diagram illustrating a specific example of the operation of the secret calculation system 2 according to the second embodiment.
  • XOR is used as the operator *.
  • the dividing unit 20D of each of the conversion devices 20 1 to 20 N uses the input value mn stored in the respective storage unit 21A.
  • step S201 Is divided into random fragments s n and t n (step S201). Then, the output unit 20C of each of the conversion devices 20 1 to 20 N transmits the fragment s n to the secret calculation device 21B (step S202), and transmits the fragment t n to the secret calculation device 21C (step S203).
  • the set selecting unit 21CE is corresponding to the W i generated as described above, each bit b of the real t n '
  • step S204 is when the input to the input wire i is lower w th bit fragments t n, means a lower w-th bit of the fragments t n. Also,
  • the output unit 21CC secure computing apparatus 21C transmits the W i to secure computing apparatus 21B (step S205),
  • the secret computing device 21B executes the following (a) to (d), whereby the logic circuit function f (s) in which the fragment s n is embedded in the logic circuit function f (x 1 ,..., X N ). 1 * X 1 ,..., S N * X N ) is concealed.
  • the logic gates constituting such a logic circuit function f (s 1 * X 1 ,..., S N * X N ) are concealed.
  • the bit concealment unit 21BD of the secret computing device 21B uses a fixed-length random number for each wire i of the logic circuit function f (s 1 * X 1 ,..., S N * X N ).
  • the bit concealing part 11BD in the secure computing apparatus 21B generates a random bit c i.
  • the bit concealment unit 21BD of the secret calculation device 21B Furthermore, the bit concealment unit 21BD of the secret calculation device 21B
  • the function concealment unit 21BF of the secret computing device 21B has four labeled data for the logic gate g with i, j as input wires and k as output wires.
  • the output unit 21BC of the secret calculation device B21 transmits the set T of T g to the secret calculation device 21A as the confidential data of f (s 1 * X 1 ,..., S N * X N ) (step S208). .
  • the secret calculation unit 21AF of the secret calculation device 21A receives the data T g and
  • the proxy 1-out-of-2 Oblivious Transfer Protocol which occupies most of the entire calculation amount in the secret calculation system using the technique of Non-Patent Document 3, is used. Since it is not necessary to execute any of the secret computing devices 21A, 21B, and 21C, the load on the secret computing devices 21A, 21B, and 21C can be greatly reduced.
  • the secret calculation device 21C added in the present embodiment is only given the fragment t n of the input value mn , the secret calculation device 21C does not impair the confidentiality of the input value mn .
  • an example in which XOR is used as the operator * is shown, but the present invention is not limited to this. For example, addition / subtraction, multiplication, or any other operator may be used as the operator *.
  • each fragment t n divided by each of the conversion devices 20 1 to 20 N is transmitted to the secret calculation device 21C (step S203).
  • the configuration may be such that each fragment t n divided by each of the conversion devices 20 1 to 20 N is first transmitted to the secret computing device 21A and then transferred to the secret computing device 21C. Further, each fragment t n divided by each of the conversion devices 20 1 to 20 N is transmitted to the secret calculation device 21A, and the secret calculation device 21A executes the processing of steps S204 and S205 of this embodiment. Also good. Even in these cases, since the fragment t n and the fragment s n are not concealed and input to the same secret computing device, the confidentiality of the input value mn is not impaired.
  • secure computing apparatus 21C that fragments t n has been input generates data W i, the generated data W i has a structure to be transmitted to the secure computing apparatus 21B.
  • secure computing apparatus 21B generates data W i, the generated data W i may be configured to send to the secure computing apparatus 21C.
  • the secret calculation system of this embodiment includes N (N is a positive integer) conversion devices and two secret calculation devices. Each conversion device holds an independent input value.
  • the secret calculation system of this embodiment calculates the operation result of the logic circuit function f for the input values held by each conversion device without being known to other devices.
  • FIG. 10 is a block diagram illustrating a configuration of the secret calculation system 3 according to the third embodiment.
  • FIGS. 11A and 11B are block diagrams showing the configuration of the secret calculation devices 31A and 31B included in the secret calculation system 3.
  • FIG. 11A and 11B are block diagrams showing the configuration of the secret calculation devices 31A and 31B included in the secret calculation system 3.
  • the secret calculation system 3 includes conversion devices 20 1 to 20 N and secret calculation devices 31A and 31B (first and second secret calculation devices).
  • the secret computing device 31A includes a storage unit 31AA, an input unit 31AB, an output unit 31AC, a bit concealment unit 31AD, a selection unit 31AE, a function concealment unit 31AF, and a 1-out-of-2 OT.
  • An execution unit 31AG is included.
  • the secret calculation device 31B includes a storage unit 31BA, an input unit 31BB, an output unit 31BC, and a secret calculation unit 31BF.
  • the secret calculation unit 31BF includes a 1-out-of-2 OT execution unit 31BFA. Note that the configurations of the converters 20 1 to 20 N are the same as those described in the second embodiment (FIG. 8).
  • examples of the secret computing devices 31A and 31B are devices configured by reading a predetermined program into a known computer including a CPU, a RAM, a ROM, a communication device, an input interface, an output interface, and the like.
  • the secret computing devices 31A and 31B may include an integrated circuit.
  • the processing of this embodiment is an example of the second aspect of the present invention described above.
  • the input values m 1 to m N are stored in the storage units 20A of the respective conversion devices 20 1 to 20 N by preprocessing, and the logic circuit function f (x (x) is stored in the storage unit 31AA of the secret calculation device 31A. 1 ,..., X N ) are stored.
  • the input values m 1 to m N held by the conversion devices 20 1 to 20 N are not known to other devices, and the input values m n (1 ⁇ n ⁇ N) a logic circuit function f as input to calculate (x 1, ⁇ , x N ) computation result f of (m 1, ⁇ , m N ) a.
  • the secure computing apparatus 31A, 31B without restoring the input values m n, and without obtaining data that can be easily restored input values m n, the operation result f (m 1, ⁇ , m N ).
  • the operations of the other conversion devices 20 2 to 20 N are the same as those of the conversion device 20 1 (step E3-1).
  • the secret computing device 31A uses the logic circuit function f (x) and the fragment t n transmitted from the conversion devices 20 1 to 20 N and uses the logic circuit function f (x) in which the fragment t n is embedded.
  • f (X 1 * t 1, ⁇ , X n * t n) is the confidential data T
  • the operation result f (m 1 and a corresponding data T and fragmentation s n, ⁇ , m n ) Is generated.
  • the secret computing device 31A transmits data T to the secret computing device 31B (step E3-2).
  • the secure computing apparatus 31B, the fragment s n and the data T is inputted.
  • Secure computing apparatus 31B, the operation result f by using the fragment s n and the data T (m 1, ⁇ , m N) is calculated.
  • the secret computing device 11B receives the fragment s n and calculates the operation result f (m 1 ,..., M N ) from the data T g without actually restoring the input value mn (step E3- 3, 4, 5).
  • FIG. 12 is a sequence diagram illustrating a specific example of the operation of the secret calculation system 3 according to the third embodiment.
  • the dividing unit 20D of each of the conversion devices 20 1 to 20 N uses the input value mn stored in the respective storage unit 21A.
  • step S301 the output unit 20C of each of the conversion devices 20 1 to 20 N transmits the fragment s n to the secret calculation device 31B (step S302), and transmits the fragment t n to the secret calculation device 31A (step S303).
  • Step E3-2 By executing the following (a) to (d), the secret computing device 31A performs a logic circuit function f (X (X 1 ,..., X N ) in which a fragment t n is embedded. 1 * t 1 ,..., X N * t N ) are concealed.
  • each logic gate constituting such a logic circuit function f (X 1 * t 1 ,..., X N * t N ) is concealed.
  • the bit concealment unit 31AD of the secret calculation device 31A is fixed to each wire i of each logic gate constituting the logic circuit function f (s 1 * X 1 ,..., S N * X N ). Long random number
  • the bit concealment unit 31AD of the secret calculation device 31A generates random bits c i ⁇ ⁇ 0, 1 ⁇ .
  • the bit concealment unit 31AD of the secret calculation device 31A generates random bits c i ⁇ ⁇ 0, 1 ⁇ .
  • b w is the lower w-th bit of the fragment t n .
  • the function concealment unit 31AF of the secret computing device 31A has four labeled data for the logic gate g having i and j as input wires and k as an output wire.
  • the output unit 31AC of the secret calculation device 31A transmits the set T of T g to the secret calculation device 31B as concealment data of the logic circuit function f (X 1 * t 1 ,..., X N * t N ) ( Step S305).
  • the input section 31BB of the secure computing apparatus 31B, fragments s n transmitted from each converter 20 1 ⁇ 20 N are input.
  • the secret calculation unit 31BD of the secret calculation device 31B uses these fragments s n and corresponds to each bit b of the fragment s n.
  • the 1-out-of-2 OT execution unit 31BDA and the 1-out-of-2 OT execution unit 31AG cooperate to generate a prime number p and satisfy 2 or more and less than p satisfying h q ⁇ 1 (mod p).
  • An integer h and a minimum natural number q are obtained.
  • an integer z of 2 or more and less than p is selected.
  • the prime number p, natural number q, integer h, and integer z set in this way are stored in, for example, the storage unit 31AA of the secret calculation device 31A and the storage unit 31BA of the secret calculation device 31B.
  • the 1-out-of-2 OT execution unit 31BDA randomly selects a natural number u less than q. This natural number u is a secret key.
  • the output unit 31AC of the secret calculation device 31A transmits the obtained ciphertexts Z 0 and Z 1 to the secret calculation device 31B.
  • E PK (x) is an encryption function using the public key PK of plaintext x, and the ciphertext can be decrypted by the decryption key u.
  • the 1-out-of-2 OT execution unit 31BDA of the secret computing device 31B decrypts Z 0 and Z 1 using the decryption key u, and the decryption result identified by C when correctly restored
  • the input unit 31BB of the secret computing device 31B has a set T of data T g and
  • the secret calculation unit 31BD of the secret calculation apparatus 31B has T g and
  • the conversion devices 20 1 to 20 N divide the data m n held into s n and t n , send s n to the secret calculation device 31B, and send t n to the secret calculation device 31A. And does not need to run the proxy 1-out-of-2 Oblivious Transfer Protocol. Therefore, compared with the method disclosed in Non-Patent Document 3 that requires this, the load on the conversion devices 201 to 20N is reduced.
  • secure computing apparatus 31B is, in step S306, as the data corresponding to each bit b of the fragment s n, confidential data of each bit b
  • Such a configuration can be realized, for example, by using the following Z 0 and Z 1 instead of the above Z 0 and Z 1 when the operator * is XOR.
  • v denotes the bit fragments t n.
  • the secret calculation system of this embodiment includes N (N is a positive integer) conversion devices and two secret calculation devices. Each conversion device holds an independent input value.
  • the secret calculation system of this embodiment calculates the operation result of the logic circuit function f for the input values held by each conversion device without being known to other devices. However, in this embodiment, the 1-out-of-2 Oblivious Transfer Protocol is not used.
  • FIG. 13 is a block diagram illustrating a configuration of the secret calculation system 4 according to the fourth embodiment.
  • FIGS. 14A and 14B are block diagrams showing the configuration of the secret calculation devices 41A and 41B included in the secret calculation system 4.
  • FIG. 15 is a block diagram showing the configuration of the conversion devices 40 1 to 40 N included in the secret calculation system 4.
  • the conversion devices 40 1 to 40 N are collectively referred to as the conversion device 40.
  • the secret calculation system 4 includes conversion devices 40 1 to 40 N and secret calculation devices 41A and 41B (first and second secret calculation devices).
  • the secret calculation device 41A includes a storage unit 41AA, an input unit 41AB, an output unit 41AC, a bit concealment unit 41AD, and a function concealment unit 41AF.
  • the secret calculation device 41B includes a storage unit 41BA, an input unit 41BB, an output unit 41BC, and a secret calculation unit 41BF.
  • the conversion device 40 includes a storage unit 40A, an input unit 40B, an output unit 40C, a bit concealment unit 40D, and a selection unit 40E.
  • examples of the secret computing devices 41A and 41B and the conversion device 40 are devices configured by reading a predetermined program into a known computer including a CPU, a RAM, a ROM, a communication device, an input interface, an output interface, and the like. Moreover, the secret calculation devices 31A and 31B and the conversion device 40 may include an integrated circuit.
  • the processing of this embodiment is an example of the second aspect of the present invention described above.
  • the input values m 1 to m N are stored in the storage units 40A of the respective conversion devices 40 1 to 40 N by preprocessing, and the logic circuit function f (x (x)) is stored in the storage unit 41AA of the secret calculation device 41A. 1 ,..., X N ) are stored.
  • the input values m 1 to m N held in the conversion devices 40 1 to 40 N are not known to other devices, and the input values m n (1 ⁇ n ⁇ N) a logic circuit function f as input to calculate (x 1, ⁇ , x N ) computation result f of (m 1, ⁇ , m N ) a.
  • the secure computing apparatus 41A, 41B without restoring the input values m n, and without obtaining data that can be easily restored input values m n, the operation result f (m 1, ⁇ , m N ).
  • the converters 40 1 to 40 N have data Wb corresponding to each bit b of each input value m 1 to m N and data W (1-b) corresponding to an inverted bit (1-b) for each bit b. ) And generate. Then, the conversion devices 40 1 to 40 N transmit the data Wb as one fragment obtained by dividing the input values m 1 to m N to the secret calculation device 41B. The conversion devices 40 1 to 40 N convert the data Wb and the data W (1-b) corresponding to the inverted bit (1-b) of each bit b into the data Wb and the data W (1-b and b And the data W including without specifying the correspondence with (1-b) is transmitted to the secret computing device 41A as the other fragment (step E4-1).
  • the secret computing device 41A uses the data W and generates the data T in which the logic circuit function f is concealed and the operation result f (m) can be obtained using the data T and the data Wb.
  • the secret calculation device 41A transmits the generated data T to the secret calculation device 41B (step E4-2).
  • Data T and data Wb are input to the secret computing device 11A.
  • the secret computing device 11A calculates the calculation result f (m) using the data T and the data Wb (steps E4-3, 4, 5).
  • FIG. 16 is a sequence diagram illustrating a specific example of the operation of the secret calculation system 4 according to the fourth embodiment.
  • Bit concealing part 40D of the converter 40 1 ⁇ 40 N are, among the logic gates constituting the logic circuit function f (x 1, ⁇ , x N) a, bit b of each input value m 1 ⁇ m N for each input wire i but inputted, the random bit c i and a random number of fixed length
  • Step E4-2 The function concealment unit 41AF of the secret calculation device 41A executes the logic circuit functions f (x 1 ,..., X N ) by executing (a) to (d) as in step E3-2 described above.
  • a set T of T g in which each constituting logic gate is concealed is generated.
  • the input wire i of each bit of the input values m 1 to m N is
  • the output unit 41AC of the secret calculation device 41A transmits the set T of T g to the secret calculation device 41B as the concealment data of the logic circuit function f (x 1 ,..., X N ) (step S406).
  • the secret calculation unit 41BF of the secret calculation device 41B has T g and
  • the secret calculation devices 41A and 41B cannot obtain significant information regarding the input value mn only from the information received by the secret calculation devices 41A and 41B, and the confidentiality of the input value mn is ensured.
  • the present invention is not limited to the embodiment described above.
  • the configuration method of the logic circuit function in which input values and fragments are embedded is not limited to the above.
  • the various processes described above are not only executed in time series according to the description, but may be executed in parallel or individually according to the processing capability of the apparatus that executes the processes or as necessary.
  • the system is a logical set configuration of a plurality of devices.
  • the configuration of each device is not necessarily in the same housing. Needless to say, other modifications are possible without departing from the spirit of the present invention.
  • processing contents of functions that each device should have are described by a program.
  • the processing functions are realized on the computer by executing the program on the computer.
  • the program describing the processing contents can be recorded on a computer-readable recording medium.
  • the computer-readable recording medium for example, 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 the processing function only by the execution instruction and result acquisition. It is good.
  • ASP Application Service Provider
  • the present invention can be applied to, for example, various systems that utilize personal information while protecting privacy.
  • the present invention can be used for any information aggregation system including an auction.
  • an auction result or a decision result by majority decision can be obtained as a calculation result without leaking data held by each user.
  • Another application example of the present invention is, for example, a system that aggregates data held by each user without the knowledge of others and performs various statistical processing and mining processing based on the data.
  • the present invention can be used in a biometric authentication system. In this case, it is possible to determine whether or not the biometric information is valid while the biometric information of each user is kept secret.

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Computing Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Logic Circuits (AREA)
  • Storage Device Security (AREA)

Abstract

　第３の秘密計算装置は、第１の入力値ｍＡ及び演算子*に対してｍＡ＝ｓ*ｔを満たす断片ｔの各ビットｂに対応した各データＷｂと、各ビットｂの各反転ビット（１－ｂ）に対応した各データＷ（１－ｂ）とを生成し、データＷｂを第１の秘密計算装置に送信し、データＷｂ及びデータＷ（１－ｂ）を含むデータＷを第２の秘密計算装置に送信する。第２の秘密計算装置は、ｍＡ＝ｓ*ｔを満たす断片ｓと論理回路関数ｆとデータＷとを用い、論理回路関数ｆに断片ｓが埋め込まれた論理回路関数ｆ（ｓ*Ｘ）が秘匿されたデータＴであって、当該データＴとデータＷｂとから演算結果ｆ（ｍＡ）を求めることができるものを生成し、データＴを第１の秘密計算装置に送信する。第１の秘密計算装置は、データＴとデータＷｂとを用いて演算結果ｆ（ｍＡ）を算出する。

Description

[規則37.2に基づきISAが決定した発明の名称]　秘密計算システム
　本発明は暗号応用技術に関し、特に、入力値を秘匿したまま、その入力値に対する演算の結果を得る技術に関する。
　非特許文献１には、入力値を秘匿したままで演算結果を得る技術が開示されている。図１は、非特許文献１に開示された技術を用いた秘密計算システムの構成を示すブロック図である。図１を参照すると、秘密計算システムは、秘密計算装置８１Ａと秘密計算装置８１Ｂを有している。
　秘密計算装置８１Ａは、論理回路関数ｆ（ｘ，ｙ）と、ｘへの入力となるビット列ｍAとを保有している。秘密計算装置８１Ｂは、同じく論理回路関数ｆ（ｘ，ｙ）と、ｙへの入力となるビット列ｍBとを保有している。
　秘密計算装置８１Ａと秘密計算装置８１Ｂが互いに通信することにより、秘密計算装置８１ＡがｍBを容易に復元できるデータを得ることなく、秘密計算装置８１ＢがｍAを容易に復元できるデータを得ることなく、秘密計算装置８１Ａ，Ｂのいずれか一方または両方が論理回路関数ｆ（ｘ，ｙ）の演算結果ｆ（ｍA，ｍB）を得る。
　なお、論理回路関数ｆ（ｘ，ｙ）は、１又は複数の論理ゲートｇの組み合わせで実現できる。論理ゲートｇは、入力された１つ又は２つのビットに対して所定の論理演算を行い、その結果を示す１つのビットを出力する。論理ゲートの例は、ＡＮＤゲート、ＯＲゲートなどである。また、各論理ゲートｇの入出力系列をワイヤーと呼び、入力側のワイヤーを入力ワイヤーと呼び、出力側のワイヤーを出力ワイヤーと呼ぶ。
　非特許文献１に開示された方法について概説する。以下に、一例として、秘密計算装置８１Ａがｆ（ｍA，ｍB）を得るための処理手順を挙げる。
　[ステップＣ１－１]
　論理回路関数ｆ（ｘ，ｙ）と、ｙへの入力となるビット列ｍBとを保有する秘密計算装置Ｂは、論理回路関数ｆ（ｘ，ｙ）を構成する各論理ゲートの真理値表を秘匿することで論理回路関数ｆ（ｘ，ｙ）を秘匿する。
　論理ゲートの真理値表は以下のようになる。なお、ＡＮＤゲートの例では、ｇ（０，０）＝ｇ（０，１）＝ｇ（１，０）＝０，ｇ（１，１）＝１である。
　入力ワイヤー　　　出力ワイヤー
　　０，０　　　　　ｇ（０，０）
　　０，１　　　　　ｇ（０，１）
　　１，０　　　　　ｇ（１，０）
　　１，１　　　　　ｇ（１，１）
　論理ゲートを秘匿する場合、秘密計算装置Ｂは、各入力ワイヤーと出力ワイヤーとに、それぞれ、各ワイヤーの値に対応する固定長の乱数と、各ワイヤーの値に対応するランダムビットとの組を対応付ける。そして、対応付けられた（固定長の乱数，ランダムビット）を用いて真理値表を再構成することで真理値表を秘匿する。ただし、これだけでは、各ワイヤーの値と（固定長の乱数，ランダムビット）との対応を知らない者であっても、出力ワイヤーに対応する（固定長の乱数，ランダムビット）の組み合わせから、論理ゲートの内容が推測できてしまう。そのため、擬似ランダム関数を用い、更なる秘匿を行う。これにより、論理ゲートを秘匿できる。そして、論理回路関数ｆ（ｘ，ｍB）を構成する各論理ゲートについて同様な秘匿化を実行することで、論理回路関数ｆ（ｘ，ｍB）を秘匿できる。
　具体的には、秘密計算装置Ｂは、以下の（ａ）～（ｄ）を実行することにより、論理回路関数ｆ（ｘ，ｍB）を秘匿する。
（ａ）　秘密計算装置８１Ｂは、論理回路関数ｆ（ｘ，ｍB）の各ワイヤーｉに対して、固定長の乱数 
Figure JPOXMLDOC01-appb-M000001
を生成し、それぞれ０，１に対応させる。
（ｂ）　次に、秘密計算装置８１Ｂはランダムビットｃi∈｛０，１｝を生成する。ｃiはランダム化されたラベルとして用いる。
（ｃ）　更に、秘密計算装置８１Ｂは、
Figure JPOXMLDOC01-appb-M000002
をワイヤーｉに対応させる。ここで
Figure JPOXMLDOC01-appb-M000003
とする。なお、<α,β>はαがβに対応することを意味する。
（ｄ）次に、秘密計算装置８１Ｂは、ｉ，ｊを入力ワイヤー、ｋを出力ワイヤーとする論理ゲートｇに対して、４つのラベル付きデータ
Figure JPOXMLDOC01-appb-M000004
を生成し、それらをランダムな順番に並べたデータＴgを生成する。ここでコロンの左側をラベル、右側をデータとし、ＦW（ｘ）はｘ，Ｗを入力として、ｘ，Ｗに対して一義的に定まる固定長の乱数を出力する関数（擬似ランダム関数）である。また、
Figure JPOXMLDOC01-appb-M000005
はαとβとの排他的論理和を示す。また、
Figure JPOXMLDOC01-appb-M000006
は、αとβとのビット連結値α｜βとγとの排他的論理和を意味する。
　また、論理回路関数ｆの最終段のゲートｇに対応するＴｇのｃkは０に設定しておく。
　上記のようなＴgは、論理回路関数ｆ（ｘ，ｍB）を構成する各ゲートについて生成され、生成されたＴgの集合Ｔは、論理回路関数ｆ（ｘ，ｍB）の秘匿化データとして秘密計算装置８１Ａに送信される。
　[ステップＣ１－２]
　ｘへの入力となるビット列ｍAを保有する秘密計算装置８１Ａは、秘密計算装置８１Ｂと１－ｏｕｔ－ｏｆ－２　Ｏｂｌｉｖｉｏｕｓ　Ｔｒａｎｓｆｅｒプロトコルを実行する。これにより、秘密計算装置８１Ａは、ｍAのビットｂ∈｛０，１｝を入力とするワイヤーに対応するデータ

を得る。
　[ステップＣ１－３]
　続いて、秘密計算装置８１Ａは、秘密計算装置８１Ｂから受信したデータＴgと、
Figure JPOXMLDOC01-appb-M000008
とを用いて、論理回路関数ｆの最終段の論理ゲートｇのワイヤーの出力
Figure JPOXMLDOC01-appb-M000009
を算出する。
　[ステップＣ１－4]
　更に、秘密計算装置８１Ａは、
Figure JPOXMLDOC01-appb-M000010
から、演算結果ｆ（ｍA，ｍB）のビット
Figure JPOXMLDOC01-appb-M000011
を得る。
　[ステップＣ１－３の詳細]
　上記処理手順におけるステップＣ１－３では、秘密計算装置８１Ａは、入力ワイヤーｉ，ｊ、出力ワイヤーｋのゲートに対応するデータＴgと、
Figure JPOXMLDOC01-appb-M000012
 とが与えられたとき、先ずデータＴgからラベル
Figure JPOXMLDOC01-appb-M000013
に対応するデータ
Figure JPOXMLDOC01-appb-M000014
 を取り出す。また、秘密計算装置８１Ａは、
Figure JPOXMLDOC01-appb-M000015
 を計算する。秘密計算装置８１Ａは、式(2)と式(3)との排他的論理和を行い、出力ワイヤーに対応するデータ
Figure JPOXMLDOC01-appb-M000016
 を得る。そして、秘密計算装置８１Ａは、例えば、出力ワイヤーに対応するデータを他の論理ゲートの入力ワイヤーの1つのデータとし、他の論理ゲートについても同様の処理を行い、最終的にｆの最終段の論理ゲートｇのワイヤーの出力を得る。
　[ステップＣ１－４の詳細]
　論理回路関数ｆの最終段のゲートｇに対応するＴｇのｃkを０に設定しておくことで、
Figure JPOXMLDOC01-appb-M000017
となるため、秘密計算装置８１Ａは、ステップＣ１－４において、
Figure JPOXMLDOC01-appb-M000018
を得ることができる。
　以上説明したように、非特許文献１の方法では、第２のステップにおいて秘密計算装置８１Ａと秘密計算装置８１Ｂが１－ｏｕｔ－ｏｆ－２　Ｏｂｌｉｖｉｏｕｓ　Ｔｒａｎｓｆｅｒプロトコルを実行する必要がある。１－ｏｕｔ－ｏｆ－２　Ｏｂｌｉｖｉｏｕｓ　Ｔｒａｎｓｆｅｒプロトコルは、秘密計算装置８１Ｂがデータｄ0，ｄ1を保有し、秘密計算装置８１Ａがビットｂを保有するとき、秘密計算装置８１Ａはｄbを得ることができるが、
Figure JPOXMLDOC01-appb-M000019
を得ることはできず、かつ秘密計算装置８１Ｂはｂを得ることができないような特徴をもつプロトコルである。このプロトコルを用いることで、秘密計算装置８１Ａから秘密計算装置８１Ｂへ、ｍAのビットｂが漏洩することを防止できるとともに、Ｔgに秘匿化されている論理回路関数ｆ(x,mB)の情報が秘密計算装置８１Ａに漏洩することを防止できる。なお、このプロトコルの詳細は、非特許文献２に説明がある。
　非特許文献３には、入力値を秘匿したままで演算結果を得る他の技術が開示されている。図２は、非特許文献３に開示された技術を用いた秘密計算システムの構成を示すブロック図である。図２を参照すると、秘密計算システムは、複数の変換装置９０1～９０Nと秘密計算装置９１Ａ，９１Ｂとを有している。２つの秘密計算装置９１Ａ，９１Ｂによって秘密計算装置群９１をなしている。
　秘密計算装置９１Ａ，９１Ｂからなる秘密計算装置群９１は、各変換装置９０1～９０Nが保有するデータｍｎ（１≦ｎ≦Ｎ）を用いて、入力値ｍｎを容易に復元できるデータを得ることなく、論理回路関数ｆ（ｘ1，・・・，ｘN）の演算結果ｆ（ｍ1，・・・，ｍN）を求める。
　以下にその処理手順について概説する。
　[ステップＣ２－１]
　まず、秘密計算装置９１Ｂは、以下の（ａ）～（ｄ）を実行することにより、論理回路関数ｆを秘匿する。そして、秘密計算装置９１Ｂは、論理回路関数ｆに対応するデータＴgを、論理回路関数ｆ（ｘ1，・・・，ｘN）の秘匿化データとして秘密計算装置９１Ａに送信する。
（ａ）　秘密計算装置９１Ｂは論理回路関数ｆ（ｘ1，・・・，ｘN）の各ワイヤーｉに対して、固定長の乱数
Figure JPOXMLDOC01-appb-M000020
を生成し、それぞれ０，１に対応させる。
（ｂ）　次に、秘密計算装置９１Ｂは、ランダムビットｃi∈｛０，１｝を生成する。
（ｃ）　更に、秘密計算装置９１Ｂは、
Figure JPOXMLDOC01-appb-M000021
をワイヤーｉに対応させる。ここで
Figure JPOXMLDOC01-appb-M000022
とする。
（ｄ）　更に、秘密計算装置９１Ｂは、ｉ，ｊを入力ワイヤー、ｋを出力ワイヤーとする論理ゲートｇに対して、４つのラベル付きデータ
Figure JPOXMLDOC01-appb-M000023
を生成し、それらをランダムな順番に並べたデータＴgを生成する。データＴgの集合Ｔが、論理回路関数ｆ（ｘ1，・・・，ｘN）の秘匿化データとして秘密計算装置９１Ａに送信される。
　[ステップＣ２－２]
　各変換装置９０1～９０Nが、秘密計算装置９１Ａ，９１Ｂとともに、ｐｒｏｘｙ　１－ｏｕｔ－ｏｆ－２　Ｏｂｌｉｖｉｏｕｓ　Ｔｒａｎｓｆｅｒプロトコルを実行することにより、秘密計算装置９１Ａはｍの各ビットｂの入力ワイヤーｉに対応するデータ
Figure JPOXMLDOC01-appb-M000024
を得る。
　[ステップＣ２－３]
　更に、秘密計算装置９１Ａは、データＴgと、
Figure JPOXMLDOC01-appb-M000025
とを用いて、論理回路関数ｆの最終段の論理ゲートｇのワイヤーの出力
Figure JPOXMLDOC01-appb-M000026
を得る。
　（ステップＣ２－４）
　更に、秘密計算装置９１Ａは、
Figure JPOXMLDOC01-appb-M000027
から、演算結果ｆ（ｍ1，・・・，ｍN）のビット
Figure JPOXMLDOC01-appb-M000028
を得る。
　上記処理手順のステップＣ２－２では、ｐｒｏｘｙ　１－ｏｕｔ－ｏｆ－２　Ｏｂｌｉｖｉｏｕｓ　Ｔｒａｎｓｆｅｒプロトコルが用いられている。このプロトコルは、１－ｏｕｔ－ｏｆ－２　Ｏｂｌｉｖｉｏｕｓ　Ｔｒａｎｓｆｅｒプロトコルを拡張したプロトコルである。このプロトコルによれば、変換装置９０1～９０Nが保有しているデータに関する情報であるビットｂを秘密計算装置９１Ａに知られることなく、変換装置９０1～９０Nの代わりに秘密計算装置９１Ａが
Figure JPOXMLDOC01-appb-M000029
を算出することができる。
Ａ．Ｃ．Ｙａｏ，　Ｈｏｗ　ｔｏ　ｇｅｎｅｒａｔｅ　ａｎｄ　ｅｘｃｈａｎｇｅ　ｓｅｃｒｅｔｓ，Ｐｒｏｃ．　ｏｆ　ＦＯＣＳ　’８６，　ｐｐ．１６２－１６７，ＩＥＥＥ　Ｐｒｅｓｓ，１９８６． Ｓ．Ｅｖｅｎ，　Ｏ．Ｇｏｌｄｒｅｉｃｈ　ａｎｄ　Ａ．Ｌｅｍｐｅｌ，Ａ　ｒａｎｄｏｍｉｚｅｄ　ｐｒｏｔｏｃｏｌ　ｆｏｒ　ｓｉｇｎｉｎｇ　ｃｏｎｔｒａｃｔｓ，　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　ｏｆ　ｔｈｅ　ＡＣＭ，Ｖｏｌ．２８，Ｎｏ．６，ｐｐ．６３７－６４７，１９８５． Ｍ．Ｎａｏｒ，　Ｂ．Ｐｉｎｋａｓ，　ａｎｄ　Ｒ．Ｓｕｍｎｅｒ，Ｐｒｉｖａｃｙ　ｐｒｅｓｅｒｖｉｎｇ　ａｕｃｔｉｏｎｓ　ａｎｄ　ｍｅｃｈａｎｉｓｍ　ｄｅｓｉｇｎ，Ｐｒｏｃ．　ｏｆ　ＡＣＭ　ＥＣ　’９９，ｐｐ．１２９－１３９，ＡＣＭ　Ｐｒｅｓｓ，１９９９．
　上述したように、非特許文献１に開示された方法では、秘密計算装置８１Ａ，８１Ｂが１－ｏｕｔ－ｏｆ－２　Ｏｂｌｉｖｉｏｕｓ　Ｔｒａｎｓｆｅｒプロトコルを実行する必要がある。また、特許文献３に開示された方法では、変換装置９０１～９０Ｎ及び秘密計算装置９１Ａ，９１Ｂが、ｐｒｏｘｙ　１－ｏｕｔ－ｏｆ－２　Ｏｂｌｉｖｉｏｕｓ　Ｔｒａｎｓｆｅｒプロトコルを実行する必要がある。
　Ｄ．Ｍａｌｋｈｉ，　Ｎ．Ｎｉｓａｎ，　Ｂ．Ｐｉｎｋａｓ，　ａｎｄ　Ｙ．Ｓｅｌｌａ，Ｆａｉｒｐｌａｙ　－　ａ　ｓｅｃｕｒｅ　ｔｗｏ－ｐａｒｔｙ　ｃｏｍｐｕｔａｔｉｏｎ　ｓｙｓｔｅｍ，Ｐｒｏｃ．　ｏｆ　ＵＳＥＮＩＸ　Ｓｅｃｕｒｉｔｙ　Ｓｙｍｐｏｓｉｕｍ，ｐｐ．２８７－３０２，ＵＳＥＮＩＸ，２００４．という文献によれば、実装上、１－ｏｕｔ－ｏｆ－２　Ｏｂｌｉｖｉｏｕｓ　Ｔｒａｎｓｆｅｒプロトコルを実行するための計算量が秘密計算システム全体の計算量の大部分を占めると報告されている。
　また、１－ｏｕｔ－ｏｆ－２　Ｏｂｌｉｖｉｏｕｓ　Ｔｒａｎｓｆｅｒプロトコルを拡張したｐｒｏｘｙ　１－ｏｕｔ－ｏｆ－２　Ｏｂｌｉｖｉｏｕｓ　Ｔｒａｎｓｆｅｒプロトコルを実行する際に必要となる計算量は、１－ｏｕｔ－ｏｆ－２　Ｏｂｌｉｖｉｏｕｓ　Ｔｒａｎｓｆｅｒプロトコルと同程度である。
　したがって、実装上、これらのプロトコルに関連する処理量を削減することができれば、秘密計算システムの負荷を低減することができる。
　本発明の第１態様は、第１の秘密計算装置と、論理回路関数ｆを格納した第２の秘密計算装置と、第３の秘密計算装置とによって実行される。
　第３の秘密計算装置は、第１の入力値ｍＡ及び演算子*に対してｍＡ＝ｓ*ｔを満たす断片ｔの各ビットｂに対応した各データＷｂと、各ビットｂの各反転ビット（１－ｂ）に対応した各データＷ（１－ｂ）とを生成する。第３の秘密計算装置は、データＷｂを第１の秘密計算装置に送信し、ビットｂ及び反転ビット（１－ｂ）とデータＷｂ及びデータＷ（１－ｂ）との対応を特定せずに、データＷｂ及びデータＷ（１－ｂ）を含むデータＷを第２の秘密計算装置に送信する。
　第２の秘密計算装置は、ｍＡ＝ｓ*ｔを満たす断片ｓと論理回路関数ｆとデータＷとを用い、論理回路関数ｆに断片ｓが埋め込まれた論理回路関数ｆ（ｓ*Ｘ）が秘匿されたデータＴであって、当該データＴとデータＷｂとから演算結果ｆ（ｍＡ）を求めることができるものを生成する。第２の秘密計算装置は、データＴを第１の秘密計算装置に送信する。
　第１の秘密計算装置には、データＴとデータＷｂとが入力され、データＴとデータＷｂとを用いて演算結果ｆ（ｍＡ）を算出する。
　本発明の第２態様は、論理回路関数ｆ（ｘ）を格納した第１の秘密計算装置と、第２の秘密計算装置とによって実行される。
　第１の秘密計算装置には、入力値ｍから分割された断片Ａと断片Ｂとのうち断片Ｂが入力される。第１の秘密計算装置は、論理回路関数ｆ（ｘ）と断片Ｂとを用い、論理回路関数ｆ（ｘ）が秘匿されたデータＴであって、当該データＴと断片Ａとから演算結果ｆ（ｍ）を求めることのできるものを生成する。
　第２の秘密計算装置には、断片ＡとデータＴとが入力され、断片ＡとデータＴとを用いて演算結果ｆ（ｍ）を算出する。
　本発明によれば、論理回路関数ｆの入力値の情報が２つの断片に分割され、分割された２つの断片がそれぞれ異なる秘密計算装置に入力されて処理される。その結果、１－ｏｕｔ－ｏｆ－２　Ｏｂｌｉｖｉｏｕｓ　Ｔｒａｎｓｆｅｒプロトコルやｐｒｏｘｙ　１－ｏｕｔ－ｏｆ－２　Ｏｂｌｉｖｉｏｕｓ　Ｔｒａｎｓｆｅｒプロトコルに関する処理負荷を軽減でき、秘密計算装置の負荷を大幅に低減できる。
図１は、非特許文献１に開示された技術を用いた秘密計算システムの構成を示すブロック図である。 図２は、非特許文献３に開示された技術を用いた秘密計算システムの構成を示すブロック図である。 図３は、第１の実施形態の秘密計算システムの構成を示すブロック図である。 図４（Ａ）（Ｂ）（Ｃ）は、第１の実施形態の秘密計算システムが含む秘密計算装置１１Ａの構成を示すブロック図である。 図５は、第1の実施形態の秘密計算システムの動作の具体例を示すシーケンス図である。 第２の実施形態の秘密計算システムの構成を示すブロック図である。 図７（Ａ）（Ｂ）（Ｃ）は、第２の実施形態の秘密計算システムが含む秘密計算装置の構成を示すブロック図である。 図８は、秘密計算システムが含む変換装置の構成を示すブロック図である。 図９は、第２の実施形態の秘密計算システムの動作の具体例を示すシーケンス図である。 図１０は、第３の実施形態の秘密計算システムの構成を示すブロック図である。 図１１（Ａ）（Ｂ）は、第３の実施形態の秘密計算システムが含む秘密計算装置の構成を示すブロック図である。 図１２は、第３の実施形態の秘密計算システムの動作の具体例を示すシーケンス図である。 図１３は、第４の実施形態の秘密計算システムの構成を示すブロック図である。 図１４（Ａ）（Ｂ）は、秘密計算システムが含む秘密計算装置の構成を示すブロック図である。 図１５は、秘密計算システムが含む変換装置の構成を示すブロック図である。 図１６は、第４の実施形態の秘密計算システムの動作の具体例を示すシーケンス図である。
符号の説明
　１～４　秘密計算システム
　本発明の実施形態を、図面を参照して詳細に説明する。
　〔第１の実施形態〕
　本実施形態の秘密計算システムは３つの秘密計算装置からなる。この秘密計算システムを構成する２つの秘密計算装置は、それぞれ、互いに独立な入力値を保持している。本実施形態の秘密計算システムは、秘密計算装置によって保有された入力値が他の秘密計算装置に知られることなく、当該入力値に対する論理回路関数ｆの演算結果を算出する。
　＜構成＞
　図３は、第１の実施形態の秘密計算システム１の構成を示すブロック図である。また、図４（Ａ）（Ｂ）（Ｃ）は、秘密計算システム１が含む秘密計算装置１１Ａ，１１Ｂ，１１Ｃの構成を示すブロック図である。
　図３に示すように、秘密計算システム１は、秘密計算装置１１Ａ，１１Ｂ，１１Ｃ（第１、２、３の秘密計算装置）を有する。
　図４（Ａ）に示すように、秘密計算装置１１Ａは、記憶部１１ＡＡ、入力部１１ＡＢ、出力部１１ＡＣ、分割部１１ＡＤ、ビット秘匿部１１ＡＥ及び秘密計算部１１ＡＦを有する。また、図４（Ｂ）に示すように、秘密計算装置１１Ｂは、記憶部１１ＢＡ、入力部１１ＢＢ、出力部１１ＢＣ、ビット秘匿部１１ＢＤ、及び関数秘匿部１１ＢＦを有する。また、図４（Ｃ）に示すように、秘密計算装置１１Ｃは、記憶部１１ＣＡ、入力部１１ＣＢ、出力部１１ＣＣ、ビット秘匿部１１ＣＤ及び選択部１１ＣＥを有する。
　なお、秘密計算装置１１Ａ，１１Ｂ，１１Ｃの例は、ＣＰＵ（central processing unit）、ＲＡＭ（random-access memory）、ＲＯＭ（read-only memory）、通信装置、入力インタフェース、出力インタフェースなどからなる公知のコンピュータに所定のプログラムが読み込まれて構成された装置である。また、秘密計算装置１１Ａ，１１Ｂ，１１Ｃが集積回路を含んでもよい。
　＜処理＞
　本実施形態の処理は、前述した本発明の第１態様の一例である。本実施形態では、前処理によって、秘密計算装置１１Ａの記憶部１１ＡＡに入力値ｍAが格納され、秘密計算装置１１Ｂの記憶部１１ＢＡに入力値ｍBと論理回路関数ｆ（ｘ，ｙ）とが格納されている。本実施形態の秘密計算システム１は、秘密計算装置１１Ａによって保有された入力値ｍＡが秘密計算装置に知られることなく、かつ、秘密計算装置１１Ｂによって保有された入力値ｍＢが秘密計算装置に知られることなく、論理回路関数ｆ（ｘ，ｙ）の演算結果ｆ（ｍA，ｍB）を算出する。
　まず、秘密計算装置１１Ａは、入力値ｍAを、演算子*に対してｍＡ＝ｓ*ｔを満たす断片ｓと断片ｔの２つに分割し、断片ｓを秘密計算装置１１Ｂに送信し、断片ｔを秘密計算装置１１Ｃに送信する（ステップＥ１－１）。
　秘密計算装置１１Ｃは、入力された断片ｔの各ビットｂに対応した各データＷｂと、各ビットｂの各反転ビット（１－ｂ）に対応した各データＷ（１－ｂ）とを生成する。そして、秘密計算装置１１Ｃは、ビットｂ及び反転ビット（１－ｂ）とデータＷｂ及びデータＷ（１－ｂ）との対応を特定せずに、データＷｂ及びデータＷ（１－ｂ）を含むデータＷを秘密計算装置１１Ｂに送信し、データＷｂを秘密計算装置１１Ａに送信する（ステップＥ１－２）。
　秘密計算装置１１Ｂは、断片ｓと論理回路関数ｆ（ｘ，ｙ）とデータＷと入力値ｍＢを用い、論理回路関数ｆ（ｘ，ｙ）に断片ｓと入力値ｍＢとが埋め込まれた論理回路関数ｆ（ｓ*Ｘ，ｍＢ）が秘匿されたデータＴであって、当該データＴとデータＷｂとから入力値ｍＡ及び入力値ｍＢに対する論理回路関数ｆ（ｘ，ｙ）の演算結果ｆ（ｍＡ，ｍＢ）を求めることができるものを生成する。秘密計算装置１１Ｂは、データＴを秘密計算装置１１Ａに送信する（ステップＥ１－３）。
　秘密計算装置１１Ａには、データＴとデータＷｂとが入力される。秘密計算装置１１Ａは、データＴとデータＷｂとを用いて演算結果ｆ（ｍＡ，ｍＢ）を算出する（ステップＥ１－４，５）。
　以下に、本実施形態の秘密計算システム１の動作の具体例を示す。
　図５は、第1の実施形態の秘密計算システム１の動作の具体例を示すシーケンス図である。
　[ステップＥ１－１]
　この例では、演算子*としてＸＯＲ（排他的論理和演算子）を用いる。秘密計算装置１１Ａの分割部１１ＡＤが、記憶部１１ＡＡに格納された入力値ｍAを
Figure JPOXMLDOC01-appb-M000030
となるランダムな断片ｓ，ｔに分割する（ステップＳ１０１）。そして、秘密計算装置１１Ａの出力部１１ＡＣが、断片ｓを秘密計算装置１１Ｂに送信し（ステップＳ１０２）、断片ｔを秘密計算装置１１Ｃにそれぞれ送信する（ステップＳ１０３）。
　[ステップＥ１－２]
　秘密計算装置１１Ｃのビット秘匿部１１ＣＤは、論理回路関数ｆ（ｓ*Ｘ，ｍＢ）のｍＡ＝ｓ*ＸのＸに対応する入力ワイヤーｉごとに、固定長の乱数であるデータＷi ０とランダムビットｃiとの組、及び、固定長の乱数であるＷi 1とランダムビットｃiの反転ビットとの組からなる
Figure JPOXMLDOC01-appb-M000031
を生成する（「データＷ」の具体例）。
　また、選択部１１ＣＥは、上記のように生成されたＷｉから、実際のｔの各ビットｂ’に対応する組
Figure JPOXMLDOC01-appb-M000032
をそれぞれ選択する（ステップＳ１０４）。なお、ｂ’は、入力ワイヤーｉへの入力が断片ｔの下位ｗ番目のビットである場合における、断片ｔの下位ｗ番目のビットを意味する。また、
Figure JPOXMLDOC01-appb-M000033
は「データＷｂ」の具体例である。
　そして、秘密計算装置１１Ｃの出力部１１ＣＣは、Ｗiを秘密計算装置１１Ｂに送信し（ステップＳ１０５）、
Figure JPOXMLDOC01-appb-M000034
を秘密計算装置１１Ａに送信する（ステップＳ１０６）。
　[ステップＥ１－３]
　秘密計算装置１１Ｂが、以下の（ａ）～（ｄ）を実行することにより、論理回路関数ｆ（ｘ，ｙ）に断片ｓと入力値ｍＢとが埋め込まれた論理回路関数ｆ（ｓ*Ｘ，ｍＢ）を秘匿する。なお、この例の論理回路関数ｆ（ｘ，ｙ）に断片ｓと入力値ｍＢとが埋め込まれた論理回路関数ｆ（ｓ*Ｘ，ｍＢ）は、断片Ｘ＝ｔを入力としてｍA＝ｓ*Ｘを復元する関数ｍA＝ｓ*Ｘと、論理回路関数ｆ（ｘ，ｙ）に入力値ｍＢが埋め込まれた論理回路関数ｆ（ｘ，ｍＢ）とを含み、論理回路関数ｆ（ｘ，ｍＢ）に関数ｍA＝ｓ*Ｘの出力値ｍAを入力してｆ（ｍA，ｍＢ）を出力する関数である。以下では、このような論理回路関数ｆ（ｘ，ｍＢ）を構成する各論理ゲートを秘匿する。
（ａ）　秘密計算装置１１Ｂのビット秘匿部１１ＢＤが、ｆ（ｓ*Ｘ，ｍB）の各ワイヤーｉに対して、固定長の乱数
Figure JPOXMLDOC01-appb-M000035
を生成し、それぞれ０，１に対応させる。ただし、関数ｍA＝ｓ*Ｘを構成する論理ゲートのうち、Ｘ＝ｔのビットが入力される入力ワイヤーに対しては、秘密計算装置１１Ｃから受け取った
Figure JPOXMLDOC01-appb-M000036
を対応させる。
（ｂ）　次に、秘密計算装置１１Ｂのビット秘匿部１１ＢＤは、ランダムビットｃiを生成する。ただし、関数ｍA＝ｓ*Ｘを構成する論理ゲートのうち、Ｘ＝ｔのビットが入力される入力ワイヤーに対しては、秘密計算装置１１Ｃから受け取ったｃiを用いるため、Ｘ＝ｔのビットが入力される入力ワイヤーに対しては新たなランダムビットｃiを生成しない。
（ｃ）　更に、秘密計算装置１１Ｂのビット秘匿部１１ＢＤは、
Figure JPOXMLDOC01-appb-M000037
をワイヤーｉに対応させる。ただし、断片ｓの下位ｗ番目のビットに対応するワイヤーｉには、
Figure JPOXMLDOC01-appb-M000038
を対応させる。ここで、ｂは断片ｓの下位ｗ番目のビットである。
（ｄ）　次に、秘密計算装置１１Ｂの関数秘匿部１１ＢＦが、ｉ，ｊを入力ワイヤー、ｋを出力ワイヤーとする各論理ゲートｇに対して、４つのラベル付きデータ
Figure JPOXMLDOC01-appb-M000039
を生成し、それらをランダムな順番に並べたデータＴgを生成する。このＴgの集合Ｔが論理回路関数ｆ（ｓ*Ｘ，ｍＢ）を秘匿したデータとなる（ステップＳ１０７）。なお、論理回路関数ｆ（ｓ*Ｘ，ｍＢ）の最終段のゲートｇに対応するＴｇのｃkは０に設定しておく。
　秘密計算装置１１Ｂの出力部１１ＢＣは、Ｔgの集合Ｔを論理回路関数ｆ（ｓ*Ｘ，ｍＢ）の秘匿化データとして秘密計算装置１１Ａに送信する（ステップＳ１０８）。
　[ステップＥ１－４]
　秘密計算装置１１Ａの入力部１１ＡＢには、データＴgの集合Ｔと
Figure JPOXMLDOC01-appb-M000040
が入力される。秘密計算装置１１Ａの秘密計算部１１ＡＦは、データＴgと
Figure JPOXMLDOC01-appb-M000041
を用いて、論理回路関数ｆの最終段の論理ゲートｇのワイヤーの出力
Figure JPOXMLDOC01-appb-M000042
を得る。
　[ステップＥ１－５]
　秘密計算装置１１Ａの秘密計算部１１ＡＦは、
Figure JPOXMLDOC01-appb-M000043
から、演算結果ｆ（ｍA，ｍB）のビット
Figure JPOXMLDOC01-appb-M000044
を得る（ステップＳ１０９）。
　[ステップＥ１－４の詳細]
　上記処理手順のステップＥ１－４では、秘密計算装置１１Ａの秘密計算部１１ＡＦに、入力ワイヤーｉ，ｊ、出力ワイヤーｋのゲートｇに対応するＴgと、
Figure JPOXMLDOC01-appb-M000045
 とが与えられたとき、秘密計算部１１ＡＦは、先ずＴgからラベル
Figure JPOXMLDOC01-appb-M000046
をラベルに対応するデータ
Figure JPOXMLDOC01-appb-M000047
 を取り出す。また、秘密計算部１１ＡＦは、
Figure JPOXMLDOC01-appb-M000048
 を計算する。秘密計算部１１ＡＦは、式(6)と式(7)との排他的論理和を行い、出力ワイヤーに対応するデータ
Figure JPOXMLDOC01-appb-M000049
 を得る。そして、秘密計算部１１ＡＦは、例えば、出力ワイヤーに対応するデータを他のゲートの入力ワイヤーの1つのデータとし、他のゲートについても同様の処理を行い、最終的に論理回路関数ｆの最終段の論理ゲートｇのワイヤーの出力を得る。
　[ステップＥ１－５の詳細]
　論理回路関数ｆ（ｓ*Ｘ，ｍＢ）の最終段のゲートｇに対応するＴｇのｃkを０に設定しておくことで、
Figure JPOXMLDOC01-appb-M000050
となるため、秘密計算装置１１Ａの秘密計算部１１ＡＦは、
Figure JPOXMLDOC01-appb-M000051
を得ることができる。
　以上、説明したように、本実施形態によれば、非特許文献１の技術を用いた秘密計算システムでは全体の計算量の大部分を占めていた１－ｏｕｔ－ｏｆ－２　Ｏｂｌｉｖｉｏｕｓ　Ｔｒａｎｓｆｅｒプロトコルを秘密計算装置１１Ａ，１１Ｂ，１１Ｃのいずれも実行する必要がないので、秘密計算装置１１Ａ，１１Ｂ，１１Ｃの負荷を大幅に低減することができる。
　なお、本実施形態で追加された秘密計算装置１１Ｃには入力値ｍAの断片ｔが与えられるだけなので、秘密計算装置１１Ｃによって入力値ｍA，ｍBの秘匿性が損なわれることはない。
　また、本実施形態では、ＸＯＲを演算子*として用いる例を示したが、本発明はこれに限定されるものではない。例えば、加減算、乗算、その他どのような演算子を演算子*としてもよい。
　〔第２の実施形態〕
　第２の実施形態は第１の実施形態の変形例である。第２の実施形態の第１の実施形態との主な相違点は以下である。
　・第１の実施形態では、３つの秘密計算装置から秘密計算システムが構成されていた。第２の実施形態では、Ｎ個（Ｎは正の整数）の変換装置と３つの秘密計算装置とから秘密計算システムが構成される。
　・第１の実施形態では、２つの秘密計算装置がそれぞれ入力値を保持し、１つの秘密計算装置が入力値を２つの断片に分割していた。第２の実施形態では、各変換装置がそれぞれ互いに独立な入力値を保持し、各変換装置が入力値を２つの断片に分割する。
　＜構成＞
　図６は、第２の実施形態の秘密計算システム２の構成を示すブロック図である。また、図７（Ａ）（Ｂ）（Ｃ）は、秘密計算システム２が含む秘密計算装置２１Ａ，２１Ｂ，２１Ｃの構成を示すブロック図である。また、図８は、秘密計算システム２が含む変換装置２０の構成を示すブロック図である。なお、変換装置２０１～２０Ｎを総称して変換装置２０と呼ぶ。
　図６に示すように、秘密計算システム２は、秘密計算装置２１Ａ，２１Ｂ，２１Ｃ（第１、２、３の秘密計算装置）を有する。
　図７（Ａ）に示すように、秘密計算装置２１Ａは、記憶部２１ＡＡ、入力部２１ＡＢ、出力部２１ＡＣ、ビット秘匿部２１ＡＥ及び秘密計算部２１ＡＦを有する。また、図７（Ｂ）に示すように、秘密計算装置２１Ｂは、記憶部２１ＢＡ、入力部２１ＢＢ、出力部２１ＢＣ、ビット秘匿部２１ＢＤ、選択部２１ＢＥ及び関数秘匿部２１ＢＦを有する。また、図７（Ｃ）に示すように、秘密計算装置２１Ｃは、記憶部２１ＣＡ、入力部２１ＣＢ、出力部２１ＣＣ、ビット秘匿部２１ＣＤ及び選択部２１ＣＥを有する。また、図８に示すように、変換装置２０は、それぞれ、記憶部２０Ａ、入力部２０Ｂ、出力部２０Ｃ及び分割部２０Ｄを有する。
　なお、秘密計算装置１１Ａ，１１Ｂ，１１Ｃ、変換装置２０の例は、ＣＰＵ、ＲＡＭ、ＲＯＭ、通信装置、入力インタフェース、出力インタフェースなどからなる公知のコンピュータに所定のプログラムが読み込まれて構成された装置である。また、秘密計算装置２１Ａ，２１Ｂ，２１Ｃ、変換装置２０が集積回路を含んでもよい。
　＜処理＞
　本実施形態の処理は、前述した本発明の第１態様の一例である。
　本実施形態では、前処理によって、各変換装置２０1～２０Nの記憶部２０Ａに、それぞれ入力値ｍ１～ｍＮが格納され、秘密計算装置２１Ｂの記憶部２１ＢＡに論理回路関数ｆ（ｘ１，・・・，ｘＮ）が格納されている。本実施形態の秘密計算システム２は、各変換装置２０1～２０Nによって保有された入力値ｍ１～ｍＮが他の装置に知られることなく、入力値ｍｎ（１≦ｎ≦Ｎ）を入力とした論理回路関数ｆ（ｘ１，・・・，ｘＮ）の演算結果ｆ（ｍ１，・・・，ｍＮ）を算出する。その際、各秘密計算装置２１Ａ，２１Ｂ，２１Ｃは、入力値ｍｎを復元することなく、また入力値ｍｎを容易に復元できるデータを得ることなく、演算結果ｆ（ｍ１，・・・，ｍＮ）を求める。
　まず、変換装置２０1は、入力値ｍ１を、演算子*に対してｍ１＝ｓ１*ｔ１を満たす断片ｓ１と断片ｔ１の２つに分割し、断片ｓ１を秘密計算装置２１Ｂに送信し、断片ｔ１を秘密計算装置２１Ｃに送信する。他の変換装置２０2～２０Nの動作も変換装置２０1と同様である（ステップＥ２－１）。
　秘密計算装置２１Ｃは、変換装置２０1～２０Nから送信された断片ｔｎの各ビットｂに対応した各データＷｂと、各ビットｂの各反転ビット（１－ｂ）に対応した各データＷ（１－ｂ）とを生成する。そして、秘密計算装置２１Ｃの出力部２１ＣＣは、ビットｂ及び反転ビット（１－ｂ）とデータＷｂ及びデータＷ（１－ｂ）との対応を特定せずに、データＷｂ及びデータＷ（１－ｂ）を含むデータＷを秘密計算装置２１Ｂに送信し、データＷｂを秘密計算装置２１Ａに送信する（ステップＥ２－２）。
　秘密計算装置２１Ｂは、変換装置２０1～２０Nから送信された断片ｓｎと論理回路関数ｆ（ｘ１，・・・，ｘＮ）とデータＷを用い、論理回路関数ｆ（ｘ１，・・・，ｘＮ）に断片ｓｎが埋め込まれた論理回路関数ｆ（ｓ１*Ｘ１，・・・，ｓＮ*ＸＮ）が秘匿されたデータＴであって、当該データＴとデータＷｂとから、入力値ｍ1～ｍNに対する論理回路関数ｆ（ｘ１，・・・，ｘＮ）の演算結果ｆ（ｍ１，・・・，ｍＮ）を求めることができるものを生成する。秘密計算装置２１Ｂは、データＴを秘密計算装置２１Ａに送信する（ステップＥ２－３）。
　秘密計算装置２１Ａには、データＴとデータＷｂとが入力される。秘密計算装置２１Ａは、データＴとデータＷｂとを用いて演算結果ｆ（ｍ１，・・・，ｍＮ）を算出する（ステップＥ２－４，５）。
　以下に、本実施形態の秘密計算システム２の動作の具体例を示す。
　図９は、第２の実施形態の秘密計算システム２の動作の具体例を示すシーケンス図である。
　[ステップＥ２－１]
　この例では、演算子*としてＸＯＲを用いる。各変換装置２０1～２０Nの分割部２０Ｄが、それぞれの記憶部２１Ａに格納された入力値ｍｎを
Figure JPOXMLDOC01-appb-M000052
となるランダムな断片ｓｎ，ｔｎに分割する（ステップＳ２０１）。そして、各変換装置２０1～２０Nの出力部２０Ｃが、断片ｓｎを秘密計算装置２１Ｂに送信し（ステップＳ２０２）、断片ｔｎを秘密計算装置２１Ｃにそれぞれ送信する（ステップＳ２０３）。
　[ステップＥ２－２]
　秘密計算装置２１Ｃのビット秘匿部２１ＣＤは、論理回路関数ｆ（ｓ１*Ｘ１，・・・，ｓＮ*ＸＮ）のｍｎ＝ｓｎ*ＸｎのＸｎに対応する入力ワイヤーｉごとに、固定長の乱数であるデータＷi ０とランダムビットｃiとの組、及び、固定長の乱数であるＷi 1とランダムビットｃiの反転ビットとの組からなる
Figure JPOXMLDOC01-appb-M000053
を生成する（「データＷ」の具体例）。
　また、選択部２１ＣＥは、上記のように生成されたＷｉから、実際のｔｎの各ビットｂ’に対応する組
Figure JPOXMLDOC01-appb-M000054
をそれぞれ選択する（ステップＳ２０４）。なお、ｂ’は、入力ワイヤーｉへの入力が断片ｔｎの下位ｗ番目のビットである場合における、断片ｔｎの下位ｗ番目のビットを意味する。また、
Figure JPOXMLDOC01-appb-M000055
は「データＷｂ」の具体例である。
　そして、秘密計算装置２１Ｃの出力部２１ＣＣは、Ｗiを秘密計算装置２１Ｂに送信し（ステップＳ２０５）、
Figure JPOXMLDOC01-appb-M000056
を秘密計算装置２１Ａに送信する（ステップＳ２０６）。
　[ステップＥ２－３]
　秘密計算装置２１Ｂが、以下の（ａ）～（ｄ）を実行することにより、論理回路関数ｆ（ｘ１，・・・，ｘＮ）に断片ｓｎが埋め込まれた論理回路関数ｆ（ｓ１*Ｘ１，・・・，ｓＮ*ＸＮ）を秘匿する。なお、この例の論理回路関数ｆ（ｘ１，・・・，ｘＮ）に断片ｓｎが埋め込まれた論理回路関数ｆ（ｓ１*Ｘ１，・・・，ｓＮ*ＸＮ）は、断片Ｘ＝ｔｎを入力としてｍｎ＝ｓｎ*Ｘｎを復元する関数ｍｎ＝ｓｎ*Ｘｎと、論理回路関数ｆ（ｘ１，・・・，ｘＮ）とを含み、論理回路関数ｆ（ｘ１，・・・，ｘＮ）に各関数ｍｎ＝ｓｎ*Ｘｎの出力値ｍｎを入力してｆ（ｍ１，・・・，ｍＮ）を出力する関数である。以下では、このような論理回路関数ｆ（ｓ１*Ｘ１，・・・，ｓＮ*ＸＮ）を構成する各論理ゲートを秘匿する。
（ａ）　秘密計算装置２１Ｂのビット秘匿部２１ＢＤが、論理回路関数ｆ（ｓ１*Ｘ１，・・・，ｓＮ*ＸＮ）の各ワイヤーｉに対して、固定長の乱数
Figure JPOXMLDOC01-appb-M000057
を生成し、それぞれ０，１に対応させる。ただし、関数ｍｎ＝ｓｎ*Ｘｎを構成する論理ゲートのうち、Ｘｎ＝ｔｎのビットが入力される入力ワイヤーに対しては、秘密計算装置２１Ｃから受け取った
Figure JPOXMLDOC01-appb-M000058
を対応させる。
（ｂ）　次に、秘密計算装置２１Ｂのビット秘匿部１１ＢＤは、ランダムビットｃiを生成する。ただし、関数ｍｎ＝ｓｎ*Ｘｎを構成する論理ゲートのうち、Ｘｎ＝ｔｎのビットが入力される入力ワイヤーに対しては、秘密計算装置１１Ｃから受け取ったｃiを用いるため、Ｘｎ＝ｔｎのビットが入力される入力ワイヤーに対しては新たなランダムビットｃiを生成しない。
（ｃ）　更に、秘密計算装置２１Ｂのビット秘匿部２１ＢＤは、
Figure JPOXMLDOC01-appb-M000059
をワイヤーｉに対応させる。ただし、ｓｎの下位ｗ番目のビットに対応するワイヤーｉには、
Figure JPOXMLDOC01-appb-M000060
を対応させる。ここでｂはｓｎの下位ｗ番目のビットである。
（ｄ）　更に、秘密計算装置２１Ｂの関数秘匿部２１ＢＦが、ｉ，ｊを入力ワイヤー、ｋを出力ワイヤーとする論理ゲートｇに対して、４つのラベル付きデータ
Figure JPOXMLDOC01-appb-M000061
を生成し、それらをランダムな順番に並べたデータＴgを生成する。Ｔgの集合Ｔが論理回路関数ｆ（ｓ１*Ｘ１，・・・，ｓＮ*ＸＮ）を秘匿化したデータとなる（ステップＳ２０７）。
　秘密計算装置Ｂ２１の出力部２１ＢＣは、Ｔgの集合Ｔをｆ（ｓ１*Ｘ１，・・・，ｓＮ*ＸＮ）の秘匿化データとして秘密計算装置２１Ａに送信する（ステップＳ２０８）。
　[ステップＥ２－４]
　秘密計算装置２１Ａの入力部２１ＡＢには、データＴgの集合Ｔと
Figure JPOXMLDOC01-appb-M000062
が入力される。秘密計算装置２１Ａの秘密計算部２１ＡＦは、データＴgと
Figure JPOXMLDOC01-appb-M000063
を用いて、論理回路関数ｆの最終段の論理ゲートｇのワイヤーの出力
Figure JPOXMLDOC01-appb-M000064
を得る。
　[ステップＥ２－５]
　秘密計算装置２１Ａの秘密計算部２１ＡＦは、
Figure JPOXMLDOC01-appb-M000065
から、演算結果ｆ（ｍ1，・・・，ｍN）のビット
Figure JPOXMLDOC01-appb-M000066
を得る（ステップＳ２０９）。
　以上、説明したように、本実施形態によれば、非特許文献３の技術を用いた秘密計算システムでは全体の計算量の大部分を占めていた、ｐｒｏｘｙ　１－ｏｕｔ－ｏｆ－２　Ｏｂｌｉｖｉｏｕｓ　Ｔｒａｎｓｆｅｒプロトコルを秘密計算装置２１Ａ，２１Ｂ，２１Ｃのいずれも実行する必要がないので、秘密計算装置２１Ａ，２１Ｂ，２１Ｃの負荷を大幅に低減することができる。
　なお、本実施形態で追加された秘密計算装置２１Ｃには入力値ｍｎの断片ｔｎが与えられるだけなので、秘密計算装置２１Ｃによって入力値ｍｎの秘匿性が損なわれることはない。
　また、本実施形態では、ＸＯＲを演算子*として用いる例を示したが、本発明はこれに限定されるものではない。例えば、加減算、乗算、その他どのような演算子を演算子*としてもよい。
　また、本実施形態では、各変換装置２０１～２０Ｎによって分割された各断片ｔｎが秘密計算装置２１Ｃに送信される構成であった（ステップＳ２０３）。しかし、各変換装置２０１～２０Ｎによって分割された各断片ｔｎが、まず、秘密計算装置２１Ａに送信され、そこから秘密計算装置２１Ｃに転送される構成であってもよい。また、各変換装置２０１～２０Ｎによって分割された各断片ｔｎが、秘密計算装置２１Ａに送信され、本実施形態のステップＳ２０４，Ｓ２０５の処理を秘密計算装置２１Ａが実行する構成であってもよい。これらの場合であっても、断片ｔｎと断片ｓｎとが秘匿されることなく同一の秘密計算装置に入力されることはないため、入力値ｍｎの秘匿性が損なわれることはない。
　また、本実施形態では、断片ｔｎが入力された秘密計算装置２１ＣがデータＷｉを生成し、生成したデータＷｉを秘密計算装置２１Ｂに送信する構成とした。しかし、秘密計算装置２１ＢがデータＷｉを生成し、生成したデータＷｉを秘密計算装置２１Ｃに送信する構成であってもよい。
　〔第３の実施形態〕
　本実施形態の秘密計算システムは、Ｎ個（Ｎは正の整数）の変換装置と２つの秘密計算装置とからなる。各変換装置はそれぞれ互いに独立な入力値を保持している。本実施形態の秘密計算システムは、各変換装置によって保有された入力値が他の装置に知られることなく、それらの入力値に対する論理回路関数ｆの演算結果を算出する。
　＜構成＞
　図１０は、第３の実施形態の秘密計算システム３の構成を示すブロック図である。また、図１１（Ａ）（Ｂ）は、秘密計算システム３が含む秘密計算装置３１Ａ，３１Ｂの構成を示すブロック図である。
　図１０に示すように、秘密計算システム３は、変換装置２０１～２０Ｎ及び秘密計算装置３１Ａ，３１Ｂ（第１、２の秘密計算装置）を有する。図１１（Ａ）に示すように、秘密計算装置３１Ａは、記憶部３１ＡＡ、入力部３１ＡＢ、出力部３１ＡＣ、ビット秘匿部３１ＡＤ、選択部３１ＡＥ、関数秘匿部３１ＡＦ及び１－ｏｕｔ－ｏｆ－２　ＯＴ実行部３１ＡＧを有する。また、図１１（Ｂ）に示すように、秘密計算装置３１Ｂは、記憶部３１ＢＡ、入力部３１ＢＢ、出力部３１ＢＣ及び秘密計算部３１ＢＦを有する。秘密計算部３１ＢＦは１－ｏｕｔ－ｏｆ－２　ＯＴ実行部３１ＢＦＡを含む。なお、変換装置２０１～２０Ｎの構成は、第２の実施形態で説明したものと同様である（図８）。
　なお、秘密計算装置３１Ａ，３１Ｂの例は、ＣＰＵ、ＲＡＭ、ＲＯＭ、通信装置、入力インタフェース、出力インタフェースなどからなる公知のコンピュータに所定のプログラムが読み込まれて構成された装置である。また、秘密計算装置３１Ａ，３１Ｂが集積回路を含んでもよい。
　＜処理＞
　本実施形態の処理は、前述した本発明の第２態様の一例である。本実施形態では、前処理によって、各変換装置２０1～２０Nの記憶部２０Ａに、それぞれ入力値ｍ１～ｍＮが格納され、秘密計算装置３１Ａの記憶部３１ＡＡに論理回路関数ｆ（ｘ１，・・・，ｘＮ）が格納されている。本実施形態の秘密計算システム３は、各変換装置２０1～２０Nによって保有された入力値ｍ１～ｍＮが他の装置に知られることなく、入力値ｍｎ（１≦ｎ≦Ｎ）を入力とした論理回路関数ｆ（ｘ１，・・・，ｘＮ）の演算結果ｆ（ｍ１，・・・，ｍＮ）を算出する。その際、各秘密計算装置３１Ａ，３１Ｂは、入力値ｍｎを復元することなく、また入力値ｍｎを容易に復元できるデータを得ることなく、演算結果ｆ（ｍ１，・・・，ｍＮ）を求める。
　まず、変換装置２０1は、入力値ｍ１を、演算子*に対してｍ１＝ｓ１*ｔ１を満たす断片ｓ１と断片ｔ１の２つに分割し、断片ｔ１を秘密計算装置３１Ａに送信し、断片ｓ１を秘密計算装置３１Ｂに送信する。他の変換装置２０2～２０Nの動作も変換装置２０1と同様である（ステップＥ３－１）。
　秘密計算装置３１Ａは、論理回路関数ｆ（ｘ）と変換装置２０1～２０Nから送信された断片ｔｎとを用い、論理回路関数ｆ（ｘ）に断片ｔｎが埋め込まれた論理回路関数ｆ（Ｘ１*ｔ１，・・・，ＸＮ*ｔＮ）が秘匿されたデータＴであって、当該データＴと断片ｓｎとから演算結果ｆ（ｍ１，・・・，ｍＮ）を求めることのできるものを生成する。秘密計算装置３１Ａは、データＴを秘密計算装置３１Ｂに送信する（ステップＥ３－２）。
　秘密計算装置３１Ｂには、断片ｓｎとデータＴとが入力される。秘密計算装置３１Ｂは、断片ｓｎとデータＴとを用いて演算結果ｆ（ｍ１，・・・，ｍＮ）を算出する。秘密計算装置１１Ｂは、断片ｓｎを入力として、入力値ｍｎを実際に復元することなく、データＴgから演算結果ｆ（ｍ1，・・・，ｍN）を算出する（ステップＥ３－３、４、５）。
　以下に、本実施形態の秘密計算システム３の動作の具体例を示す。
　図１２は、第３の実施形態の秘密計算システム３の動作の具体例を示すシーケンス図である。
　[ステップＥ３－１]
　各変換装置２０1～２０Nの分割部２０Ｄが、それぞれの記憶部２１Ａに格納された入力値ｍｎを
Figure JPOXMLDOC01-appb-M000067
となるランダムな断片ｓｎ，ｔｎに分割する（ステップＳ３０１）。そして、各変換装置２０1～２０Nの出力部２０Ｃが、断片ｓｎを秘密計算装置３１Ｂに送信し（ステップＳ３０２）、断片ｔｎを秘密計算装置３１Ａにそれぞれ送信する（ステップＳ３０３）。
　[ステップＥ３－２]
　秘密計算装置３１Ａは、以下の（ａ）～（ｄ）を実行することにより、論理回路関数ｆ（ｘ１，・・・，ｘＮ）に断片ｔｎが埋め込まれた論理回路関数ｆ（Ｘ１*ｔ１，・・・，ＸＮ*ｔＮ）を秘匿する。なお、この例の論理回路関数ｆ（ｘ１，・・・，ｘＮ）に断片ｔｎが埋め込まれた論理回路関数ｆ（Ｘ１*ｔ１，・・・，ＸＮ*ｔＮ）は、断片Ｘ＝ｓｎを入力としてｍｎ＝Ｘｎ*ｔｎを復元する関数ｍｎ＝Ｘｎ*ｔｎと、論理回路関数ｆ（ｘ１，・・・，ｘＮ）とを含み、論理回路関数ｆ（ｘ１，・・・，ｘＮ）に各関数ｍｎ＝Ｘｎ*ｔｎの出力値ｍｎを入力してｆ（ｍ１，・・・，ｍＮ）を出力する関数である。以下では、このような論理回路関数ｆ（Ｘ１*ｔ１，・・・，ＸＮ*ｔＮ）を構成する各論理ゲートを秘匿する。
（ａ）秘密計算装置３１Ａのビット秘匿部３１ＡＤが、論理回路関数ｆ（ｓ１*Ｘ１，・・・，ｓＮ*ＸＮ）を構成する各論理ゲートの各ワイヤーｉに対して、固定長の乱数
Figure JPOXMLDOC01-appb-M000068
を生成し、それぞれ０，１に対応させる。
（ｂ）　秘密計算装置３１Ａのビット秘匿部３１ＡＤは、ランダムビットｃi∈｛０，１｝を生成する。
（ｃ）　秘密計算装置３１Ａのビット秘匿部３１ＡＤは、
Figure JPOXMLDOC01-appb-M000069
をワイヤーｉに対応させる。ただし、断片ｔｎの下位ｗ番目のビットに対応する入力ワイヤーｉには、
Figure JPOXMLDOC01-appb-M000070
を対応させる。ここでｂwは、断片ｔｎの下位ｗ番目のビットである。
（ｄ）　秘密計算装置３１Ａの関数秘匿部３１ＡＦが、ｉ，ｊを入力ワイヤー、ｋを出力ワイヤーとする論理ゲートｇに対して、４つのラベル付きデータ
Figure JPOXMLDOC01-appb-M000071
を生成し、それらをランダムな順番に並べたデータＴgを生成する。Ｔgの集合Ｔが論理回路関数ｆ（Ｘ１*ｔ１，・・・，ＸＮ*ｔＮ）を秘匿化したデータとなる（ステップＳ３０４）。
　秘密計算装置３１Ａの出力部３１ＡＣは、Ｔgの集合Ｔを論理回路関数ｆ（Ｘ１*ｔ１，・・・，ＸＮ*ｔＮ）の秘匿化データとして秘密計算装置３１Ｂに送信する（ステップＳ３０５）。
　[ステップＥ３－３]
　秘密計算装置３１Ｂの入力部３１ＢＢには、各変換装置２０1～２０Nから送信された断片ｓｎが入力されている。秘密計算装置３１Ｂの秘密計算部３１ＢＤは、これらの断片ｓｎを用い、断片ｓｎの各ビットｂに対応する
Figure JPOXMLDOC01-appb-M000072
を求める。しかしながら、Ｗｉ ｂやｃｉは秘密計算装置３１Ａで設定されたものであり、秘密計算装置３１Ｂのみでは、断片ｓｎの各ビットｂに対応するＷｉ ｂやｃｉを設定できない。一方、断片ｓｎの各ビットｂに対応するＷｉ ｂやｃｉを秘密計算装置３１Ａから得るために、秘密計算装置３１Ａに断片ｓｎの各ビットｂの情報を与えたのでは、秘密計算装置３１Ａに入力値ｍｎが復元されてしまう。よって、秘密計算装置３１Ｂの秘密計算部３１ＢＤが具備する１－ｏｕｔ－ｏｆ－２　ＯＴ実行部３１ＢＤＡは、秘密計算装置３１Ａの１－ｏｕｔ－ｏｆ－２　ＯＴ実行部３１ＡＧとの間で１－ｏｕｔ－ｏｆ－２　Ｏｂｌｉｖｉｏｕｓ　Ｔｒａｎｓｆｅｒプロトコルを実行し、秘密計算装置３１Ａに断片ｓｎの各ビットｂの情報を与えることなく、秘密計算装置３１Ａから断片ｓｎの各ビットｂに対応するＷｉ ｂやｃｉを取得する。以下、この処理の一例を示す。
　[１－ｏｕｔ－ｏｆ－２　Ｏｂｌｉｖｉｏｕｓ　Ｔｒａｎｓｆｅｒプロトコルの例]
　《パラメータ設定》
　１－ｏｕｔ－ｏｆ－２　ＯＴ実行部３１ＢＤＡと１－ｏｕｔ－ｏｆ－２　ＯＴ実行部３１ＡＧとは、協力して素数ｐを生成し、ｈq≡１（ｍｏｄ　ｐ）を満たす２以上ｐ未満の整数ｈおよび最小の自然数ｑを求める。また、これらは、別に２以上ｐ未満の整数ｚを選ぶ。このように設定された素数ｐ，自然数ｑ，整数ｈ，整数ｚは、例えば、秘密計算装置３１Ａの記憶部３１ＡＡと秘密計算装置３１Ｂの記憶部３１ＢＡとに格納される。
　《秘密鍵設定》
　１－ｏｕｔ－ｏｆ－２　ＯＴ実行部３１ＢＤＡが、ｑ未満の自然数ｕをランダムに選ぶ。この自然数ｕは秘密鍵である。
　《公開鍵設定》
　１－ｏｕｔ－ｏｆ－２　ＯＴ実行部３１ＢＤＡが、ｑ未満の自然数ｕをランダムに選ぶ。この自然数ｕは秘密鍵である。ＰＫb＝ｈuｍｏｄ　ｐを計算する。このＰＫbは公開鍵であり、秘密鍵ｕで暗号化された暗号文はＰＫbによって正しく復号できる。
　《公開鍵の改変》
　１－ｏｕｔ－ｏｆ－２　ＯＴ実行部３１ＢＤＡは、ｂ＝１であれば
Figure JPOXMLDOC01-appb-M000073
を計算する。
　《公開鍵の送信》
　秘密計算装置３１Ｂの出力部３１ＢＣは、ＰＫ0を秘密計算装置３１Ａに送信する。なお、ｂ＝０であればＰＫ0は自然数ｕに対応する正しい公開鍵である。一方、ｂ＝１であればＰＫ0は自然数ｕに対応する正しい公開鍵ではなく、かつ、ＰＫ1＝ｚ／ＰＫ0ｍｏｄ　ｐによって得られるＰＫ1が自然数ｕに対応する正しい公開鍵となる。
　《暗号化》
　秘密計算装置３１Ａの１－ｏｕｔ－ｏｆ－２　ＯＴ実行部３１ＡＧは、送信されたＰＫ0を用いてＰＫ1＝ｚ／ＰＫ0ｍｏｄ　ｐを計算した後、
Figure JPOXMLDOC01-appb-M000074
を計算する。秘密計算装置３１Ａの出力部３１ＡＣは、得られた暗号文Ｚ0，Ｚ1を秘密計算装置３１Ｂに送信する。ここでＥPK（ｘ）は平文ｘの公開鍵ＰＫを用いた暗号化関数であるとし、その暗号文は復号鍵ｕにより復号できるものとする。またＣは平文が正しく復元できたか識別可能な関数である。なお、秘密計算装置３１Ａは、ＰＫ0及びＰＫ1の何れが自然数ｕに対応する正しい公開鍵であることを知ることはできない。そのため、秘密計算装置３１Ａは、秘密計算装置３１Ａがビットｂ＝0に対応するデータを取得しようとしているのか、ビットｂ＝１に対応するデータを取得しようとしているのかを知ることができない。
　《復号》
　秘密計算装置３１Ｂの１－ｏｕｔ－ｏｆ－２　ＯＴ実行部３１ＢＤＡは、復号鍵ｕを用いてＺ0，Ｚ1を復号し、正しく復元されているとＣにより識別される復号結果
Figure JPOXMLDOC01-appb-M000075
を得る。すなわち、ｂ＝０であればＰＫ0が自然数ｕに対応する正しい公開鍵であるためＺ0のみが正しく復元され、ｂ＝１であればＰＫ1が自然数ｕに対応する正しい公開鍵であるためＺ1のみが正しく復元される（ステップＳ３０６）。
　[ステップＥ３－４]
　秘密計算装置３１Ｂの入力部３１ＢＢには、データＴgの集合Ｔと
Figure JPOXMLDOC01-appb-M000076
が入力される。秘密計算装置３１Ｂの秘密計算部３１ＢＤは、Ｔgおよび
Figure JPOXMLDOC01-appb-M000077
を用いて、論理回路関数ｆの最終段の論理ゲートｇのワイヤーの出力
Figure JPOXMLDOC01-appb-M000078
を得る。
　[ステップＥ３－５]
　秘密計算装置３１Ｂの秘密計算部３１ＢＤは、
Figure JPOXMLDOC01-appb-M000079
から、演算結果ｆ（ｍ1，・・・，ｍN）のビット
Figure JPOXMLDOC01-appb-M000080
を得る（ステップＳ３０７）。
　本実施形態によれば、変換装置２０1～２０Nは、保有しているデータｍｎをｓｎとｔｎに分割し、ｓｎを秘密計算装置３１Ｂに送り、ｔｎを秘密計算装置３１Ａに送るだけでよく、ｐｒｏｘｙ　１－ｏｕｔ－ｏｆ－２　Ｏｂｌｉｖｉｏｕｓ　Ｔｒａｎｓｆｅｒプロトコルを実行する必要はない。よって、これが必要な非特許文献３に開示された方法に比べて、変換装置２０１～２０Ｎの負荷が低減される。
　なお、本実施形態では、秘密計算装置３１Ｂが、ステップＳ３０６で、断片ｓｎの各ビットｂに対応するデータとして、各ビットｂの秘匿データ
Figure JPOXMLDOC01-appb-M000081
を取得する例を示した。
　しかし、秘密計算装置３１Ｂが、断片ｓｎの各ビットｂに対応するデータとして、入力値ｍｎ＝ｓｎ*ｔｎの各ビットｒに対応する秘匿データを取得する構成であってもよい。このような構成は、例えば、演算子*がＸＯＲであるならば、上述のＺ０，Ｚ１の代わりに以下のＺ０，Ｚ１を用いることで実現できる。なお、ｖは断片ｔｎのビットを示す。
Figure JPOXMLDOC01-appb-M000082
　これは、断片ｓｎのビットｂが０であれば、それと同じ桁の入力値ｍｎ＝ｓｎ*ｔｎのビットｒは、それと同じ桁の断片ｔｎのビットｖと等しくなるし、断片ｓｎのビットｂが１であれば、それと同じ桁の入力値ｍｎ＝ｓｎ*ｔｎのビットｒは、それと同じ桁の断片ｔｎのビットｖの反転ビットとなることに基づく。この場合、秘密計算装置３１Ｂは、
Figure JPOXMLDOC01-appb-M000083
の何れかを得る。これに応じたデータＴgの集合Ｔが設定してあれば、これらから演算結果ｆ（ｍ1，・・・，ｍN）の演算結果を得ることができる。
　また、本実施形態では、ＸＯＲを演算子*として用いる例を示したが、本発明はこれに限定されるものではない。例えば、加減算、乗算、その他どのような演算子を演算子*としてもよい。
　〔第４の実施形態〕
　本実施形態の秘密計算システムは、Ｎ個（Ｎは正の整数）の変換装置と２つの秘密計算装置とからなる。各変換装置はそれぞれ互いに独立な入力値を保持している。本実施形態の秘密計算システムは、各変換装置によって保有された入力値が他の装置に知られることなく、それらの入力値に対する論理回路関数ｆの演算結果を算出する。ただし、本実施形態では、１－ｏｕｔ－ｏｆ－２　Ｏｂｌｉｖｉｏｕｓ　Ｔｒａｎｓｆｅｒプロトコルを用いない。
　＜構成＞
　図１３は、第４の実施形態の秘密計算システム４の構成を示すブロック図である。また、図１４（Ａ）（Ｂ）は、秘密計算システム４が含む秘密計算装置４１Ａ，４１Ｂの構成を示すブロック図である。また、図１５は、秘密計算システム４が含む変換装置４０１～４０Ｎの構成を示すブロック図である。なお、変換装置４０１～４０Ｎを総称して変換装置４０と呼ぶ。
　図１３に示すように、秘密計算システム４は、変換装置４０１～４０Ｎ及び秘密計算装置４１Ａ，４１Ｂ（第１、２の秘密計算装置）を有する。図１４（Ａ）に示すように、秘密計算装置４１Ａは、記憶部４１ＡＡ、入力部４１ＡＢ、出力部４１ＡＣ、ビット秘匿部４１ＡＤ及び関数秘匿部４１ＡＦを有する。また、図１４（Ｂ）に示すように、秘密計算装置４１Ｂは、記憶部４１ＢＡ、入力部４１ＢＢ、出力部４１ＢＣ及び秘密計算部４１ＢＦを有する。また、図１５示すように、変換装置４０は、記憶部４０Ａ、入力部４０Ｂ、出力部４０Ｃ、ビット秘匿部４０Ｄ及び選択部４０Ｅを有する。
　なお、秘密計算装置４１Ａ，４１Ｂ及び変換装置４０の例は、ＣＰＵ、ＲＡＭ、ＲＯＭ、通信装置、入力インタフェース、出力インタフェースなどからなる公知のコンピュータに所定のプログラムが読み込まれて構成された装置である。また、秘密計算装置３１Ａ，３１Ｂ及び変換装置４０が集積回路を含んでもよい。
　＜処理＞
　本実施形態の処理は、前述した本発明の第２態様の一例である。本実施形態では、前処理によって、各変換装置４０1～４０Nの記憶部４０Ａに、それぞれ入力値ｍ１～ｍＮが格納され、秘密計算装置４１Ａの記憶部４１ＡＡに論理回路関数ｆ（ｘ１，・・・，ｘＮ）が格納されている。本実施形態の秘密計算システム４は、各変換装置４０1～４０Nに保有された入力値ｍ１～ｍＮが他の装置に知られることなく、入力値ｍｎ（１≦ｎ≦Ｎ）を入力とした論理回路関数ｆ（ｘ１，・・・，ｘＮ）の演算結果ｆ（ｍ１，・・・，ｍＮ）を算出する。その際、各秘密計算装置４１Ａ，４１Ｂは、入力値ｍｎを復元することなく、また入力値ｍｎを容易に復元できるデータを得ることなく、演算結果ｆ（ｍ１，・・・，ｍＮ）を求める。また、これらの処理の過程で１－ｏｕｔ－ｏｆ－２　Ｏｂｌｉｖｉｏｕｓ　Ｔｒａｎｓｆｅｒプロトコルを実行する必要はない。
　まず、変換装置４０１～４０Ｎが、各入力値ｍ１～ｍＮの各ビットｂに対応したデータＷｂと、各ビットｂに対する反転ビット（１－ｂ）に対応したデータＷ（１－ｂ）とを生成する。そして、変換装置４０１～４０Ｎは、各入力値ｍ１～ｍＮを分割した一方の断片としてデータＷｂを秘密計算装置４１Ｂに送信する。また、変換装置４０１～４０Ｎは、データＷｂと各ビットｂの反転ビット（１－ｂ）に対応した各データＷ（１－ｂ）とを、データＷｂ及びデータＷ（１－ｂとｂ及び（１－ｂ）との対応を特定せずに含むデータＷを他方の断片として秘密計算装置４１Ａに送信する（ステップＥ４－１）。
　秘密計算装置４１Ａは、データＷを用い、論理回路関数ｆが秘匿されたデータＴであって当該データＴとデータＷｂとを用いて演算結果ｆ（ｍ）を求めることのできるものを生成する。秘密計算装置４１Ａは、生成したデータＴを秘密計算装置４１Ｂに送信する（ステップＥ４－２）。
　秘密計算装置１１Ａには、データＴとデータＷｂとが入力される。秘密計算装置１１Ａは、データＴとデータＷｂとを用いて演算結果ｆ（ｍ）を算出する（ステップＥ４－３，４，５）。
　以下に、本実施形態の秘密計算システム４の動作の具体例を示す。
　図１６は、第４の実施形態の秘密計算システム４の動作の具体例を示すシーケンス図である。
　[ステップＥ４－１]
　各変換装置４０１～４０Ｎのビット秘匿部４０Ｄが、論理回路関数ｆ（ｘ１，・・・，ｘＮ）を構成する各論理ゲートのうち、各入力値ｍ１～ｍＮのビットｂが入力される各入力ワイヤーｉに対して、ランダムビットｃi及び固定長の乱数
Figure JPOXMLDOC01-appb-M000084
を生成する。そして、各変換装置４０ｎの秘匿部４０Ｄは、
　　Ｗｎ＝（ｃｉ，Ｗｉ ０，Ｗｉ １）ｎ
を生成し（データＷの例／ステップＳ４０１）、各変換装置４０ｎの選択部４０Ｅは、各ビットｂに対応する
Figure JPOXMLDOC01-appb-M000085
を生成する（データＷｂの例／ステップＳ４０２）。各変換装置４０ｎの出力部４０ＣはＷｎを秘密計算装置４１Ｂに送信し（ステップＳ４０３）、
Figure JPOXMLDOC01-appb-M000086
を秘密計算装置４１Ａに送信する（ステップＳ４０４）。
　[ステップＥ４－２]
　秘密計算装置４１Ａの関数秘匿部４１ＡＦは、上述したステップＥ３－２と同様に、（ａ）～（ｄ）を実行することにより、論理回路関数ｆ（ｘ１，・・・，ｘＮ）を構成する各論理ゲートが秘匿されたＴgの集合Ｔを生成する。ただし、入力値ｍ１～ｍＮの各ビットの入力ワイヤーｉには、
Figure JPOXMLDOC01-appb-M000087
を対応させる（ステップＳ４０５）。
　秘密計算装置４１Ａの出力部４１ＡＣは、Ｔgの集合Ｔを論理回路関数ｆ（ｘ１，・・・，ｘＮ）の秘匿化データとして秘密計算装置４１Ｂに送信する（ステップＳ４０６）。
　[ステップＥ４－３]
　秘密計算装置４１Ｂの入力部４１ＢＦには、データＴgの集合Ｔと

が入力される。秘密計算装置４１Ｂの秘密計算部４１ＢＦは、Ｔgおよび
Figure JPOXMLDOC01-appb-M000089
を用いて、論理回路関数ｆの最終段の論理ゲートｇのワイヤーの出力
Figure JPOXMLDOC01-appb-M000090
を得る。
　[ステップＥ４－５]
　秘密計算装置４１Ｂの秘密計算部４１ＢＤは、
Figure JPOXMLDOC01-appb-M000091
から、演算結果ｆ（ｍ1，・・・，ｍN）のビット
Figure JPOXMLDOC01-appb-M000092
を得る（ステップＳ４０７）。
　この例によれば、１－ｏｕｔ－ｏｆ－２　Ｏｂｌｉｖｉｏｕｓ　Ｔｒａｎｓｆｅｒプロトコルを実行する必要が無いので、第３の実施形態と比べて、秘密計算装置４１Ａ，４１Ｂの処理が軽減される。
　また、各変換装置４０ｎから秘密計算装置４１Ａに送信される
　　　Ｗｎ＝（ｃｉ，Ｗｉ ０，Ｗｉ １）ｎ
には、入力値ｍｎに関する情報が含まれていない。また、各変換装置４０ｎから秘密計算装置４１Ｂに送信される
Figure JPOXMLDOC01-appb-M000093
は、入力値ｍｎのビットｂがランダムビットｃiでマスクされているため、入力値ｍｎに関する有意な情報とはならない。したがって、秘密計算装置４１Ａ，４１Ｂは自身の受信した情報からだけでは、入力値ｍｎに関する有意な情報を得ることができず、入力値ｍｎの秘匿性が確保される。
　〔変形例等〕
　なお、本発明は上述の実施の形態に限定されるものではない。例えば、入力値や断片が埋め込まれた論理回路関数の構成方法は上述のものには限定されない。また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、本明細書においてシステムとは、複数の装置の論理的集合構成である。また、各装置の構成が同一筐体内にあるとは限らない。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
　また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
　この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
　また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ－ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
　このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
　本発明は、例えば、プライバシーを保護しつつ個人的な情報を活用する様々なシステムに適用できる。例えば、本発明は、オークションを含む任意の情報集計システムに利用できる。この場合、各ユーザーが保有するデータを漏洩させることなく、オークション結果や多数決による意思決定の結果などを演算結果として得ることができる。また、本発明の他の適用例は、例えば、各ユーザーが保有するデータを他者に知られること無く集計し、それらのデータを元にした各種統計処理やマイニング処理を行うシステムである。更に他の例として、本発明を生体認証システムに利用することも可能である。この場合には、各ユーザーの生体情報が秘匿されたままで、生体情報が正当なものであるかを否か判定できる。

Claims (25)

  1. 　第１の入力値ｍＡが秘匿されたままで、当該第１の入力値ｍＡに対する論理回路関数ｆの演算結果ｆ（ｍＡ）を算出する秘密計算システムであって、
    　第１の秘密計算装置と、前記論理回路関数ｆを格納した第２の秘密計算装置と、第３の秘密計算装置とを有し、
    　前記第３の秘密計算装置は、
    　前記第１の入力値ｍＡ及び演算子*に対してｍＡ＝ｓ*ｔを満たす断片ｔの各ビットｂに対応した各データＷｂと、前記各ビットｂの各反転ビット（１－ｂ）に対応した各データＷ（１－ｂ）とを生成する手段と、
    　前記データＷｂを前記第１の秘密計算装置に送信する手段と、
    　前記ビットｂ及び反転ビット（１－ｂ）と前記データＷｂ及び前記データＷ（１－ｂ）との対応を特定せずに、前記データＷｂ及び前記データＷ（１－ｂ）を含むデータＷを前記第２の秘密計算装置に送信する手段と、を含み、
    　前記第２の秘密計算装置は、
    　ｍＡ＝ｓ*ｔを満たす断片ｓと前記論理回路関数ｆと前記データＷとを用い、前記論理回路関数ｆに前記断片ｓが埋め込まれた論理回路関数ｆ（ｓ*Ｘ）が秘匿されたデータＴであって、当該データＴと前記データＷｂとから前記演算結果ｆ（ｍＡ）を求めることができるものを生成する手段と、
    　前記データＴを前記第１の秘密計算装置に送信する手段と、を含み、
    　前記第１の秘密計算装置は、
    　前記データＴと前記データＷｂとが入力される手段と、
    　前記データＴと前記データＷｂとを用いて前記演算結果ｆ（ｍＡ）を算出する手段と、を含む。
  2. 　請求項１の秘密計算システムであって、
    　前記第１の秘密計算装置は、
    　前記第１の入力値ｍＡを格納する手段と、
    　前記第１の入力値ｍＡを、ｍＡ＝ｓ*ｔを満たす前記断片ｓ，ｔに分割する手段と、
    　前記断片ｓを前記第２の秘密計算装置に送信する手段と、
    　前記断片ｔを前記第３の秘密計算装置に送信する手段と、を含む。
  3. 　請求項１又は２の秘密計算システムであって、
    　前記論理回路関数ｆは、２つの入力値を入力とする論理回路関数ｆ（ｘ，ｙ）であり、
    　前記第２の秘密計算装置は、第２の入力値ｍＢを格納する手段を含み、
    　前記データＴを生成する手段は、前記断片ｓと前記論理回路関数ｆ（ｘ，ｙ）と前記データＷと前記入力値ｍＢを用い、前記論理回路関数ｆ（ｘ，ｙ）に前記断片ｓと前記入力値ｍＢとが埋め込まれた論理回路関数ｆ（ｓ*Ｘ，ｍＢ）が秘匿されたデータＴであって、当該データＴと前記データＷｂとから前記第１の入力値ｍＡ及び前記第２の入力値ｍＢに対する前記論理回路関数ｆ（ｘ，ｙ）の演算結果ｆ（ｍＡ，ｍＢ）を求めることができるものを生成する手段を含み、
    　前記演算結果ｆ（ｍＡ）を算出する手段は、
    　前記データＴと前記データＷｂとを用いて前記演算結果ｆ（ｍＡ，ｍＢ）を算出する手段を含む。
  4. 　請求項１の秘密計算システムであって、
    　前記第１の入力値ｍＡを、ｍＡ＝ｓ*ｔを満たす前記断片ｓ，ｔに分割する手段と、
    　前記断片ｓを前記第２の秘密計算装置に送信する手段と、
    　前記断片ｔを前記第３の秘密計算装置に送信する手段と、を含む変換装置を更に有する。
  5. 　秘密計算装置であって、
    　１の入力値ｍＡ及び演算子*に対してｍＡ＝ｓ*ｔを満たす断片ｔが入力される手段と、
    　前記断片ｔの各ビットｂに対応した各データＷｂと、前記各ビットｂの各反転ビット（１－ｂ）に対応した各データＷ（１－ｂ）とを生成する手段と、
    　前記データＷｂを、前記第１の入力値ｍＡに対する論理回路関数ｆの演算結果ｆ（ｍＡ）を算出する他の秘密計算装置に送信する手段と、
    　前記ビットｂ及び反転ビット（１－ｂ）と前記データＷｂ及び前記データＷ（１－ｂ）との対応を特定せずに、前記データＷｂ及び前記データＷ（１－ｂ）を含むデータＷを、ｍＡ＝ｓ*ｔを満たす断片ｓが入力された他の秘密計算装置に送信する手段と、を有する。
  6. 　秘密計算装置であって、
    　１の入力値ｍＡ及び演算子*に対してｍＡ＝ｓ*ｔを満たす断片ｓが入力される手段と、
    　前記断片ｓと論理回路関数ｆとデータＷとを用い、当該論理回路関数ｆに前記断片ｓが埋め込まれた論理回路関数ｆ（ｓ*Ｘ）が秘匿されたデータＴであって、当該データＴと前記データＷｂとから前記第１の入力値ｍＡに対する前記論理回路関数ｆの演算結果ｆ（ｍＡ）を求めることができるものを生成する手段と、
    　前記データＴを、前記演算結果ｆ（ｍＡ）を算出する他の秘密計算装置に送信する手段と、を有する。
  7. 　第１、第２、及び第３の秘密計算装置により、第１の入力値ｍＡが秘匿されたままで、当該第１の入力値ｍＡに対する論理回路関数ｆの演算結果ｆ（ｍＡ）を算出する秘密計算方法であって、
    　(A) 前記第３の秘密計算装置において、前記第１の入力値ｍＡ及び演算子*に対してｍＡ＝ｓ*ｔを満たす断片ｔの各ビットｂに対応した各データＷｂと、前記各ビットｂの各反転ビット（１－ｂ）に対応した各データＷ（１－ｂ）とを生成するステップと、
    　(B) 前記第３の秘密計算装置において、前記データＷｂを前記第１の秘密計算装置に送信するステップと、
    　(C) 前記第３の秘密計算装置において、前記ビットｂ及び反転ビット（１－ｂ）と前記データＷｂ及び前記データＷ（１－ｂ）との対応を特定せずに、前記データＷｂ及び前記データＷ（１－ｂ）を含むデータＷを前記第２の秘密計算装置に送信するステップと、
    　(D) 前記第２の秘密計算装置において、ｍＡ＝ｓ*ｔを満たす断片ｓと当該第２の秘密計算装置に格納された前記論理回路関数ｆと前記データＷとを用い、前記論理回路関数ｆに前記断片ｓが埋め込まれた論理回路関数ｆ（ｓ*Ｘ）が秘匿されたデータＴであって、当該データＴと前記データＷｂとから前記演算結果ｆ（ｍＡ）を求めることができるものを生成すステップと、
    　(E) 前記第２の秘密計算装置において、前記データＴを前記第１の秘密計算装置に送信するステップと、
    　(F) 前記第１の秘密計算装置に前記データＴと前記データＷｂとが入力されるステップと、
    　(G) 前記第１の秘密計算装置において、前記データＴと前記データＷｂとを用いて前記演算結果ｆ（ｍＡ）を算出するステップと、を有する。
  8. 　請求項７の秘密計算方法であって、
    　前記第１の秘密計算装置において、当該第１の秘密計算装置に格納された前記第１の入力値ｍＡを、ｍＡ＝ｓ*ｔを満たす前記断片ｓ，ｔに分割するステップと、
    　前記断片ｓを前記第２の秘密計算装置に送信するステップと、
    　前記断片ｔを前記第３の秘密計算装置に送信するステップと、を有する。
  9. 　請求項７又は８の秘密計算方法であって、
    　前記論理回路関数ｆは、２つの入力値を入力とする論理回路関数ｆ（ｘ，ｙ）であり、
    　前記第２の秘密計算装置には、第２の入力値ｍＢが格納されており、
    　前記ステップ(D)は、前記断片ｓと前記論理回路関数ｆ（ｘ，ｙ）と前記データＷと前記入力値ｍＢとを用い、前記論理回路関数ｆに前記断片ｓと前記入力値ｍＢとが埋め込まれた論理回路関数ｆ（ｓ*Ｘ，ｍＢ）が秘匿されたデータＴであって、当該データＴと前記データＷｂとから前記第１の入力値ｍＡ及び前記第２の入力値ｍＢに対する前記論理回路関数ｆ（ｘ，ｙ）の演算結果ｆ（ｍＡ，ｍＢ）を求めることができるものを生成するステップを含み、
    　前記ステップ(G)は、前記第１の秘密計算装置において、前記データＴと前記データＷｂとを用いて前記演算結果ｆ（ｍＡ，ｍＢ）を算出するステップを含む。
  10. 　入力値ｍが秘匿にされたままで、当該入力値ｍに対する論理回路関数ｆ（ｘ）の演算結果ｆ（ｍ）を算出する秘密計算システムであって、
    　前記論理回路関数ｆ（ｘ）を格納した第１の秘密計算装置と、第２の秘密計算装置とを有し、
    　前記第１の秘密計算装置は、
    　前記入力値ｍから分割された断片Ａと断片Ｂとのうち断片Ｂが入力される手段と、
    　前記論理回路関数ｆ（ｘ）と前記断片Ｂとを用い、前記論理回路関数ｆ（ｘ）が秘匿されたデータＴであって、当該データＴと前記断片Ａとから前記演算結果ｆ（ｍ）を求めることのできるものを生成する手段と、を含み、
    　前記第２の秘密計算装置は、
    　前記断片Ａと前記データＴとが入力される手段と、
    　前記断片Ａと前記データＴとを用いて前記演算結果ｆ（ｍ）を算出する手段と、を含む。
  11. 　請求項１０の秘密計算システムであって、
    　前記断片Ａ、Ｂは、演算子*に対してｍＡ＝ｓ*ｔを満たす断片ｓ，ｔであり、
    　前記データＴを生成する手段は、前記論理回路関数ｆ（ｘ）と前記断片ｔとを用い、前記論理回路関数ｆ（ｘ）に前記断片ｔが埋め込まれた論理回路関数ｆ（Ｘ＊ｔ）が秘匿されたデータＴであって、当該データＴと前記断片ｓとから前記演算結果ｆ（ｍ）を求めることのできるものを生成する手段を含み、
    　前記断片Ａと前記データＴとを用いて前記演算結果ｆ（ｍ）を算出する手段は、前記断片ｓと前記データＴとを用いて前記演算結果ｆ（ｍ）を算出する手段を含む。
  12. 　請求項１１の秘密計算システムであって、
    　前記断片Ａと前記データＴとを用いて前記演算結果ｆ（ｍ）を算出する手段は、前記入力値ｍを復元することなく、前記断片ｓと前記データＴとを用いて前記演算結果ｆ（ｍ）を算出する手段を含む。
  13. 　請求項１２の秘密計算システムであって、
    　前記断片Ａと前記データＴとを用いて前記演算結果ｆ（ｍ）を算出する手段は、
    　前記第１の秘密計算装置との間で１－ｏｕｔ－ｏｆ－２　Ｏｂｌｉｖｉｏｕｓ　Ｔｒａｎｓｆｅｒプロトコルを実行し、前記断片ｓを前記第１の秘密計算装置に知られることなく、前記断片ｓに対応する前記第１の秘密計算装置で設定された秘匿データを取得する手段と、
    　前記秘匿データと前記データＴとを用いて前記演算結果ｆ（ｍ）を算出する手段と、を含む手段である。
  14. 　請求項１１の秘密計算システムであって、
    　前記断片Ａと前記データＴとを用いて前記演算結果ｆ（ｍ）を算出する手段は、
    　前記第１の秘密計算装置との間で１－ｏｕｔ－ｏｆ－２　Ｏｂｌｉｖｉｏｕｓ　Ｔｒａｎｓｆｅｒプロトコルを実行し、前記断片ｓを前記第１の秘密計算装置に知られることなく、前記断片ｓに対応する前記第１の秘密計算装置で設定された秘匿データを取得する手段と、
    　前記秘匿データと前記データＴとを用いて前記演算結果ｆ（ｍ）を算出する手段と、を含む手段である。
  15. 　請求項１１から１４の何れかの秘密計算システムであって、
    　前記入力値ｍを、ｍ＝ｓ*ｔを満たす前記断片ｓ，ｔに分割する手段と、
    　前記断片ｔを前記第１の秘密計算装置に送信する手段と、
    　前記断片ｓを前記第２の秘密計算装置に送信する手段と、
    　を含む変換装置を更に有する。
  16. 　請求項１０の秘密計算システムであって、
    　前記断片Ａは、前記入力値ｍの各ビットｂに対応した各データＷｂであり、
    　前記断片Ｂは、前記データＷｂと前記各ビットｂの反転ビット（１－ｂ）に対応した各データＷ（１－ｂ）とを、前記データＷｂ及び前記データＷ（１－ｂ）とｂ及び（１－ｂ）との対応を特定せずに含むデータＷであり、
    　前記データＴを生成する手段は、前記データＷを用い、論理回路関数ｆが秘匿されたデータＴであって当該データＴと前記データＷｂとを用いて前記演算結果ｆ（ｍ）を求めることのできるものを生成する手段を含み、
    　前記断片Ａと前記データＴとを用いて前記演算結果ｆ（ｍ）を算出する手段は、前記データＷｂと前記データＴとを用いて前記演算結果ｆ（ｍ）を算出する手段を含む。
  17. 　秘密計算装置であって、
    　入力値ｍから分割された断片Ａと断片Ｂとのうち断片Ｂが入力される手段と、
    　論理回路関数ｆ（ｘ）と前記断片Ｂとを用い、前記論理回路関数ｆ（ｘ）が秘匿されたデータＴであって、当該データＴと前記断片Ａとから前記演算結果ｆ（ｍ）を求めることのできるものを生成する手段と、
    　前記断片Ａが入力された他の秘密計算装置に前記データＴを送信する手段と、を有する。
  18. 　入力値ｍが秘匿にされたままで、当該入力値ｍに対する論理回路関数ｆ（ｘ）の演算結果ｆ（ｍ）を算出する秘密計算方法であって、
    　(A) 前記第１の秘密計算装置に、前記入力値ｍから分割された断片Ａと断片Ｂとのうち断片Ｂが入力されるステップと、
    　(B) 前記第１の秘密計算装置において、当該第１の秘密計算装置が格納した前記論理回路関数ｆ（ｘ）と前記断片Ｂとを用い、前記論理回路関数ｆ（ｘ）が秘匿されたデータＴであって、当該データＴと前記断片Ａとから前記演算結果ｆ（ｍ）を求めることのできるものを生成するステップと、
    　(C) 前記第２の秘密計算装置に、前記断片Ａと前記データＴとが入力されるステップと、
    　(D) 前記第２の秘密計算装置において、前記断片Ａと前記データＴとを用いて前記演算結果ｆ（ｍ）を算出するステップと、を有する。
  19. 　請求項１８の秘密計算方法であって、
    　前記断片Ａ、Ｂは、演算子*に対してｍＡ＝ｓ*ｔを満たす断片ｓ，ｔであり、
    　前記ステップ(B)は、前記論理回路関数ｆ（ｘ）と前記断片ｔとを用い、前記論理回路関数ｆ（ｘ）に前記断片ｔが埋め込まれた論理回路関数ｆ（Ｘ＊ｔ）が秘匿されたデータＴであって、当該データＴと前記断片ｓとから前記演算結果ｆ（ｍ）を求めることのできるものを生成するステップを含み、
    　前記ステップ(D)は、前記断片ｓと前記データＴとを用いて前記演算結果ｆ（ｍ）を算出するステップを含む。
  20. 　請求項１８の秘密計算方法であって、
    　前記ステップ(D)は、前記入力値ｍを復元することなく、前記断片ｓと前記データＴとを用いて前記演算結果ｆ（ｍ）を算出するステップを含む。
  21. 　請求項２０の秘密計算方法であって、
    　前記ステップ(D)は、
    　(D-1) 前記第２の秘密計算装置が前記第１の秘密計算装置との間で１－ｏｕｔ－ｏｆ－２　Ｏｂｌｉｖｉｏｕｓ　Ｔｒａｎｓｆｅｒプロトコルを実行し、前記断片ｓを前記第１の秘密計算装置に知られることなく、前記断片ｓに対応する前記第１の秘密計算装置で設定された秘匿データを取得するステップと、
    　(D-2)前記秘匿データと前記データＴとを用いて前記演算結果ｆ（ｍ）を算出するステップと、を含む。
  22. 　請求項１９の秘密計算方法であって、
    　前記ステップ(D)は、
    　(D-1) 前記第２の秘密計算装置が前記第１の秘密計算装置との間で１－ｏｕｔ－ｏｆ－２　Ｏｂｌｉｖｉｏｕｓ　Ｔｒａｎｓｆｅｒプロトコルを実行し、前記断片ｓを前記第１の秘密計算装置に知られることなく、前記断片ｓに対応する前記第１の秘密計算装置で設定された秘匿データを取得するステップと、
    　(D-2)前記秘匿データと前記データＴとを用いて前記演算結果ｆ（ｍ）を算出するステップと、を含む。
  23. 　請求項１９から２２の何れかの秘密計算方法であって、
    　変換装置において、前記入力値ｍを、ｍ＝ｓ*ｔを満たす前記断片ｓ，ｔに分割するステップと、
    　前記変換装置において、前記断片ｔを前記第１の秘密計算装置に送信するステップと、
    　前記変換装置において、前記断片ｓを前記第２の秘密計算装置に送信するステップと、を更に有する。
  24. 　請求項１９の秘密計算方法であって、
    　前記断片Ａは、前記入力値ｍの各ビットｂに対応した各データＷｂであり、
    　前記断片Ｂは、前記データＷｂと前記各ビットｂの反転ビット（１－ｂ）に対応した各データＷ（１－ｂ）とを、前記データＷｂ及び前記データＷ（１－ｂ）とｂ及び（１－ｂ）との対応を特定せずに含むデータＷであり、
    　前記ステップ(B)は、前記データＷを用い、論理回路関数ｆが秘匿されたデータＴであって当該データＴと前記データＷｂとを用いて前記演算結果ｆ（ｍ）を求めることのできるものを生成するステップを含み、
    　前記ステップ(D)は、前記データＷｂと前記データＴとを用いて前記演算結果ｆ（ｍ）を算出するステップを含む。
  25. 　請求項５、６、１７の何れかの秘密計算装置としてコンピュータを機能させるためのプログラム。
PCT/JP2009/050857 2008-01-21 2009-01-21 秘密計算システム Ceased WO2009093603A1 (ja)

Priority Applications (3)

Application Number Priority Date Filing Date Title
CN200980102192.4A CN101911153B (zh) 2008-01-21 2009-01-21 秘密计算系统、秘密计算方法、秘密计算装置
EP09703675.0A EP2242032B1 (en) 2008-01-21 2009-01-21 Secure computing system, secure computing method, secure computing apparatus and program therefor
US12/812,916 US9300469B2 (en) 2008-01-21 2009-01-21 Secure computing system, secure computing method, secure computing apparatus, and program therefor

Applications Claiming Priority (4)

Application Number Priority Date Filing Date Title
JP2008-010929 2008-01-21
JP2008010929 2008-01-21
JP2008-010928 2008-01-21
JP2008010928A JP5078632B2 (ja) 2008-01-21 2008-01-21 秘密計算システム、秘密計算方法、および秘密計算プログラム

Publications (1)

Publication Number Publication Date
WO2009093603A1 true WO2009093603A1 (ja) 2009-07-30

Family

ID=40901111

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2009/050857 Ceased WO2009093603A1 (ja) 2008-01-21 2009-01-21 秘密計算システム

Country Status (4)

Country Link
US (1) US9300469B2 (ja)
EP (1) EP2242032B1 (ja)
CN (1) CN101911153B (ja)
WO (1) WO2009093603A1 (ja)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2009199068A (ja) * 2008-01-21 2009-09-03 Nippon Telegr & Teleph Corp <Ntt> 秘密計算システム、秘密計算方法、秘密計算装置、検証装置、およびプログラム
WO2017038761A1 (ja) * 2015-08-31 2017-03-09 日本電気株式会社 秘密計算システム、秘密計算装置、および、秘密計算方法

Families Citing this family (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN103392197B (zh) * 2011-03-04 2016-04-13 日本电信电话株式会社 代理计算系统、方法、委托装置
JP2015108807A (ja) * 2013-10-23 2015-06-11 株式会社インテック データ秘匿型統計処理システム、統計処理結果提供サーバ装置及びデータ入力装置、並びに、これらのためのプログラム及び方法
JP6006842B1 (ja) * 2015-07-22 2016-10-12 日本電信電話株式会社 秘密計算装置、その方法、およびプログラム
JP6034927B1 (ja) * 2015-07-27 2016-11-30 日本電信電話株式会社 秘密計算システム、秘密計算装置、およびプログラム
JP7067632B2 (ja) * 2018-10-04 2022-05-16 日本電信電話株式会社 秘密シグモイド関数計算システム、秘密ロジスティック回帰計算システム、秘密シグモイド関数計算装置、秘密ロジスティック回帰計算装置、秘密シグモイド関数計算方法、秘密ロジスティック回帰計算方法、プログラム
CN109766705B (zh) * 2018-12-10 2021-03-19 北京链化未来科技有限公司 一种基于电路的数据验证方法、装置及电子设备
US12585766B2 (en) * 2024-01-22 2026-03-24 Hewlett Packard Enterprise Development Lp Intermittent encryption attack

Family Cites Families (23)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4656633A (en) * 1985-03-15 1987-04-07 Dolby Laboratories Licensing Corporation Error concealment system
US5295188A (en) * 1991-04-04 1994-03-15 Wilson William J Public key encryption and decryption circuitry and method
DE19921122C1 (de) * 1999-05-07 2001-01-25 Fraunhofer Ges Forschung Verfahren und Vorrichtung zum Verschleiern eines Fehlers in einem codierten Audiosignal und Verfahren und Vorrichtung zum Decodieren eines codierten Audiosignals
US6834272B1 (en) * 1999-08-10 2004-12-21 Yeda Research And Development Company Ltd. Privacy preserving negotiation and computation
US6990468B1 (en) * 2000-06-19 2006-01-24 Xerox Corporation System, method and article of manufacture for cryptoserver-based auction
US7181017B1 (en) * 2001-03-23 2007-02-20 David Felsher System and method for secure three-party communications
US7844496B2 (en) * 2003-05-05 2010-11-30 International Business Machines Corporation Method and system for processing a request of a customer
US7290150B2 (en) * 2003-06-09 2007-10-30 International Business Machines Corporation Information integration across autonomous enterprises
JP4006403B2 (ja) * 2004-01-21 2007-11-14 キヤノン株式会社 ディジタル署名発行装置
JPWO2005098795A1 (ja) * 2004-03-31 2008-02-28 松下電器産業株式会社 コンピュータシステム、コンピュータプログラム及び加算方法
JP4666943B2 (ja) * 2004-04-23 2011-04-06 株式会社エヌ・ティ・ティ・ドコモ Ｉｄタグ、タグリーダ、ｉｄタグセキュリティシステム及びｉｄタグ送信復元方法
US8132006B2 (en) * 2005-05-03 2012-03-06 Ntt Docomo, Inc. Cryptographic authentication and/or establishment of shared cryptographic keys, including, but not limited to, password authenticated key exchange (PAKE)
JP4818651B2 (ja) * 2005-07-13 2011-11-16 ルネサスエレクトロニクス株式会社 暗号化・復号化回路
WO2008048713A2 (en) * 2006-05-05 2008-04-24 President And Fellows Of Harvard College Practical secrecy-preserving, verifiably correct and trustworthy auctions
US7685115B2 (en) * 2006-07-21 2010-03-23 Mitsubishi Electronic Research Laboratories, Inc. Method for classifying private data using secure classifiers
WO2008127446A2 (en) * 2006-12-01 2008-10-23 President And Fellows Of Harvard College A method and apparatus for time-lapse cryptography
US8752032B2 (en) * 2007-02-23 2014-06-10 Irdeto Canada Corporation System and method of interlocking to protect software-mediated program and device behaviours
US8271796B2 (en) * 2008-05-12 2012-09-18 Telecommunications Research Laboratory Apparatus for secure computation of string comparators
US20100150349A1 (en) * 2008-12-12 2010-06-17 Electronics And Telecommunications Research Institute Method and system for performing quantum bit commitment protocol
US8549290B2 (en) * 2009-04-24 2013-10-01 Nippon Telegraph And Telephone Corporation Secret sharing system, sharing apparatus, share management apparatus, acquisition apparatus, processing methods thereof, secret sharing method, program, and recording medium
US8311213B2 (en) * 2009-12-07 2012-11-13 Mitsubishi Electric Research Laboratories, Inc. Method for determining functions applied to signals
US8416955B2 (en) * 2009-12-07 2013-04-09 Mitsubishi Electric Research Laboratories, Inc. Method for determining functions applied to signals
US8539220B2 (en) * 2010-02-26 2013-09-17 Microsoft Corporation Secure computation using a server module

Non-Patent Citations (6)

* Cited by examiner, † Cited by third party
Title
"Proceedings of the 28th Symposium on Information Theory and Its Applications, 20 November, 2005 (20.11.05)", vol. II OF II, article URARA SHINMYO ET AL: "Bunsan Server ni Motozuku Oblivious Transfer o Mochiita Denshi Shimon Gijutsu", pages: 705 - 708, XP008132530 *
CLAUDE CREPEAU ET AL: "Committed Oblivious Transfer and Private Multi-Party Computation", LECTURE NOTES IN COMPUTER SCIENCE, vol. 963, 16 October 1995 (1995-10-16), pages 110 - 123, XP000533636 *
HOSSEIN GHODOSI ET AL: "Comments on the 'm out of n oblivious transfer.", INFORMATION PROCESSING LETTERS, vol. 97, no. 4, 28 February 2006 (2006-02-28), pages 153 - 155, XP005224701 *
KOJI CHIDA ET AL: "Privacy Preserving Computations without Public Key Cryptographic Operation", LNCS, vol. 5312, 24 February 2009 (2009-02-24), pages 184 - 200, XP019112014 *
S. EVEN; O. GOLDREICH; A. LEMPEL: "A randomized protocol for signing contracts", COMMUNICATIONS OF THE ACM, vol. 28, no. 6, 1985, pages 637 - 647
See also references of EP2242032A4 *

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2009199068A (ja) * 2008-01-21 2009-09-03 Nippon Telegr & Teleph Corp <Ntt> 秘密計算システム、秘密計算方法、秘密計算装置、検証装置、およびプログラム
WO2017038761A1 (ja) * 2015-08-31 2017-03-09 日本電気株式会社 秘密計算システム、秘密計算装置、および、秘密計算方法
US10924270B2 (en) 2015-08-31 2021-02-16 Nec Corporation Secret calculation system, secret calculation apparatus, and secret calculation method

Also Published As

Publication number Publication date
US20110040963A1 (en) 2011-02-17
EP2242032A1 (en) 2010-10-20
EP2242032A4 (en) 2012-03-21
CN101911153A (zh) 2010-12-08
CN101911153B (zh) 2014-08-20
EP2242032B1 (en) 2013-10-02
US9300469B2 (en) 2016-03-29

Similar Documents

Publication Publication Date Title
WO2009093603A1 (ja) 秘密計算システム
Sasikumar et al. Comprehensive review and analysis of cryptography techniques in cloud computing
US9413729B2 (en) Symmetric encryption apparatus and storage medium, and symmetric decryption apparatus and storage medium
JP4938766B2 (ja) プログラム難読化システム、プログラム難読化装置及びプログラム難読化方法
US8031865B2 (en) Multiple level security system and method for encrypting data within documents
JP5855696B2 (ja) 完全性検証を含むブロック暗号化方法およびブロック復号化方法
WO2019106166A1 (en) Cryptography device having secure provision of random number sequences
Gupta et al. A new way to design and implementation of hybrid crypto system for security of the information in public network
TW202232913A (zh) 共享金鑰產生技術
JP6041864B2 (ja) データの暗号化のための方法、コンピュータ・プログラム、および装置
JP5992651B2 (ja) 暗号化方法、プログラム、および、システム
US20090010433A1 (en) Schryption method and device
US20210135851A1 (en) Encryption processing system and encryption processing method
JPWO2008114829A1 (ja) 暗号装置、復号装置、暗号プログラム、復号プログラム、及び記録媒体
JP5047198B2 (ja) 秘密計算システム、秘密計算方法、秘密計算装置、検証装置、およびプログラム
US8862893B2 (en) Techniques for performing symmetric cryptography
Bokhari et al. Securing IoT Communications: A Novel Lightweight Stream Cipher Using DNA Cryptography and Grain-80 Cipher
Abdul Hussien An Integrated Cryptographic Approach Using Elliptic Curve Cryptography, Triple Data Encryption Standard and Hash-based Message Authentication Code.
JP6949276B2 (ja) 再暗号化装置、再暗号化方法、再暗号化プログラム及び暗号システム
JP7383985B2 (ja) 情報処理装置、情報処理方法及びプログラム
CN112104450A (zh) 一种对称式数据加密方法、系统及电子设备
CN118586019B (zh) 一种保险数据安全加密方法和系统
JP7700960B2 (ja) 情報処理装置、方法及びプログラム
JP7466791B2 (ja) 暗号化装置、復号装置、復号可能検証装置、暗号システム、暗号化方法、及び暗号化プログラム
Singh et al. Security of Data with 3DES & Watermarking Algorithm

Legal Events

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

Ref document number: 200980102192.4

Country of ref document: CN

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

Ref document number: 09703675

Country of ref document: EP

Kind code of ref document: A1

WWE Wipo information: entry into national phase

Ref document number: 2009703675

Country of ref document: EP

NENP Non-entry into the national phase

Ref country code: DE

WWE Wipo information: entry into national phase

Ref document number: 12812916

Country of ref document: US