Patent Description:
This specification generally relates to authentication of electronic devices.

Electronic authentication is a process of verifying digital credentials of electronic devices. <CIT> discloses systems, methods and apparatus for authenticating a device, such as a wireless charger which transmits an authentication request. <CIT> discloses an inductive charging system which transfers energy by inductive charging.

The appended independent claims define the scope of protection. When an electronic device is plugged into a charger or placed in range of a wireless charger, it is desirable for the device to authenticate that the charger is genuine or certified before requesting that the charger deliver power. This protects the device from being exposed to high currents and voltages that may be delivered by a counterfeit charger. Likewise, a charger may verify that a device is genuine or certified before providing current to the device. The authentication techniques discussed herein can be used for wired power delivery, wireless power delivery, and for other device interactions that do not involve power transfer.

In some implementations, the authentication process satisfies several constraints to improve security, privacy, and usability. For example, one constraint is that the authentication process operate without relying on a network connection or any device other than the charger and the device to be charged. Another constraint is that the authentication process be substantially anonymous, so that a charger cannot uniquely identify a specific charged device and/or the charged device cannot uniquely identify a specific charger. As another example, it is desirable that credentials of compromised devices be revocable to block the use of devices that have been compromised or had their credentials improperly duplicated. However, revocation of credentials for compromised devices should cause very few, if any, uncompromised chargers or devices to no longer pass the authentication process. These constraints and ways to satisfy them are discussed in detail below.

In some implementations, the verification process between electronic devices and chargers is designed to occur without an Internet connection or any other connection to a network. In other words, the charged device and charger can be configured to authenticate each other by direct communication, without the need to communicate with any other devices (that is, the messages passed between the charged device and charger are not relayed by any other device). This can be helpful when a network connection is not available, for example, if a traveler needs to charge a device in an airport in a country where the traveler does not have Internet service. The charged device, the charger, or both, may have the ability to connect to the Internet or another network. In some implementations, network connections may be used at times for updates or configuration, as discussed below. Nevertheless, an active network connection is not required for the authentication process at the time of charging. Also, in many cases the charger is unlikely to have Internet access itself, because that would add significantly to the cost of the charger. In many cases, the charger can communicate only with the device to be charged, for example, over a charging cable or a short-range wireless connection, such as inductive coupling for wireless charging or Bluetooth.

To protect against potential misuse of credentials, the authentication scheme can allow for revocation of credentials. For example, a counterfeiter may dismantle a valid device to extract its certificates, and then use those certificates in the counterfeit devices. Accordingly, the system can have a revocation mechanism for revoking certifications compromised in this way. Revoking a certification should result in de-authenticating as few valid devices (e.g., genuine chargers or genuine charged devices) as possible. In particular, it is undesirable for the revocation of a single certificate to de-authenticate all devices of a given model. Thus, even devices of the same model or type should not all rely on the same certificate for authentication. At the same time, individual devices should not rely on unique certificates in the authentication process, because this would allow individual devices (e.g., chargers or charged devices) to be uniquely identified and thus would take away anonymity.

The authentication process may be used for any anonymized authentication between devices. The process can be two-way anonymized, where two devices each confirm that the other is valid without providing uniquely identifying information. In some cases, the process may be one-way anonymized, where the identity of only one of the devices is hidden. Similarly, the authentication may be one-way, with only one device proving its authorization to the other, or two-way, with both devices each proving their authorization to the other. Although power delivery (referred to simply as "charging" herein) is a useful application for anonymous authentication, the techniques discussed herein can be used for any other application where two devices each want to confirm that the other one is a valid device to communicate with, and one or both of the devices want to carry out authentication without providing uniquely identifying information.

When anonymous authentication is used for charging, a charger is not able to uniquely identify a charged device, and a charged device is not able to uniquely identify a charger. Anonymous authentication can be used to maintain user privacy. The threat model may be asymmetric. That is, it may be more important for the charged device to protect itself against an invalid charger than vice versa.

The present disclosure is defined by the claims. In one general aspect of the specification, a method performed by an electronic device includes: accessing, by the electronic device, data stored by the electronic device that identifies authentication keys the electronic device accepts as valid; sending, by the electronic device to a second electronic device, an authentication request that identifies a set of authentication keys including at least some of the authentication keys the electronic device accepts as valid; and receiving, by the electronic device, response data that the second electronic device provides in response to the authentication request. The response data (i) identifies a particular authentication key from the set of authentication keys identified by the authentication request, and (ii) includes a signature generated using the particular authentication key. The method includes authenticating, by the electronic device, the second electronic device by determining that the received signature was generated using the particular authentication key.

In another general aspect of the specification, a method performed by an electronic device includes: receiving, by the electronic device, an authentication request identifying a set of authentication keys; identifying, by the electronic device, an authentication key stored by the electronic device that is in the set identified by the authentication request; using, by the electronic device, the identified authentication key to generate a signature; and providing, by the electronic device, response data in response to receiving the authentication request, the response data including (i) the signature and (ii) an identifier for the authentication key used to generate the signature.

These and other aspects of the specification include corresponding systems, apparatus, and computer programs, configured to perform actions of methods encoded on computer storage devices. A system of one or more computers or other processing devices can be so configured by virtue of software, hardware, or a combination of them installed on the system that in operation cause the system to perform the actions. One or more computer programs can be so configured by virtue having instructions that, when executed by data processing apparatus, cause the apparatus to perform the actions.

These and other aspects of the specification may each optionally include one or more of the following features.

In some implementations, the second electronic device is a wireless charger and the electronic device is a device to be charged by the wireless charger.

In some implementations, the method further includes, in response to authenticating the second electronic device, initiating charging of the electronic device by the second electronic device or increasing power transfer from the second electronic device to the electronic device.

