Method and system for secure computational outsourcing and disguise

• US 6,957,341 B2
• Filed: 03/18/2002
• Issued: 10/18/2005
• Est. Priority Date: 05/14/1998
• Status: Expired due to Fees

• Current Assignee: Purdue Research Foundation (The Trustees of Purdue University (d/b/a Purdue University))
• Original Assignee: Purdue Research Foundation (The Trustees of Purdue University (d/b/a Purdue University))
• Inventors: Rice, John R., Atallah, Mikhail J.
• Primary Examiner(s): Smithers, Matthew
• Application Number:
  US10/100,682
• Publication Number:
  US 20030018608A1
• Time in Patent Office: 1,310 Days
• Field of Search: 713/190, 713/189, 708/200, 708/446
• US Class Current: 713/190
• CPC Class Codes: G06F 21/14 against software analysis or reverse engineering, e.g. by obfuscation
• CPC Class Codes: G06F 21/606 by securing the transmission between two devices or processes
• CPC Class Codes: G06F 21/62 Protecting access to data via a platform, e.g. using keys or access control rules
• CPC Class Codes: G06F 21/6254 by anonymising data, e.g. decorrelating personal data from the owner's identification
• CPC Class Codes: G06F 21/629 to features or functions of an application

Abstract

A method and system for secure computational outsourcing and disguise. According to an embodiment, a first set of actual arguments and a second set of actual arguments for an outsourced computation are determined. A first group of disguised arguments corresponding to the first set of actual arguments is prepared with a first computer. A second group of disguised arguments corresponding to the second set of actual arguments is prepared with a second computer. The first and second groups of disguised arguments are output from the first and second computers, respectively, for performance of the outsourced computation. A third computer performs the outsourced computation and returns a disguised result to the first and/or second computers. The first and/or second computers then unveil the actual result from the disguised result.

Claims

1. A method for secure computational outsourcing comprising:

determining a first set of actual arguments for an outsourced computation;

determining a second set of actual arguments for said outsourced computation;

preparing a first group of disguised arguments corresponding to said first set of actual arguments with a first computer;

preparing a second group of disguised arguments corresponding to said second set of actual arguments with a second computer;

outputting said first and second groups of disguised arguments from said first and second computers, respectively, for performance of said outsourced computation;

receiving said first and second groups of disguised arguments with a third computer;

performing said outsourced computation with said third computer using said first and second groups of disguised arguments to achieve a result;

sending said result from said third computer to said first and second computers; and

receiving said result with said first and second computers.

2. The method of claim 1, wherein said result is in a disguised form relative to an actual answer that would have been obtained by submitting said first and second sets of actual arguments to said third computer for said outsourced computation.

3. The method of claim 1, further comprising computing an actual answer from said result with said first and second computers.

4. The method of claim 1, wherein said first computer has a memory, said memory comprising a plurality of computation types, and wherein said step of preparing said first group of disguised arguments comprises:

classifying said outsourced computation into one of said plurality of computation types;

selecting at least one of a plurality of disguising operations based on said classifying step; and

performing said at least one disguising operation on said first set of actual arguments with said first computer to provide said first group of disguised arguments.

5. The method of claim 4, wherein said plurality of computation types comprises at least one computation type selected from the group consisting of matrix multiplication, matrix inversion, solution of a linear system of equations, quadrature, convolution, solution of one or more differential equations, optimization, solution of a nonlinear system of equations, image edge detection, sorting, character string pattern matching, integral equations, statistical regression, statistical correlation, natural language processing, biometric data matching, database analysis, data mining, and classification problems.

6. The method of claim 1, wherein said second computer has a memory, said memory comprising a plurality of computation types, and wherein said step of preparing said second group of disguised arguments comprises:

classifying said outsourced computation into one of said plurality of computation types;

selecting at least one of a plurality of disguising operations based on said classifying step; and

performing said at least one disguising operation on said second set of actual arguments with said second computer to provide said second group of disguised arguments.

7. The method of claim 6, wherein said plurality of computation types comprises at least one computation type selected from the group consisting of matrix multiplication, matrix inversion, solution of a linear system of equations, quadrature, convolution, solution of one or more differential equations, optimization, solution of a nonlinear system of equations, image edge detection, sorting, character string pattern matching, integral equations, statistical regression, statistical correlation, natural language processing, biometric data matching, database analysis, data mining, and classification problems.

