WO2017167771A1

WO2017167771A1 - Handshake protocols for identity-based key material and certificates

Info

Publication number: WO2017167771A1
Application number: PCT/EP2017/057349
Authority: WO
Inventors: Oscar Garcia Morchon; Ronald Rietman; Ludovicus Marinus Gerardus Maria Tolhuizen; Maarten Peter Bodlaender
Original assignee: Koninklijke Philips NV
Current assignee: Koninklijke Philips NV
Priority date: 2016-03-29
Filing date: 2017-03-29
Publication date: 2017-10-05
Anticipated expiration: 2018-09-29

Abstract

A first network node is provided arranged to obtain a second certificate and a second authentication token from a second network node. An identity unit is arranged to obtain a second identifier from the second certificate. An identity-based shared key unit (147) arranged to generate an identity-based shared key by applying a key establishment algorithm of the identity-based key pre-distribution scheme on the second identifier and the first local 5 key material. An authentication unit (148) is arranged to authenticate the second network node by cryptographically verifying that the second authentication token has been computed from at least the identity-based shared key.

Description

Handshake protocols for identity-based key material and certificates

FIELD OF THE INVENTION

The invention relates to a first network node, a first network node method, a computer program, a computer readable medium.

BACKGROUND

A current approach in cryptography is the use of so-called identity-based key pre-distribution scheme. Using such schemes, two network nodes can agree on a shared key which is based on their identities. A traditional approach in which a key is determined for each pair network nodes would grow quadratically. However, identity -based key pre- distribution scheme need only distribute one set of local key material for each node, and thus grow linearly.

There has been a problem integrating the identity-based key pre-distribution schemes in larger cryptographic systems. In particular, there is a desire authenticate network nodes in addition to agree on a key.

In many current cryptographic infrastructures that do not use identity -based key pre-distribution scheme use is made of so-called certificates. One popular certificate system employs X.509 certificates as described in RFC 5280. In the X.509 system, a certificate contains a public key and information on the owner of the public key. The owner of the public also has the corresponding private key. The public and private key together form a key-pair for use in an asymmetric cryptographic scheme, e.g., encryption or signing, etc.

In X.509 a certificate authority signs the certificate. When later the certificate is used, the signature can be verified. A verification of the signature proves that the certificate authority certified the combination of public key and the other information.

Certificates have become ubiquitous in some types of secure communications. For example, X.509 certificate are used in the https protocol against hijacking of a website. Unfortunately, certificates also have a number of drawbacks that make them less suitable for some applications. For example, signed certificate can be quite large. For example, a typical X.509 certificate using 1024 bit RSA keys may be about 1 kilobyte. The size of a certificate for 2048 bit keys would be considerably larger still. This makes certificates less suitable for networks in which communication overhead must be small. For example, in internet-of- things, sensor networks, etc, communication overhead is preferably minimized. Furthermore, using certificates requires quite substantial computation capabilities, not only during set-up of the certificate but during regular use, as the signature on received certificates must be verified. Asymmetric cryptography, such as RSA and the like, typically require large-number computations which may take too long for regular communication on low-resource devices.

There is thus a desire to address these problems, and other problems as set out herein.

SUMMARY OF THE INVENTION

Handshake protocols are provided which use an identity -based key pre- distribution scheme and also authenticate a network node. The protocols allow the use of certificates that are not signed, yet may still be authenticated.

A first network node is provided as defined in the claims that comprises a key storage arranged to store at least first local key material of an identity-based key pre- distribution scheme, and a certificate storage arranged to store a first certificate. The first network node can communicate with a second network node, and authenticate its certificate using its local key material. In an embodiment, the communication only involves an exchange of certificates, nonces, and authentication tokens, but no signatures. Also the certificates need not be signed. Accordingly, long signatures are avoided. Furthermore, a man in the middle would try to intercept a certificate and replace the public key with his own; this will not work as the identity based share key would be different. Furthermore, the system can easily support multiple certificate authorities without little additional overhead.

In an embodiment, the authentication unit is arranged to generate a further shared key with at least the first private key, the further shared key being a shared-key, shared with the second network node. Because the further shared key depends on secret information to which the trusted third party has no access, this improves security against an attack on trusted third parties that generated the local key material. Even if all local key material is comprised, secure communication remains possible.

In an embodiment, the first network node comprises a key pair generation unit arranged to generate a first ephemeral public key and a corresponding first ephemeral private key, according to an asymmetric-key cryptographic scheme, the communication device being arranged to send the first ephemeral public key to the second network node, and optionally receive a second ephemeral public key from the second network node. An advantage of including ephemeral keys in the protocol is to obtain forward security.

Even if the trusted third party and the network nodes are all completely broken then past communication may still be secure.

In an embodiment, the authentication unit is arranged to generate a combined key from the identity -based shared key and the further shared key, said combined key being used to verify the second authentication token and/or to compute the first authentication token. This has the advantage that authentication may be identity based as well as private key based, without having to increase the number or size of the messages.

In an embodiment, an authentication token is computed over the public key of the other party and/or over a value encrypted with said public key. This binds the

authentication token to the public key, and protects the authentication token from being replayed with other network nodes.

The certificate and local key material may be provided in the first and/or second network node in a variety of ways. In an embodiment, the first network node is arranged to receive the first certificate and the local key material from a certificate authority device using a protocol executed over a digital computer network.

The first and second network device and the certificate authority device are electronic devices. For example, a network node may be a mobile electronic device. A network node may be a mobile phone, set-top box, smart-card, computer, etc. The certificate authority device may be a computer, a server, etc. In an embodiment, the first network device is a client and the second network device is a server, e.g., web server arranged to provide web pages to the client on request of said client.

A method according to the invention may be implemented on a computer as a computer implemented method, or in dedicated hardware, or in a combination of both.

Executable code for a method according to the invention may be stored on a computer program product. Examples of computer program products include memory devices, optical storage devices, integrated circuits, servers, online software, etc. Preferably, the computer program product comprises non-transitory program code stored on a computer readable medium for performing a method according to the invention when said program product is executed on a computer. In a preferred embodiment, the computer program comprises computer program code adapted to perform all the steps of a method according to the invention when the computer program is run on a computer. Preferably, the computer program is embodied on a computer readable medium.

Another aspect of the invention provides a method of making the computer program available for downloading. This aspect is used when the computer program is uploaded into, e.g., Apple's App Store, Google's Play Store, or Microsoft's Windows Store, and when the computer program is available for downloading from such a store. BRIEF DESCRIPTION OF THE DRAWINGS

Further details, aspects, and embodiments of the invention will be described, by way of example only, with reference to the drawings. Elements in the figures are illustrated for simplicity and clarity and have not necessarily been drawn to scale. In the Figures, elements which correspond to elements already described may have the same reference numerals. In the drawings,

Figure 1 schematically shows an example of an embodiment of a cryptographic system,

Figure 2a schematically shows a sequence diagram of an embodiment of an authentication protocol,

Figure 2b schematically shows a sequence diagram of an embodiment of an authentication protocol,

Figure 3 schematically shows a sequence diagram of an embodiment of an authentication protocol,

Figure 4 schematically shows of an embodiment a cryptographic system, Figure 5 schematically shows a sequence diagram of an embodiment of a protocol for distributing certificates,

Figure 6a schematically shows a computer readable medium having a writable part comprising a computer program according to an embodiment,

Figure 6b schematically shows a representation of a processor system according to an embodiment.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

While this invention is susceptible of embodiment in many different forms, there are shown in the drawings and will herein be described in detail one or more specific embodiments, with the understanding that the present disclosure is to be considered as exemplary of the principles of the invention and not intended to limit the invention to the specific embodiments shown and described.

The current public key infrastructure relies on a certification authority that issues certificates. When two network nodes wish to communicate, e.g., a client and a server, e.g., two sensor nodes, etc, they exchange their certificates containing their public-keys. In this way, they can mutually verify the public-keys and agree on a shared key using their public and private keys. The shared key, e.g., a common secret accessible by the two network nodes, may be used to encrypt and authenticate messages sent between the client and server in the future.