In some implementations, sending the authentication request and receiving the response data are performed using a direct communication link between the electronic device and the second electronic device.

In some implementations, the direct communication link between the electronic device and the second electronic device includes an electromagnetic coupling between a power transmission coil of the second device and a power receiving coil of the electronic device, the electronic device including a battery and circuitry configured to charge the battery based on power received using the power receiving coil.

In some implementations, accessing the data stored by the electronic device that identifies authentication keys the electronic device accepts as valid includes accessing data that identifies a set of key indices corresponding to valid authentication keys. The authentication request specifies the set of key indices; the response data identifies the particular authentication key by indicating a particular key index for the particular authentication key; and authenticating the second electronic device includes determining that the received signature was generated using an authentication key corresponding to the particular key index.

In some implementations, the authentication request includes a nonce. The method further includes, in response to receiving the response data, obtaining, from data storage of the electronic device, a public key that corresponds to the particular authentication key or a hash of the public key. Authenticating the second electronic device includes using the public key or the hash to determine that that the signature was generated as a function of the nonce and a private key that corresponds to the public key.

In some implementations, the method includes storing, before sending the authentication request, public keys corresponding to each of the authentication keys in set of authentication keys.

In some implementations, the method includes storing, before sending the authentication request, hashes of public keys corresponding to each of the authentication keys in set of authentication keys.

The method includes detecting, by the electronic device, the second electronic device. Sending the authentication request is performed in response to detecting the second electronic device.

In some implementations, the second electronic device stores only a proper subset of the indicated set of authentication keys. For example, it may store few than one half of the authentication keys, or even few than <NUM>% or <NUM>% of the indicated set of authentication keys.

In some implementations, the accessing, sending, receiving, and authenticating are performed in an anonymous manner such that neither the electronic device nor the second electronic device provides uniquely identifying information.

In some implementations, the electronic device is a wireless charger, and the authentication request is received from a device to be charged that is in proximity to the wireless charger.

In some implementations, identifying the authentication key includes: determining that a set of stored authentication keys stored by the electronic device includes multiple authentication keys in the set of authentication keys identified by the authentication request; and selecting one of the stored authentication keys determined to be included in the set of authentication keys identified by the authentication request.

In some implementations, the authentication request indicates multiple key indices that identify the set of authentication keys. The identifier in the response data includes a key index from among the multiple key indices.

In some implementations, the authentication request includes a nonce. Using the identified authentication key to generate a signature includes generating the signature using a private key stored by the electronic device and the nonce.

In some implementations, the method includes providing to the electronic device, in the response data, a public key corresponding to the private key.

<FIG> is an illustration of an example environment <NUM> that includes a device <NUM> and a charger <NUM>. In the example, the device <NUM> authenticates the charger before requesting power and initiating charging.

The device <NUM> stores information about an approved set of keys, any one of which the charger <NUM> can use to prove its authenticity. The device <NUM> communicates with the charger <NUM> to begin the process of authenticating the charger <NUM>. For example, the device <NUM> may indicate the set of keys (typically, a plurality of keys) that the device <NUM> considers to be valid. The charger <NUM> cannot determine the identity of the device <NUM> because the message from the device <NUM> to the charger <NUM> does not include any uniquely identifying information about the device <NUM>. The charger <NUM> then generates and provides a response to the device <NUM> using one of the keys from the approved set of keys. Because the response is generated using one of several valid keys, none of which are unique to the particular charger <NUM>, the device <NUM> cannot determine the identity of the charger <NUM>. The device <NUM> examines the response from the charger <NUM> and verifies that it was in fact generated using one of the approved keys, which confirms that the charger <NUM> is authentic. Once the device <NUM> confirms the authenticity of the charger <NUM> is confirmed, the device <NUM> initiates charging.

In general, a device <NUM> may require authentication before requesting or accepting power at certain power levels or operating modes. In some implementations, the device <NUM> may block all power transfer until authentication occurs. In other implementations, the device <NUM> may allow power transfer in one or more modes, such as a default low-power charging mode before authentication, but may require authentication before initiating power transfer in one or more other modes, such as a high-power charging mode. For some wireless chargers, some level of electromagnetic coupling and power transfer occurs as a part of communicating to set the parameters for the charging cycle, and so the device <NUM> naturally may allow this low or default level of power transfer to occur before or during the authentication process, prior to initiating charging in a higher power or fast charging mode.

In the example of <FIG>, the charger <NUM> is a wireless charger configured to deliver power to the device <NUM> wirelessly. Power is transferred through inductive coupling of a power transmission coil in the charger <NUM> with a power receiving coil in the device <NUM>. The data communication that occurs between the device <NUM> and the charger <NUM> to carry out the anonymous authentication can be achieved through the electromagnetic coupling of the coils. For example, the charger <NUM> may modulate the frequency of transmissions from its transmission coil to provide data to the device <NUM>, and the device <NUM> may modulate the effective impedance of its receiving coil to provide data to the charger <NUM>. In some implementations, power delivery and communication may occur according to the Qi wireless charging standard or other wireless charging standards.

Other types of communication between the device <NUM> and the charger <NUM> may additionally or alternatively be used to perform the authentication. For example, the device <NUM> and the charger <NUM> may communicate using a short-range radiofrequency communication link such as Bluetooth or Wi-Fi. Typically, communication takes place over a direct link between the device <NUM> and charger <NUM>, and does not require a connection of either device to a communication network.

Although the example of <FIG> and other examples discussed below involve wireless charging, the same authentication technique can be used for wired charging. For example, the charger <NUM> can be a wired charger that connects to a charging port on the device <NUM> via a charging cable. In this case, the communication between the charger <NUM> and the device <NUM> can occur over the charging cable.

