Thursday, May 20, 2010

Self- Organized Public Key Management


A self-organized approach for public key certificates, which is similar to PGP , but unlike PGP it does not depend on the certificate directories for the distribution of certificates. In this key management service the need for the existence of a centralized certification authority is omitted and every node in the network is responsible for generating their keys, issuing, storing and distributing public key certificates. The key management scheme is said to be self-organized, as it does not require any external configuration or management.

The relationship between users of the system is denoted by a directed trust graph G (V, E), where the vertices represent the nodes and an edge E denotes a public key certificate.

The main working principle is, each user maintains a local repository, which contains a limited number of certificates selected by the users based on an algorithm. When a user u wants to verify the public key certificates of another user v, then they merge the local certificate repositories and user u tries to find a certificate chain to user v in the merged repository.

Following sub-sections discusses and analyses the various operations of the self organized key management scheme:

Generating Keys, Each user of the system generates its own public key and corresponding private key locally.

Issuing Certificates, Each user in the system has the capability to issue a public key certificate. Suppose user u gets a public key of another user v through a secure channel or from another user whom user u trusts. If a user u believes that a public key Kpub belongs to a user v, then it can issue a public key certificate for v, which is signed by u. The system assumes that users are honest and do not issue false certificates. So, if user u issues a public key certificate for user v, then there must exist a directed edge form vertex u to vertex v in the trust graph G (V, E)

Storing Certificates, As mentioned earlier, each user of the system maintains a local repository where it stores the public key certificates. The local repository consists of two parts; first, each user stores the certificates that it issues and the certificates issued to it. This is necessary, as in this process all the certificates that have been issued is stored at least once. Along with these each user stores a set of other certificates issued by other users. The later set of certificates is selected using a common algorithm. In terms of the system model, each user u selects a sub graph of the trust graph G (V, E) which consists of the outgoing edges and corresponding vertices from user u and an additional set of selected edges and corresponding vertices.


This key management scheme that does not require any existing infrastructure and nodes in the networks are responsible for issuing, distributing and storing certificates in a distributed manner. The key management service works like PGP, but instead of using separate directories, it uses the local repositories maintained by each user. Uses of public key cryptography ensure confidentiality and a decentralized approach means that there is no single point of failure. The proposal does not discuss about the scalability issue.

Some of the key points need to be mentioned regarding the efficiency of the proposed scheme:
• The proposed key management service lacks the certificate revocation mechanism, which is an important issue that should be considered.

• The authenticity of a received public key is achieved based on the probability of finding a certificate chain in the merged directory. Though, it was shown that the probability is always high if each user uses the same algorithm. Even though, all nodes may not be honest and issue false certificates. So, there is a risk using this type of model in applications where security and accountability is a prime issue.

• As discusses earlier that the proposed scheme is similar to PGP. Like PGP It has a problem in the initial stages of its execution before the number of certificates issued reaches to a certain number consider the scenario shown in fig, where a dashed line represent only friendship and a directed line represents a certificate. Now, if node 9 wants to communicate securely with node 1, it has to find a chain of certificate in the graph. But, as it is the initial stage and only nodes 2,8 and 9 have issued a certificate. So, node 9 has to wait for some other nodes to issue certificates to find a certificate chain between node 1 and 9

Key Distribution in Cluster Formation

Asymmetric decentralize approaches for key distribution

As key distribution based on a centralized key management server (i.e., Certification Authority) can leads the whole system to a single point of failure, the idea to share the :ask of key distribution in a distributed manner was attempted. The two schemes in the following sub sections, one is based on a partially distributed CA and another scheme uses a fully distributed certification authority (CA).
Partially distributed certification authority


A decentralized approach based on a public key infrastructure for key management where task of the CA is divided to a subset of nodes in the networks. Threshold Cryptography is used for establishing trust among the set of servers and the proposed key management service also uses share refreshing to achieve proactive security.


The task of the key management service is distributed over a certain number of nodes in the network called servers. The service as a whole has a service private key (skpriv) / public key (skpub). All the nodes in the system know the public key (skpub) of the service and trust any certificates that have been signed with the corresponding private key (skpriv). The normal nodes (i.e., client nodes), can requests to the key management service for other client's public key or for an update of its own public key. Fig shows the architecture of the key management services.

The n servers that are chosen arbitrarily, configured with an (n, H 1) threshold cryptographic scheme, where (n3t+ 1) and t is the maximum number of servers that can be compromised within a given period of time. Each server has its own public (Ki) / private key (ki) pair and knows the public key of all other servers. The private key of the service skpriv is divided into n shares (sl, s2, s3, s4 ..., sn) where each of the n servers gets one share each.


The key management scheme discussed ensures confidentiality as it uses threshold cryptography and the task of the CA is shared among some nodes. So, there is no single point of failure and authenticated nodes get the service done as and when requested. Thus, it ensures availability and by using share refreshing it keeps the shares of the secret key fresh. The key management service can changes its configuration to changing situations, which helps ensuring the scalability requirement.

Though the management technique is concrete and good one for distributing the task of a CA to a set of servers, it still have some lacking while implementing in a mobile ad hoc network environment from an efficiency point of view:

• The scheme do not addresses the issue of certificate revocation mechanism, which is very important for a service implementing public key infrastructure.

• It requires that all the server store certificates of all the nodes in the network. In that case, a new certificate is propagated to all the servers. Consider a segmentation of the network, and then a synchronization mechanism between the servers will be required.

• The use of public key and threshold cryptography requires a lot of computational tasks, which could consume the energies of small Energy constrained devices used in ad hoc networks.

• The availability of the key management service depends on an Assumption that in a given time at most t number of servers can be compromised, where t is the threshold parameter. So, higher the t is chosen, higher the security.

• The key management service requires that a given set of nodes do some specific task at a given time, which is suitable for a military environment. In a normal environment nodes may not behave in a pre- defined way