Due to resource constraints, however, achieving key agreement, e.g., in wireless sensor networks, is non-trivial. For example, public-key based schemes, may not be suitable, e.g., for wireless sensor networks due to the limited computational abilities of the sensor nodes.

So-called identity-based key pre-distribution schemes provide a possible way to simplify the key agreement. An identity-based key pre-distribution scheme has two phases: key pre-distribution and key derivation. Associated with the two phases of the identity-based key pre-distribution scheme are two algorithms: a local key material generation algorithm and a key establishment algorithm, respectively.

The identity-based key pre-distribution scheme is set up by providing a trusted third party with root key material. The trusted third party may be the manufacturer of the device, and may, e.g., provision devices during their manufacturing or in some other trusted environment. Alternatively, the trusted third party may be a certificate authority device, e.g., a device that provisions devices, e.g., using some online protocol.

During key pre-distribution local key material is generated for each network node and stored on the network node, by applying the local key material generation algorithm on the root key material and an identifier of each network node. During the key derivation phase, two network nodes can derive a shared key by applying the key establishment algorithm on their local key material and the identifier of the other network node. For example, a first node may apply the key establishment algorithm on the second identifier of the second network node and its own first local key material, while the second node may apply the key establishment algorithm on the first identifier of the first network node and its second local key material. The result of the key establishment algorithm is an identity-based key shared between two network nodes. There exist a number of identity-based key pre-distribution schemes. For example, an identity-based key pre-distribution scheme is described in "HIMMO - A lightweight collusion-resistant key predistribution scheme", by Oscar Garcia-Morchon, Domingo Gomez-Perez, Jaime Gutierrez, Ronald Rietman, Berry Schoenmakers and Ludo Tolhuizen. Published in Cryptology ePrint Archive, Report 2014/698. An improved version of HIMMO is described in European patent application "Improved system for key sharing" filed with the EPO at 17.12.2015 and with filing number EP15200857.9, with attorney docket 2015PF01725, of the same applicant, and incorporated by reference. HIMMO, like some other identity-based key-distribution schemes, has the disadvantage that sometimes key agreement may fail, or that additional key-reconciliation data (also referred to as helper data) is needed to arrive at a shared key. The key-reconciliation data is usually generated by the first network node that has access to both identities, e.g., the second network node, if the first network note initiated the key agreement.

HIMMO is an identity-based key pre-distribution scheme based on the Hiding Information (HI) and Mixing Modular Operations (MMO) problem. HIMMO is lightweight and more quantum-safe since all existing attacks rely on lattices. In HIMMO, the TTP has some secret root keying material, e.g. a bivariate function R(x,y). The TTP can extract a secret function G_A(x) for a node A from its root keying material (G_A(x)=R(A,y) where this operation is done as described in HIMMO). When A and B wish to establish a common key, A evaluates G_A(x=B) and B evaluates G_B(x=A).

Another usable identity -based key pre-distribution scheme is described in "Perfectly-Secure Key Distribution for Dynamic Conferences" by Carlo Blundo, et al. This scheme has the advantage that key agreement cannot fail, and that no key-reconciliation data is needed. On the other hand the scheme of Blundo is much less resilient against collusion attacks. Yet a further identity-based key-distribution schemes are the Sakai-Ohgishi-Kasahara identity-based non-interactive key exchange (ID-NIKE) schemes.

In an embodiment the root key material comprises a bivariate polynomial and the local key material comprises a univariate polynomial. For example, in the Blundo identity-based key pre-distribution scheme the root key material is formed by a bivariate polynomial f(x, y). Local key material g for and a first node with identifier ID_X, is formed by collapsing the bivariate to a univariate polynomial g(y^~) = f(ID y). A node with local key material g and the identifier of a second node ID₂ obtains a shared key by computing g(ID₂) . All polynomial computations may be done modulo a modulus m. In the following, for the sake of understanding, elements of embodiments are described in operation. However, it will be apparent that the respective elements are arranged to perform the functions being described as performed by them.

Further, the invention is not limited to the embodiments, and the invention lies in each and every novel feature or combination of features described above or recited in mutually different dependent claims.

Figure 1 schematically illustrates an embodiment of a cryptographic system 100. Cryptographic system 100 comprises multiple network nodes; shown are network nodes 140, 150 and 160. The network nodes comprise a communication unit allowing the network node to engage in communication with another network node. There is a desire to secure the communication between two network nodes. In the embodiment illustrated in figure 1, the communication unit 142 of network node 140 is shown connected to network node 150 to illustrate that network node 140 and network node 150 are currently in communication with each other to execute an authentication protocol. Two such network nodes, such as network node 140 and 150, may be referred to as a first network node and a second network node.

The communication between the network nodes could be wireless communication, wired communication or a combination thereof. For example, the multiple network nodes may be a sensor network, in which the sensors communicate with each other. For example, the multiple network nodes may be in the internet of things. One or more of the network nodes may be a server in communication with network nodes that have considerably fewer resources.

Below embodiments of network node 140 will be given in more detail. The other network nodes, e.g. n may use an embodiment corresponding to the embodiment of network node 140. In a typical design of cryptographic network 100, most network nodes have the same basic design differing in the keys.

Network node 140 comprises a key storage 144 and a certificate storage 145. For example, the storage 144 and 145 may be non-volatile memory, e.g. flash memory, or a magnetic storage, etc. They may be implemented as two parts of a single memory unit. They may also be implemented in different memories. For example, the certificate storage 145 contains information that is not considered secret, while the information in key storage 144 is secret. For example, key storage 144 may be secure memory, protected against tampering; For example, the key storage 144 may be encrypted with a symmetric key stored in a onetime programmable memory, such as fuses; while certificate storage 145 may be stored in regular non-volatile memory. The private key, local key material and the certificate are stored in digital form.

The key storage is arranged to store at least first local key material and a first private key. The certificate store 145 is arranged to store a certificate of network node 140. The certificate comprises a public key that corresponds to the private key. The public key may, e.g., be arranged for encryption according to an asymmetric-key cryptographic scheme. The private key corresponds to the public key, e.g., is arranged for decryption according to the asymmetric -key cryptographic scheme. The public and private key correspond to each other and are part of the same asymmetric key-pair. The type of asymmetric scheme may be, e.g., encryption, signing, key agreement (e.g., for Diffie-Hellman), etc. For example, the key- pair may be RSA keys, ECDSA keys, ElGamal keys, etc. The key-pair may be dual use. For example, the key-pair may be an RSA key used both for encryption and for signing, or an ECDSA key used for signing, key-agreement (using Diffie-Hellman) and encryption (using ElGamal).

The key-pair may have been generated by network node 140 itself. This has the advantage that the private key need never leave the device which improves security. But this is not needed, for example, the public-private key pair may have been generated by a trusted third party, during manufacture, testing of the device, e.g. during provisioning, etc. Especially for resource restricted devices having key generation external to the device is advantageous.

Network node 140 comprises an identity unit 146. Identity unit 146 is arranged to form an identifier by applying an identity forming function to a certificate. The identity forming function is preferably a one-way function, so that it is infeasible to find two different messages with the same function value. What is infeasible is considered with respect to the value of breaking the system.

The identifier identifies the certificate. Each network node in the cryptographic system 100 stores a certificate and corresponding local key material. The certificate may be used to identify the network node. The certificate at least comprises a public key, and may also comprise optional additional information. For example, the certificate could comprise one or more of a user name, a computer network address, e.g. a

MAC address, an IP address, a URL, etc, an expiry date, a certificate authority name (if any). It is important to note that the certificate need not be signed; this is different from, e.g., X.509 certificates. X.509 certificates are always signed by a certificate authority device. Each network node has an identifier obtainable by applying the identity forming function to its certificate. In particular, network node 140 has an identifier obtainable by applying the identity forming function to the certificate in certificate storage 145. The certificate and the local key material are linked through the identifier. The local key material has been generated by applying a local key material generation algorithm of an identity-based key pre-distribution scheme on root key material and the first identifier.

