Policy-based key recovery

• US 10,263,775 B2
• Filed: 06/23/2017
• Issued: 04/16/2019
• Est. Priority Date: 06/23/2017
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Setty, Srinath Tumkur Venkatacha, Venkatesan, Ramarathnam, Zwiefel, Brant Lee, Chandran, Nishanth, Lokam, Satyanarayana V., Lee, Jonathan David, Selvis, Sharmila Deva
• Primary Examiner(s): Moorthy, Aravind K
• Application Number:
  US15/631,563
• Publication Number:
  US 20180375653A1
• Time in Patent Office: 662 Days
• Field of Search: 713171, 380262, 380278, 380282, 380 44
• CPC Class Codes: H04L 2463/062 applying encryption of the keys cryptographic mechanisms or cryptographic arrangements for key distribution using key encryption key H04L9/0822
• CPC Class Codes: H04L 63/0435 wherein the sending and receiving network entities apply symmetric encryption, i.e. same key used for encryption and decryption cryptographic mechanisms or cryptographic arrangements for symmetric key encryption H04L9/06
• CPC Class Codes: H04L 63/0442 wherein the sending and receiving network entities apply asymmetric encryption, i.e. different keys for encryption and decryption cryptographic mechanisms or cryptographic arrangements for public-key encryption H04L9/30
• CPC Class Codes: H04L 63/061 for key exchange, e.g. in peer-to-peer networks cryptographic mechanisms or cryptographic arrangements for key agreement H04L9/0838
• CPC Class Codes: H04L 63/062 for key distribution, e.g. centrally by trusted party cryptographic mechanisms or cryptographic arrangements for key distribution involving a central third party H04L9/0819
• CPC Class Codes: H04L 63/20 for managing network security; network security policies in general filtering policies H04L63/0227
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

A device establishes a key recovery policy and generates a key that is protected based on the key recovery policy. The key recovery policy indicates which combinations of other entities can recover the protected key. The device generates different shares of the protected key, each share being a value that, in combination with the other share(s), allows the protected key to be recovered. Each share is associated with a particular leaf agent, the device encrypts each share with the public key of the leaf agent associated with the share and provides the encrypted share to a service. When recovery of the protected key is desired, a recovering authority can generate the protected key only if the recovering authority receives decrypted shares from a sufficient one or combination of leaf agents as indicated by the recovery policy.

Claims

1. A method comprising:

obtaining a key recovery policy for a protected key, the key recovery policy specifying a set of possible combinations of multiple leaf agents that can assist in recovering the protected key;

generating, based on the key recovery policy, multiple key shares of the protected key;

associating ones of the multiple key shares with ones of the multiple leaf agents based at least in part on the key recovery policy;

encrypting each of the multiple shares of the key with a public key of a public/private key pair of the leaf agent with which the key share is associated; and

sending the encrypted key shares to a service for storage.

2. The method as recited in claim 1, the key recovery policy indicating, using combinatorial logic, which combinations of the multiple leaf agents can, by providing their respective key shares, allow the protected key to be recovered.

3. The method as recited in claim 1, the associating ones of the multiple key shares with ones of the multiple leaf agents comprising:

identifying a node in a policy tree, the node being either the protected key or an internal node;

determining whether two leaf agents that make up the node are combined using a logical AND operation or a logical OR operation;

in response to the two leaf agents being combined using the logical OR operation, providing a same key share of the protected key to each of the two leaf agents; and

in response to the two leaf agents being combined using the logic AND operation;

generating two key shares that can be multiplied together to generate the protected key, the two key shares being generated from the protected key or key share associated with the node;

associating a first key share of the two key shares with a first leaf agent of the two leaf agents; and

associating a second key share of the two key shares with a second leaf agent of the two leaf agents.

4. The method as recited in claim 1, the associating ones of the multiple key shares with ones of the multiple leaf agents comprising:

identifying a node in a policy tree, the node being either the protected key or an internal node;

determining whether two leaf agents that make up the node are combined using a logical AND operation or a logical OR operation;

in response to the two leaf agents being combined using the logical OR operation, providing a same key share of the protected key to each of the two leaf agents; and

