Private Certifier Intersection: Finding common certificate authorities without compromising privacy

In the traditional web, users are dependent on a limited set of identity and service providers and public certificate authorities (CAs) to initiate trusted interactions. Recent trends in decentralization towards Web3 aim to replace dependencies on centralized service providers like these with a self-sovereign ability to create, update, and selectively share identity records. The aim is to enable entities to prove properties (or claims) about themselves without relying on centralized or federated identity providers, or a canonical trusted set of CAs. This requires a suitable mechanism for a trust-based negotiation between the prover and the verifier. In situations where the prover and the verifier are mutually distrusting, such a mechanism should ideally be privacy-preserving, in the sense that it should allow the prover to prove its claims to the verifier while revealing as little information as possible about its private attributes and associations.

It turns out that such a mechanism is especially useful in the context of blockchain interoperability – one of the most important and widely researched areas in the space of blockchains and distributed ledger technologies (DLTs).

Interoperability in the context of blockchains refers to the ability of two blockchain networks to exchange data and assets with each other. Over the past four years, IBM Research has played a pivotal role in the design and development of the blockchain interoperability project Weaver (and its eventual merger into the Hyperledger Cacti project). Weaver is a framework, with a family of protocols, to enable interoperation for data sharing and asset movements among independent networks built on similar or different distributed ledger technologies (DLTs) in a manner that preserves the core blockchain tenets of decentralization and security.

A key design philosophy underlying Weaver is the assumption that networks are, and wish to, remain self-sovereign and govern themselves, while interacting with other networks in a secure and controllable manner. The Weaver system is designed to ensure that these goals are met while avoiding trusted mediators and maintaining minimal dependence on external infrastructure. As an additional goal, networks may need and want to maintain their respective members’ privacy from others. For example, several prominent blockchain and DLT networks are built for consortia of enterprises that don’t necessarily trust each other. Any privacy loss resulting from interoperation between two mutually distrusting blockchain networks could result in loss of competitive advantage. This naturally motivates the need for a privacy-preserving trust basis negotiation mechanism. Unfortunately, state-of-the-art mechanisms for blockchain interoperability fall short of such privacy guarantees, which was the primary motivation behind our work.

We proposed, designed and prototyped a family of protocols called Private Certifier Intersection (PCI) that allows mutually distrusting parties to establish a trust basis for cross-validation of claims if they have one or more trust authorities (or certifiers) in common. PCI enables additional privacy in applications such as blockchain interoperability without compromising on decentralization. Our research led to a paper in collaboration with  Bishakh Ghosh and Sandip Chakraborty at the Department of Computer Science and Engineering, Indian Institute of Technology Kharagpur, which was accepted to the 2023 Watch our presentation on Private Certifier Intersection on March 1.Network and Distributed System Security Symposium (NDSS).

Let’s sketch out how the PCI might be used with a simple example. Suppose two companies, let’s call them S₁ and S₂, wish to obtain and offer services to each other, a common scenario in the supply chain world consisting of suppliers, distributors, brokers, and retailers, not to mention financial institutions and carriers. One may get assets or information from another in exchange for payment or other kinds of assets or information. Yet, any such deal, let alone a long-term business relationship, must begin with a baseline level of trust. Unless the two companies are subsidiaries of a common higher authority or have a completely trusted intermediary (these are unlikely and infeasible in global cross-border scenarios), there will always be a concern about the counterparty reneging on a deal or supplying spurious resources, or fake information. After first contact, you can imagine the conversation going as illustrated below.

As you can see in the latter part of the conversation, there is a criteria one can use to determine whether to associate and deal with another: “Does somebody who trusts us also trust them?” What this means is that if there exist common authorities that are willing to endorse an entity, either in a general way or for specific attributes, that significantly decreases the likelihood of that party reneging on a deal or committing fraud.

This scenario occurs in both the physical and the online world today. In the latter, services or agents acting on behalf of real-world entities can negotiate using automated protocols and APIs. With AI advances, you can imagine the need for such automated deals between AI proxies for real-world entities growing more salient. The technology for secure certification has existed for several decades in the form of public key infrastructure (PKI) infrastructure, and prominently, X.509 certificates, which embody endorsements by a certificate authority (CA) on an entity or another certificate authority (thereby creating a hierarchy of endorsements).

Now this might seem like an easy problem to handle. S₁ asks S₂ for its list of CAs, and similarly S₂ asks S₁ for its list of CAs. They compute the intersection, or the set of common CAs, select one or more certificates attested by those CAs, and validate the digital signatures within before proceeding with their interaction. But this process carries a different set of hazards, impacting the entities’ privacy. As an example, let us assume that S₁ and S₂ hold certificates attested by the following authorities:

• S₁: {Financial Institution A, Political Organization M, Scientific Organization N, Governmental Agency B}
• S₂: {Financial Institution D, Governmental Agency B, Scientific Organization N, Consortium C}

It is easy to observe that the two have Scientific Organization N and Governmental Agency B as common CAs. If either or both were revealed to S₁ and S₂, they could strike a deal and build a business relationship, as illustrated below.

But what if a different CA were revealed before any of these common ones? If the counterparty does not trust that CA or holds a negative opinion of that CA, the deal may fall through as illustrated below.

It is clearly not in S₁’s interest to reveal that it is certified by M unless it knows that S₂ also trusts M. Further, S₂ may leak this information to other parties, negatively impacting S₁’s reputation in many circles.

