System and method utilizing function secret sharing with conditional disclosure of secrets

A method, comprising:

• decomposing a function into a plurality of function shares, the function returning a Boolean result based on whether an input y satisfies a query on a data set, the function shares hiding the function from non-collaborating entities that separately execute the function shares;
• sending each the function shares to a respective one of a plurality of servers having a same data set;
• executing the function shares on the data set at the plurality of servers to obtain a respective plurality of shares;
• simulating a conditional disclosure of secrets operation on the shares and the input y, the conditional disclosure of secrets operation using a secret known to at least one of the plurality of servers, and further using a source of randomness shared between the plurality of servers;
• and
• returning a Boolean value corresponding to the Boolean result based on the conditional disclosure of secrets operation returning the secret.

A system comprising:

• a plurality of servers each having access to a same data set;
• and
• a computing entity coupled via a network to the plurality of servers and operable to:
• decompose a function into a plurality of function shares, the function returning a Boolean result based on whether an input y satisfies a query on a data set, the function shares hiding the function from non-collaborating entities that separately execute the function shares;
• and
• send each the function shares to a respective one of the plurality of servers;
• wherein the plurality of servers are operable to:
• receive and execute the function shares on the data set to obtain a respective plurality of shares;
• simulate a conditional disclosure of secrets operation on the shares and the input y, the conditional disclosure of secrets operation using a secret known to at least one of the plurality of servers, and further using a source of randomness shared between the plurality of servers;
• and
• return a Boolean value corresponding to the Boolean result based on the conditional disclosure of secrets operation returning the secret.