Interoperabilität kann definiert werden als die Fähigkeit, die eine verlässliche Kommunikation zwischen Produkten unterschiedlicher Hersteller ermöglicht, ohne dass proprietäre Schnittstellen die Daten konvertieren. Der Erzeuger einer signierten oder verschlüsselten E-Mail braucht daher die Komponenten der Kommunikationspartner nicht zu kennen, um für sie verständliche Datenformate zu erzeugen. Die Schnittstellen (Protokolle und Formate) werden von Internet-Standards (RFCs) definiert, die den Programmierern zur Verfügung stehen. Die Bundesregierung formuliert diesen Zusammenhang in ihrem Beschluss vom 16.01.2002 als horizontale Interoperabilität.

Trotz umfangreicher Normenwerke treten Interoperabilitäsprobleme bei den Kommunikationspartnern auf. Nachrichten können nicht dargestellt werden und Verifikationsprozesse schlagen fehl.

Während des Projekts SPHINX wurden zur Qualitätssicherung Tests auf Interoperabilität durchgeführt. Durch diese Tests wurde sicher gestellt, dass die in einem europaweit geführten Feldversuch eingesetzten PKI-Produkte und Trustcenter zueinander interoperabel waren. Durch den Aufbau einer PKI für die öffentliche Verwaltung und der damit beginnenden großflächigen Ausstattung der Bundes- und Länderverwaltungen mit PKI-Produkten zur Absicherung der E-Mail-Kommunikation waren weitere Funktionalitäten und damit verbundene Interoperabilitätsprobleme zu lösen. Um sicherzustellen, dass nur interoperable Produkte zum Einsatz kommen, wurden die Interoperabilitätstests ab Dezember 2001 fortgeführt.

Mit den Interoperabilitätstests wird durch das Bundesministerium des Innern empfohlen, nur erfolgreich geprüfte Produkte für den Einsatz in der Bundesverwaltung zu beschaffen. Die Tests werden im Auftrag des BSI einmal pro Quartal vom Testlabor des Unternehmens Atos Origin GmbH (ehemals: SchlumbergerSema Competence Center Informatik GmbH) in Meppen durchgeführt. Die Basis der Tests bildet die Testspezifikation