For example, the trusted third party may apply the same identifier forming function to the certificates of the multiple network nodes and obtain the corresponding identifiers, then apply the local key material generation algorithm to the identifiers to obtain local key material specific for each certificate. The local key material and the certificate are stored at the certificate.

For example, the identity forming function may be a cryptographic hash function, e.g., SHA-1, SHA-2, etc, RIPEMD, etc. The output of the hash function may be shortened if desired and acceptable given the number of public keys generated by the multiple nodes in system 100. The identifier identifies at least the public key. That is, given the identifier and all public keys used in the multiple nodes 140-160, the identifier corresponds to a unique public key.

All participants in the system, network nodes and trusted third party(ies) are capable of computing the same identifiers. For example, the identity forming function applied to the certificate may be keyed, e.g., a keyed hash, e.g., a MAC, HMAC etc, but in this case all participants in the system have access to the same key used in the identity forming function. This limits participation in the system to devices that have access to the key. Such a key may be provided in network nodes during manufacture.

As noted above, network node 140 comprises a communication unit 142. Communication unit 140 is arranged to communicate with network node 150, e.g., to exchange multiple digital messages. Communication unit 140 is at least arranged to obtain the certificate of network node 150 and an authentication token from network node 150. Below further embodiments are described in which the communication units of the network nodes exchange more messages. The communication of communication unit 142 is preferably digital communication. Identity unit 146 is arranged to obtain the identifier from the certificate received from network node 150.

An authentication token generated with a key is a digital message that is hard to create without the key, and thus increases assurance that the origin of the authentication token had access to the key. Often an authentication token is computed over data that includes a nonce, to avoid replay, but this is not always needed. An authentication token is computed by applying a keyed cryptographic function to data. For example, the

authentication token may be computed by computing a message authentication code (MAC) using the key as key. Possible MACs are HMAC (e.g., RFC 2104), e.g., based on SHA-1, SHA-2, Ripemd, etc, CMAC, e.g., CMAC based on AES or DES, see, e.g., RFC 4493, 4494, and 4615.

Network node 140 comprises an identity-based shared key unit 147 arranged to generate an identity-based shared key by applying a key establishment algorithm of the identity-based key pre-distribution scheme on the second identifier and the first local key material. For example, identity -based shared key unit 147 may be connected to key storage 144 to obtain the local key material. For example, if the identity -based key pre-distribution scheme is the Blundo scheme a univariate polynomial is applied to the identifier of network node 150 to obtain the shared identity-based key.

Network node 140 comprises an authentication unit 148 arranged to authenticate the second network node by cryptographically verifying that the authentication token received form network 150 has been computed from at least the identity-based shared key. Verifying the authentication token implicitly verifies the certificate of network node 150.

For example, network node 140 can reason as follows: since the network node 150 has access to the shared key, it must have local key material that corresponds to the second identifier in order to compute the shared key. Thus the trusted third party had access to the second identifier in order to compute the local key material. The trusted third party computes the identifier from a certificate, as the identifiers match, the certificate for which the trusted third party provided local key material, i.e., which the trusted third party authenticated, is the same certificate as the network node 140 received from the network node 150.

Authentication unit 148 may also be arranged to compute an authentication token from at least the identity-based shared key and to send the authentication token to the network node 150. It is not always required that both parties authenticate to each other. For example, if network node 140 and network node 150 have a client-server relationship it may not be needed that the client (e.g., network node 140) authenticates to the server. For example, to receive a web page it may be desired that the receiver of the web page can authenticate to origin of the web page, yet the receiver of the information may be anonymous and unauthenticated to the server. A number of embodiments of network nodes are described with reference to sequence diagrams 2a, 2b and 3. In each sequence diagram time increases from top to bottom of the figure. Two time lines are shown one for a first network node 240 and one for a second network node 250.

The qualifiers 'first' and 'second' are used mostly for convenience, and serve to distinguish the two nodes. They do not imply an ordering on the network nodes or on the messages they sent. In particular, any one of two network nodes that receives an

authentication token from the other party may be termed the first network node. Apart from that restriction, the qualifiers 'first' and 'second' are interchangeable. In particular, in embodiments in which both network nodes receive an authentication token, one may replace all occurrences of 'first' with 'second' and vice versa to obtain equally valid embodiments. Below, we will refer to network node 240 as the 'first' and network node 250 as the 'second' network node. First network node 240 and second network node 250 may be embodiments of network nodes 140 and 150, respectively.

Figure 2a shows a sequence diagram in which two messages are exchanged.

The diagram shows processing parts 240.1, and 240.3 for first network node 240, and 250.1 for the second network node 250. The diagram shows a message 240.2 sent from first network node 240 to second network node 250, and a message 250.2 sent from second network node 250 to first network node 240. In addition to the shown messages, additional messages may be exchanged. For example, the protocols corresponding to figure 2a may be part of a larger communication. For example, following the exchange of figure 2a, additional communication may follow between first network node 240 and second network node 250.

Objects such as public key, certificate, local key material, authentication token, etc are referred to as first or second depending on where the object was computed or sent from. For example, first certificate C_{l 5} first public key, and the first local key material may be the corresponding material stored at network node 140. Functions _x( ) and /₂( ) refer to the first and second local key material respectively.

In embodiment A:

In message 240.2: First network node 240 sends to second network node 250 - the first certificate C₁

In processing part 250.1: Second network node 250

applies the identity forming function to the first certificate to obtain the first identifier, ID₁ = h^), computes the identity-based shared key from the first identifier and the second local key material K_IB = f₂ (ID₁).

compute a second authentication token with the identity-based shared key K_1B

In message 250.2: Second network node 250 sends to first network node 240 the second authentication token, the second certificate

In processing part 240.3: First network node 240

applies the identity forming function to the second certificate to obtain the second identifier, ID₂ = h(C₂),

- computes the identity-based shared key from the first identifier and the second local key material K_IB = Λ (/£ )·

verifying that the second authentication token has been computed with identity-based shared key

If the first network node 240 succeeds in verifying the second authentication token, this increases the trust first network node 240 has in the second certificate. Processing part 240.1 may be empty.

In general, if the identity-based key pre-distribution system requires the use of helper data, such helper data may be generated when the identity-based shared key is first generated and communicated to the other network node in, say, the next message. For example, helper data may be computed by second network node 250 in processing part 250.1 and communicated to the first network node 240 in message 250.2. First network node 240 uses the helper data when computing the identity based shared key, to ensure that the identity-based shared key is the same at both the first and second network node.

In an embodiment, the second authentication token may be computed over the first public key or over the first certificate. This helps to prevent replay of messages that were used between a different pair of network nodes. For some applications this is sufficient. Consider for example, an ad-hoc network in which many network nodes frequently make contact with other nodes, but only rarely twice with the same node. In such a situation, a lot of assurance is obtained by avoiding the replay of message generated by other network nodes, since those types of messages are the majority. For example, the second authentication token may MAC over the first public key using the identity -based shared key. Replay protection may also be achieved through other means outside the scope of the authentication protocol. The first and second certificates need not be signed, yet this does not open up the protocol to a man in the middle attack. Consider a man in the middle between first network node 240 and second network node 250. The man in the middle wishes to impersonate second network node. Consider, for example, that first network node 240 is a client and second network node 250 is a server. Suppose first network node 240 wants to get a web page with information from second network node 250. The attacker, the man in the middle, wants to replace the page with a page of his own.

For example, the man in the middle could intercept the message 240.2. He sends a message to second network node 250 with his own certificate. This will not work, since second network node 250 will now compute authentication data using the identity- based shared key for the identity of the man in the middle. Such an authentication token will be rejected by first network node 140. If on the other hand, the man in the middle sends the first certificate to second network node 150, he obtains a correct authentication token. But should he try to deliver the authentication token with his own certificate, the authentication token will not verify.