8. The method of claim 1, wherein said step of preparing said first group of disguised arguments comprises performing at least one disguising operation on said first set of actual arguments with said first computer to provide said first group of disguised arguments, and said step of preparing said second group of disguised arguments comprises performing at least one disguising operation on said second set of actual arguments with said second computer to provide said second group of disguised arguments, the method further comprising the step of:

exchanging information related to said at least one disguising operation performed on said first set of actual arguments and said at least one disguising operation performed on said second set of actual arguments between said first and second computers to permit each of said first and second computers to compute an actual answer from said result.

9. The method of claim 1, wherein said third computer is remotely located relative to said first and second computers.

10. The method of claim 1, wherein each of said steps of preparing a first group of disguised arguments and a second group of disguised arguments comprises generating a plurality of random numbers, said random numbers each being generated by one of a plurality of random number generation techniques, said techniques each comprising at least one different distribution parameter.

11. The method of claim 10, wherein each of said steps of preparing a first group of disguised arguments and a second group of disguised arguments further comprises defining a plurality of disguise functions with one or more of said random numbers.

12. The method of claim 1, wherein each of said steps of preparing a first group of disguised arguments and a second group of disguised arguments comprises modifying a linear operator.

13. The method of claim 1, wherein each of said steps of preparing a first group of disguised arguments and a second group of disguised arguments comprises altering a dimension corresponding to said first and second sets of actual arguments to provide said first and second groups of disguised arguments, respectively.

14. The method of claim 13, wherein each of said altering steps comprises expanding the dimension.

15. The method of claim 1, wherein each of said steps of preparing a first group of disguised arguments and a second group of disguised arguments comprises performing a function substitution in accordance with at least one mathematical identity.

16. A method for secure computational outsourcing comprising:

providing to a computer a plurality of disguised arguments from a first source and a second source, said plurality of disguised arguments hiding a plurality of actual arguments;

providing said computer with one or more instructions for performing an outsourced computation on said plurality of disguised arguments;

performing said outsourced computation on said disguised arguments with said first computer using said one or more instructions; and

outputting a result of said outsourced computation with said computer to both said first source and said second source.

17. The method of claim 16, wherein said outsourced computation is of a type selected from the group consisting of matrix multiplication, matrix inversion, solution of a linear system of equations, quadrature, convolution, solution of one or more differential equations, optimization, solution of a nonlinear system of equations, image edge detection, sorting, character string pattern matching, integral equations, statistical regression, statistical correlation, natural language processing, biometric data matching, database analysis, data mining, and classification problems.

18. A system for secure computational outsourcing comprising:

a first computer operable to define a first set of actual arguments for an outsourced computation, said first computer being programmed to determine a first group of disguised arguments from said first set of actual arguments, said first group of disguised arguments hiding at least one characteristic of said first set of actual arguments;

a second computer operable to define a second set of actual arguments for said outsourced computation, said second computer being programmed to determine a second group of disguised arguments from said second set of actual arguments, said second group of disguised arguments hiding at least one characteristic of said second set of actual arguments;

first and second output devices responsive to said first and second computers, respectively, to output said first and second groups of disguised arguments for remote performance of said outsourced computation; and

first and second input devices to permit said first and second computers, respectively, to receive a disguised result of said outsourced computation performed with said first and second groups of disguised arguments, said first and second computers being operable to determine an actual answer from said disguised result.

19. The system of claim 18, wherein said first and second computers are further programmed to classify said outsourced computation as being one of a plurality of computation types, said plurality of computation types comprising at least one computation type selected from the group consisting of matrix multiplication, matrix inversion, solution of a linear system of equations, quadrature, convolution, solution of one or more differential equations, optimization, solution of a nonlinear system of equations, image edge detection, sorting, character string pattern matching, integral equations, statistical regression, statistical correlation, natural language processing, biometric data matching, database analysis, data mining, and classification problems.

20. The system of claim 18, further comprising a computing center, said computing center being programmed to perform said outsourced computation with said first and second groups of disguised arguments.

21. The system of claim 18, wherein said first and second computers each comprises a memory and a library of disguising operations stored in said memory, wherein said programming of each said first and second computers references said library to generate said first and second groups of disguised arguments, respectively.

