Secure computational outsourcing techniques
First Claim
1. A method comprising:
- determining a set of arguments for an outsourced computation;
classifying, with a first computer, said outsourced computation into at least one computation type, said at least one computation type being selected from the group consisting of quadrature computations, image edge detection computations, convolution computations, character string pattern matching computations, sorting computations, and computations for solving one or more differential equations;
selecting, with said first computer, one or more disguising operations from a predetermined set of disguising operations based on said classifying;
performing said one or more selected disguising operations on said actual arguments with said first computer to provide disguised arguments;
outputting said disguised arguments from said first computer for performance of said outsourced computation; and
receiving a result of said outsourced computation performed with said disguised arguments.
5 Assignments
0 Petitions
Accused Products
Abstract
A technique includes the determination of a set of arguments for an outsourced computation and preparing a group of disguised arguments corresponding to the set of arguments with a first computer. The first computer outputs the disguised arguments to a second computer. The second computer performs the outsourced computation with the disguised arguments to determine a corresponding disguised result. The second computer returns the disguised result to the first computer. The first computer recovers an actual answer from the disguised result. Before outsourcing, the first computer can classify the outsourced computation into one of a number of computation types and select one or more of a number of disguising operations based this classification.
-
Citations
74 Claims
-
1. A method comprising:
-
determining a set of arguments for an outsourced computation;
classifying, with a first computer, said outsourced computation into at least one computation type, said at least one computation type being selected from the group consisting of quadrature computations, image edge detection computations, convolution computations, character string pattern matching computations, sorting computations, and computations for solving one or more differential equations;
selecting, with said first computer, one or more disguising operations from a predetermined set of disguising operations based on said classifying;
performing said one or more selected disguising operations on said actual arguments with said first computer to provide disguised arguments;
outputting said disguised arguments from said first computer for performance of said outsourced computation; and
receiving a result of said outsourced computation performed with said disguised arguments. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A system comprising:
-
a computer operable to define a set of actual arguments for an outsourced computation, said computer being programmed to classify said computation into at least one computation type, said at least one computation type being selected from the group consisting of quadrature computations, image edge detection computations, convolution computations, character string pattern matching computations, sorting computations, and computations for solving one or more differential equations, said computer being programmed to determine a group of disguised arguments from said set of actual arguments, said disguised arguments hiding one or more characteristics of said set of actual arguments;
an output device responsive to said computer to output said disguised arguments for remote performance of said outsourced computation; and
an input device to receive a result of said outsourced computation performed with said disguised arguments, wherein said computer is responsive to said input device to determine a desired answer from said result. - View Dependent Claims (12, 13, 14, 15)
-
-
16. An apparatus, comprising:
- a computer readable medium, said medium defining computer programming instructions to hide a group of actual arguments for a computation to be outsourced, said programming instructions being operable to classify said computation into at least one computation type, said at least one computation type being selected from the group consisting of quadrature computations image edge detection computations, convolution computations, character string pattern matching computations, sorting computations, and computations for solving one or more differential equations, said programming instructions being operable to generate a group of disguised arguments corresponding to said actual arguments, said disguised arguments being generated to produce a disguised result from said computation, an actual answer being recoverable from said disguised result in accordance with said programming instructions, said actual answer being returned by said computation when said computation is provided said actual arguments.
- View Dependent Claims (17, 18, 19)
-
20. A system comprising:
-
a computer operable to define a set of actual arguments for an outsourced computation, said computer being programmed to determine a group of disguised arguments from said set of actual arguments, said computer comprising instructions to generate a cubic spline to provide a disguise for said actual arguments, said disguised arguments hiding one or more characteristics of said set of actual arguments;
an output device responsive to said computer to output said disguised arguments for remote performance of said outsourced computation;
an input device to receive a result of said outsourced computation performed with said disguised arguments; and
wherein said computer is responsive to said input device to determine a desired answer from said result.
-
-
21. An apparatus comprising:
a computer readable medium, said medium comprising computer programming instructions to hide a group of actual arguments for a computation to be outsourced, said programming instructions being operable to generate a group of disguised arguments corresponding to said actual arguments, said programming instructions comprising a routine to generate a cubic spline to provide at least one disguise function, said disguised arguments being generated to provide a disguised result when provided for said computation, an actual answer being recoverable from said disguised result in accordance with said instructions, said actual answer being returned by said computation when said computation is provided said actual arguments.
-
22. A method for outsourcing a matrix multiplication computation from a first computer to a second computer, wherein the contents of a matrix are disguised prior to delivery of the matrix to the second computer for the matrix multiplication computation thereby hindering discovery of the contents of the matrix by the second computer and unauthorized parties, the method comprising the steps of:
-
providing, in a memory of a first computer, a first actual matrix M1 comprising a first plurality of actual arguments, and a second actual matrix M2 comprising a second plurality of actual arguments, wherein a multiplicative product of said first actual matrix M1 and said second actual matrix M2 is desired;
preparing, in said memory of said first computer, at least two disguising matrices, each said disguising matrix being a sparse matrix comprising at least one non-zero disguising argument, wherein each said at least one non-zero disguising argument comprises a pseudorandom number;
disguising said first plurality of actual arguments by computing, with said first computer, a first disguised matrix X using said first actual matrix M1 and at least one said disguising matrix, said first disguised matrix X comprising a first plurality of disguised arguments; and
disguising said second plurality of actual arguments by computing, with said first computer, a second disguised matrix Y using said second actual matrix M2 and at least one said disguising matrix, said second disguised matrix Y comprising a second plurality of disguised arguments. - View Dependent Claims (23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34)
-
-
35. A method for outsourcing a matrix inversion computation from a first computer to a second computer, wherein the contents of a matrix are disguised prior to delivery of the matrix to the second computer for the matrix inversion computation thereby hindering discovery of the contents of the matrix by the second computer and unauthorized parties, the method comprising the steps of:
-
(a) providing, in a memory of a first computer, a first actual matrix M comprising a first plurality of actual arguments, wherein an inverse of said first actual matrix M is desired;
(b) providing, in said memory of said first computer, a matrix S comprising a plurality of pseudorandom arguments;
(c) generating, with said first computer, a first disguising matrix P1 and a second disguising matrix P2, wherein each said disguising matrix is a sparse matrix comprising at least one non-zero disguising argument, and wherein each said at least one non-zero disguising argument comprises a pseudorandom number;
(d) disguising said first plurality of actual arguments by computing, with said first computer, a matrix Q as follows;
Q=P1*M*S*P2−
1,
said matrix Q comprising a first plurality of disguised arguments;
(e) transmitting said matrix Q to a second computer; and
(f) determining, with said second computer, whether said matrix Q is invertible. - View Dependent Claims (36, 37, 38)
-
-
39. A method for outsourcing the computation of a solution vector for a system of linear equations of the form Mx=b from a first computer to a second computer, wherein the system of linear equations is disguised prior to delivery of the system of linear equations to the second computer for computation of the solution vector, thereby hindering discovery of the system of linear equations by the second computer and unauthorized parties, the method comprising the steps of:
-
providing a matrix M, said matrix M having n rows and n columns and comprising a first plurality of actual arguments, wherein n is a positive integer;
providing a vector b, said vector b having n elements and comprising a second plurality of actual arguments;
generating, with a first computer, a matrix B having dimensions identical to said matrix M, said matrix B comprising a plurality of pseudorandom arguments;
disguising said second plurality of actual arguments by replacing, in a memory of said first computer, a row of said matrix B with said vector b;
preparing, in said memory of said first computer, at least two disguising matrices, each said disguising matrix being a sparse matrix comprising at least one non-zero disguising argument, wherein each said at least one non-zero disguising argument comprises a pseudorandom number;
disguising said first plurality of actual arguments by computing, with said first computer, a matrix C′
using said matrix M and at least two of said at least two disguising matrices, said matrix C′
comprising a first plurality of disguised arguments;
disguising said second plurality of actual arguments by computing, with said first computer, a matrix G′
using said matrix B and at least two of said at least two disguising matrices; and
transmitting said matrix C′ and
said matrix G′
to a second computer. - View Dependent Claims (40)
-
-
41. A method for outsourcing the computation of a solution vector for a system of linear equations of the form Mx=b from a first computer to a second computer, wherein the system of linear equations is disguised prior to delivery of the system of linear equations to the second computer for computation of the solution vector, thereby hindering discovery of the system of linear equations by the second computer and unauthorized parties, the method comprising the steps of:
-
providing a matrix M, said matrix M having n rows and n columns and comprising a first plurality of actual arguments, wherein n is a positive integer;
providing a vector b, said vector b having n elements and comprising a second plurality of actual arguments;
disguising said first plurality of actual arguments by embedding, in a memory of a first computer, said matrix M in a larger matrix M′
;
disguising said second plurality of actual arguments by embedding, in said memory of said first computer, said vector b in a larger vector b′
;
computing a solution vector x′
that satisfies the equation M′
x′
=b′
, wherein said computation of said solution vector x′
is allocated between said first computer and a second computer with each of said first computer and said second computer performing at least a portion of said computation of said solution vector x′
; and
deriving, with said first computer, a solution vector x from said solution vector x′
, said solution vector x satisfying the equation Mx=b.
-
-
42. A method for outsourcing the computation of an estimate for the solution of a quadrature computation of the form
-
a b f ( x ) ⅆ x , from a first computer to a second computer, wherein the estimate to be computed must conform to a predetermined level of accuracy, and wherein function f(x) is disguised to hinder discovery of function f(x) by the second computer and unauthorized parties, the method comprising the steps of;
creating, in a memory of a first computer, at least seven numbers yi, wherein i is an integer index variable having a property of 1≦
i≦
max, wherein y1=a and ymax=b, and wherein said other numbers yi satisfy the following properties;
a<
yi<
b, and
yi−
1<
yi;
creating, in said memory of said first computer, a number of values v1, wherein i is an integer index variable having a property of 1≦
i≦
max, wherein there are the same number of values vi as numbers yi, and wherein said values vi satisfy the following properties;
vi−
1<
vi, andmin |f(x)|≈
v1≦
vmax≈
max|f(x)|, wherein the operations min |f(x)| and max |f(x)| return the minimum and maximum absolute value of function f(x), respectively;
creating, in said memory of said first computer, a cubic spline g(y) with breakpoints comprising said numbers yi such that g(yi)=vi;
integrating, with said first computer, cubic spline g(y) from a to b to obtain a value I1;
creating disguised function h(x), said disguised function h(x) being created using said function f(x) and said cubic spline g(y);
transmitting said disguised function h(x) and a designation of said predetermined level of accuracy to a second computer;
computing, with said second computer, a value I2 using said disguised function h(x) and said designation of said predetermined level of accuracy; and
computing, with said first computer, said estimate by subtracting said value I1 from said I2.
-
-
43. A method for outsourcing a convolution computation of two vectors from a first computer to a second computer, wherein the contents of the vectors are disguised prior to delivery of the vectors to the second computer for the convolution computation, thereby hindering discovery of the contents of the vectors by the second computer and unauthorized parties, the method comprising the steps of:
-
providing, in a memory of a first computer, a first vector M1 and a second vector M2, said first vector M1 and said second vector M2 being of equivalent size;
creating, in said memory of said first computer, a first pseudorandom vector S1 and a second pseudorandom vector S2, said first pseudorandom vector S1 and second pseudorandom vector S2 being the same size as said first vector M1, and said second vector M2;
generating, with said first computer, a first pseudorandom number α
, a second pseudorandom number β
, a third pseudorandom number γ
, a fourth pseudorandom number β
′
, and a fifth pseudorandom number γ
′
; and
disguising said first vector M1 and said second vector M2 by generating vector D, vector E, vector F, vector G, vector H, and vector I as follows;
D=α
M1, E=α
M2, F=β
M1, G=β
M2, H=β
′
M1, and I=β
′
M2. - View Dependent Claims (44, 45)
-
-
46. A method for outsourcing the computation of a solution to a linear differential equation Ly=F(x,y) of order N from a first computer to a second computer, wherein N is a positive integer, the linear differential equation having boundary conditions y(xi)=yi, wherein i is an integer index variable and 0≦
- i≦
N, wherein the linear differential equation and boundary conditions are disguised prior to delivery of the linear differential equation and boundary conditions to the second computer for the convolution computation, thereby hindering discovery of the linear differential equation and boundary conditions by the second computer and unauthorized parties, the method comprising the steps of;creating, in a memory of a first computer, a cubic spline g(x) and a function u(x)=Lg(x), wherein Lg(x) is a linear differential equation of order N;
disguising said linear differential equation Ly by adding said function u(x) thereto;
disguising said boundary conditions y(xi) by adding function u(xi) thereto;
transmitting said disguised linear differential equation Ly and said disguised boundary conditions v(xi) to a second computer;
deriving, with said second computer, a solution function z(x) from said disguised linear differential equation Ly and said disguised boundary conditions y(xi);
deriving, with said first computer, a solution to said linear differential equation Ly from said solution function z(x).
- i≦
-
47. A method for disguising a symbolic mathematical expression in a software program, the method comprising the step of:
automatically applying one or more transformation techniques to said symbolic mathematical expression, said one or more transformation techniques selected from the group consisting of disguising constants in said symbolic mathematical expression and replacing variable names in said symbolic mathematical expression.
-
48. A method for disguising a symbolic mathematical expression in a software program, the method comprising the step of:
automatically applying one or more transformation techniques to said symbolic mathematical expression, said one or more transformation techniques selected from the group consisting of applying at least one mathematical identity function to said symbolic mathematical expression and applying at least one expansion of unity to said symbolic mathematical expression.
-
49. A method for analyzing a digital image wherein a computation for detecting edges of the digital image is outsourced from a first computer to a second computer, and wherein the digital image is disguised prior to delivery of the digital image to the second computer for the edge detection computation thereby hindering discovery of the digital image by the second computer and unauthorized parties, the method comprising the steps of:
-
providing a digital image, said digital image being represented by an n×
n array of pixel values p(x,y) between 0 and N on a unit square 0≦
x,y≦
1, wherein n and N are positive integers;
creating, in a memory of a first computer, at least ten ordered number pairs xi,yi, wherein i is an integer index variable having a property of 1≦
i≦
max, wherein x1,y1=0, wherein xmax,ymax=1, and wherein the remaining ordered number pairs xi,yi satisfy the following properties;
0<
xi,yi<
1, and
xi−
1,yi−
1<
xi,yi;
creating, in said memory of said first computer, a plurality of pseudorandom values vij such that 0≦
vij≦
N/2;
creating, in said memory of said first computer, four number pairs ak,bk, wherein k is an integer index variable having a property of 1≦
k≦
4, each said number pair ak,bk comprising positive pseudorandom numbers such that a1=min(ak), a4=max(ak), b1=min(bk), and b4=max(bk);
creating, in said memory of said first computer, a bi-cubic spline s(x,y), such that each s(xi,yi)=vij;
determining, with said first computer, a linear change of coordinates from (x,y) coordinates to (u,v) coordinates that maps said unit square into a rectangle with vertices (ak,bk);
disguising said pixel values p(x,y) by converting, with said first computer, said pixel values p(x,y) to pixel values p(u,v);
disguising said bi-cubic spline s(x,y) by converting, with said first computer, said bi-cubic spline s(x,y) to a bi-cubic spline s(u,v); and
transmitting said pixel values p(u,v) and said bi-cubic spline s(u,v) to a second computer. - View Dependent Claims (50)
-
-
51. A method for analyzing a digital image wherein the desired outcome of the analysis is an approximation of whether a digital image object appears in a larger digital image, wherein a portion of the analysis is outsourced from a first computer to a second computer, and wherein the digital image object and the larger digital image are disguised prior to delivery of the digital image object and the larger digital image to the second computer for the analysis thereby hindering discovery of the image object and the larger image by the second computer and unauthorized parties, the method comprising the steps of:
-
providing an image I, said image I being represented by a matrix of size N×
N, wherein N is a positive integer;
providing an image object P, said image object P being represented by matrix of size n×
n, wherein n is a positive integer, and wherein n<
N;
generating, with a first computer, a random matrix S1 of size N×
N, and a random said matrix S1 comprising a plurality of pseudorandom arguments;
generating, with a first computer, a matrix S2 of size n×
n, said matrix S2 comprising a plurality of pseudorandom arguments;
generating, with said first computer, first pseudorandom number α
, second pseudorandom number β
, third pseudorandom number γ
, fourth pseudorandom number β
′
, and fifth pseudorandom number γ
′
;
disguising said image object P and said image I by computing, with said first computer, a set of disguised arguments comprising the following matrices;
G=α
I+S1,
H=α
P+S2,
J=β
I−
γ
S1,
K=β
P−
γ
S2,
L=β
′
I−
γ
′
S1, and
M=β
P−
γ
′
S2; and
transmitting said matrices G, H, J, K, L, and M to a second computer. - View Dependent Claims (52, 53)
-
-
54. A method for outsourcing the sorting of a plurality of numbers from a first computer to a second computer, wherein the plurality of numbers is disguised prior to delivery of the plurality of numbers to the second computer thereby hindering discovery of the plurality of numbers by the second computer and unauthorized parties, the method comprising the steps of:
-
providing a set of n numbers E a plurality of n numbers E={e1, . . . , en}, wherein n is a positive integer;
selecting, with a first computer, a strictly increasing function f( );
generating, with said first computer, a sorted sequence {Λ
=λ
I, . . . ,λ
n} of n pseudorandom numbers;
disguising said plurality of numbers E by computing, with said first computer, a plurality of numbers E′
=f(E) and sequence Λ
′
=f(Λ
), where wherein f(E) is obtained from plurality of numbers E by replacing every element ei of plurality of numbers E with f(ei);
computing, with said first computer, set W;
by concatenating said plurality of numbers E′ and
said sequence Λ
′
; and
disguising set W by randomly permuting set W with said first computer. - View Dependent Claims (55)
-
-
56. A method for text string analysis wherein it is desired to determine whether a text pattern appears in a larger text string, wherein a portion of the analysis is outsourced from a first computer to a second computer, and wherein the text pattern and the text string are disguised prior to delivery of the text pattern and the text string to the second computer thereby hindering discovery of the text pattern and the text string by the second computer and unauthorized parties, the method comprising the steps of:
-
(a) providing a text string T of length N, wherein N is a positive integer, said text string T comprising N text symbols, and wherein P is;
(b) providing a text pattern P of length n, wherein n is a positive integer that is smaller than N, said text pattern P comprising n text symbols;
(c) providing an alphabet A, said alphabet A comprises the comprising a plurality of possible text symbols that could appear in said text string T or said text pattern P;
(d) selecting a text symbol from said alphabet A;
(e) generating disguised text string Tx by replacing, with a first computer, each instance of said selected text symbol in said text string T with the number 1, and replacing each other text symbol in said text string T with the number 0;
(f) generating disguised text pattern Px by replacing, with a first computer, each instance of said selected text symbol in said text pattern P with the number 1, and replacing each other text symbol in text pattern P with the number 0; and
(g) augmenting, with a first computer, said text pattern Px into a longer text string P′
of length N by adding zeros thereto;
(h) transmitting said text string Tx and said text string P′
to a second computer. - View Dependent Claims (57)
-
-
58. A first computer for disguising the contents of a matrix prior to delivery of the matrix to a second computer for a matrix multiplication computation thereby hindering discovery of the matrix by the second computer and unauthorized parties, the computer comprising:
-
a memory;
computer circuitry configured to define a first actual matrix M1 in said memory, said first actual matrix M1 comprising a first plurality of actual arguments;
computer circuitry configured to define a second actual matrix M2 in said memory, said second actual matrix M2 comprising a second plurality of actual arguments;
computer circuitry configured to prepare at least two disguising matrices in said memory, each said disguising matrix being a sparse matrix comprising at least one non-zero disguising argument, wherein each said at least one non-zero disguising argument comprises a pseudorandom number;
computer circuitry configured to disguise said first plurality of actual arguments by computing a first disguised matrix X using said first actual matrix M1 and at least one said disguising matrix, said first disguised matrix X comprising a first plurality of disguised arguments; and
computer circuitry configured to disguise said second plurality of actual arguments by computing a second disguised matrix Y using said second actual matrix M2 and at least one disguising matrix, said second disguised matrix Y comprising a second plurality of disguised arguments. - View Dependent Claims (59, 60)
-
-
61. A computer for disguising a matrix prior to transmitting the matrix to another computer for a matrix inversion computation thereby hindering discovery of the matrix by the other computer and unauthorized parties, the computer comprising:
-
a memory;
computer circuitry configured to define a matrix M in said memory, said matrix M comprising a first plurality of actual arguments;
computer circuitry configured to prepare a pseudorandom matrix S, said pseudorandom matrix S comprising a plurality of pseudorandom arguments;
computer circuitry configured to generate a first disguising matrix P1 and a second disguising matrix P2, wherein each said disguising matrix is a sparse matrix comprising at least one non-zero disguising argument, wherein each said at least one non-zero disguising argument comprises a pseudorandom number; and
computer circuitry configured to disguise said matrix M by computing a matrix Q as follows;
Q=P1*M*S*P2−
1. - View Dependent Claims (62, 63)
-
-
64. A computer for use in the computation of a solution vector for a system of linear equations of the form Mx=b, the computer being able to disguise the system of linear equations prior to delivery of the system of linear equations to another computer for computation of the solution vector, thereby hindering discovery of the system of linear equations by the other computer and unauthorized parties, the computer comprising:
-
a memory;
computer circuitry configured to receive a matrix M and store said matrix M in said memory, said matrix M comprising n rows and n columns wherein n is a positive integer, said matrix M comprising a first plurality of actual arguments;
computer circuitry configured to receive a vector b and store said vector b in said memory, said vector b comprising n elements, said vector b comprising a second plurality of actual arguments;
computer circuitry configured to generate a matrix B having the same dimensions as matrix M and comprising a plurality of pseudorandom arguments;
computer circuitry configured to disguise said second plurality of actual arguments by replacing a row of said matrix B with said vector b;
computer circuitry configured to prepare at least two disguising matrices, each said disguising matrix being a sparse matrix comprising at least one non-zero disguising argument, wherein each said at least one non-zero disguising argument comprises a pseudorandom number;
computer circuitry configured to disguise said first plurality of actual arguments by computing a matrix C′
using said matrix M and at least two of said at least two disguising matrices;
computer circuitry configured to disguise said second plurality of actual arguments by computing a matrix G′
using said matrix B and at least two of said at least two disguising matrices;
computer circuitry configured to output said matrices C′ and
G′
;
computer circuitry configured to receive a matrix U, said a matrix U computed from said matrix G′ and
the inverse of said matrix C′
;
computer circuitry configured to compute a matrix X using said matrix U and at least two of said at least two disguising matrices; and
computer circuitry configured to derive a solution vector x from said matrix X, said solution vector x satisfying the following;
Mx=b.
-
-
65. A computer for use in the computation of a solution vector x for a system of linear equations of the form Mx=b, the computer being able to disguise the system of linear equations prior to delivery of the system of linear equations to another computer for computation of the solution vector, thereby hindering discovery of the system of linear equations by the other computer and unauthorized parties, the computer comprising:
-
a memory;
computer circuitry configured to receive a matrix M and store said matrix M in said memory, said matrix M comprising a first plurality of actual arguments;
computer circuitry configured to receive a vector b and store said vector b in said memory, said vector b comprising a second plurality of actual arguments;
computer circuitry configured to disguise said first plurality of actual arguments by embedding said matrix M in a matrix M′
, said matrix M′
being larger than said matrix M;
computer circuitry configured to disguise said second plurality of actual arguments by embedding said vector b in a vector b′
, said vector b′
being larger than said vector b;
computer circuitry configured to outsource to another computer at least a portion of the computation of a solution vector x′
that satisfies equation M′
x′
=b′
; and
computer circuitry configured to derive a solution vector x from said solution vector x′
, said solution vector x satisfying the equation Mx=b.
-
-
66. A computer for use in disguising a function f(x) to hinder discovery of function f(x) by other computers or unauthorized parties, wherein the function f(x) is used in the computation of an estimate for the solution of a quadrature computation of the form
-
a b f ( x ) ⅆ x , and wherein the estimate to be computed must conform to a predetermined level of accuracy, the computer comprising;
a memory;
computer circuitry configured to receive a function f(x) and store said function f(x) in said memory;
computer circuitry configured to generate at least seven numbers yi, wherein i is an integer index variable having a property of 1≦
i≦
max, wherein y1=a and ymax=b, and wherein said other numbers yi satisfy the following properties;
a<
yi<
b, and
yi−
1<
yi;
computer circuitry configured to generate a quantity of values vi, wherein i is an integer index variable having a property of 1≦
i≦
max, wherein there are the same quantity of said values vi as said numbers yi, and wherein said values vi satisfy the following properties;
vi−
1<
vi, andmin |f(x)|≈
v1≦
vmax≈
max |f(x)|, wherein the operations min |f(x)| and max |f(x)| return the minimum and maximum absolute value of function f(x), respectively;
computer circuitry configured to generate a cubic spline g(y) with breakpoints comprising cubic spline said numbers yi such that g(yi)=vi;
computer circuitry configured to integrate said cubic spline g(y) from a to b to obtain a value I1;
computer circuitry configured to create disguised function h(x), said disguised function h(x) being created using said function f(x) and said cubic spline g(y);
computer circuitry configured to output said disguised function h(x) and a designation of said predetermined level of accuracy;
computer circuitry configured to receive a value I2 from another computer, wherein said value I2 is computed using said disguised function h(x) and said designation of said predetermined level of accuracy; and
computer circuitry configured to compute said estimate using said value I1 and said value I2.
-
-
67. A computer for use in disguising two vectors, wherein said vectors are to be used in a convolution computation, and wherein the contents of the vectors are disguised prior to delivery of the vectors to another computer for the convolution computation thereby hindering discovery of the contents of the vectors by the other computer and unauthorized parties, the computer comprising:
-
a memory;
computer circuitry configured to define a first vector M1 and a second vector M2 in said memory, said first vector M1 and said second vector M2 being of equivalent size;
computer circuitry configured to define a first pseudorandom vector S1 and a second pseudorandom vector S2, said first pseudorandom vector S1 and second pseudorandom vector S2 being the same size as said first vector M1 and said second vector M2;
computer circuitry configured to define a first pseudorandom number α
, a second pseudorandom number β
, a third pseudorandom number γ
, a fourth pseudorandom number β
′
, and a fifth pseudorandom number γ
′
;
computer circuitry configured to disguise said first vector M1 and said second vector M2 by generating vector D, vector E, vector F, vector G, vector H, and vector I as follows;
D=α
M1, E=α
M2, F=β
M1, G=β
M2, H=β
′
M1, and I=β
′
M2;
computer circuitry configured to disguise said first pseudorandom vector S1 and said second pseudorandom vector S2 by generating vector J, vector K, vector L, and vector M as follows;
J=γ
S1, K=γ
S2, L=γ
′
S1, and M=γ
′
S2;
computer circuitry configured to supply said vectors S1, S2, D, E, F, G, H, I, J, K, L, and M to another computer for the computation of a vector U, a vector U′
, and a vector W as follows;
W=(D−
S1){circle around (x)}(E+S2),
U=(F−
J){circle around (x)}(G−
K), and
U′
=(H−
L){circle around (x)}(I−
M);
computer circuitry configured to receive said vector U, said vector U′
, and said vector W;
computer circuitry configured to derive a convolution of said first vector M1 and said second vector M2 using said vector U, said vector U′
, said vector W.
-
-
68. A computer for use in disguising a linear differential equation prior to delivery of the linear differential equation to another computer where a solution to the linear differential equation will be solved, thereby hindering discovery of the linear differential equation by the other computer and unauthorized parties, the computer comprising:
-
a memory;
a linear differential equation Ly=F(x,y) of order N stored in said memory, wherein N is a positive integer, the linear differential equation having boundary conditions y(xi)=yi stored in said memory, wherein i is an integer index variable and 0≦
i<
N;
computer circuitry configured to define a cubic spline g(x) and a function u(x)=Lg(x), wherein Lg(x) is a linear differential equation of order N;
computer circuitry configured to disguise said linear differential equation Ly by adding said function u(x) thereto;
computer circuitry configured to disguise said boundary conditions y(xi) by adding function u(xi) thereto;
computer circuitry configured to transmit said disguised linear differential equation Ly and said disguised boundary conditions y(xi) to at least one other computer;
computer circuitry configured to receive a solution function z(x) from said at least one other computer, said solution function z(x) being derived from said disguised linear differential equation Ly and said disguised boundary conditions v(xi); and
computer circuitry configured to derive a solution to said linear differential equation Ly from said solution function z(x).
-
-
69. A computer comprising:
-
a memory, said memory comprising a software program; and
computer circuitry configured to automatically apply one or more transformation techniques to a symbolic mathematical expression in said software program, said one or more transformation techniques selected from the group consisting of disguising constants in said symbolic mathematical expression and replacing variable names in said symbolic mathematical expression.
-
-
70. A computer comprising:
-
a memory, said memory comprising a software program; and
computer circuitry configured to automatically apply one or more transformation techniques to a symbolic mathematical expression in said software program, said one or more transformation techniques selected from the group consisting of applying at least one mathematical identity function to said symbolic mathematical expression and applying at least one expansion of unity to said symbolic mathematical expression.
-
-
71. A first computer for use in analyzing a digital image wherein a computation for detecting edges of digital image is to be outsourced to a second computer, and wherein the digital image is disguised prior to delivery of the digital image to the second computer for the edge detection computation thereby hindering discovery of the digital image by the second computer and unauthorized parties, the first computer comprising:
-
a memory, said memory comprising a digital image, wherein said digital image is represented in said memory by an n×
n array of pixel values p(x,y) between 0 and N on a unit square 0≦
x,y≦
1, wherein n and N are positive integers;
computer circuitry configured to define at least ten ordered number pairs xi,yi in said memory, wherein i is an integer index variable having a property of 1≦
i≦
max, wherein x1,y1=0, wherein xmax,ymax=1, and wherein the remaining ordered number pairs xi,yi satisfy the following properties;
0<
xi,yi<
1, and
xi−
1,yi−
1<
xi,yi;
computer circuitry configured to define a plurality of pseudorandom values vij such that 0≦
vij≦
N/2 in said memory;
computer circuitry configured to define four number pairs ak,bk in said memory, wherein k is an integer index variable having a property of 1≦
k≦
4, each said number pair ak,bk comprising positive pseudorandom numbers such that a1=min(ak), a4=max(ak), b1=min(bk), and b4=max(bk);
computer circuitry configured to define a bi-cubic spline s(x,y) in said memory, such that s(xi,yi)=vij;
computer circuitry configured to determine a linear change of coordinates from (x,y) coordinates to (u,v) coordinates that maps said unit square into a rectangle with vertices (ak,bk);
computer circuitry configured to disguise said pixel values p(x,y) by converting said pixel values p(x,y) to pixel values p(u,v);
computer circuitry configured to disguise said bi-cubic spline s(x,y) by converting said bi-cubic spline s(x,y) to a bi-cubic spline s(u,v);
computer circuitry configured to output said pixel values p(u,v) and said bi-cubic spline s(u,v) to another computer;
computer circuitry configured to receive an image e(u,v) computed using said pixel values p(u,v) and said bi-cubic spline s(u,v); and
computer circuitry configured to derive edges of said image e(u,v).
-
-
72. A first computer for use in analyzing a digital image wherein the desired outcome of the analysis is an approximation of whether a digital image object appears in a larger digital image, wherein a portion of the analysis is outsourced from the first computer to a second computer, and wherein the image object and the larger image are disguised prior to delivery of the image object and the larger image to the second computer for the analysis thereby hindering discovery of the image object and the larger image by the second computer and unauthorized parties, the first computer comprising:
-
a memory, said memory comprising an image I, said image I being represented in said memory by a matrix of size N×
N, wherein N is a positive integer;
an image object P in said memory, said image object P being represented by matrix of size n×
n, wherein n is a positive integer, and wherein n<
N;
computer circuitry configured to define matrix S1 of size N×
N, said matrix S1 comprising a plurality of pseudorandom arguments;
computer circuitry configured to define a matrix S2 of size n×
n, said matrix S2 comprising a plurality of pseudorandom arguments;
computer circuitry configured to define, in said memory, a first pseudorandom number α
, a second pseudorandom number β
, a third pseudorandom number γ
, a fourth pseudorandom number β
′
, and a fifth pseudorandom number γ
′
;
computer circuitry configured to disguise said image I and said image object P by computing a set of disguised arguments comprising the following matrices;
G=α
I+S1,
H=α
P+S2,
J=β
I−
γ
S1,
K=β
P−
γ
S2,
L=β
′
I−
γ
′
S1, and
M=β
′
P−
γ
′
S2;
computer circuitry configured to output said set of disguised arguments;
to a second computer for computation of a first score matrix, a second score matrix, and a third score matrix, said first score matrix being computed using said matrices G and H, said second score matrix being computed using said matrices J and K, and said third score matrix being computed using said matrices L and M;
computer circuitry configured to receive said first score matrix, said second score matrix, and said third score matrix; and
computer circuitry configured to derive a final score matrix using said first score matrix, said second score matrix, and said third score matrix, said final score matrix comprising an approximation of whether said image object P appears in said image I.
-
-
73. A first computer for use in preparing a set of numbers to be outsourced from the first computer to a second computer where the set of numbers will be sorted into a sequence by the second computer, and wherein the set of numbers is disguised prior to delivery of the set of numbers to the second computer thereby hindering discovery of the set of numbers by the second computer and unauthorized parties, the first computer comprising:
-
a memory, said memory comprising a set of n numbers E, wherein n is a positive integer;
computer circuitry configured to define a strictly increasing function f( ) in said memory;
computer circuitry configured to define, in said memory, a sorted sequence {Λ
=λ
I, . . . ,λ
n} of n pseudorandom numbers;
computer circuitry configured to disguise said set of numbers E by computing a set of n numbers E′
=f(E) and a sequence n numbers Λ
′
=f(Λ
), wherein f(E) is a set of numbers obtained from E by replacing every element ei by f(ei), and f(Λ
) is a sequence of numbers obtained from Λ
by replacing every element λ
i by f(λ
i);
computer circuitry configured to compute a set of numbers W by concatenating said plurality of numbers E′ and
said sequence Λ
′
;
computer circuitry configured to randomly permute set W;
computer circuitry configured to output said randomly permuted set W for sorting by a second computer;
computer circuitry configured to receive sorted set W′
from said second computer, said sorted set W′
being derived by sorting said randomly permuted set W; and
computer circuitry configured to derive sorted sequence E″
={e1, . . . , en} from said sorted set W′
.
-
-
74. A first computer for use in text string analysis wherein it is desired to determine whether a text pattern appears in a larger text string, and wherein the text pattern and the text string are disguised prior to delivery of the text pattern and the text string to a second computer for a text string pattern matching computation, thereby hindering discovery of the text pattern and the text string by the second computer and unauthorized parties, the first computer comprising:
-
a memory, said memory comprising a test string T is a text string of length N, wherein N is a positive integer, said text string T comprising N text symbols;
a text pattern P in said memory, said text pattern P being of length n, wherein n is a positive integer that is smaller than N, said text pattern P comprising n text symbols;
an alphabet A in said memory, said alphabet A comprising the plurality of possible text symbols that could appear in text string T or text pattern P;
computer circuitry configured to iteratively select one text symbol from said alphabet A until all text symbols from said alphabet A have been selected one time;
computer circuitry configured to, for each selected text symbol in said alphabet A;
(i) generate, in said memory, a disguised text string Tx by replacing each instance of said selected text symbol in said text string T with the number 1, and replacing each other text symbol in text string T with the number 0;
(ii) generate, in said memory, disguised text pattern Px by replacing each instance of said selected text symbol in said text pattern P with the number 1, and replacing each other text symbol in said text pattern P with the number 0;
(iii) augment said text pattern Px into a text string P′
of length N by adding zeros thereto;
(iv) output said text string P′ and
said text string Tx to a second computer; and
(v) receive a value Dx computed using said text string P′ and
said text string Tx; and
computer circuitry configured to compute a score matrix using said values Dx for all said text symbols in said alphabet A.
-
Specification