In the example of <FIG>, the device <NUM> initiates the authentication process in which the device <NUM> verifies the authenticity or credentials of the charger <NUM>. Nevertheless, in some implementations, the charger <NUM> can additionally or alternatively initiate a similar authentication process to verify the authenticity of the device <NUM>. For example, the charger <NUM> may require proof of authenticity of the device to be charged before providing power in certain operating modes or power levels, such as high-power or fast charging modes that are only supported for certain device types. In some implementations, both the device <NUM> and the charger <NUM> can initiate the authentication processes to verify the authenticity of the other apparatus.

<FIG> is a block diagram showing a system <NUM> for configuring devices to perform anonymous authentication. For example, <FIG> shows how different devices can be set up by manufacturers with the appropriate authentication keys and other data, so that they are able to later perform anonymous authentication. As discussed further below, this set-up process of providing the needed data to the different devices may additionally or alternatively occur after manufacture in some implementations, through a software update, a firmware update, or another process.

The system <NUM> includes a computer system <NUM> that generates authentication keys and other related data. The system <NUM> also includes chargers 220a-220n and chargeable devices 210a-210z. The computer system <NUM> generates and provides the information that the chargers 220a-220n and chargeable devices 210a-210z will need to effectively perform anonymous authentication.

The computer system <NUM> acts as a central authority that defines the authentication scheme and sets the authentication keys to be used. The actions of the computer system <NUM> may be distributed across multiple computers or may involve the coordination of multiple computers. For example, in some implementations a group of multiple manufacturers may desire to make different chargers 220a-220n and chargeable devices 210a-210z that are interoperable, even though they are manufactured by different companies. The computer system <NUM> may assign the keys and other data to the different manufacturer and to different sets of devices to allow proper authentication.

In general, the computer system <NUM> defines a large set of authentication key pairs, for example, M=<NUM> authentication key pairs. Of course, more or fewer may be used depending on the application (e.g., <NUM>, <NUM>, <NUM>, <NUM>, etc.). Each authentication key pair includes a private key and a public key. In some implementations, the computer system <NUM> uses elliptic curve cryptography to generate the key pairs. As an example, the public and private keys can each be <NUM> bits, though other lengths may be used (e.g., <NUM> bit, <NUM> bit, etc.). Each public-private key pair is assigned to a specific key index value, for example, with <NUM> key pairs being assigned index values <NUM>-<NUM> respectively.

Once the set of key pairs has been determined, the computer system <NUM> selects different subsets of the keys to load onto different charger devices 220a-220n. Each subset typically includes keys from only a small portion of the total set of authentication key pairs, for example, keys for only <NUM>%, <NUM>%, <NUM>%, or <NUM>% of the key indices. For example, if <NUM> key pairs are defined, each charger 220a-220n may receive and store keys for only <NUM> of the key indices. Even within the same model of charger, different instances of the charger will receive different subsets of keys.

Many different techniques may be used to select the subsets of keys loaded to different chargers 220a-220n. In some implementations, the subset for each charger 220a-220n is separately selected randomly or pseudo-randomly. In other implementations, a portion of the subset is selected randomly or pseudo-randomly for each individual charger 220a-220n, but another portion of the subset is shared by multiple chargers 220a-220n in the same manufacturing batch. For example, of <NUM> keys, <NUM> keys may be selected for every charger randomly or pseudo-randomly and another <NUM> keys may be shared by all chargers manufactured that day. In some implementations, some keys are selected randomly or pseudo-randomly, while certain keys are shared by all chargers of the same model type. This can enhance compatibility of the model with other devices, but with the tradeoff of increase risk of needing to later revoke those shared keys if the device is compromised. For inexpensive devices or for small batches, all chargers 220a-220n in the batch may share the entire subset of keys, e.g., with chargers in a first batch all receiving a first subset of keys, and the next batch of chargers all receiving a second subset of keys, and so on.

Accordingly, the different subsets of keys for the chargers 220a-220n can be overlapping and can be selected, in whole or in part, randomly or pseudo-randomly. In this way, for a given model of charger, all instances of the charger will have some number (typically the same number) of the valid authentication keys. However, each charger instance will have only a small number of the total valid authentication keys. This helps to maintain security, so that if one charger is compromised and the authentication keys taken, only a small percentage of the total number of authentication keys are compromised. In addition, the set of authentication keys held by a charger instance is not unique and so does not uniquely identify a specific charger instance.

To prevent counterfeiting, instead of each charger 220a-220n having a random subset of keys, the subset of keys for some chargers 220a-220n may be selected from only a part of the overall set of keys. For example, a factory may choose each day a group of <NUM> keys from the full list of <NUM>,<NUM> keys. All chargers 220a built on that day can load <NUM> random keys selected from that group of <NUM> keys. If a potential attacker obtains several chargers 220a manufactured on the same day, which is likely if the attacker purchased a large box or shipment of chargers to attack, the potential attacker is likely to only extract the keys in the group of <NUM> keys. A potential attacker would need to obtain chargers from multiple locations over a longer period of time in order to obtain more of the total <NUM>,<NUM> keys.

In some implementations, each charger's subset of keys is sufficiently large and the keys are sufficiently distributed among different chargers so that identifying one or two keys held by a charger does not uniquely identify that charger. For example, if there are <NUM>,<NUM> keys and each charger loads <NUM> keys, with the keys being well distributed among the different key subsets, <NUM>,<NUM> devices could be built in which <NUM>,<NUM> devices have any given key.