22. The system of claim 21, wherein said library of disguising operations comprises at least one disguising operation selected from the group consisting of random object generation, argument dimension modification, linear operator modification, mathematical identity substitution, coordinate system modification, domain mapping, inserting partitions of unity, logical identity substitution, inserting redundant computations, and disguise function generation.

23. The system of claim 18, wherein said first and second computers are operable to generate said first and second groups of disguised arguments, respectively, using first and second disguising operations, respectively, said first computer being operable to output information related to said first disguising operation to be received by said second input device of said second computer, and said second computer being operable to output information related to said second disguising operation to be received by said first input device of said first computer, thereby permitting each of said first and second computers to determine said actual answer from said result.

24. A method for secure computational outsourcing comprising:

obtaining a first set of actual data;

preparing a first set of disguised data corresponding to said first set of actual data with a first computer;

transmitting said first set of disguised data from said first computer to a second computer;

preparing a second set of disguised data corresponding to a second set of actual data;

comparing said first set of disguised data to said second set of disguised data with said second computer; and

transmitting a result of said comparing step from said second computer to said first computer.

25. The method of claim 24, further comprising the step of transmitting said second set of disguised data from a third computer to said second computer prior to said comparing step.

26. The method of claim 24, wherein said second set of actual data is stored in a database, said third computer being operable to prepare said second set of disguised data from said database prior to said transmitting step.

27. The method of claim 24, further comprising the step of selectively performing a function in response to instructions from said first computer based on said result received from said second computer.

28. The method of claim 27, wherein said selectively performed function comprises an authorization function selected from the group consisting of providing access to an area of a building, automatically unlocking a door, and approving a business transaction.

29. The method of claim 24, wherein said first set and said second set of actual data are disguised using an identical disguising operation.

30. The method of claim 24, wherein said first set of actual data is selected from a group consisting of fingerprint identification data, DNA sequence data, credit card data, image data, text data, biometric data, password data, keyword data, smart card data, and planar graph data.

31. The method of claim 24, wherein said first set and said second set of actual data each comprises an image matrix.

32. The method of claim 31, wherein said result comprises a score matrix.

33. The method of claim 24, wherein said first set of actual data is obtained using at least one input device.

34. The method of claim 33, wherein said at least one of said at least one input devices is selected from the group consisting of a fingerprint reader, a voice print reader, a face geometry reader, a hand geometry reader, an iris scanner, a retina scanner, a bar code reader, an IR signal receiver, an RF signal receiver, a magnetic stripe reader, and a smart card reader.

35. The method of claim 24, wherein said second set of disguised data is prepared by a third computer.

36. A method for secure computational outsourcing comprising:

providing a first computer having a memory, said memory comprising a plurality of computation types, said plurality of computation types comprising at least one computation type selected from the group consisting of matrix multiplication, matrix inversion, solution of a linear system of equations, quadrature, convolution, solution of one or more differential equations, optimization, solution of a nonlinear system of equations, image edge detection, sorting, character string pattern matching, integral equations, statistical regression, statistical correlation, natural language processing, biometric data matching, database analysis, data mining, and classification problems;

providing a second computer having a memory, said memory comprising a plurality of computation types, said plurality of computation types comprising at least one computation type selected from the group consisting of matrix multiplication, matrix inversion, solution of a linear system of equations, quadrature, convolution, solution of one or more differential equations, optimization, solution of a nonlinear system of equations, image edge detection, sorting, character string pattern matching, integral equations, statistical regression, statistical correlation, natural language processing, biometric data matching, database analysis, data mining, and classification problems;

determining a first set of actual arguments for an outsourced computation;

determining a second set of actual arguments for said outsourced computation;

preparing a first group of disguised arguments corresponding to said first set of actual arguments with said first computer by classifying said outsourced computation into one of said plurality of computation types, selecting at least one of a plurality of disguising operations based on said classification, and performing said at least one selected disguising operation on said first set of actual arguments with said first computer to provide said first group of disguised arguments;

preparing a second group of disguised arguments corresponding to said second set of actual arguments with said second computer by classifying said outsourced computation into one of said plurality of computation types, selecting at least one of a plurality of disguising operations based on said classification, and performing said at least one selected disguising operation on said second set of actual arguments with said second computer to provide said first group of disguised arguments;

