Secure computing system, secure computing method, secure computing apparatus, and program therefor

• US 9,300,469 B2
• Filed: 01/21/2009
• Issued: 03/29/2016
• Est. Priority Date: 01/21/2008
• Status: Active Grant

• Current Assignee: Nippon Telegraph and Telephone Corporation
• Original Assignee: Nippon Telegraph and Telephone Corporation
• Inventors: Chida, Koji
• Primary Examiner(s): Zele, Krista
• Assistant Examiner(s): NAJEE-ULLAH, TARIQ S
• Application Number:
  US12/812,916
• Publication Number:
  US 20110040963A1
• Time in Patent Office: 2,624 Days
• Field of Search: 713/150
• US Class Current: 1/1
• CPC Class Codes: H04L 2209/12 Details relating to cryptographic hardware or logic circuitry
• CPC Class Codes: H04L 2209/16 Obfuscation or hiding, e.g. involving white box
• CPC Class Codes: H04L 2209/50 Oblivious transfer
• CPC Class Codes: H04L 9/30 Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
• CPC Class Codes: H04L 9/3221 interactive zero-knowledge proofs

Abstract

A third secure computing apparatus generates data Wb associated with each bit b of a segment t that satisfies a relation m_A=s*t for a first input value m_A and an operator * and data W(1-b) associated with an inversion bit (1-b) of the bit b, transmits the data Wb to a first secure computing apparatus, and transmits data W including the data Wb and the data W(1-b) to a second secure computing apparatus. The second secure computing apparatus uses a segment s that satisfies the relation m_A=s*t, a logic circuit function f and the data W to generate data T in which a logic circuit function f(s*X), which is the logic circuit function fin which the segment s is substituted, is concealed, and transmits the data T to the first secure computing apparatus. A computation result f(m_A) can be determined from the data T and the data Wb. The first secure computing apparatus obtains the computation result f(m_A) using the data T and the data Wb.

Claims

1. A secure computing system that obtains a computation result f(m) of a logic circuit function f(x) for an input value m while concealing said input value m, comprising:

a first secure computing apparatus that stores said logic circuit function f(x); and

a second secure computing apparatus which is independent from said first secure computing apparatus,

wherein said first secure computing apparatus includes;

a first receiver that receives a segment B of said input value m, said input value m having been divided into a segment A and said segment B; and

a generator that uses said logic circuit function f(x) and said segment B to generate data T in which said logic circuit function f(x) and said segment B are concealed by concealing the specific logic gates used to achieve the logic circuit function f(X*B) where * is an operator, with segment B as an input, when generating the data T, said input value m corresponding to said segment A and said segment B; and

wherein said second secure computing apparatus includes;

a second receiver that receives said segment A and said data T; and

a calculator that obtains said computation result f(m) by using said segment A and said data T without using said segment B.

2. The secure computing system according to claim 1, wherein said segments A and B are segments s and t that satisfy a relation m=s*t for an operator *,

said generator uses said logic circuit function f(x) and said segment t to generate data T in which a logic circuit function f(X*t) is concealed, said logic circuit function f(X*t) being obtained by substituting said segment t into said logic circuit function f(x), said computation result f(m) being determined from the data T and said segment s, and

said calculator obtains said computing result f(m) using said segment s and said data T.

3. The secure computing system according to claim 2, wherein said calculator obtains said computation result f(m) using said segment s and said data T without reconstructing said input value m.

4. The secure computing system according to claim 3, wherein said calculator performs a 1-out-of-2 oblivious transfer protocol with said first secure computing apparatus to acquire concealing data associated with said segment s generated by said first secure computing apparatus without letting said segment s be known to said first secure computing apparatus;

and

obtains said computation result f(m) using said concealing data and said data T.

5. The secure computing system according to claim 2, wherein said generator performs a 1-out-of-2 oblivious transfer protocol with said first secure computing apparatus to acquire concealing data associated with said segment s generated by said first secure computing apparatus without letting said segment s be known to said first secure computing apparatus, and

obtains said computation result f(m) using said concealing data and said data T.

6. The secure computing system according to any of claims 2 to 5, further comprising:

a transforming apparatus that includes;

a divider that divides said input value m into said segments s and t that satisfy a relation m=s*t;

a first transmitter that transmits said segment t to said first secure computing apparatus; and

a second transmitter that transmits said segment s to said second secure computing apparatus.

