Method and system for privacy-preserving linear optimization

Abstract

A method for using a privacy preserving linear optimization technique to perform computations on encrypted data while ensuring that the original data remains confidential and secure from any unauthorized access based on secure multi-party computation is provided. The method includes: receiving, from each of several entities, a respective input that includes encrypted data; constructing a table that includes first information that relates to an objective function, second information that relates to a boundary value, and third information that relates to a polynomial function that is applicable to each respective input; and determining a value that maximizes the polynomial function subject to a constraint that a result of applying the objective function to the value is less than or equal to the boundary value.

What is claimed is: 
     
         1 . A method for using a privacy preserving linear optimization technique to perform computations on encrypted data while ensuring that original data remains confidential and secure from unauthorized access, the method being implemented by at least one processor, the method comprising:
 establishing, by the at least one processor and via a network, a joint optimization session with a plurality of entities, wherein the each of the plurality of entities are external entities with respect to one another and resides on a differing network;   receiving, by the at least one processor from the plurality of entities, respective inputs, wherein each of the respective inputs includes first encrypted data, and wherein encryption performed on the first encrypted data is performed by each of the respective entity among the plurality of entities for limiting exposure of underlying data of the first encrypted data to other entities among the plurality of entities;   constructing, by the at least one processor and using the respective inputs received from the plurality of entities, a first table that includes first information that relates to a first predetermined objective function, second information that relates to a first predetermined boundary value, and third information that relates to a predetermined polynomial function that is applicable to each respective input among the respective inputs received;   performing a plurality of iterations for each of the respective inputs, wherein each of the plurality of iterations include:
 determining, by the at least one processor, a pivot column of the first table based on the received respective inputs; 
 determining, by the at least one processor, a pivot row of the first table based on the received respective inputs and the pivot column; 
 updating, by the at least one processor, the pivot row by performing a first predetermined operation that is based on the predetermined polynomial function and the first predetermined boundary value; and 
 updating, by the at least one processor, each respective column of the first table by performing a second predetermined operation that is based on the predetermined polynomial function, the first predetermined boundary value, and the updated pivot row; and 
   determining, by the at least one processor and based on performing the plurality of iterations for each respective input, a first value that maximizes the predetermined polynomial function while satisfying a constraint that a result of applying the first predetermined objective function to the first value is less than or equal to the first predetermined boundary value, wherein underlying data of the first value remain unexposed to the plurality of entities for reducing gross exposure to the plurality of entities.   
     
     
         2 . The method of  claim 1 , wherein the determining of the pivot column comprises:
 applying a predetermined minimum element function to each respective column of the first table;   computing a most significant bit of a respective vector that corresponds to each respective column of the first table;   reconstructing an encrypted value with respect to the most significant bit; and   determining the pivot column based on a result of the reconstructing of the encrypted value.   
     
     
         3 . The method of  claim 1 , wherein the determining of the pivot row comprises:
 retrieving elements of the pivot column;   constructing a vector of tuples based on the elements of the pivot column;   applying a predetermined positive minimum function to the vector of tuples; and   determining the pivot row based on a result of the applying of the predetermined positive minimum function to the vector of tuples.   
     
     
         4 . The method of  claim 1 , wherein the first predetermined operation includes a predetermined table-set function that updates respective elements from the first table on an element-by-element basis. 
     
     
         5 . The method of  claim 4 , wherein the second predetermined operation includes the predetermined table-set function and a predetermined truncation function that truncates an authenticated sharing of each respective input by a predetermined number of bits. 
     
     
         6 . The method of  claim 1 , wherein each respective entity corresponds to a financial portfolio that is associated with a respective client. 
     
     
         7 . The method of  claim 6 , further comprising calculating a market netting metric that relates to a respective degree of risk to a privacy associated with each respective financial portfolio. 
     
     
         8 . The method of  claim 7 , wherein the market netting metric includes at least one from among a first metric that relates to an allocation of exposure of each respective entity, a second metric that relates to an amount of funds that are required with respect to at least one entity from among the plurality of entities, and a third metric that relates to a number of shares associated with at least one entity from among the plurality of entities. 
     
     
         9 . A computing apparatus for using a privacy preserving linear optimization technique to perform computations on encrypted data while ensuring that original data remains confidential and secure from unauthorized access, the computing apparatus comprising:
 a processor;   a memory; and   a communication interface coupled to each of the processor and the memory,   wherein the processor is configured to:
 establish, via a network, a joint optimization session with a plurality of entities, wherein the each of the plurality of entities are external entities with respect to one another and resides on a differing network; 
 receive, via the communication interface from each respective entity from among the plurality of entities, a respective input that includes first encrypted data, wherein encryption performed on the first encrypted data is performed by each of the respective entity among the plurality of entities for limiting exposure of underlying data of the first encrypted data to other entities among the plurality of entities; 
 construct, using the respective input from each respective entity among the plurality of entities, a first table that includes first information that relates to a first predetermined objective function, second information that relates to a first predetermined boundary value, and third information that relates to a predetermined polynomial function that is applicable to each respective input; 
 perform a plurality of iterations for each respective input, wherein each of the plurality of iterations include:
 determining a pivot column of the first table based on the received respective inputs; 
 determining a pivot row of the first table based on the received respective inputs and the pivot column; 
 updating the pivot row by performing a first predetermined operation that is based on the first predetermined polynomial function and the first predetermined boundary value; and 
 updating each respective column of the first table by performing a second predetermined operation that is based on the first predetermined polynomial function, the first predetermined boundary value, and the updated pivot row; 
 
 determine, based on performing the plurality of iterations for each respective input, a first value that maximizes the predetermined polynomial function while satisfying a constraint that a result of applying the first predetermined objective function to the first value is less than or equal to the first predetermined boundary value, wherein underlying data of the first value remain unexposed to the plurality of entities for reducing gross exposure to the plurality of entities. 
   
     
     
         10 . The computing apparatus of  claim 9 , wherein the processor is further configured to determine the pivot column by:
 applying a predetermined minimum element function to each respective column of the first table;   computing a most significant bit of a respective vector that corresponds to each respective column of the first table;   reconstructing an encrypted value with respect to the most significant bit; and   determining the pivot column based on a result of the reconstruction of the encrypted value.   
     
     
         11 . The computing apparatus of  claim 9 , wherein the processor is further configured to determine the pivot row by:
 retrieving elements of the pivot column;   constructing a vector of tuples based on the elements of the pivot column;   applying a predetermined positive minimum function to the vector of tuples; and   determining the pivot row based on a result of the applying of the predetermined positive minimum function to the vector of tuples.   
     
     
         12 . The computing apparatus of  claim 9 , wherein the first predetermined operation includes a predetermined table-set function that updates respective elements from the first table on an element-by-element basis. 
     
     
         13 . The computing apparatus of  claim 12 , wherein the second predetermined operation includes the predetermined table-set function and a predetermined truncation function that truncates an authenticated sharing of each respective input by a predetermined number of bits. 
     
     
         14 . The computing apparatus of  claim 9 , wherein each respective entity corresponds to a financial portfolio that is associated with a respective client. 
     
     
         15 . The computing apparatus of  claim 14 , wherein the processor is further configured to calculate a market netting metric that relates to a respective degree of risk to a privacy associated with each respective financial portfolio. 
     
     
         16 . The computing apparatus of  claim 15 , wherein the market netting metric includes at least one from among a first metric that relates to an allocation of exposure of each respective entity, a second metric that relates to an amount of funds that are required with respect to at least one entity from among the plurality of entities, and a third metric that relates to a number of shares associated with at least one entity from among the plurality of entities. 
     
     
         17 . A non-transitory computer readable storage medium storing instructions for using a privacy preserving linear optimization technique to perform computations on encrypted data while ensuring that original data remains confidential and secure from unauthorized access, the storage medium comprising executable code which, when executed by a processor, causes the processor to:
 establish, via a network, a joint optimization session with a plurality of entities, wherein the each of the plurality of entities are external entities with respect to one another and resides on a differing network; 
 receive, from each respective entity from among the plurality of entities, a respective input that includes first encrypted data, wherein encryption performed on the first encrypted data is performed by each of the respective entity among the plurality of entities for limiting exposure of underlying data of the first encrypted data to other entities among the plurality of entities; 
 construct, using the respective input from each respective entity among the plurality of entities, a first table that includes first information that relates to a first predetermined objective function, second information that relates to a first predetermined boundary value, and third information that relates to a predetermined polynomial function that is applicable to each respective input; 
 perform a plurality of iterations for each respective input, wherein each of the plurality of iterations include:
 determining a pivot column of the first table based on the received respective inputs; 
 determining a pivot row of the first table based on the received respective inputs and the pivot column; 
 updating the pivot row by performing a first predetermined operation that is based on the first predetermined polynomial function and the first predetermined boundary value; and 
 updating each respective column of the first table by performing a second predetermined operation that is based on the first predetermined polynomial function, the first predetermined boundary value, and the updated pivot row; 
 
 determine, based on performing the plurality of iterations for each respective input, a first value that maximizes the predetermined polynomial function while satisfying a constraint that a result of applying the first predetermined objective function to the first value is less than or equal to the first predetermined boundary value, wherein underlying data of the first value remain unexposed to the plurality of entities for reducing gross exposure to the plurality of entities.