# US 2018/0324175 A1 · Implicit certificates using ring learning with errors

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2018/0324175 A1
- Document ID: US20180324175A1
- Status: Published application
- Kind: A1
- Application number: 15/589,783
- Filed: 2017-05-08
- Published: 2018-11-08
- Earliest claimed: 2017-05-08
- Assignees: Amazon Technologies, Inc.
- Applicants: Amazon Technologies, Inc.
- Inventors: Matthew John Campagna; Marguerite Marie Nathalie Delcourt
- Web page: https://patentgrep.com/patent/US20180324175A1

## CPC

- H04L 63/0823: {using certificates (cryptographic mechanisms or cryptographic arrangements for entity authentication involving certificates H04L9/3263)}
- H04L 9/0825: {using asymmetric-key encryption or public key infrastructure [PKI], e.g. key signature or public key certificates}
- H04L 9/0838: {Key agreement, i.e. key establishment technique in which a shared key is derived by parties as a function of information contributed by, or associated with, each of these (network architectures or network communication protocols for key exchange in a packet data network H04L63/061)}
- H04L 9/088: {Usage controlling of secret information, e.g. techniques for restricting cryptographic keys to pre-authorized uses, different access levels, validity of crypto-period, different key- or password length, or different strong and weak cryptographic algorithms (network architectures or network communication protocols for using time-dependent keys in a packet data network H04L63/068)}
- H04L 9/3263: {involving certificates, e.g. public key certificate [PKC] or attribute certificate [AC]; Public key infrastructure [PKI] arrangements (network architectures or network communication protocols for supporting authentication of entities using certificates in a packet data network H04L63/0823)}
- H04L 63/061: {for key exchange, e.g. in peer-to-peer networks (cryptographic mechanisms or cryptographic arrangements for key agreement H04L9/0838)}
- H04L 63/04: {for providing a confidential data exchange among entities communicating through data packet networks}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

An implicit certificate is based on a ring learning with errors (“RLWE”) public keys that are, in some examples, resistant to quantum-based computing attacks. Various methods are described that request, generate, verify, and use the implicit certificates. In some examples, the system provides an implicit certificate that enables communication between two parties that are identified at the time of certificate generation. In another example, the system provides a certificate that may be used to communicate with a variety of different parties. The implicit certificate generation algorithm yields a public key purportedly bound to U. Confirmation that the public key is bound to U is obtained after use of the corresponding private key. Binding of an entity to its associated public key and accessibility to the private key, are verified as a result of successful key use.

## Claims

### Claim 1

A computer-implemented method, comprising:
acquiring a set of domain parameters, the domain parameters including a ring of integers, a hash function, and a domain polynomial;
acquiring, from a requesting entity, a certificate request and information that identifies the requesting entity, the certificate request based at least in part on a first sample from the ring of integers, the first sample selected by the requesting entity;
acquiring a second sample from the ring of integers;
determine a public contribution value based at least in part on the certificate request, the second sample, and the domain polynomial;
generating a certificate from the public contribution value and the information that identifies the requesting entity;
generating a requester-specific contribution value associated with the requester based at least in part on a private key of a public/private key pair associated with a certificate authority, a hash of the certificate determined in accordance with the hash function, and the second sample; and
transmitting, to the requester, the certificate.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1, wherein:
the certificate request is based at least in part on a first error term associated with the first sample;
the public contribution value is based at least in part on a second error term associated with the second sample; and
the requester-specific contribution value associated with the requester is based at least in part on a third error term associated with the private key.

### Claim 3 (depends on 1)

The computer-implemented method of claim 1, wherein:
the requester is a client computer system; and
the certificate authority is a computer system trusted by the client computer system.

### Claim 4 (depends on 1)

The computer-implemented method of claim 1, further comprising:
determining that the identity of the requesting entity matches information that identifies the requesting entity; and
wherein the information is provided by the requesting entity with the certificate request.

### Claim 5 (depends on 1)

The computer-implemented method of claim 1, wherein the certificate is generated as a result of having determined that the identity of the requesting entity is valid.

### Claim 6

