Generation of shared secrets using pairwise implicit certificates

1. A computer-implemented method, comprising:

obtaining, at a first entity, an implicit certificate associated with a communication channel between the first entity and a second entity;

deriving, from the implicit certificate, a first private key associated with the first entity and a second public key associated with the second entity;

obtaining a first private static key based at least in part on a distribution;

determining a first difference based at least in part on the first private static key, a domain polynomial associated with a ring of integers, the first private key, and a first public key associated with the first entity;

providing the first difference to the second entity;

obtaining, from the second entity, a second difference that is based at least in part on a second private static key associated with the second entity, the domain polynomial associated with the ring of integers, a second private key associated with the second entity, and a second public key associated with the second entity;

determining a second static public key from the second public key and the second difference; and

generating a shared key based at least in part on the second public static key and the first private static key.

2. The computer-implemented method of claim 1 , further comprising:

determining a first private ephemeral key on the ring of integers;

determining a first public ephemeral key based at least in part on the domain polynomial and first private ephemeral key;

providing the first public ephemeral key to the second entity;

obtaining a second public ephemeral key from the second entity; and

wherein the shared key is based at least in part on the second public ephemeral key and the first private ephemeral key.

3. The computer-implemented method of claim 2 , further comprising:

selecting a sample from a ring of integers;

determining the shared key based at least in part on the difference between a product of the second public static key and the first private ephemeral key, and a product of the second public ephemeral key and the first private static key; and

extracting shared bits from coefficients of the sample.

4. The computer-implemented method of claim 1 , further comprising:

establishing a network connection from the first entity to the second entity;

generating a message;

encrypting the message with the shared key to produce an encrypted message;

transmitting the encrypted message to the second entity via the network connection; and

wherein the first entity and the second entity are computer systems.

5. The computer-implemented method of claim 1 , wherein the ring of integers is part of a ring learning with errors problem used to generate the implicit certificate.

6. A system, comprising:

one or more processors; and

memory that stores computer-executable instructions that, if executed, cause the one or more processors to:

derive, from an implicit certificate, a first private key associated with a first entity and a second public key associated with a second entity;

obtain a first private static key;

provide a first difference to the second entity, the first difference based at least in part on the first private static key, a domain polynomial associated with a ring of integers, the first private key, and a first public key associated with the first entity;

obtain, from the second entity, a second difference that is based at least in part on a second private static key associated with the second entity, the domain polynomial associated with the ring of integers, a second private key associated with the second entity, and a second public key associated with the second entity;

determine a second static public key from the second public key and the second difference; and

generate a shared key based at least in part on the first private static key and the second static public key.

7. The system of claim 6 , wherein the first private static key is generated stochastically based at least in part on a probability distribution.

8. The system of claim 6 , wherein the instructions further comprise instructions that, if executed, cause the one or more processors to use the shared key to communicate using encrypted communications.

9. The system of claim 6 , wherein the first difference enables the second entity to derive the shared key.

10. The system of claim 6 , wherein the implicit certificate is associated with a communication channel between the first entity and a second entity.

11. The system of claim 6 , wherein:

determining the shared key based at least in part on the first private static key and the second static public key; and

the shared key is determined based at least in part on an ephemeral key generated by the second entity.

12. The system of claim 6 , wherein the instructions further comprise instructions that, if executed, cause the one or more processors to:

determine a first private ephemeral key;

determine a first public ephemeral key based at least in part on the first private ephemeral key; and

provide the first public ephemeral key to the second entity to enable the second entity to determine the shared key.

13. The system of claim 6 , wherein the instructions further comprise instructions that, if executed, cause the one or more processors to:

obtain a message;

generate a digital signature for the message using the shared key; and

provide the message and the digital signature to the second entity.

14. A non-transitory computer-readable storage medium including executable instructions that, as a result of being executed by one or more processors of a computer system, cause the computer system to at least:

derive, from an implicit certificate, a second public key associated with a second entity;

obtain a first private static key;

determining a first difference based at least in part on the first private static key, a domain polynomial associated with a ring of integers, the first private key, and a first public key associated with the first entity;

providing the first difference to the second entity;

obtaining, from the second entity, a second difference that is based at least in part on a second private static key associated with the second entity, the domain polynomial associated with the ring of integers, a second private key associated with the second entity, and a second public key associated with the second entity;

determine a second static public key from the second public key and the value;

generate a shared key based at least in part on the second static public key, and the first private static key.

15. The non-transitory computer-readable storage medium of claim 14 , wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to:

determine a first public ephemeral key associated with the first entity;

provide the first public ephemeral key to the second entity; and

obtain a second public ephemeral key from the second entity.

16. The non-transitory computer-readable storage medium of claim 15 , wherein the second public ephemeral key is used by the first entity to generate the shared key.

17. The non-transitory computer-readable storage medium of claim 15 , wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to:

determine the first public ephemeral key based at least in part on the first private ephemeral key.

18. The non-transitory computer-readable storage medium of claim 14 , wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to:

use the shared key to encrypt a message to result in an encrypted message; and

transmit the encrypted message to the second entity.

19. The non-transitory computer-readable storage medium of claim 14 , wherein the value is generated based at least in part on a second private static key associated with the second entity, a domain polynomial associated with a ring of integers, the second private key, and the second public key.

20. The non-transitory computer-readable storage medium of claim 14 , wherein successful use of the second public key verifies a cryptographic binding between the second entity and the second public key.

21. The non-transitory computer-readable storage medium of claim 14 , wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to verify that the implicit certificate is bound to the second entity by verifying a digital signature using the shared key.