In other words, first network node can verify that the authentication token he receives really corresponds to second network node 250, even without a signature on the certificate.

The authentication protocols have several advantages. The certificates used are not signed. Accordingly, the overhead of signatures is avoided. The signature on a certificate in conventional communication can be an important source of overhead. Moreover, also no signatures need to be verified.

For example, if 2048 bit RSA keys are used, the signature and public key are each about 256 bytes long; eliminating the signature about halves the size of the certificate. Another particularly advantageous situation is in high security situations where care must be taken that the system is secure even in the presence of an attacker with access to a quantum computer. Although at present quantum computers have not evolved to the point where they can attack computer communication, it is known that most known signature algorithms would be vulnerable were the attack to be performed on a quantum computer. In signed certificates one could address this threat by using so-called Quantum safe signatures such as the Merkle signature scheme. However, Merkle signatures have several disadvantages, making them less suitable in practice. For example, the Merkle signature scheme is a onetime signature scheme with limited signing capacity, Moreover Merkle signatures tend to be very long. Thus, when security against quantum threats is required, the certificates according to an embodiment, which do not have a signature on the certificate, sidestep this issue.

Combination with HIMMO based key pre-distribution schemes is especially advantageous as such schemes are considered saver against quantum threads.

For high security applications the security of a signature against non-quantum attacks could be combined with the security against quantum attacks by signing the certificate using a signing key (private) key of certificate authority device 110. For example, the certificate could be signed by RSA, ECDSA, etc, or such keys could be used elsewhere in the protocol.

The embodiment A does not use the public key in the certificates other than for identification. This is no problem in itself. Such public keys may be used for unrelated applications. For example, the public keys may have been used to distribute the local key material. However, the public keys can offer protection for the situation in which the trusted third party is hacked. Below protocols are disclosed that use both the local key material as well as the public key.

In embodiment B:

In processing part 240.1: First network node 240

selects a first nonce η_γ

In message 240.2: First network node 240 sends to second network node 250 the first certificate C_l5 and first nonce n₁

In processing part 250.1 : Second network node 250

applies the identity forming function to the first certificate to obtain the first identifier, ID₁ = ftCCJ,

computes the identity-based shared key from the first identifier and the second local key material K_IB = f₂ (ID₁).

- obtains the first public key Pub from the first certificate C

selects a symmetric encryption key Q

encrypts at least key Q with the first public key Pub_x

computes a second authentication token with the identity-based shared key and the first nonce n_l5 and key Q

- obtains a communication key from key Q

In message 250.2: Second network node 250 sends to first network node 240 the second authentication token, the second certificate C₂, and the encrypted key Q

In processing part 240.3: First network node 240 applies the identity forming function to the second certificate to obtain the second identifier, ID₂ = h(C₂),

computes the identity-based shared key from the first identifier and the second local key material K_IB = /i(/D₂).

- decrypts the encrypted key Q

verifies that the second authentication token has been computed with the identity-based shared key, the first nonce, and key Q. obtains a communication key from key Q

After successful completion of this protocol, the communication key may be used to protect further communication.

In embodiment B, a further shared key is generated (key Q) with the first private key. A communication key is derived from at least the further shared key. For example, key Q may itself be used as a communication key, but key Q may also be combined with the identity -based shared key. The communication key may be used to cryptographically protect future communication between the first network node 240 and the second network node 250. Processing part 250.1 may comprise computing helper data, and message 250.2 may include the helper data.

Involving the private key through a further shared key protects the users of cryptographic system 100 against central attacks on the trusted party. Even if the trusted third party (or all trusted third parties) is hacked, the confidentiality of the communication holds. In this eventuality, the attacker may perhaps be able to create identities and carry out an active attack, but the attacker cannot eavesdrop on arbitrary communication links. In embodiment B, the further shared key may be obtained from a second random number generated by the second network node encrypted by the first public key. In embodiment B, the public/private keys used are suitable for encryption/decryption, e.g., RSA

encryption/decryption keys or ElGamal keys, etc.

There are a number of ways in which second network node 250 may encrypt key Q and compute a second authentication token with the identity-based shared key K_IB, the first nonce n_l5 and key Q :

In a first example: second network node 250 computes

- e = Enc_Pubi(Q)

mac = Mac_KlB e, n₂)

In a second example: second network node 250 computes

mac = Mac_KlB(Q, n₂~) e = Enc_Pubi(Q, mac)

In a third example: second network node 250 computes

- e₀ = Enc_Publ(Q)

mac = Mac_Kw(e₀, n₂ ^')

- e = Enc_Publ(Q, mac)

In all three examples, the encryption e is sent to network node 240. In the first example, mac is sent separately; in examples two and three the value mac is sent encrypted. In the first and third example, the second authentication token is computed by applying a cryptographic function, e.g., a message authentication code, to a value encrypted with the first public key. This implicitly links the authentication token to the public key of the first network node. These constructions for computing an authentication token could also be applied in other embodiments, using a further key, e.g., key Q , a nonce, and a public key suitable for encryption. If replay protection between nodes is not required the nonce could be omitted or replaced by, e.g., the certificate or public key of the other party. The protocol of embodiment B could be extended with an additional message by computing a first authentication token at the first network node and sending it to the second network node.

Figure 2b shows a sequence diagram in which three messages are exchanged. In addition to the processing parts and messages of figure 2a, figure 2b shows processing parts 250.3, and message 240.4.

In the following embodiment, embodiment A has been extended with nonces and an additional authentication token. One could also have an embodiment in which no nonces are used (e.g., computing authentication tokens over public keys) or an embodiment in which a nonce is used but only a single authentication token, and in which message 240.4 may be omitted. A nonce is a number used only once. For example, the nonce may be a random number, a time stamp, a serial number etc. If the communication channel is prone to replay attacks, the nonces protect against this threat.

In embodiment C:

In processing part 240.1: First network node 240

selects a first nonce n₁

In message 240.2: First network node 240 sends to second network node 250 the first certificate C_l5 and first nonce η_γ

In processing part 250.1: Second network node 250

applies the identity forming function to the first certificate to obtain the first identifier, ID₁ = ftCCJ, computes the identity-based shared key from the first identifier and the second local key material K_IB = f₂ (ID₁).

computes a second authentication token with the identity-based shared key and the first nonce η_γ

- selects a second nonce n₂.

In message 250.2: Second network node 250 sends to first network node 240 the second authentication token, the second certificate C₂, and the second nonce n₂

In processing part 240.3: First network node 240

- applies the identity forming function to the second certificate to obtain the second identifier, ID₂ = h(C₂),

verifies that the second authentication token has been computed with the identity-based shared key and the first nonce

computes a first authentication token with the identity-based shared key and the second nonce n₂

In message 240.4: First network node 240 sends to second network node 250 the first authentication token

In processing part 250.3: Second network node 250

verifies that the first authentication token has been computed with the identity-based shared key and the second nonce

In processing parts 240.3 and 250.3 also a communication key may be obtained e.g., the identity-based shared-key, or a key derived therefrom.

In general if verification of an authentication token fails, the communication may be broken off, and/or other appropriate action may be taken, e.g., sending a warning signal for the user, or to a server. After successful completion of an embodiment of a protocol between the first and second network node the nodes may start further communication. The further communication may be cryptographically protected, e.g., encrypted and/or

authenticated, using a shared communication key. The shared communication key is typically a symmetric key and may be, e.g., the identity-based shared key. For example, a key derivation function (KDF) may be first applied to obtain the communication key. The identity-based shared key may be diversified, e.g., into an encryption and authentication key. The former may be used for a block cipher, e.g., AES, the latter for authentication, e.g., a MAC.

Also embodiment B could be extended with two nonces rather than one, e.g., by selecting and sending a second nonce at the second network node 250, and computing and sending a first authentication token from the first network node 240. Processing part 250.1 may comprise computing helper data, and message 250.2 may include the helper data.

Asymmetric cryptography may be combined in different ways with the identity-based key pre-distribution. In the following embodiment, keys suitable for Diffie- Hellman (DH) are used

In embodiment D:

In processing part 240.1: First network node 240

selects a first nonce η_γ

In message 240.2: First network node 240 sends to second network node 250 the first certificate C_{l 5} and first nonce n₁

In processing part 250.1: Second network node 250

applies the identity forming function to the first certificate to obtain the first identifier, ID₁ = h^),