Another potential downside of, say S₂, revealing a non-common CA is that it may expose confidential information to S₁, resulting in the latter gaining leverage or competitive advantage over the former, as illustrated below.

In summary, what this example reveals is that counterparties that wish to make deals have a genuine interest or need for both the following simultaneously:

• Resource/information need: Revealing one or more common CAs that certify both.
• Privacy need: Hiding every CA that certifies only one counterparty.

The Private Certifier Intersection Problem

We can generalize the above story to describe the PCI problem in more generic and formal terms using a representative example. Consider two parties P₁ and P₂, each possessing certificates attested by particular CAs as illustrated below.

There are certifiers in common that are highlighted in green while the remaining certifiers are highlighted in red. The dual goal of PCI is the following:

• Output: P₁→{Cert4,Cert5,Cert6},P₂→{Cert7,Cert8,Cert9} (Note: implicitly the common CAs {f,b,e} are also revealed.)
• Do not leak: P₁→{Cert1,Cert2,Cert3},P₂→{Cert10,Cert11,Cert12,Cert13}

The PCI model and objective, represented by this example, is illustrated in the figure below.

Why not use Private Set Intersection (PSI)?

A classic problem that has been researched by the cryptography community over the past couple of decades is one where two parties, each possessing a set of elements, must compute the intersection of those sets without leaking the elements in the respective sets that don’t lie in the intersection. Called PSI, or Private Set Intersection, this mechanism has been used in many real-world applications, notably by the Apple PSI system ¹ as part of a larger system for detecting CSAM. PSI can be illustrated using a representative example below.

Superficially, PSI seems to resemble PCI. Can PCI be an extrapolation of PSI, or use PSI as a black box building block? Let us consider the following process, referring to the PCI example diagram presented earlier:

• P₁ and P₂ compute their respective CA sets (the box at the bottom).
• These sets are input to PSI, which computes the intersection, following which the certificates can be shared between the parties for signature validations.

It is easy to spot the flaw in this process. There is no guarantee that either P₁ or P₂ will honestly provide an accurate set of CAs as input to PSI, and PSI has no way of determining whether a given CA specified by either party actually issued a certificate to that party. If either party is malicious, it can launch a universal set attack using this process, whereby it supplies a large (possibly universal) set of CAs despite not possessing certificates issued by all those CAs. The counterparty, if it remains honest, will then inadvertently reveal its entire set of CAs to the other, because the intersection of a given set with a universal set is simply that set. Any valid PCI procedure must be able to prevent either party from falsely claiming to possess a certificate from a given CA. Therefore, PCI cannot be a simple extrapolation or wrapper over PSI.

A PCI solution

We encountered the PCI problem, and tried to find a solution, in the context of a long-term blockchain interoperability project. One aspect of this project involved decentralized cross-blockchain-network identity management, which was researched in collaboration with IIT Kharagpur.

The solution, as it turned out, could be built on a mechanism that has gained salience in the past few years since blockchains started getting popular: Multi-Party Computation (MPC) ². Specifically, we were able to solve PCI by devising an MPC extension for elliptic curve pairings, with the key innovation being efficient secret-sharing. We identified the MP-SPDZ library ³ as a suitable target for experimentation and implemented our new techniques by extending it. For evaluation and comparison purposes, we used ECDSA and BLS signature schemes, both of which are popular in the blockchain and distributed ledger community, which is where we envision that the main applications of PCI will lie.

Details on our solution mechanisms, including a formal definition of PCI in the Simplified Universal Composability (SUC) framework ⁴ can be found in the full paper. The paper also lists a taxonomy of different varieties of PCI and presents detailed solutions for particular <variety, signature scheme> combinations. These varieties are useful to consider when the set of claims made within the certificates by the respective CAs also hold importance, and where we can devise different techniques to produce different output sets and control leakage of claim information. The table below illustrates the PCI protocol variants we have implemented and experimented with.

We found the PCI-All protocol for BLS to be particularly efficient thanks to signature aggregation schemes. For details as well as security analyses, performance measurement results, and extensions PCI from 2-party to multi-party, read the full paper.

Application in Blockchain and DLT Interoperability

Interoperability is one of the most important research areas in the blockchain and distributed ledger systems world, where both open and permissioned networks, as well as DLTs built on diverse technology stacks, co-exist without possessing secure means of sharing ledger data (with authenticity proof), exchanging digital assets, and transferring digital assets, across network boundaries. This can be visualized in the “Data Plane” box in the figure below. Especially for networks that are permissioned, some mechanism for cross-network identity syncing must exist in order to establish a trust basis, and the “Identity Plane” box illustrates such mechanisms in conjunction with decentralized identity registries.

The PCI protocols can serve a key purpose in the Identity Plane for cross-network interoperability, allowing networks to identity common Certificate Authorities (or, in the future, Verifiable Credential Issuers) without revealing the ones they wish and need to keep private. As several prominent blockchain and DLT networks are built for consortia of enterprises that don’t necessarily trust each other, the downside of losing competitive advantage in the market upon privacy loss makes PCI a very compelling solution.

For more information about the blockchain interoperability project that inspired the quest for PCI, visit the Weaver and Hyperledger Cacti project repositories, and check out the blog post that describes the Cacti vision.