in response to the two leaf agents being combined using the logic AND operation;

generating two key shares that can be added together to generate the protected key, the two key shares being generated from the protected key or key share associated with the node;

associating a first key share of the two key shares with a first leaf agent of the two leaf agents; and

associating a second key share of the two key shares with a second leaf agent of the two leaf agents.

5. The method as recited in claim 1, further comprising sending, to the service for storage, an encryption value for a policy tree representing the key recovery policy, a digital signature generated on the encryption value, and a proof value indicating that each possible combination of the set of possible combinations is able recover the protected key.

6. The method as recited in claim 1, further comprising generating a proof indicating, without revealing the multiple shares of the protected key, that each possible combination of the set of possible combinations is to able recover the protected key.

7. The method as recited in claim 6, wherein a policy tree represents the key recovery policy, the method further comprising using, in generating the proof, correlated randomness at OR gates in the policy tree.

8. The method as recited in claim 6, wherein a policy tree represents the key recovery policy, the method further comprising using, in generating the proof, uncorrelated randomness by fixing a child of each OR gate to propagate encryption of the nodes of the policy tree.

9. The method as recited in claim 6, further comprising using a Decisional Diffie-Hellman assumption as a basis for generating the multiple key shares, encrypting each of the multiple shares of the key, and generating the proof.

10. A method comprising:

obtaining a key recovery policy for a protected key, the key recovery policy specifying a set of possible combinations of multiple leaf agents that can assist in recovering the protected key;

attempting to obtain decrypted key shares from leaf agents in one or more of the set of possible combinations of leaf agents; and

in response to obtaining decrypted key shares from leaf agents in one or more of the set of possible combinations of leaf agents, using the decrypted key shares to recover the protected key.

11. The method as recited in claim 10, the key recovery policy indicating, using combinatorial logic, which combinations of the multiple leaf agents can, by providing their respective decrypted key shares, allow the protected key to be recovered.

12. The method as recited in claim 10, the method being implemented in a recovering authority device, the attempting to obtain the decrypted key shares comprising:

sending, to a leaf agent, a request for the decrypted key share associated with the leaf agent; and

receiving, from a leaf agent device associated with the leaf agent, the decrypted key share only if the leaf agent determines it is acceptable for the recovering authority device to recover the protected key.

13. The method as recited in claim 10, the using the decrypted key shares comprising multiplying together appropriate ones of the decrypted key shares in accordance with the key recovery policy.

14. The method as recited in claim 10, the decrypted key shares having been generated based on a Decisional Diffie-Hellman assumption.

15. A device comprising:

a processor; and

a computer-readable storage medium having stored thereon multiple instructions that, responsive to execution by the processor, cause the processor to;

obtain a key recovery policy for a protected key of the device, the key recovery policy specifying a set of combinations of multiple leaf agents that can assist in recovering the protected key;

generate, based on the key recovery policy, multiple key shares of the protected key;

associate ones of the multiple key shares with ones of the multiple leaf agents based at least in part on the key recovery policy;

encrypt each of the multiple shares of the key with a public key of a public/private key pair of the leaf agent with which the key share is associated; and

send the encrypted key shares to a service for storage.

16. The device as recited in claim 15, the multiple instructions further causing the processor to use a Decisional Diffie-Hellman assumption as a basis for generating the multiple key shares and encrypting each of the multiple shares of the key.

17. The device as recited in claim 15, the key recovery policy indicating, using combinatorial logic, which combinations of the multiple leaf agents can, by providing their respective key shares, allow the protected key to be recovered.

18. The device as recited in claim 15, the multiple instructions further causing the processor to generate a proof indicating, without revealing the multiple shares of the protected key, that each possible combination of the set of possible combinations is able to recover the protected key.

19. The device as recited in claim 18, wherein a policy tree represents the key recovery policy, the multiple instructions further causing the processor to use, in generating the proof, correlated randomness at OR gates in the policy tree.

20. The device as recited in claim 18, wherein a policy tree represents the key recovery policy, the multiple instructions further causing the processor to use, in generating the proof, uncorrelated randomness by fixing a child of each OR gate to propagate encryption of the nodes of the policy tree.