Self-organized public key management (SOPKM)

The scope of key management.

Public key management system.

• How to get the authentic public key of a user?

Users issue certificates based on personal acquaintance.

• Certificate: binding between a node and its public key: public key, identity, and signature of the issuer.

• Certificates are stored and distributed by the users themselves.

Updated certificate repository.

Non-updated certificate repository.

• Expired certificates.

Public Keys and Public-Key Certificates

If a user u believes that a given public key Kv belongs to a given user v, then u can issue a public-key certificate in which Kv is bound to v by the signature of u.

Certificates are issued with a limited validity period Tv.

Each certificate contains its issuing and expiration times.

• u gets the public key Kv of v through a side channel.

• u creates a certificate for v to bind the Kv and v.

• u stores the certificate of v in its local repository Gu and sends the certificate to v.

• Each time a user u issues a certificate that binds another user v to her public-key Kv, u sends the certificate to v.

  • In this way, each certificate is stored at least twice: by its issuer and by the user to whom it is issued.

Update repositories of certificate graphs

Certificate of u to v, using u private key pr Ku(v, Kv).

Gu Updated global certificate of u NGu non-updated global certificate of u.

Certificate Exchange

Each node u multicasts its subgraphs Gu and GuN to its physical neighbors (only 1 hop away).

In this message, u does not send actual certificates, but only appropriate unique identifiers (e.g., their hash values).

The neighbors of node u that receive the message from u reply with the hash values of the certificates in their updated and non-updated repositories.

Node u then crosschecks the received values with the certificates that it holds and requests from its neighbors only the certificates that it does not hold.

Global Connectivity Graph

Global certificate graph.

Connectivity of certificate graph.

• Small world phenomenon.

  • Due to social relationships.

  • Mobility increases connectivity.

    • Mobile nodes/users exchange their public keys whenever they meet.

Vertices: public keys of some nodes.

Edges: public key certificates issued by users.

Certificate graph

Vertices: public keys of the nodes.

Edges: public key certificates issued by users.

User u wants to obtain the public key of user v.

• Find a chain of valid public key certificates leading to v.

  • The first hop uses edge from u (certificate issued by u).

  • The last hop is a certificate issued by v.

  • Intermediate nodes are trusted through the previous certificate in the path.

Certificate Revocation

Certificate revocation.

• Explicitly.

  • Each node has a list of nodes that request updates for the certificates they issue.

• Implicitly.

  • Expiration time of the certificate.

  • Simple but need time synchronization of the nodes and deciding the expiration time properly.

Key revocation.

• Inform the issuers of its certificate, then the certificate is invalid.

Malicious Users

The certificate exchange mechanism allows nodes to gather virtually all certificates from G.

• Nodes cross-check user-key bindings in certificates that they hold and detect any inconsistencies (i.e., conflicting certificates).

• If they contain inconsistent user-key bindings (i.e., if both certificates contain the same username but different public keys).

• If they contain the same public key but are bound to different usernames.

Several certificate exchanges to solve conflicts, if they are needed.