Security of computer networks normally relies on a trusted authority who is responsible for setting up the system and distributing cryptographic keys. If the trusted authority is compromised due to an attack, then the security of the entire system will be compromised. In this paper, we will look into this issue in terms of identity-based (or ID-based) cryptography. Since the introduction of identity-based (or ID-based) cryptography in 1984 by Shamir, IDbased cryptography has attracted many research due to its simplicity. However, ID-based cryptography suffers from several drawbacks, namely the requirement of having a secure channel during the key extraction and a complete trust to be placed on a trusted authority (or a so-called Private Key Generator PKG). In this paper, we overcome these problems by proposing a new key extraction algorithm that does not have these two limitations. We are only concentrating on the key extraction problem and hence, our schemes are applicable in any other ID-based scheme that has similar structure, such as Boneh-Franklin ID-based encryption scheme, etc.