In the example of <FIG>, the computer system <NUM> generates a total of nine public-private key pairs. Table <NUM> shows key index values <NUM>, private keys <NUM>, and public keys <NUM>. The private keys <NUM> are designated p1 through p9, and the corresponding public keys <NUM> are designated P1 through P9. The key index values <NUM> are <NUM> through <NUM>. Each row represents a different public-private key pair <NUM>, e.g., in which key index <NUM> corresponds to private key p1 and public key P1; key index <NUM> corresponds to private key p2 and public key P2; and so on. Each private key <NUM> and public key <NUM> can be identified by its key index <NUM>.

The computing system <NUM> selects different subsets of the private keys <NUM> to be loaded onto different chargers 220a-220n. Each charger 220a-240n receives three private keys <NUM>, respectively shown as key data 221a-221n. The contents of each subset may be randomly or pseudo-randomly selected from the overall set of private keys <NUM>, e.g., keys p1 through p9. In some implementations, the contents of each subset may be set in a programmatic or deterministic way to provide a desired level of diversity and/or overlap among the subsets. As noted above, at least a portion of each key subset may be set based on other factors, such as a set of keys corresponding to the charger model or to the current production batch. As shown in the key data 221a-221n, some of the different subsets can include overlapping keys. In some implementations, some of the chargers 220a-220n may receive the same key subset, although the computer system <NUM> can define a sufficiently large number of keys and subsets so that only small groups of chargers share exactly the same subset.

In the example of <FIG>, the key data 221a-221n for each charger 220a-220n includes private keys <NUM> for three key indices <NUM>. However, the three key indices are different for different instances of the charger. Chargers 220a-220n may store only the private keys <NUM> for the applicable key indices, and exclude the public keys <NUM>. Nevertheless, in other implementations, as discussed in <FIG>, the corresponding public keys <NUM> may also be stored. The key data 221a-221n also maps the respective private keys <NUM> to their corresponding key indices <NUM>, and those relationships are later used in the authentication process.

In some implementations, the private keys <NUM> in the key data 221a-221n are stored in protected storage of the chargers 220a-220n so it is difficult to obtain the private keys <NUM> even with a hardware debugger.

In addition to providing the private key subsets to configure the chargers 220a-220n, the computing system <NUM> can provide data to configure a set of devices 210a-210z to authenticate the chargers 220a-220n. The computing system <NUM> provides key data to the devices <NUM>0a-<NUM>0z, so that the devices 210a-210z can each verify the authenticity of the chargers 220a-220n. To maximize compatibility, it is generally desirable for each of the devices 210a-210z to have sufficient information to be capable of authenticating each of the chargers 220a-220n. Thus, each of the devices 210a-210z may receive and store key data, e.g., the public keys <NUM>, for each of the key indices <NUM>. This is illustrated in <FIG>, with each set of key data 211a-211z including each of the public keys <NUM>, e.g., P1-P9, for all key indices <NUM>, e.g., <NUM>-<NUM>. The key data 211a-211z associates the public keys <NUM> with their corresponding key indices. This can be significant for later use in authentication as well as to allow effective revocation, as these processes typically operate for specific key indexes not the set of keys as a whole. The devices 210a-210z may store the key data 211a-211z in a protected manner, such as protected or signed, to prevent tampering.

The example of <FIG> shows an initial set of keys provided to the chargers 220a-220n and devices 210a-210z by the manufacturer. Nevertheless, this type of data can additionally or alternatively be provided after the devices are sold and in use by users. For example, one or more server systems can provide data over a network to update the authentication key sets and corresponding key data from time to time. Similarly, server systems may provide data to effect revocation of individual keys or groups of keys if those keys are compromised. For example, devices 210a-210z can be informed about specific keys which have been revoked. Other communications can be performed. For example, a device 210a-210z can periodically download updates that provide key data that includes public keys and corresponding key indices to be able to operate with chargers from one or more manufacturers. The computing system <NUM> may provide additional keys beyond the original set of keys that were available at the time of manufacturing. For example, if <NUM>% of the keys in an original set of <NUM>,<NUM> authentication keys have been compromised, <NUM>,<NUM> new authentication of keys may be made available, to double the total set to <NUM>,<NUM> authentication keys.

The example of <FIG> shows the arrangement for a device 210a-210z to be able to authenticate the chargers 220a-220n. In addition, or as an alternative, a complementary process can be performed so that the chargers 220a-220n can authenticate the devices 210a-210z. For example, additional key data can be provided to and stored by the devices 210a-210z, where the additional key data for the devices 210a-210z includes different proper subsets of the private keys <NUM>. Similarly, the chargers 220a-220n can receive and store public keys <NUM> which can be used to verify use of valid private keys. In this manner, the chargers 220a-220n and the devices 210a-210z can each authenticate each other. In some implementations, a different set of authentication public-private key pairs may be used for each type of authentication, e.g., with one set of key pairs used for authentication of chargers and another set of key pairs used for authentication of devices to be charged.

<FIG> is a block diagram showing another system <NUM> for configuring devices to perform anonymous authentication. <FIG> shows an alternative manner of configuring the chargers 220a-220n and 210a-210z to support anonymous authentication, with somewhat different sets of key data being provided. Rather than each device 210a-210z storing all of the public keys <NUM>, each device 210a-210z receives and stores hashes <NUM> of the public keys <NUM>. The hashes are shorter than the corresponding public keys <NUM>, and thus require less storage on each device 210a-210z. When the system uses large numbers of authentication public-private key pairs, e.g., hundreds or thousands, the space savings can be significant.