7. The secure computing system according to claim 1, wherein said segment A is data Wb associated with each bit b of said input value m,

said segment B is data W including said data Wb and data W(1-b) associated with an inversion bit (1-b) of said bit b without identifying the association between said data Wb and said data W(1-b) and said bit b and said bit (1-b),

said generator uses said data W to generate said data T in which the logic circuit function f is concealed, said computation result f(m) being determined using the data T and said data Wb, and

said obtains said computation result f(m) using said data Wb and said data T.

8. A secure computing apparatus, comprising:

a receiver that receives a segment B of said input value m, said input value m having been divided into a segment A and said segment B; and

a generator that uses a logic circuit function f(x) and said segment B to generate data T in which said logic circuit function f(x) and said segment B are concealed by concealing the specific logic gates used to achieve the logic circuit function f(X*B) where * is an operator, with segment B as an input, when generating the data T, said input value m corresponding to said segment A and said segment B; and

a transmitter that transmits said data T to another secure computing apparatus that receives said segment A;

wherein computation result f(m) can be determined by using said data T and said segment A without using said segment B.

16. A non-transitory computer readable medium that stores a program that makes a computer function as a secure computing apparatus according to claim 8.

9. A secure computing method that obtains a computation result f(m) of a logic circuit function f(x) for an input value m while concealing said input value m, comprising:

(A) a step of receiving a segment B of said input value m by a first secure computing apparatus, said input value m having been divided into a segment A and said segment B;

(B) a step of using said logic circuit function f(x) stored in said first secure computing apparatus and said segment B, by said first secure computing apparatus, to generate data T in which said logic circuit function f(x) and said segment B are concealed by concealing the specific logic gates used to achieve the logic circuit function f(X*B) where * is an operator, with segment B as an input, when generating the data T, said input value m corresponding to said segment A and said segment B;

(C) a step of receiving said segment A and said data T by a second secure computing apparatus which is independent from said first secure computing apparatus; and

(D) a step of obtaining said computation result f(m) by using said segment A and said data T by said second secure computing apparatus without using said segment B.

10. The secure computing method according to claim 9, wherein said segments A and B are segments s and t that satisfy a relation mA=s*t for an operator *,

said step (B) includes a step of using said logic circuit function f(x) and said segment t to generate data T in which a logic circuit function f(X*t) is concealed, said logic circuit function f(X*t) being obtained by substituting said segment t into said logic circuit function f(x), said computation result f(m) being determined from the data T and said segment s, and

said step (D) includes a step of obtaining said computing result f(m) using said segment s and said data T.

11. The secure computing method according to claim 9, wherein said step (D) includes a step of obtaining said computation result f(m) using said segment s and said data T without reconstructing said input value m.

12. The secure computing method according to claim 11, wherein said step (D) includes:

(D-1) a step of performing a 1-out-of-2 oblivious transfer protocol with said first secure computing apparatus to acquire concealing data associated with said segment s generated by said first secure computing apparatus without letting said segment s be known to said first secure computing apparatus, in said second secure computing apparatus; and

(D-2) a step of obtaining said computation result f(m) using said concealing data and said data T.

13. The secure computing method according to claim 10, wherein said step (D) includes:

(D-1) a step of performing a 1-out-of-2 oblivious transfer protocol with said first secure computing apparatus to acquire concealing data associated with said segment s generated by said first secure computing apparatus without letting said segment s be known to said first secure computing apparatus, in said second secure computing apparatus; and

(D-2) a step of obtaining said computation result f(m) using said concealing data and said data T.

14. The secure computing method according to any of claims 10 to 13, further comprising:

a step of dividing said input value m into said segments s and t that satisfy a relation m=s*t in a transforming apparatus;

a step of transmitting said segment t to said first secure computing apparatus from said transforming apparatus; and

a step of transmitting said segment s to said second secure computing apparatus from said transforming apparatus.

15. The secure computing method according to claim 9, wherein said segment A is data Wb associated with each bit of said input value m,

said segment B is data W including said data Wb and data W(1-b) associated with an inversion bit (1-b) of said bit b without identifying the association between said data Wb and said data W(1-b) and said bit b and said bit (1-b),

said step (B) includes a step of using said data W to generate said data T in which the logic circuit function f is concealed, said computation result f(m) being determined using the data T and said data Wb, and

said step (D) includes a step of obtaining said computation result f(m) using said data Wb and said data T.