# US 10,771,265 B2 · Cryptographic methods and systems for managing digital certificates with linkage values

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

- Number: US 10,771,265 B2
- Document ID: US10771265B2
- Status: Granted
- Kind: B2
- Application number: 16/136,621
- Filed: 2018-09-20
- Published: 2019-03-21
- Granted: 2020-09-08
- Earliest claimed: 2017-09-21
- Assignees: LG Electronics Inc.; University of Sao Paulo
- Applicants: LG Electronics, Inc.; University of SãO Paulo
- Inventors: Marcos A. Simplicio, Jr.; Eduardo Lopes Cominetti; Harsh Kupwade Patil; Jefferson E. Ricardini; Leonardo T. D. Ferraz; Marcos Vinicius M. Silva
- Web page: https://patentgrep.com/patent/US10771265B2

## CPC

- H04L 9/3268: {using certificate validation, registration, distribution or revocation, e.g. certificate revocation list [CRL]}
- H04L 9/006: {involving public key infrastructure [PKI] trust models (network architecture or network communication protocol for supporting authentication of entities using certificates in a packet data network H04L63/0823)}
- H04L 9/008: {involving homomorphic encryption}
- H04L 9/0825: {using asymmetric-key encryption or public key infrastructure [PKI], e.g. key signature or public key certificates}
- H04L 9/0861: {Generation of secret information including derivation or calculation of cryptographic keys or passwords}
- H04L 9/0869: {involving random numbers or seeds}
- H04L 9/321: {involving a third party or a trusted authority}
- H04L 9/3239: {involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD}
- H04L 9/3247: {involving digital signatures}
- H04L 9/3297: {involving time stamps, e.g. generation of time stamps}
- H04L 63/0823: {using certificates (cryptographic mechanisms or cryptographic arrangements for entity authentication involving certificates H04L9/3263)}
- H04L 63/104: {Grouping of entities}
- H04L 63/108: {when the policy decisions are valid for a limited amount of time}
- H04W 12/04: Key management, e.g. using generic bootstrapping architecture [GBA]
- H04W 12/069: using certificates or pre-shared keys
- H04L 9/50: {using hash chains, e.g. blockchains or hash trees}
- H04L 63/0421: {Anonymous communication, i.e. the party's identifiers are hidden from the other party or parties, e.g. using an anonymizer}
- H04L 63/068: {using time-dependent keys, e.g. periodically changing keys (cryptographic mechanisms or cryptographic arrangements for controlling usage of secret information H04L9/088)}
- H04L 67/12: specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks
- H04L 2209/42: Anonymization, e.g. involving pseudonyms
- H04L 2209/805: Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
- H04L 2209/84: Vehicles
- H04W 4/40: for vehicles, e.g. vehicle-to-pedestrians [V2P]
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72)

## Abstract

Improved pseudonym certificate management is provided for connected vehicle authentication and other applications. Temporary revocation of a certificate is enabled. With respect to Security Credential Management Systems (SCMS), linkage authorities can be eliminated without compromising the system security. Other embodiments are also provided.

## Claims

### Claim 1

A method for managing digital certificates by entities operable to perform computing on digital values and to communicate with each other, each digital certificate comprising a corresponding linkage value linkable to linkage values of one or more other digital certificates to define one or more groups of digital certificates, the method comprising performing the following operations to generate the digital certificates:
generating, by a first entity, first pre-linkage values;
receiving, by the first entity, encrypted second pre-linkage values from a second entity, wherein the second pre-linkage values have a similar format as the first pre-linkage values, wherein each encrypted second pre-linkage value is not decryptable by the first entity;
for each digital certificate:
selecting, by the first entity, a first pre-linkage value and an encrypted second pre-linkage value;
combining, by the first entity, the selected first pre-linkage value with the selected encrypted second pre-linkage value without decrypting the second pre-linkage value, to obtain an encrypted combined value, the encrypted combined value being decryptable by the second entity but not the first entity; and
sending, by the first entity to the second entity, a certificate generation request comprising the encrypted combined value.

### Claim 2 (depends on 1)

The method of claim 1, further comprising performing, by the second entity, operations of:
receiving the certificate generation requests;
for each certificate generation request:
decrypting the corresponding encrypted combined value; and
creating the corresponding digital certificate with a linkage value obtained from the corresponding encrypted combined value.