In addition, the chargers 220a-220n receive and store the public keys <NUM> corresponding to their respective subsets of the private keys <NUM>. As a result, whenever a charger 220a-220n uses a private key <NUM> from its locally-stored subset, the charger 220a-220n can also provide the corresponding public key <NUM> to one of the devices 210a-210z. The device 210a-210z that receives the public key <NUM> can use the hashes <NUM> to verify the authenticity of the public key <NUM> the charger provides, and then use the verified public key <NUM> to authenticate the charger. Having each charger 220a-220n store public keys <NUM> in addition to private keys <NUM> increases the storage requirements for the chargers 220a-220n, but because the chargers 220a-220n each store only a small subset of the total number of authentication keys, the increase is quite small and is acceptable to achieve a much greater reduction in storage requirements by the devices 210a-210z.

In the example, the computer system <NUM> computes a hash <NUM> of each public key <NUM>. The server 205b can compute the hashes <NUM> using a hash function such as SHA256. The addition of these hashes <NUM> is shown in the table <NUM>. In the example in <FIG>, the computer system <NUM> has nine public-private key pairs with their corresponding public key hashes <NUM>. To configure the chargers 220a-220n, the computer system <NUM> selects different subsets of the private keys <NUM> for different chargers 220a-220n as discussed for <FIG>, then provides both the private key <NUM> and public key <NUM> for the selected subset. To configure the devices 210a-210z to authenticate the chargers 220a-220n, the computer system <NUM> provides each device 210a-210z with each of the hashes <NUM> for valid key indices <NUM>. Loading hashes 215b instead of public keys 220b can reduce the amount of storage required on the devices 230b.

For very large sets of authentication keys, storage requirements may still become prohibitive for some types of devices. One way to address this issue is for devices 210a-210z to store only a subset of the public key hashes <NUM>. For example, only the first half of the list (e.g., hashes <NUM> for key indexes <NUM>-<NUM>) may be stored. Nevertheless, this increases the risk that a charger and device authentication may fail due to not having key data for any key index in common. Another option is to truncate the hash values so that each hash uses less space. For example, only the first <NUM> bits of each hash <NUM> may be stored. This, however, increases the risk that an attacker may find a hash collision and more easily compromise authentication keys.

In a similar manner as discussed for <FIG>, the system <NUM> provides additional data so that chargers 220a-220n can authenticate the devices 210a-210z. For example, in addition to what is illustrated in <FIG>, each device 210a-210z stores a proper subset of the private keys <NUM> and public keys <NUM>, and the chargers 220a-220n each store all of the public key hashes <NUM>. Note that the number of keys in the list and the number of keys on each device may be different for charger <NUM> and device <NUM>. The devices 210a-210z will usually have much more storage available, and may store larger subsets of private keys <NUM> than the chargers 220a-220n.

The techniques discussed for both <FIG> and <FIG> support revocation of keys for devices that have been compromised. If a charger 220a-220n is compromised, all of its keys are removed from the list of valid charger public keys. This will render the compromised device unable to pass authentication, and potentially thus unusable in some implementations. Nevertheless, all or nearly all of the other chargers 220a-220n will be able to continue operating normally because most if not all of the other chargers 220a-220n will not share the identical subset of keys as the compromised charger. Thus, even though some of the keys in their respective subsets may become invalidated, other keys will generally remain valid and usable for authentication. In other words, each charger 220a-220n has a different subset of N keys, so revoking all of the keys from one charger 220a-220n is unlikely to invalidate more than N/M of the keys from a second charger <NUM>. For sample values of N = <NUM> and M = <NUM>, this represents a small effect on other chargers. An attacker would need to compromise a large number of devices before any given charger <NUM> would not have any valid keys left.

To obtain information about revocations, the devices 210a-210z can periodically download an updated list of which keys are valid or revoked from a secure server when Internet access is available.

<FIG> is a diagram illustrating an example of a process 300a of performing anonymous authentication. In the example, the device 210a authenticates the charger 220b, while preserving the anonymity of both devices. <FIG> uses the data storage scheme discussed with respect to <FIG>, in which the charger 220b stores key data 221b that includes only a proper subset of the various private keys <NUM>, and the charger 220b does not store the corresponding public keys <NUM>.

The device 210a stores key data 211a that includes the public keys <NUM> for all of the valid authentication key pairs. The device 210a also stores information that indicates whether the various public keys <NUM> are still valid, so that if the authorization for a key pair is revoked, the device 210a no longer accepts it as valid. Storage of the data indicating that keys are valid or invalid can be done in various ways, such as with a flag for each key index that indicates whether a key has been revoked, by deleting public keys once the revoked, or through other data.

In step <NUM>, the device 210a sends an authentication request <NUM> to the charger 220b. The authentication request includes a nonce <NUM> and an indication <NUM> of key indices that the device 210a will accept for authentication. The nonce <NUM> can be a random or pseudo-randomly generated value. The indication <NUM> of acceptable key indices can indicate the set of keys for which the device 210a stores the corresponding public keys and which have not yet been revoked.

In step <NUM>, after the charger 220b receives the authentication request <NUM>, the charger <NUM> compares the set of key indices <NUM> indicated by the authentication request <NUM> with the set of key indices for which the charger 220b stores private keys <NUM>. This results in a set <NUM> of key indices with corresponding authentication private keys <NUM> that the charger 220b can use to perform the authentication. Only one matching key index is needed to carry out the authentication. In most cases, however, there will multiple key indices indicated by the authentication request <NUM> that the charger 220b stores keys <NUM> for and thus can use.

If no key indices overlap between those indicated in the authentication request <NUM> and the set of key indices for which the charger 220b stores private keys, then the charger 220b will not be able to authenticate. In this case, the charger 220b and/or the device 210a would need to be updated, for example, with new key data for additional key indices so that both have key data for a shared key index, in order for the charger 220b and the device 210a to be able to perform authentication successfully.

