This paper concerns the barriers to interoperability that exist between the X.509 and EDIFACT Public Key Infrastructures (PKI), and proposes a method to overcome them. The solution lies in the DEDICA1 (Directory based EDI Certificate Access and management) TELEMATIC Project, funded by the European Union. The main objective of this project is to define and provide means to make these two infrastructures inter-operable without increasing the amount of information that they have to manage. The proposed solution is a gateway tool interconnecting both PKIs. The main purpose of this gateway is to act as a TTP that “translates” certificates issued in one PKI to the other’s format, and then signs the translation to make it a new certificate. The gateway will in fact act as a proxy CA for the CAs of the other PKI.