Efficient computation of a threshold partially-oblivious pseudorandom function

A computing device comprising:

• an interface configured to interface and communicate with a communication system;
• memory that stores operational instructions;
• and
• processing circuitry operably coupled to the interface and to the memory, wherein the processing circuitry is configured to execute the operational instructions to:
• process an input value that is associated with a key based on a blinding key in accordance with a Threshold Partially-Oblivious Pseudorandom Function (TP-OPRF) blinding operation to generate a blinded input, wherein key is unknown to a plurality of shareholder computing devices and includes a Data Encryption Key (DEK) or a Key Encryption Key (KEK);
• select a threshold number of shareholder computing devices that are associated with a Key Management System (KMS) service, wherein a TP-OPRF key includes a plurality of unique PRF keys that are distributedly stored among the plurality of shareholder computing devices, wherein the threshold number of shareholder computing devices includes fewer than or all of the plurality of shareholder computing devices;
• transmit, via the communication system, the blinded input to at least the threshold number of shareholder computing devices associated with the KMS service;
• receive, via the communication system and from the at least the threshold number of shareholder computing devices associated with the KMS service, at least a threshold number of blinded output components, wherein:
• a first blinded output component of the at least the threshold number of blinded output components is based on processing of the blinded input based on a Partially-Oblivious Pseudorandom Function (P-OPRF) using a first unique share of a P-OPRF secret and an arbitrary exposed message by a first shareholder computing device of the plurality of shareholder computing devices;
• a second blinded output component of the at least the threshold number of blinded output components is based on processing of the blinded input based on the P-OPRF using a second unique share of the P-OPRF secret and the arbitrary exposed message by a second shareholder computing device of the plurality of shareholder computing devices;
• the first unique share of the P-OPRF secret is associated with the first shareholder computing device of the plurality of shareholder computing devices;
• and
• the second unique share of the P-OPRF secret is associated with the second shareholder computing device of the plurality of shareholder computing devices;
• process the at least the threshold number of blinded output components to generate a blinded output;
• process the blinded output based on the blinding key in accordance with a TP-OPRF unblinding operation to generate the key that is associated with the input value;
• and
• access secure information based on the key.

A method for execution by a computing device, the method comprising:

• processing an input value that is associated with a key based on a blinding key in accordance with a Threshold Partially-Oblivious Pseudorandom Function (TP-OPRF) blinding operation to generate a blinded input;
• selecting a threshold number of shareholder computing devices that are associated with a Key Management System (KMS) service, wherein a TP-OPRF key includes a plurality of unique PRF keys that are distributedly stored among a plurality of shareholder computing devices, wherein the threshold number of shareholder computing devices includes fewer than or all of the plurality of shareholder computing devices;
• transmitting, via an interface of the computing device that is configured to interface and communicate with a communication system and via the communication system, the blinded input to at least the threshold number of shareholder computing devices associated with the KMS service;
• receiving, via the interface, via the communication system, and from the at least the threshold number of shareholder computing devices associated with the KMS service, at least a threshold number of blinded output components, wherein a blinded output component of the at least the threshold number of blinded output components is based on processing of the blinded input based on a Partially-Oblivious Pseudorandom Function (P-OPRF) using a unique share of a P-OPRF secret and an arbitrary exposed message by a shareholder computing device of the plurality of shareholder computing devices, wherein the arbitrary exposed message is known to the shareholder computing device of the plurality of shareholder computing devices, and the unique share of the P-OPRF secret is associated with the shareholder computing device of the plurality of shareholder computing devices;
• processing the at least the threshold number of blinded output components to generate a blinded output;
• processing the blinded output based on the blinding key in accordance with a TP-OPRF unblinding operation to generate the key that is associated with the input value;
• and
• accessing secure information based on the key.