obtains the first public key Pub from the first certificate C computes a Diffie-Hellman key K_DH from the first public key Pub and the second private key Priv₂

combines the Diffie-Hellman key K_DH and the identity-based shared key K_IB to form a combined key K_cmb .

computes a second authentication token with the combined key

K_cmb and the first nonce n₁

selects a second nonce n₂.

In processing part 240.3: First network node 240

applies the identity forming function to the second certificate to obtain the second identifier, ID₂ = h(C₂), computes the identity-based shared key from the first identifier and the second local key material K_IB = Α( β₂)

obtains the second public key Pub₂ from the first certificate C₂ compute the Diffie-Hellman key K_DH from the second public key Pub₂ and the first private key Priv₁

- computes a first authentication token with the combined shared key K_cmb and the second nonce n₂

In processing part 250.3: Second network node 250

- verifies that the first authentication token has been computed with the combined shared key K_cmb and the second nonce

In embodiment D, a further shared key (Diffie-Hellman key K_DH) is obtained with at least the first private key. This further shared key does not (only) depend on information distributed by the trusted third party. Thus even in the face of an attack of the trusted party, both past and future communication could remain secure. The further shared key is obtained by applying a Diffie-Hellman key agreement algorithm on a second public key obtained from the second certificate and the first private key. The further shared key is used by the first network node to verify the second authentication token and to compute the first authentication token. Note that also a communication key could be derived from the further shared key or from the combined key. Embodiment D sends two nonces, but could instead be adapted not to work with nonces that need not always be sent, e.g., timestamps. Embodiment D could be adapted to work without nonces, if replay is less of a concern and instead compute the authentication token on the public key of the other party, etc.

Embodiment D could also be adapted to work with only one authentication token, depending on which party needs to be authenticated. Processing part 250.1 may comprise computing helper data, and message 250.2 may include the helper data.

Embodiment D may work with any asymmetric scheme that supports Diffie- Hellman. For example, the private key a and the public key A of the first network node may be related as A = g^a(mod N) for some known g and iV, and the private key b and the public key B for the second node may satisfy B = g^b, (mod N). In this case the further shared key K_DH may be computed by either network node as K_DH = A^b = B^a (mod N) . A similar scheme is possible for Elliptic Curve Diffie Hellmann. The Diffie-Hellman shared key may be notated as Pub Priv₂ which key is equal to Pub₂ Priv^ . There are multiple asymmetric cryptosystems which have a component as above which allows for this Diffie Hellmann algorithm.

In embodiment D, a combined key is generated from the identity-based shared key and the further shared key. The combined key is used to verify the second authentication token and/or to compute the first authentication token. Interestingly, authentication is thus identity-based as well as private key based, without having an increase in the number or size of the messages.

Embodiment D may be extended with ephemeral keys, e.g., a temporary key, to improve forward security, so that even if at some point both network nodes and/or the trusted third parties are compromised past communication is still safe.

In embodiment E:

In processing part 240.1 : First network node 240

selects a first nonce η_γ