### Claim 3 (depends on 1)

The method of claim 1, wherein:
the second entity performs verification operations on consecutive groups of n certificate generation requests received from the first entity, where n is greater than one, wherein for each group of n certificate generation requests, performing the verification operation comprises:
(a) receiving from the first entity a list of the encrypted second pre-linkage values for the group without an indication which of the encrypted second pre-linkage values corresponds to any given certificate generation request;
(b) receiving from the first entity an output of a computation performed on the first pre-linkage values for the group, the output not disclosing which of the first pre-linkage values corresponds to any given certificate generation request;
(c) matching the combined values for the group with the values received in (a) and (b);
(d) if there is no match in (c), then generating an error report.

### Claim 4 (depends on 1)

The method of claim 1, wherein for each combined value, the second entity does not know which second pre-linkage value was selected by the first entity for the combined value.

### Claim 5 (depends on 1)

The method of claim 1, further comprising:
receiving, by the first entity, an identification of a certificate generation request corresponding to a first digital certificate which is a member of a group to be revoked;
in response to the certificate generation request, determining, by the first entity:
a first group-linking value from which the first pre-linkage values corresponding to the digital certificates in the group are computable; and
second group-linking data allowing the second computer entity to determine a second group-linking value from which the second pre-linkage values corresponding to the digital certificates in the group are computable;
determining the second group-linking value by the second entity from the second group-linking data;
revoking the digital certificates in the group by making available, to potential verifiers of validity of the digital certificates, the first and second group-linking values, and/or the first and second pre-linkage values corresponding to the digital certificates in the group, to allow the potential verifiers to match a linkage value of any digital certificate against the linkage values of the digital certificates in the group.

### Claim 6 (depends on 5)

The method of claim 5, wherein the certificate generation request received by the first entity is determined by the second entity based on the linkage value of the first digital certificate.

### Claim 7 (depends on 1)

The method of claim 1, further comprising:
receiving, by the first entity, an identification of a certificate generation request corresponding to a first digital certificate which is a member of a group to be revoked;
in response to the certificate generation request, determining, by the first entity:
a first group-linking value from which the first pre-linkage values corresponding to the digital certificates in the group are computable; and
second group-linking data allowing the second computer entity to determine a second group-linking value from which the second pre-linkage values corresponding to the digital certificates in the group are computable;
determining the second group-linking value by the second entity from the second group-linking data;
verifying whether the first and second group-linking values match the linkage value of the first digital certificate;
if the verifying is successful, then revoking the digital certificates in the group by making available, to potential verifiers of validity of the digital certificates, the first and second group-linking values, and/or the first and second pre-linkage values corresponding to the digital certificates in the group, to allow the potential verifiers to match a linkage value of any digital certificate against the linkage values of the digital certificates in the group;
if the verifying fails, then generating an error report.

### Claim 8 (depends on 6)

The method of claim 6 wherein:
each digital certificate is associate with a validity time period which is a time period when the certificate is valid;
the first entity receives an indication of one or more validity time periods for the group to be revoked, the group being limited to certificates valid in the one or more validity time periods; and
the first and second group-linking values correspond to the indication of the one or more time periods.

### Claim 9 (depends on 6)

The method of claim 6 wherein:
each digital certificate is associate with a type;
the first entity receives an indication of one or more types for the group to be revoked, the group being limited to certificates associated with the one or more types; and
the first and second group-linking values correspond to the indication of the one or more types.

### Claim 10 (depends on 1)

The method of claim 1 wherein:
the digital certificates are generated in response to the first entity receiving one or more user requests, each user request being a request to generate a batch of digital certificates for a respective user for a plurality of time periods, each batch including, for each time period, a plurality of digital certificates valid in the time period;
wherein each digital certificate is not trackable to the respective user without secret information available to the first entity;
wherein the second entity does not receive the secret information m generating the certificates;
wherein the method further comprises, for each digital certificate generated by the second entity, the first entity receiving, from the second entity, a message comprising the digital certificate encrypted by the second entity, wherein each encrypted digital certificate is not decryptable by the first entity, and the first entity sending the message to the respective user, the user being able to decrypt the digital certificate upon receipt of the message.