In step <NUM>, the charger 220b selects a key index from the set <NUM> identified in step <NUM>. The key <NUM> corresponding to any of the key indices in the set <NUM> can be used. Nevertheless, the selection process may be used to further obscure the identity of the charger 220b. The charger 220b may select the first matching key index in the set <NUM>, the last matching key index in the set <NUM>, a randomly or pseudo-randomly selected key index in the set, etc. In some implementations, the charger 220b varies which key is used from time to time, or at each charging session. Because different chargers 220a-220n store private keys <NUM> for different subsets of the key indices <NUM>, and the chargers 220a-220n may vary which private key <NUM> they use from one authentication to the next, the use of a particular authentication key <NUM> or key index <NUM> does not signal the identity of a specific charger 220a-220n.

The charger 220b uses the selected key to generate a signature <NUM>, using a predetermined function of the selected private key and the nonce <NUM>. For example, the charger 220b may encrypt the nonce <NUM> using the selected private key, with the encrypted nonce serving as the signature <NUM>.

In step <NUM>, the charger 220b generates and sends an authentication response <NUM> to the device 210a. The authentication response <NUM> includes the signature <NUM> and an indication <NUM> of which key index <NUM> corresponds to the private key <NUM> used to generate the signature <NUM>.

In step <NUM>, in response to receiving the authentication response <NUM>, the device 210a retrieves the public key <NUM> corresponding to the key index <NUM> indicated by the authentication response <NUM>. Although the device 210a indicated that any of various key indices <NUM> would be acceptable for authentication, once the charger 220b has selected a key index to use, the authentication response <NUM> will be evaluated with using the single public key for the specific key index <NUM> the charger 220b selected.

In step <NUM>, the device 210a uses the public key to verify whether the signature <NUM> was generated using the correct private key that corresponds to the key index <NUM> indicated in the authentication response. For example, given the key index of "<NUM>," the device retrieves the corresponding public key, P1, which corresponds to that key index. The device 210a then uses that public key, P1, to determine whether the signature <NUM> was generated using the correct private key, p1, corresponding to the same index "<NUM>" and public key, P1. For example, the device 210a can attempt to decrypt the signature <NUM> using the public key, P1, and then compare the decryption result with the nonce <NUM> the device 210a provided in the authentication request <NUM>. If the decryption result matches the nonce <NUM>, then the device 210a determines that authentication is successful and that the charger 220b is authorized. If the decryption result does not match the nonce <NUM>, the authentication fails.

In step <NUM>, after a successful authentication, the device <NUM> communicates further with the charger 220b and performs one or more functions that are not allowed prior to successful authentication (e.g., initiating charging, increasing the power level for charging from a default level to a higher level, etc.). In some implementations, the process also is performed with the roles reversed, e.g., with the charger 220b sending an authentication request to the device 210a, and the charger 220b may require authentication from the device 210a before certain actions or modes of charging are permitted.

<FIG> is a diagram illustrating another example of a process 300b of performing anonymous authentication. The process 300b of <FIG> is similar to the process 300a of <FIG>, except the key data used is different. <FIG> uses the data storage scheme discussed with respect to <FIG>, in which the charger 220b stores key data 225b which includes private keys <NUM> and public keys <NUM>, while the device 210a stores key data 215a which includes hashes <NUM> of public keys instead of including the public keys themselves. In the example, the device 210a authenticates the charger 220b, while preserving the anonymity of both devices.

The process 300b in <FIG> initially follows the same steps as described for <FIG>, in that the device 210a sends the authentication request <NUM> (step <NUM>), the charger 220b identifies the set <NUM> of key indices in common, and the charger selects a key corresponding to one of the key indices in the set <NUM> and uses it to generate a signature <NUM> (<NUM>). The process 300b then differs somewhat as discussed for steps <NUM> to <NUM> below
In step <NUM>, the charger 220b generates and sends an authentication response <NUM> to the device 210a. The authentication response <NUM> includes the signature <NUM> and an indication <NUM> of which key index <NUM> corresponds to the private key <NUM> used to generate the signature <NUM>. In addition, the authentication response <NUM> includes the public key for the key index specified by the indication <NUM>. Because the device 210a does not store the public key, the charger 220b will provide the public key for later use by the device 210a.

In step <NUM>, in response to receiving the authentication response <NUM>, the device 210a retrieves the hash <NUM> corresponding to the key index indicated by the authentication response <NUM>. Although the device 210a indicated that any of various key indices <NUM> would be acceptable for authentication, once the charger 220b has selected a key index to use, the authentication response <NUM> will be evaluated based on the hash and authentication key pair for the specific key index the charger 220b selected.

In step <NUM>, the device 210a verifies the authenticity of the public key received in the authentication response <NUM>. For example, the device 210a generates a hash of the received public key using a predetermined hash function, and then compares the generated hash with the hash <NUM> retrieved from storage of the device 210a. If the two hashes match, the device 210a determines that the received public key is genuine and can be trusted in the authentication process. If the hashes do not match, however, the authentication is considered unsuccessful.

In step <NUM>, the device 210a uses the received public key to verify whether the signature <NUM> was generated using the correct private key that corresponds to the key index indicated in the authentication response <NUM>. For example, given the key index of "<NUM>," the device 210a uses that received public key, P1, to determine whether the signature <NUM> was generated using the correct private key, p1, corresponding to the same index "<NUM>" and public key, P1. For example, the device 210a can attempt to decrypt the signature <NUM> using the public key, P1, and then compare the decryption result with the nonce <NUM> the device 210a provided in the authentication request <NUM>. If the decryption result matches the nonce <NUM>, then the device 210a determines that authentication is successful and that the charger 220b is authorized. If the decryption result does not match the nonce <NUM>, the authentication fails.