outputting said first and second groups of disguised arguments from said first and second computers, respectively, for performance of said outsourced computation;

receiving said first and second groups of disguised arguments with a third computer;

performing said outsourced computation with said third computer using said disguised arguments to produce a disguised result, said disguised result being in a disguised form relative to an actual result of said outsourced computation that would have been obtained by submitting said first and second sets of actual arguments to said third computer for said outsourced computation;

sending said disguised result from said third computer to said first and second computers;

receiving said disguised result with said first and second computers;

exchanging information related to said at least one selected disguising operation performed on said first set of actual arguments and said at least one selected disguising operation performed on said second set of actual arguments between said first and second computers to permit each of said first and second computers to compute an actual answer from said disguised result; and

computing said actual answer from said disguised result with said first and second computers.

37. A system for secure computational outsourcing comprising:

a first computer comprising a memory and a library of disguising operations stored in said memory, said library of disguising operations comprising at least one disguising operation selected from the group consisting of random object generation, argument dimension modification, linear operator modification, mathematical identity substitution, coordinate system modification, domain mapping, inserting partitions of unity, logical identity substitution, inserting redundant computations, and disguise function generation, said first computer being operable to define a first set of actual arguments for an outsourced computation, said first computer having a resident program for creating a first group of disguised arguments from said first set of actual arguments, said program capable of selecting one or more disguising operations from said library of disguising operations and applying said selected one or more disguising operations to said first set of actual arguments to create said first group of disguised arguments, said first group of disguised arguments hiding at least one characteristic of said first set of actual arguments, said program further capable of classifying said outsourced computation as being one of a plurality of computation types, said plurality of computation types comprising at least one computation type selected from the group consisting of matrix multiplication, matrix inversion, solution of a linear system of equations, quadrature, convolution, solution of one or more differential equations, optimization, solution of a nonlinear system of equations, image edge detection, sorting, character string pattern matching, integral equations, statistical regression, statistical correlation, natural language processing, biometric data matching, database analysis, data mining, and classification problems;

a second computer comprising a memory and a library of disguising operations stored in said memory, said library of disguising operations comprising at least one disguising operation selected from the group consisting of random object generation, argument dimension modification, linear operator modification, mathematical identity substitution, coordinate system modification, domain mapping, inserting partitions of unity, logical identity substitution, inserting redundant computations, and disguise function generation, said second computer being operable to define a second set of actual arguments for an outsourced computation, said second computer having a resident program for creating a second group of disguised arguments from said second set of actual arguments, said program capable of selecting one or more disguising operations from said library of disguising operations and applying said selected one or more disguising operations to said second set of actual arguments to create said second group of disguised arguments, said second group of disguised arguments hiding at least one characteristic of said second set of actual arguments, said program further capable of classifying said outsourced computation as being one of a plurality of computation types, said plurality of computation types comprising at least one computation type selected from the group consisting of matrix multiplication, matrix inversion, solution of a linear system of equations, quadrature, convolution, solution of one or more differential equations, optimization, solution of a nonlinear system of equations, image edge detection, sorting, character string pattern matching, integral equations, statistical regression, statistical correlation, natural language processing, biometric data matching, database analysis, data mining, and classification problems;

a first output device responsive to said first computer to output said first group of disguised arguments and first identifying information about said one or more disguising operations applied to said first set of actual arguments;

a second output device responsive to said second computer to output said second group of disguised arguments and second identifying information about said one or more disguising operations applied to said second set of actual arguments;

a computing center, said computing center being separated from said first and second computer and capable of receiving said first and second group of disguised arguments and performing said outsourced computation with said first and second groups of disguised arguments to produce a disguised result;

a first input device communicatively connected to said first computer and arranged to permit said first computer to receive said second identifying information about said one or more disguising operations applied to said second set of actual arguments from said second computer and to receive said disguised result of said outsourced computation performed with said first and second groups of disguised arguments from said computing center, said first computer being operable to determine an actual answer from said result based upon said first and second identifying information; and

a second input device communicatively connected to said second computer and arranged to permit said second computer to receive said first identifying information about said one or more disguising operations applied to said first set of actual arguments from said first computer and to receive said disguised result of said outsourced computation performed with said first and second groups of disguised arguments from said computing center, said second computer being operable to determine an actual answer from said result based upon said first and second identifying information.