### Claim 11

A method for managing digital certificates by entities operable to perform computing on digital values and to communicate with each other, the entities comprising at least a first entity and a second entity, each digital certificate comprising a corresponding linkage value linkable to linkage values of one or more other digital certificates to define one or more groups of digital certificates, the method comprising performing the following operations to generate the digital certificates:
sending by the second entity, to the first entity, encrypted second pre-linkage values which are not decryptable by the first entity;
for each digital certificate:
receiving, by the second entity from the first entity, a certificate generation request comprising an encrypted combined value obtained by the first entity combining a selected first pre-linkage value with a selected second pre-linkage value, wherein the second pre-linkage value has a similar format as the first pre-linkage value, the first and second pre-linkage values being selected by the first entity, the second entity not knowing which of the first and second pre-linkage values were selected for the encrypted combined value, the encrypted combined value not being decryptable by the first entity;
in response to the certificate generation request:
decrypting, by the second entity, the corresponding encrypted combined value; and
creating, by the second entity, the corresponding digital certificate with a linkage value obtained from the corresponding combined value.

### Claim 12 (depends on 11)

The method of claim 11 wherein:
the digital certificates are generated in response to one or more user requests, each user request being a request to generate a batch of digital certificates for a respective user for a plurality of time periods, each batch including, for each time period, a plurality of digital certificates valid in the time period;
wherein each digital certificate is not trackable to the respective user without secret information available to the first entity;
wherein the second entity does not receive the secret information m generating the certificates;
wherein the method further comprises, for each digital certificate generated by the second entity, the second entity generating and sending a message to the first entity, the message comprising the digital certificate encrypted by the second entity, wherein each encrypted digital certificate is not decryptable by the first entity but is decryptable by the respective user upon receipt of the message.

### Claim 13

A tangible non-transitory machine readable storage medium comprising instructions executable by a first entity to perform a method for managing digital certificates by entities operable to perform computing on digital values and to communicate with each other, each digital certificate comprising a corresponding linkage value linkable to linkage values of one or more other digital certificates to define one or more groups of digital certificates, the method comprising performing the following operations to generate the digital certificates:
generating, by the first entity, first pre-linkage values;
receiving, by the first entity, encrypted second pre-linkage values from a second entity, wherein the second pre-linkage values have a similar format as the first pre-linkage values, wherein each encrypted second pre-linkage value is not decryptable by the first entity;
for each digital certificate:
selecting, by the first entity, a first pre-linkage value and an encrypted second pre-linkage value;
combining, by the first entity, the selected first pre-linkage value with the selected encrypted second pre-linkage value without decrypting the second pre-linkage value, to obtain an encrypted combined value, the encrypted combined value being decryptable by the second entity but not the first entity; and
sending, by the first entity to the second entity, a certificate generation request comprising the encrypted combined value.

### Claim 14 (depends on 13)

A first entity comprising the tangible non-transitory machine readable storage medium of claim 13.

### Claim 15 (depends on 14)

The first entity of claim 14, wherein the method further comprises performing, by the second entity, operations of:
receiving the certificate generation requests;
for each certificate generation request:
decrypting the corresponding encrypted combined value; and
creating the corresponding digital certificate with a linkage value obtained from the corresponding encrypted combined value.

### Claim 16 (depends on 14)

The first entity of claim 14, wherein in the method:
the second entity performs verification operations on consecutive groups of n certificate generation requests received from the first entity, where n is greater than one, wherein for each group of n certificate generation requests, performing the verification operation comprises:
(a) receiving from the first entity a list of the encrypted second pre-linkage values for the group without an indication which of the encrypted second pre-linkage values corresponds to any given certificate generation request;
(b) receiving from the first entity an output of a computation performed on the first pre-linkage values for the group, the output not disclosing which of the first pre-linkage values corresponds to any given certificate generation request;
(c) matching the combined values for the group with the values received in (a) and (b);
(d) if there is no match in (c), then generating an error report.

### Claim 17 (depends on 14)

The first entity of claim 14, wherein in the method, for each combined value, the second entity does not know which second pre-linkage value was selected by the first entity for the combined value.