In step <NUM>, after a successful authentication, the device 210a communicates further with the charger 220b and perform one or more functions that are not allowed prior to successful authentication (e.g., initiating charging, increasing the power level for charging from a default level to a higher level, etc.). In some implementations, the process also is performed with the roles reversed, e.g., with the charger 220b sending an authentication request to the device 210a, and the charger 220b may require authentication from the device 210a before certain actions or modes of charging are permitted.

<FIG> is a block diagram showing an example of revocation of keys in an anonymous authentication framework. The key data shown corresponds to that of <FIG> but the technique can be used in the same manner for the arrangement of <FIG>.

The computer system <NUM> can store data <NUM> indicating the status of various authentication public/private key pairs. An operator of the computer system may become aware that certain keys are compromised, e.g. because the operator discovers a counterfeit charger using those keys. As keys are compromised or otherwise no longer permitted for use, the computer system <NUM> stores data indicating that those keys have been revoked. The computer system <NUM> then sends revocation data <NUM> to the devices 210a-210z over a communication network <NUM>. The revocation data <NUM> specifies key indices <NUM> that are no longer valid, and thus authentication using the corresponding private keys <NUM> should no longer be accepted. The devices 210a-210z each respond by designating the revoked key indexes as invalid, for example, by setting a flag or other value indicating the status as being revoked, by deleting the public keys corresponding to the revoked key indices, and so on.

In the example, the computer system revokes keys numbered <NUM>-<NUM>. Each of the devices 210a-210z marks those key indexes as unusable. Later, when the devices 210a-210z send authentication requests, those requests will exclude key indices <NUM>-<NUM> as usable key indices. Updating the devices 210a-210z to no longer willing to accept authentication using the revoked keys in this manner removes the risk of harm from the inappropriate use of a revoked key. The chargers 220a-220n which may not be connected to a network, do not need to be updated and will continue to authenticate appropriately with any of the devices 210a-210z, as long as there is still at least one valid, non-revoked key index shared between the key data 211a-211z of the particular device 210a-210z and the key data 211a-211n of the particular charger 210a-210n.

<FIG> is a block diagram showing an example of a process of updating authentication information in an anonymous authentication framework.

In general, a device 210a-210z can periodically download the valid key lists for all charger manufacturers from a server <NUM>, such as the computer system <NUM> or another computer system. If a key list has <NUM><NUM>-byte key hashes <NUM>, then the lists for <NUM> manufacturers combined would still be under 1MB, which is a very small compared to the storage capacity of many devices.

A device 210a-210z may also learn from the server <NUM> which keys have been revoked. If the device 210a-210z decides that it does not have enough valid private keys (in order to prove its authenticity to chargers 220a-220n), by determining that a sufficiency criterion is not met, the device 210a-210z can request for the server <NUM> to provide it additional keys. The device 210a-210z can authenticate itself to the server using a device-specific certificate. Although the server <NUM> knows at that time which device 210a-210z is requesting new keys, it will be difficult to correlate that request to the specific key used during authentication to any given charger 220a-220n.

The server <NUM> may provide the device 210a-210z with keys from a different list, the server <NUM> is not limited to the original list of keys. For example, if the original list of <NUM> device keys has been <NUM>% compromised, the device <NUM> list of keys could be doubled to <NUM> possible keys. Nevertheless, chargers 220a-220n would not know about the new keys and would not be able to use those keys and key indices unless they also receive updates.

Several techniques can be used to updating key lists on a charger 220a-220n. Typically, a charger 220a-220n is unlikely to have Internet access or other network access, but a charger 220a-220n can make use of the network connection of a device 210a-210z to obtain its updates. This process is illustrated in <FIG>.

When a device 210a-210z downloads the updated list of keys that can be used to authenticate chargers 220a-220n, the device 210a-210z can also download the list of valid keys that chargers 220a-220n can use to authenticated devices 210a-210z. The list will have a version number, which increases with each update. This list and the version number and any additional data, such as a new server public key, would be signed by the server's private key, and the charger 220a-220n would be able to validate it using the server's public key which the charger 220a-220n would also store in advance. For example, the server's public key may be installed on the charger 220a-220n at the time the charger 220a-220n is manufactured. An updated key list could also contain a new server public key, in the event it is desirable to rotate the server's public key.

After a charger 220a-220n authenticates a device 210a-210z, the charger 220a-220n can ask if the device 210a-210z has an updated list from the server <NUM>. If the device 210a-210z does, the charger <NUM> asks the device 210a-210z to send the new list. The charger 220a-220n then verifies the new list's signature using the server's public key. If the signature is valid, and the new list is newer than the charger's stored list, the charger 220a-220n updates its stored list. Note that this does not require the device 210a-210z to have Internet access at the time the charger 220a-220n asks for the update. But it is very likely that a charger 220a-220n will talk to enough devices that if an updated device key list is on the server, the charger 220a-220n will obtain it relatively soon.

The system can update a charger's private key set also. It is somewhat more challenging if a charger 220a-220n wants to update its own subset of charger private keys, because each charger <NUM>-220n should have its own unique subset, and the process of updating should not reveal those keys to the device 210a-210z.

As an example of an update process, a charger 220a generates an update request <NUM> by using the server's public key to encrypt a nonce and its public device certificate. The charger 220a asks the current device 210a to send the request <NUM> to the server <NUM>. Because the data is encrypted, the device 210a does not know what is being sent. The device 210a may refuse to pass on the data for any of multiple reasons, e.g., it has no Internet access at the current time, or it does not want to risk exposing its location by talking to the server <NUM> and telling it which charger it is currently using. If the device 210a is willing to communicate to the server <NUM>, it passes on the request <NUM>.

