A computing device includes an interface configured to interface and communicate with a communication system, a memory that stores operational instructions, and processing circuitry operably coupled to the interface and to the memory that is configured to execute the operational instructions to perform various operations. The computing device generates a sub-key identifier based on a data ID, which is based on unique ID value(s) associated with an encrypted data object, and a requester secret. The computing device processes the sub-key identifier in accordance with an Oblivious Pseudorandom Function (OPRF) blinding operation to generate a blinded input and an Oblivious Key Access Request (OKAR). The computing device transmits the OKAR to another computing device (e.g., Key Management System (KMS) service) and receives a blinded sub-key therefrom. The computing device processes the blinded sub-key in accordance with an OPRF unblinding operation to generate the key and accesses secure data thereby.