SECURE COMPUTING SYSTEM, SECURE COMPUTING METHOD, SECURE COMPUTING APPARATUS, AND PROGRAM THEREFOR

• US 20110040963A1
• Filed: 01/21/2009
• Published: 02/17/2011
• 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
• Granted Patent: US 9,300,469 B2
• Time in Patent Office: Days
• US Class Current: 713/150
• 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_A) of a logic circuit function f for a first input value m_A while concealing the first input value m_A, comprising:

a first secure computing apparatus;

a second secure computing apparatus that stores said logic circuit function f; and

a third secure computing apparatus,

wherein said third secure computing apparatus includes;

means of generating data Wb associated with each bit b of a segment t that satisfies a relation m_A=s*t for said first input value m_A and an operator * and data W(1-b) associated with an inversion bit (1-b) of said bit b;

means of transmitting said data Wb to said first secure computing apparatus; and

means of transmitting data W including said data Wb and said data W(1-b) to said second secure computing apparatus without identifying the association between said bit b and said inversion bit (1-b) and said data Wb and said data W(1-b),

said second secure computing apparatus includes;

means of using a segment s that satisfies the relation m_A=s*t, said logic circuit function f and said data W to generate data T in which a logic circuit function f(s*X) is concealed, said logic circuit function f(s*X) being obtained by substituting said segment s into said logic circuit function f, said computation result f(m_A) being determined from said data T and said data Wb;

means of transmitting said data T to said first secure computing apparatus, and

said first secure computing apparatus includes;

means of receiving said data T and said data Wb; and

means of obtaining said computation result f(m_A) using said data T and said data Wb.

2. The secure computing system according to claim 1, wherein said first secure computing apparatus further includes:

means of storing said first input value m_A;

means of dividing said first input value m_A into said segments s and t that satisfy the relation m_A=s*t;

means of transmitting said segment s to said second secure computing apparatus; and

means of transmitting said segment t to said third secure computing apparatus.

3. The secure computing system according to claim 1 or 2, wherein said logic circuit function f is a logic circuit function f(x, y) for two input values,

said second secure computing apparatus includes means of storing a second input value m_B,

said means of generating said data T includes means of using said segment s, said logic circuit function f(x, y), said data W and said input value m_B to generate data T in which a logic circuit function f(s*X, m_B) is concealed, said logic circuit function f(s*X, m_B) being obtained by substituting said segment s and said input value m_B into said logic circuit function f(x, y), a computation result f(m_A, m_B) of said logic circuit function f(x, y) for said first input value m_A and said second input value m_B being determined from said data T and said data Wb, and

said means of obtaining said computation result f(m_A) includes:

means of obtaining said computation result f(m_A, m_B) using said data T and said data Wb.

4. The secure computing system according to claim 1, further comprising:

a transforming apparatus that includes;

means of dividing said first input value m_A into said segments s and t that satisfy the relation m_A=s*t;

means of transmitting said segment s to said second secure computing apparatus; and

means of transmitting said segment t to said third secure computing apparatus.

5. A secure computing apparatus, comprising:

means of receiving a segment t that satisfies a relation m_A=s*t for a first input value m_A and an operator*;

means of generating data Wb associated with each bit b of said segment t and data W(1-b) associated with an inversion bit (1-b) of said bit b;

means of transmitting said data Wb to another secure computing apparatus that obtains a computation result f(m_A) of a logic circuit function f for said first input value m_A; and

means of transmitting data W including said data Wb and said data W(1-b) to another secure computing apparatus that receives a segment s that satisfies the relation m_A=s*t without identifying the association between said bit b and said inversion bit (1-b) and said data Wb and said data W(1-b).

6. A secure computing apparatus, comprising:

means of receiving a segment s that satisfies a relation m_A=s*t for a first input value m_A and an operator*;

means of using said segment s, a logic circuit function f and data W to generate data T in which a logic circuit function f(s*X) is concealed, said logic circuit function f(s*X) being obtained by substituting said segment s into said logic circuit function f, a computation result f(m_A) of said logic circuit function f for said first input value m_A being determined from said data T and said data Wb; and

means of transmitting said data T to another secure computing apparatus that obtains said computation result f(m_A).

7. A secure computing method that obtains a computation result f(m_A) of a logic circuit function f for a first input value m_A with a first, a second and a third secure computing apparatus while concealing the first input value m_A, comprising:

(A) a step of generating data Wb associated with each bit b of a segment t that satisfies a relation m_A=s*t for said first input value m_A and an operator * and data W(1-b) associated with an inversion bit (1-b) of said bit b in said third secure computing apparatus;

(B) a step of transmitting said data Wb to said first secure computing apparatus from said third secure computing apparatus;

(C) a step of transmitting data W including said data Wb and said data W(1-b) to said second secure computing apparatus without identifying the association between said bit b and said inversion bit (1-b) and said data Wb and said data W(1-b) from said third secure computing apparatus;