The server <NUM> authenticates that the certificate belongs to a valid (e.g., non-compromised or non-counterfeited) charger 220a-220n. The server <NUM> generates an update <NUM> for the charger 220a by encrypting some replacement private keys (potentially with corresponding public keys) using the nonce passed by the device and the public key contained in the charger's certificate. The server <NUM> provides the update <NUM> to the device 210a. The device 210a cannot determine what the update <NUM> contains because of the encryption. The device 210a passes the update <NUM> to the charger 220a.

The charger 220a decrypts the data using its private key. If the charger 220a decrypts properly, and the nonce matches, the charger 220a knows the response comes from the server <NUM>. In this case, the charger 220a stores the new private keys for authentication by devices 210a-210n, preferentially replacing keys which are no longer valid.

The owner of a charging station may wish to do these updates with their own devices, to ensure that their chargers are updated periodically even if all customers have their devices set to refuse passing charger updates.

In some implementations, the data between charger and device can be transferred over an encrypted channel, so as not to leak information to anyone snooping wirelessly. The devices may establish that channel using any typical method (e.g. Diffie-Hellman key exchange).

<FIG> is a diagram illustrating examples of various device-to-device interactions that can be authenticated using anonymous authentication. The authentication technique discussed herein is not limited to interactions between charger <NUM> and a device <NUM> to be charged. The technique can be used for authenticating any pair of devices which may connect to or otherwise communicate with each other. For example, the authentication technique can be used for any computing device to communicate with another computing device, a peripheral device, or another hardware resource. As a few examples, a computing device may be a phone, laptop computer, desktop computer, tablet computer, a wearable device, and so on. As a few examples, a peripheral device may be a printer, a display device, headphones, a docking station, a keyboard, a mouse, and so on. Other hardware resources include appliances, home automation systems, vehicles such as automobiles, and so on.

As an example, one mobile device may communicate with another mobile device and confirm authenticity or authorization anonymously. For example, an application running on one phone may want to confirm that it is communicating wirelessly to the same application on a nearby phone, but without either phone or application providing its exact identity. In this situation, the application on the first phone may use the anonymous authentication technique to verify that the application on the second phone is genuine.

A number of implementations have been described. Nevertheless, it will be understood that various modifications may be made without departing from the scope of the disclosure. For example, various forms of the flows shown above may be used, with steps re-ordered, added, or removed.

Embodiments of the invention and all of the functional operations described in this specification can be implemented in digital electronic circuitry, or in computer software, firmware, or hardware, including the structures disclosed in this specification and their structural equivalents, or in combinations of one or more of them. Embodiments of the invention can be implemented as one or more computer program products, e.g., one or more modules of computer program instructions encoded on a computer readable medium for execution by, or to control the operation of, data processing apparatus. The computer readable medium can be a machine-readable storage device, a machine-readable storage substrate, a memory device, a composition of matter effecting a machine-readable propagated signal, or a combination of one or more of them. A propagated signal is an artificially generated signal, e.g., a machine-generated electrical, optical, or electromagnetic signal that is generated to encode information for transmission to suitable receiver apparatus.

Moreover, a computer can be embedded in another device, e.g., a tablet computer, a mobile telephone, a personal digital assistant (PDA), a mobile audio player, a Global Positioning System (GPS) receiver, to name just a few.

To provide for interaction with a user, embodiments of the invention can be implemented on a computer having a display device, e.g., a CRT (cathode ray tube) or LCD (liquid crystal display) monitor, for displaying information to the user and a keyboard and a pointing device, e.g., a mouse or a trackball, by which the user can provide input to the computer.

Embodiments of the invention can be implemented in a computing system that includes a back end component, e.g., as a data server, or that includes a middleware component, e.g., an application server, or that includes a front end component, e.g., a client computer having a graphical user interface or a Web browser through which a user can interact with an implementation of the invention, or any combination of one or more such back end, middleware, or front end components.

While this specification contains many specifics, these should not be construed as limitations on the scope of the invention or of what may be claimed, but rather as descriptions of features specific to particular embodiments of the invention.

In each instance where an HTML file is mentioned, other file types or formats may be substituted. For instance, an HTML file may be replaced by an XML, JSON, plain text, or other types of files. Moreover, where a table or hash table is mentioned, other data structures (such as spreadsheets, relational databases, or structured files) may be used.

Claim 1:
A method performed by a first electronic device (<NUM>; 210a-210z), the method comprising:
detecting, by the first electronic device (<NUM>; 210a-210z), a second electronic device (<NUM>; 220a-220n);
sending (<NUM>), by the first electronic device (<NUM>; 210a-210z) to the second electronic device in response to the first electronic device (<NUM>; 210a-210z) detecting the second electronic device, an authentication request (<NUM>) that identifies, from among a larger set of authentication key pairs (<NUM>; <NUM>), a subset (<NUM>) of authentication keypairs that are usable to authenticate electronic devices;
receiving, by the first electronic device (<NUM>; 210a-210z) from the second electronic device (<NUM>; 220a-220n), response data that the second electronic device provides in response to the authentication request (<NUM>), wherein the response data:
i) identifies a selected authentication key pair from the subset of authentication key pairs identified by the authentication request as being valid for authenticating the second electronic device, and
ii) includes a signature (<NUM>) generated using a private key of the selected authentication key pair; and
authenticating, by the first electronic device (<NUM>; 210a-210z), the second electronic device (<NUM>; 220a-220n) by determining that the received signature (<NUM>) was generated using the private key from the selected authentication key pair.