generates an ephemeral public/private key pair Pub[, Privl suitable for a Diffie-Hellman algorithm

In message 240.2: First network node 240 sends to second network node 250 - the first certificate C_{l 5} first nonce n_l5 and the first ephemeral

public key Pub[,

In processing part 250.1: Second network node 250

- computes the identity-based shared key from the first identifier and the second local key material K_IB = f₂ (ID₁).

obtains the first public key Pub_x from the first certificate C_x generates an ephemeral public/private key pair Pub₂ , Privl suitable for the Diffie-Hellman algorithm

- computes a Diffie-Hellman key K_DH from the first public key Pub_x, the first ephemeral public key Publ , the second private key Priv₂ , and the second ephemeral private key Priv₂

combines the Diffie-Hellman key K_DH and the identity-based shared key K_IB to form a combined key K_cmb . computes a second authentication token with the combined key

K_cmb and the first nonce n₁

selects a second nonce n₂.

In message 250.2: Second network node 250 sends to first network node 240 - the second authentication token, the second certificate C₂, the second nonce n₂ , and the second ephemeral public key,

In processing part 240.3: First network node 240

- computes the identity-based shared key from the first identifier and the second local key material K_IB = Α( β₂)

obtains the second public key Pub₂ from the first certificate C₂ computes the Diffie-Hellman key K_DH from the second public key Pub₂ , second ephemeral public key Pub₂ , the first private key Priv^ and the first ephemeral private key Privl

In processing part 250.3: Second network node 250

The first network node 240 and second network node 250 may comprise a key pair generation unit 141 arranged to generate the ephemeral public key and corresponding ephemeral private key, e.g., according to an asymmetric -key cryptographic scheme suitable for Diffie-Hellman, e.g., the same asymmetric-key cryptographic scheme as the one use for the public key in the certificates. In embodiment E, a key pair generation unit of the first and second network node is arranged to generate a first ephemeral public key and a

corresponding first ephemeral private key, according to an asymmetric-key cryptographic scheme. The communication device is arranged to send the first ephemeral public key to the second network node, the corresponding private key is kept secret by the network node. The communication unit is also arranged to receive an ephemeral public key from the other network node; e.g. the first communication unit receives the second ephemeral public key from the second network node. Note that the ephemeral public keys are different from the public keys in the certificates. The authentication units are arranged to generate a further shared key from at least the first ephemeral private key and in this case the first private key. For example, a first authentication unit could generate a further shared key from the first ephemeral private key and the second public key. In the embodiment E, the first

authentication unit generates the further shared key from the first ephemeral private key, the first private key (corresponding to the first certificate), the second public key (from the second certificate) and the second ephemeral public key, using the Diffie-Hellman algorithm. The further shared key is used to verify the second authentication token and/or compute the first authentication token. In this case, the authentication unit is arranged to generate a combined key from the identity-based shared key and the further shared key. The further shared key could also be used, instead or in addition, to compute a communication key. The combined key in this embodiment is identity-based as well as private key based. Moreover, as there is an ephemeral key used in its generation, even after a break of the network nodes, and the trusted third parties the communication can remain secure. At some point after the authentication protocol, e.g., after the communication between network nodes 240 and 250 finished, e.g., communication protected using a communication key, the ephemeral keys and communication key derived therefrom are deleted. The same mechanism used to establish an ephemeral key could be used to establish an additional non-ephemeral key.

For example, supposing that the private key of the first network node comprises a secret exponent a, the ephemeral private key the secret exponent a_e, the private key of the second network node comprises a secret exponent b, the ephemeral private key the secret exponent b_e, the public key of the first network node comprises A = g^a(mod N), the ephemeral public key of the first network node comprises A_e = g^ae (mod N), the public key of the second network node comprises B = g^b(mod N), the ephemeral public key of the second network node comprises B_e = g^be(mod N) . The Diffie-Hellman key could be computed as (BB_e ~)^a+ae = (g^bg^be)^a+ae = (gb+b_ey+a_{e = g}(b+b_exa+a_e ) ₌ (_AAg y+b_e _ _{The latter is} p_referred as it allows blinding of the private exponent a with a_e . Alternatively, theDiffie-Hellman key may be computed as, e.g., A^bB_e ^ae .

For example, the private key a and the public key A of the first network node may be related as A = g^a(mod N) for some known g and iV, and the private key b and the public key B for the second node may satisfy B = g^b, {mod N). In this case the further shared key K_DH may be computed by either network node as K_DH = A^b = B^a (mod N).

The first and second authentication token used in the embodiment E may be computed as Hash(K_cmb \n₁ \n₂) and HashiK^^ ^ respectively or vice versa. This mechanism may also be used to compute authentication tokens in the other embodiments using nonces and a key, e.g. the combined key, further key or identity-based shared key. Note that these two tokens will not be the same, even though they are computed over the same data. The hash may be a cryptographic hash. An identity-based shared key and a Diffie- Hellman key may be combined, e.g., by XOR-ing them, or by hashing their concatenation, etc. Processing part 250.1 may comprise computing helper data, and message 250.2 may include the helper data.

Ephemeral keys may also be used that are not necessarily suitable for Diffie- Hellman. For example, the embodiment below uses an ephemeral encryption/decryption key.

In embodiment F:

In processing part 240.1: First network node 240

selects a first nonce η_γ

generates a first ephemeral public/private key pair Pub[, Privl suitable for encryption/decryption

In message 240.2: First network node 240 sends to second network node 250 the first certificate C_l5 first nonce n_{l 5} first ephemeral public key Pub[

In processing part 250.1: Second network node 250

obtains the first public key Pub_x from the first certificate C_x selects a first symmetric encryption key Q¹

selects a second symmetric encryption key Q²

encrypts at least key Q¹ with the first public key Pub_x

encrypts at least key Q² with the first ephemeral public key Publ computes a second authentication token with the identity-based shared key, first nonce n_l5 first key Q¹, and second key Q² obtains a communication key from first key Q¹, and second key Q² In message 250.2: Second network node 250 sends to first network node 240 the second authentication token, the second certificate C₂, and the encrypted first key Q¹, and encrypted second key Q²

In processing part 240.3: First network node 240

decrypts the encrypted first key Q¹, and encrypted second key Q² - verifies that the second authentication token has been computed with the identity-based shared key, the first nonce, and first key Q¹, and second key Q².

obtains a communication key from keys Q¹ and Q²

compute a first authentication token with the identity-based shared key, second nonce n₂, first key Q¹, and second key Q²

In processing part 250.3: Second network node 250

verifies that the first authentication token has been computed with the identity-based shared key, second nonce n₂, first key Q¹, and second key Q²

obtains a communication key from keys Q¹ and Q²

For example, computing the second authentication token mac and performing the encryption may be done as follows

- e₀ = Enc_Publ(Q^l)

- e₁ = Enc_Pube(Q²)

mac = Mac{e₀, e₁, K_1B)

The values e₀, e_l5 and mac are sent in message 250.2 The mac may use K_IB as key. Other constructions are possible, analogous to those given at embodiment B. The first authentication token may be computed in the same manner as the second authentication token. The authentication token mac is computed over a value a value encrypted with the public key received from the other party; in an embodiment also a nonce received from the other party is added. A further variant for the authentication tokens is given below. This

construction may be applied only to the last authentication token in the protocol (in embodiment F the first authentication token) or may be applied also to the other

authentication token. Similar application in other embodiments is also possible. For this authentication token a combined symmetric key is obtained from the further key(s) and the identity-based key. In this case, from Q¹, Q² , and K_IB . A message authentication code is computed over all information previously exchanged between the first and second network node in this protocol, or even over all messages exchanged between the first and second network node in this protocol. For example, a message authentication may be computed over C_{l 5} C₂, e₀, e_{l 5} Pub[, using the combined key as key to obtain a first authentication token.

Computing a message authentication token over all previous exchanged information provides strong assurance that the protocol cannot be chopped up and e.g. partially replayed in another order or with another node to obtain some advantage. Processing part 250.1 may comprise computing helper data, and message 250.2 may include the helper data.

In embodiment F, two further shared keys are generated. The further shared keys are used both to compute/verify authentication tokens and to compute a communication key. The way to obtain a communication key from Q¹ and Q² should be identical for network nodes 240 and 250.

The further shared keys Q¹ and Q² may be obtained from random numbers generated by the second network node and encrypted by the first public key and first public ephemeral key. Moreover, the first network node generates a first ephemeral public key and a corresponding first ephemeral private key, according to an asymmetric-key cryptographic scheme. The asymmetric -key cryptographic scheme is suitable for encryption/decryption, e.g., RSA, ElGamal, etc. The first ephemeral private key is used to decrypt the further keys obtained from the second network node 250. An authentication token is computed by applying a cryptographic function to a value encrypted with the first public key, and (in this case) also to a value encrypted with the first ephemeral public key. For example, an authentication unit may be arranged to generate the further shared key from at least the first ephemeral private key.

Figure 3 schematically illustrates an authentication protocol in which four messages are exchanged. Moreover, public/private keys are used which are suitable for cryptographic signing, e.g., ECDSA, RSA signing etc. In this case random numbers are used, which are a type of nonces. Both parties commit to a random number before computing the combined key, etc. First network node 340 and second network node 350 may be embodiments of network nodes 140 and 150.

In embodiment G:

In processing part 340.1: first network node 340

selects a first random number R₁

In message 340.2: first network node 340 sends to second network node 350 first random number R₁

In processing part 350.1: second network node 350

selects a second random number R₂

In message 350.2: second network node 350 sends to first network node 340

- second random number R₂ , second certificate C₂

In processing part 340.3: first network node 340

computes the identity-based shared key from the first identifier and the second local key material K_IB = /i(/D₂),

selects a symmetric encryption key Q

obtains the second public key Pub₂ from the second certificate C₂ encrypts at least key Q with the second public key Pub₂

computes a first authentication token by signing at least second random number R₂

computes a further first authentication token with the identity- based shared key and the second random number R₂, and key Q

In message 340.4: first network node 340 sends to second network node 350 first certificate C_{l 5} the first and further first authentication token, the encrypted key Q

In processing part 350.3: second network node

decrypts the encrypted key Q

verifies the signature

verifies the first authentication token computes a second authentication token with the identity-based shared key, and the first random number fl_x

In message 350.4: second network node 350 sends to network node 340

the second authentication token

For example, the signature in processing part 340.3 may be computed using the private key corresponding to the public key in first certificate C_x . The latter may be used if the public/private key may both be used for encryption as well as for decryption. Dual use keys may be, e.g., an RSA key which may be used both for encryption/decryption and for verification/signing, or, e.g., an ECDSA key for signing which may also be used for ElGamal encryption. The signature may also be computed using a separate private signing key. The corresponding public verification key may be embedded in the first certificate as a separate key. The signature may, e.g., be computed over the first and second random number, and possibly also over the second certificate. Processing part 340.3 may comprise computing helper data, and message 340.4 may include the helper data.

In this embodiment, a network node computes two authentication tokens, one using an asymmetric signing key, and one using an identity-based shared key. Introducing a signing based authentication token could be added to other protocols as well.

The encryption of the key Q may be done using the second public key obtained from the second certificate, e.g., e = Enc_Pub2 (Q).

The further first authentication token may be a message authentication code computed over the first and second random number, the first and second certificate, the encrypted key e, and the signature using as key a combined key. The combined key may be obtained from Q, K_IB , and the first and second random numbers R R₂

Following this protocol the first and second network node may use the combined key as communication key.

In all protocols usual protocol elements may be added as needed. For example, the messages in a particular protocol may include a session identifier, to identify the protocol session, network addresses, message headers etc. Such session identifiers and/or addresses may be included in cryptographic elements as well, e.g., authentication tokens etc. Even message headers may be included in such elements.

Devices 140, 150, 240, 250, 340, 350 may be provisioned with certificates, and local key material in any suitable manner. For example, certificates and local key material may be stored at a device during manufacture, during testing, etc. They may also be provided in some online protocol. Below, as an example, one way is given in which certificates and local key material may be distributed to a network device from a certificate authority device, e.g., a trusted third party.

Figure 4 shows network node 140 comprising a key pair generation unit 141 arranged to generate a public/private key pair according to an asymmetric cryptographic scheme suitable for encryption and decryption and e.g. for inclusion in a certificate, and a decryption unit 143 arranged to decrypt messages using the private key. Network node 140 may be used to receive local key material from a certificate authority device 110 by executing a protocol over a computer network. Only units are shown that may be used in said protocol. Also network nodes 150 and 160 may be provisioned by certificate authority device 110. Figure 5 shows in the form of a sequence diagram how a network node 240, e.g., network node 140 and a certificate authority device 210, e.g., certificate authority device 110 may cooperate to distribute a certificate.

Time increases along the vertical axes from top to bottom of the figure. In the protocol usual protocol elements may be added if needed. For example, the messages in a particular protocol may include a session identifier, to identify the protocol session. Such session identifiers may be included in cryptographic elements as well, e.g., authentication tokens etc.

Network node 240 generates 240.1 a public key and a corresponding private key and sends 240.2 the public key to the certificate authority device 210. Certificate authority device 210 generates 210.1 a certificate comprising the public key, possibly a nonce, and possibly other information, and forms 210.2 an identifier by applying an identity forming function to the certificate. The identifier depends on the public key and the other information. Certificate authority device 210 then generates 210.3 local key material specific for the network node, by applying the local key material generation algorithm of the identity- based key pre-distribution scheme on the root key material and the identifier. At least the local key material specific for the network node is encrypted 210.4 by the public key of the network node. In an embodiment, also the certificate is encrypted with the public key.

Finally, the encrypted local key material is sent 210.5 to the network node. Optionally, the certificate is also sent to network node 240.

At the network node, the sent encrypted local key material is decrypted 240.3 using the private key, thus obtaining the local key material. The local key material, the private key, and the certificate are stored 240.4, e.g., in local storage, e.g., in a key storage and certificate storage. An optional extension of the protocol up to 240.4 is to use multiple certificate authorities. Figure 5 shows a further certificate authority device 220. Network node 240 may be arranged to send the certificate to further certificate authority 220. For example, network node 240 either constructs the certificate itself, or receives the certificate from certificate authority device 210. The certificate for which it has received local key material and which defines its identity is then send to further certificate authority 220 by network node 240. Alternatively, further certificate authority 220 may receive the certificate from certificate authority device 210.

In an embodiment, a network node receives local key material from multiple certificate authorities. This local key material may be combined by the network node. Thus if a certificate authority device is hacked the local key material of a network node is not directly compromised.

Network node 240 may combine the local key material received from the certificate authority device and the further local key material received from the further certificate authority device into a single local key material. The combination may be done after receiving the local key materials, e.g., by adding the local key materials, to obtain a combined local key material. The combined local key material may be used for key agreement. The combination does not need to be done directly after receiving the

information, although this is possible.

Waiting with combining key material until needed in a key agreement has the advantage that the network nodes can engage in TTP (certificate authority) negotiation. Identity-based key pre-distribution schemes based on HIMMO are particularly advantageous for this embodiment, since in HIMMO local key materials can be combined straightforwardly by a modular addition. In an embodiment, In an embodiment, two network nodes

communicate to each other which certificate authorities they support, e.g., in a hello message at the start of the protocol. The generated key between these nodes then is based on the local keying material generated by the certification authorities supported by both network nodes. In this case, local keying material of multiple certificate authority devices is stored.

In conventional certificate authorities it is hard to certify by more than or a few certificate authorities. However, with certificates according to an embodiment combining certification of multiple certificate authorities is not a problem. For example, in an embodiment, more than two, say 50 certificate authorities are combined. For example, every mobile phone operator may operate a certificate authority. The network node uses a first certificate authority device to get a certificate and first local key material. Next the network node sends the certificate to 49 more certificate authorities and receives 49 times additional local key materials. Once a network node has received local key material, encryption and/or authentication may also be done using a shared key instead or in addition to the public key. In an embodiment, all local key material is encrypted with the public key of the network node in transit and/or with a shared key. By using at least the public key of the network node, even if the first certificate authority is compromised the network node will receive uncompromised key materials from uncompromised subsequent certificate authorities.

The local key material used by the first network node may be obtained from a single certificate authority, or from multiple certificate authorities and combined before the network node starts the above protocol. This is not necessary though, the network node may also select which local key material to use during the protocol. For example, in an

embodiment the communication node is arranged to send to the second network node from which certificate authorities the first network node received local key material, and to receive from the second network node from which certificate authorities the second network node received local key material, the identity-based shared key unit being arranged to combine local keying material generated by the certification authorities for which both the first and second network nodes received local key material, e.g., to combine local keying material for all common certificate authorities.

Certificate authority agreement has an advantage as can be seen in the following example. Suppose, the first network node received local keying material from certificate authorities CAl and CA2, and the second network node from certificate authorities CA2, and CA3. The two network nodes can communicate together using only the keying material from CA2. They cannot communicate with each other if the first network node had combined the material of CAl and CA2, whereas the second network node combined the material of CA2 and CA3. The reduce a possible risk of manipulating a network node into using a weak certificate authority, a network node could require that local keying material from at least two common certificate authorities are needed to communicate.

Further protocols for distributing local key material and/or certificates are provided in a patent application with title "System and method for distribution of identity based key material and certificate", with attorney docket 2016PF00212 which has the same inventors, and applicants as the present patent application and is filed on the same date with the same office; the patent is incorporated herein by reference.

Typically, the devices 110, 140, 150, 210, 220, 240, 250, 340 and 350 each comprise a microprocessor (not separately shown) which executes appropriate software stored at the devices; for example, that software may have been downloaded and/or stored in a corresponding memory, e.g., a volatile memory such as RAM or a non-volatile memory such as Flash (not separately shown). The devices may also be equipped with

microprocessors and memories (not separately shown). Alternatively, the devices may, in whole or in part, be implemented in programmable logic, e.g., as field-programmable gate array (FPGA). The devices may be implemented, in whole or in part, as a so-called application- specific integrated circuit (ASIC), i.e. an integrated circuit (IC) customized for their particular use. For example, the circuits may be implemented in CMOS, e.g., using a hardware description language such as Verilog, VHDL etc.

In an embodiment, a network node may comprise one or more of a key storage circuit, a certificate storage circuit, an identity circuit, a communication circuit, an identity- based shared key circuit, an authentication circuit, a key pair generation circuit. The circuits implement the corresponding units described herein. The circuits may be a processor circuit and storage circuit, the processor circuit executing instructions represented electronically in the storage circuits. The circuits may also be, FPGA, ASIC or the like.

Many different ways of executing the method are possible, as will be apparent to a person skilled in the art. For example, the order of the steps can be varied or some steps may be executed in parallel. Moreover, in between steps other method steps may be inserted. The inserted steps may represent refinements of the method such as described herein, or may be unrelated to the method. For example, some steps may be executed, at least partially, in parallel. Moreover, a given step may not have finished completely before a next step is started.

A method according to the invention may be executed using software, which comprises instructions for causing a processor system to perform a method. Software may only include those steps taken by a particular sub-entity of the system. The software may be stored in a suitable storage medium, such as a hard disk, a floppy, a memory, an optical disc, etc. The software may be sent as a signal along a wire, or wireless, or using a data network, e.g., the Internet. The software may be made available for download and/or for remote usage on a server. A method according to the invention may be executed using a bitstream arranged to configure programmable logic, e.g., a field-programmable gate array (FPGA), to perform the method.

It will be appreciated that the invention also extends to computer programs, particularly computer programs on or in a carrier, adapted for putting the invention into practice. The program may be in the form of source code, object code, a code intermediate source and object code such as partially compiled form, or in any other form suitable for use in the implementation of the method according to the invention. An embodiment relating to a computer program product comprises computer executable instructions corresponding to each of the processing steps of at least one of the methods set forth. These instructions may be subdivided into subroutines and/or be stored in one or more files that may be linked statically or dynamically. Another embodiment relating to a computer program product comprises computer executable instructions corresponding to each of the means of at least one of the systems and/or products set forth.

Figure 6a shows a computer readable medium 1000 having a writable part 1010 comprising a computer program 1020, the computer program 1020 comprising instructions for causing a processor system to perform a network node method, according to an embodiment. The computer program 1020 may be embodied on the computer readable medium 1000 as physical marks or by means of magnetization of the computer readable medium 1000. However, any other suitable embodiment is conceivable as well. Furthermore, it will be appreciated that, although the computer readable medium 1000 is shown here as an optical disc, the computer readable medium 1000 may be any suitable computer readable medium, such as a hard disk, solid state memory, flash memory, etc., and may be non- recordable or recordable. The computer program 1020 comprises instructions for causing a processor system to perform said network node method.

Figure 6b shows in a schematic representation of a processor system 1140 according to an embodiment. The processor system comprises one or more integrated circuits 1110. The architecture of the one or more integrated circuits 1110 is schematically shown in Figure 6b. Circuit 1110 comprises a processing unit 1120, e.g., a CPU, for running computer program components to execute a method according to an embodiment and/or implement its modules or units. Circuit 1110 comprises a memory 1122 for storing programming code, data, etc. Part of memory 1122 may be read-only. Circuit 1110 may comprise a

communication element 1126, e.g., an antenna, connectors or both, and the like. Circuit 1110 may comprise a dedicated integrated circuit 1124 for performing part or all of the processing defined in the method. Processor 1120, memory 1122, dedicated IC 1124 and communication element 1126 may be connected to each other via an interconnect 1130, say a bus. The processor system 1110 may be arranged for contact and/or contact-less communication, using an antenna and/or connectors, respectively. It should be noted that the above-mentioned embodiments illustrate rather than limit the invention, and that those skilled in the art will be able to design many alternative embodiments.

In the claims, any reference signs placed between parentheses shall not be construed as limiting the claim. Use of the verb "comprise" and its conjugations does not exclude the presence of elements or steps other than those stated in a claim. The article "a" or "an" preceding an element does not exclude the presence of a plurality of such elements. The invention may be implemented by means of hardware comprising several distinct elements, and by means of a suitably programmed computer. In the device claim enumerating several means, several of these means may be embodied by one and the same item of hardware. The mere fact that certain measures are recited in mutually different dependent claims does not indicate that a combination of these measures cannot be used to advantage.

In the claims references in parentheses refer to reference signs in drawings of embodiments or to formulas of embodiments, thus increasing the intelligibility of the claim. These references shall not be construed as limiting the claim.

List of Reference Numerals in figure 1 and 4:

100 a cryptographic system

110 certificate authority device

140, 150, 160 a network node

141 a key pair generation unit 142 a communication unit

143 a decryption unit

144 a key storage

145 a certificate storage

146 an identity unit

147 a identity-based shared key unit 148 an authentication unit

210, 220 a certificate authority device 240, 340 a first network node

250, 350 a second network node

Claims

CLAIMS:

1. A first network node comprising

a key storage (144) arranged to store at least first local key material, a certificate storage (145) arranged to store a first certificate,

an identity unit (146) arranged to form an identifier by applying an identity forming function to a certificate, the identifier identifying the certificate, the first network node having a first identifier obtainable by applying the identity forming function to the first certificate, the first local key material having been generated by applying a local key material generation algorithm of an identity-based key pre-distribution scheme on root key material and the first identifier,

- a communication unit (142) arranged to obtain a second certificate and a second authentication token, from a second network node, the identity unit (146) being arranged to obtain a second identifier from the second certificate,

an identity-based shared key unit (147) arranged to generate an identity-based shared key by applying a key establishment algorithm of the identity-based key pre- distribution scheme on the second identifier and the first local key material,

an authentication unit (148) arranged to authenticate the second network node by cryptographically verifying that the second authentication token has been computed from at least the identity -based shared key.

2. A first network node according to claim 1, wherein the authentication unit

(148) is arranged to compute a first authentication token from at least the identity -based shared key and the communication unit (142) is arranged to send the first authentication token to the second network node.

3. A first network node as in Claim 1 or 2, wherein

the key storage (144) is arranged to store a first private key, the first certificate comprising a first public key, the first public key corresponding to the first private key, the first public key and first private key being arranged according to an asymmetric-key cryptographic scheme.

4. A first network node as in Claim 3, wherein the authentication unit is arranged to generate a further shared key with at least the first private key, the further shared key being a shared-key, shared with the second network node, wherein

- the authentication unit is arranged to use the further shared key to verify the second authentication token and/or compute the first authentication token, and/or

the authentication unit is arranged to compute a communication key from at least the further shared key and optionally the identity -based shared key, the communication key being used to cryptographically protect future communication between the first network node and the second network node.

5. A first network node as in Claim 4, wherein

the authentication unit is arranged to obtain the further shared key by applying a Diffie-Hellman key agreement algorithm on a second public key obtained from the second certificate and the first private key, and/or

the authentication unit is arranged to obtain the further shared key from a second random number generated by the second network node encrypted by the first public key and/or to obtain the further shared key from a first random number generated by the first network node send encrypted by the second public key to the second network node.

6. A first network node as in any one of Claims 4 and 5, comprising

a key pair generation unit arranged to generate a first ephemeral public key and a corresponding first ephemeral private key, according to an asymmetric-key

cryptographic scheme,

- the communication device being arranged to send the first ephemeral public key to the second network node,

the authentication unit being arranged to generate the further shared key from at least the first ephemeral private key, the further shared key being used to verify the second authentication token and/or compute the first authentication token.

7. A first network node as in any one of claims 4, 5 and 6, wherein the authentication unit is arranged to generate a combined key from the identity -based shared key and the further shared key, said combined key being used to verify the second authentication token and/or to compute the first authentication token.

8. A first network node as in any one of the preceding claims, wherein computing the first authentication token comprises applying a cryptographic function to a second nonce received from the second network node and/or wherein verifying the second authentication token comprises applying a cryptographic function to first nonce generated by the first network node.

9. A first network node as in any one of the preceding claims, wherein

computing the first authentication token comprises applying a cryptographic function to the second public key and/or wherein verifying the second authentication token comprises applying a cryptographic function to first public key, or

computing the first authentication token comprises applying a cryptographic function to a value encrypted with the second public key and/or wherein verifying the second authentication token comprises applying a cryptographic function to a value encrypted with the first public key.

10. A first network node as in any one of the preceding claims, wherein the communication unit of the first node is arranged to send the first certificate to the second network node.

11. A first network node as in any one of the preceding claims arranged to receive the first certificate from a certificate authority device, the first network node comprising a key pair generation unit arranged to generate the first public key and the corresponding first private key, the first public key being arranged for encryption according to an asymmetric-key cryptographic scheme, the first private key being arranged for decryption according to the asymmetric-key cryptographic scheme, the communication unit being arranged to send the first public key to a certificate authority device, and to receive from the certificate authority device the first local key material encrypted with the first public key,

- a decryption unit arranged to decrypt encrypted first local key material received from the certificate authority device using the first private key obtaining the first local key material.

12. A first network node or a certificate authority device as in any one of the preceding claims, wherein the identity-based key pre-distribution scheme is a HIMMO scheme.

13. A first network node method comprising

forming an identifier by applying an identity forming function to a certificate, the identifier identifying the certificate, the first network node having a first identifier obtainable by applying the identity forming function to a first certificate of the first network node, first local key material having been generated by applying a local key material generation algorithm of an identity-based key pre-distribution scheme on root key material and the first identifier,

obtaining a second certificate and a second authentication token, from a second network node, the identity unit being arranged to obtain a second identifier from the second certificate,

- generating an identity-based shared key by applying a key establishment algorithm of the identity-based key pre-distribution scheme on the second identifier and the first local key material,

authenticating the second network node by cryptographically verifying that the second authentication token has been computed from at least the identity -based shared key.

14. A computer program (1020) comprising computer program instructions arranged to perform the method of claim 13 when the computer program is run on a computer.

15. A computer readable medium (1000) comprising the computer program (1020) as in claim 14.