A system, comprising:
one or more processors; and
memory storing computer-executable instructions that, if executed, cause the one or more processors to:
identify a set of domain parameters, the domain parameters indicating a ring of integers, a hash function, and a domain polynomial;
determine a public contribution value, the public contribution value based at least in part on a certificate request, a sample selected from the ring of integers, and the domain polynomial; and
generate a certificate from at least a certificate request associated with a requester, a sample selected from the ring of integers, the domain polynomial, and an identifier associated with the requester.

### Claim 7 (depends on 6)

The system of claim 6, wherein:
the certificate request and the identifier are acquired from the requester; and
the certificate request is based at least in part on a randomly selected sample selected from the ring of integers by the requester.

### Claim 8 (depends on 7)

The system of claim 7, wherein the computer-executable instructions cause the one or more processors to further:
generate a requester-specific contribution value associated with the requester based at least in part on a private key of a public/private key pair associated with the system, a hash of the certificate determined in accordance with the hash function, and the sample; and
provide, to the requester, the certificate, and the requester-specific contribution value.

### Claim 9 (depends on 6)

The system of claim 6, wherein:
the requester is a service running on a first computer system; and
the system is a second computer system that is trusted by the requester.

### Claim 10 (depends on 6)

The system of claim 6, wherein the computer-executable instructions cause the one or more processors to further:
verify the identity of the requester using the identifier; and
as a result of having verified the identity of the requester, generate the certificate.

### Claim 11 (depends on 6)

The system of claim 6, wherein the computer-executable instructions cause the one or more processors to further:
determine that the identity of the requester does not match the identifier; and
as a result of determining that the identity of the requester does not match the identifier, notify an entity associated with the identifier of the request that the certificate request is denied.

### Claim 12 (depends on 8)

The system of claim 8, wherein the computer-executable instructions cause the one or more processors to further:
the public contribution value is based at least in part on a second certificate request provided by a second requester;
the certificate is generated at least in part using a second identifier associated with the second requester; and
wherein the certificate is bound to a communication between the requester and the second requester.

### Claim 13 (depends on 12)

The system of claim 12, wherein:
the second certificate request is based at least in part on a second randomly selected sample selected from the ring of integers by the second requester; and
the computer-executable instructions cause the one or more processors to further provide, to the second requester, the certificate, the requester-specific contribution value.

### Claim 14

A non-transitory computer-readable storage medium having stored thereon 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:
acquire a set of domain parameters, the domain parameters including a ring of integers, a hash function, and a domain polynomial;
select a sample from the ring of integers;
generate a certificate request based at least in part on the domain polynomial and the sample;
acquire a certificate, a requester-specific contribution value, and a public contribution value, from a certificate authority in exchange for providing the certificate request;
generate a private key based at least in part on the requester-specific contribution value, a hash of the certificate in accordance with the hash function, and the sample; and
perform a cryptographic operation using the private key.

### Claim 15 (depends on 14)

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:
acquire a public contribution value from a certificate authority in exchange for providing the certificate request; and
generate a public key based at least in part on a public key of the certificate authority, a hash of the certificate in accordance with the hash function, and the public contribution value.

### Claim 16 (depends on 14)

The non-transitory computer-readable storage medium of claim 14, wherein the certificate is based at least in part on the certificate request, a second sample selected by the certificate authority from the ring of integers, the domain polynomial and identifying information associated with the computer system.

### Claim 17 (depends on 14)

The non-transitory computer-readable storage medium of claim 14, wherein the public contribution value is based at least in part on the certificate request, a second sample selected by the certificate authority from the ring of integers, and the domain polynomial.

### Claim 18 (depends on 17)

The non-transitory computer-readable storage medium of claim 17, wherein the requester-specific contribution value is based at least in part on a private key of a public/private key pair associated with the certificate authority, a hash of the certificate determined in accordance with the hash function, and the second sample.

### Claim 19 (depends on 14)

The non-transitory computer-readable storage medium of claim 14, wherein:
the certificate is based at least in part on a second certificate request provided by another computer system;
the certificate is based at least in part on identifying information associated with the other computer system; and
the certificate enables protected communication between the requester and the other computer system.

### Claim 20 (depends on 19)

The non-transitory computer-readable storage medium of claim 19, wherein the certificate does not facilitate communication between parties other than the requester and the other computer system.