(D) a step of using a segment s that satisfies the relation m_A=s*t, said logic circuit function f and said data W to generate data T in which a logic circuit function f(s*X) is concealed, said logic circuit function f(s*X) being obtained by substituting said segment s into said logic circuit function f, said computation result f(m_A) being determined from said data T and said data Wb, in said second secure computing apparatus;

(E) a step of transmitting said data T to said first secure computing apparatus from said second secure computing apparatus;

(F) a step of receiving said data T and said data Wb by said first secure computing apparatus; and

(G) a step of obtaining said computation result f(m_A) using said data T and said data Wb in said first secure computing apparatus.

8. The secure computing method according to claim 7, further comprising:

a step of dividing said first input value m_A stored in the first secure computing apparatus into said segments s and t that satisfy the relation m_A=s*t in said first secure computing apparatus;

a step of transmitting said segment s to said second secure computing apparatus from said first secure computing apparatus; and

a step of transmitting said segment t to said third secure computing apparatus from said first secure computing apparatus.

9. The secure computing method according to claim 7 or 8, wherein said logic circuit function f is a logic circuit function f(x, y) for two input values,

said second secure computing apparatus stores a second input value M_B,

said step (D) includes a step of using said segment s, said logic circuit function f(x. y), said data W and said input value m_B to generate data T in which a logic circuit function f(s*X, m_B) is concealed, said logic circuit function f(s*X, m_B) being obtained by substituting said segment s and said input value m_B into said logic circuit function f, a computation result f(m_A, m_B) of said logic circuit function f(x, y) for said first input value m_A and said second input value m_B being determined from said data T and said data Wb, and

said step (G) includes a step of obtaining said computation result f(m_A, m_B) using said data T and said data Wb in said first secure computing apparatus.

10. 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 the input value m, comprising:

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

a second secure computing apparatus,

wherein said first secure computing apparatus includes;

means of receiving a segment B of said input value m, the input value m having been divided into a segment A and the segment B; and

means of using said logic circuit function f(x) and said segment B to generate data T in which said logic circuit function f(x) is concealed, said computation result f(m) being determined from the data T and said segment A, and

said second secure computing apparatus includes;

means of receiving said segment A and said data T; and

means of obtaining said computation result f(m) using said segment

A and said data T.

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

said means of generating said data T includes means 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 means of obtaining said computation result f(m) using said segment A and said data T includes means of obtaining said computing result f(m) using said segment s and said data T.

12. The secure computing system according to claim 11, wherein said means of obtaining said computation result f(m) using said segment A and said data T includes means of obtaining said computation result f(m) using said segment s and said data T without reconstructing said input value m.

13. The secure computing system according to claim 12, wherein said means of obtaining said computation result f(m) using said segment A and said data T includes:

means 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; and

means of obtaining said computation result f(m) using said concealing data and said data T.

14. The secure computing system according to claim 11, wherein said means of obtaining said computation result f(m) using said segment A and said data T includes:

means 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; and

means of obtaining said computation result f(m) using said concealing data and said data T.

15. The secure computing system according to any of claims 11 to 14, further comprising:

a transforming apparatus that includes;

means of dividing said input value m into said segments s and t that satisfy a relation m=s*t;

means of transmitting said segment t to said first secure computing apparatus; and

means of transmitting said segment s to said second secure computing apparatus.

16. The secure computing system according to claim 10, 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 means of generating said data T includes means 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 means of obtaining said computation result f(m) using said segment A and said data T includes means of obtaining said computation result f(m) using said data Wb and said data T.

17. A secure computing apparatus, comprising:

means of receiving a segment B of said input value m, the input value m having been divided into a segment A and the segment B; and

means of using a logic circuit function f(x) and said segment B to generate data T in which said logic circuit function f(x) is concealed, computation result f(m) being determined from the data T and said segment A; and

means of transmitting said data T to another secure computing apparatus that receives said segment A.

25. A program that makes a computer function as a secure computing apparatus according to any of claims 5, 6 and 17.

18. 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 the input value m, comprising:

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

(B) a step of using said logic circuit function f(x) stored in said first secure computing apparatus and said segment B to generate data T in which said logic circuit function f(x) is concealed, said computation result f(m) being determined from the data T and said segment A, in said first secure computing apparatus;

(C) a step of receiving said segment A and said data T by said second secure computing apparatus; and

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

19. The secure computing method according to claim 18, wherein said segments A and B are segments s and t that satisfy a relation m_A=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.

20. The secure computing method according to claim 18, 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.

21. The secure computing method according to claim 20, 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.

22. The secure computing method according to claim 19, 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.

23. The secure computing method according to any of claims 19 to 22, 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.

24. The secure computing method according to claim 19, 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.