This paper introduces the problem of Private Certifier Intersection (PCI), which allows mutually distrusting parties to establish a trust basis for cross-validation of claims if they have one or more trust authorities (certifiers) in common. This is one of the essential requirements for verifiable presentations in Web 3.0, since it provides additional privacy without compromising on decentralization. We then design and implement two provably secure and practically efficient PCI protocols supporting validation of digital signature-based certificates.
Key Contributions
- Formalization of PCI: We introduced the problem of Private Certifier Intersection (PCI) and formalized it. We defined PCI under the Simplified Universal Composability (SUC) framework and introduced two variants:
- PCI-Any – Valid for any claim.
- PCI-All – Valid for all claims.
- MPC for Elliptic Curve Pairings: A novel secret-sharing-based MPC framework that efficiently supports elliptic curve operations, including pairings, with malicious security against a dishonest majority.
- Efficient Two-Party PCI Protocols: Design and implementation of:
- PCI-Any-DC (ECDSA-based) – Supports widely used ECDSA certificates while optimizing expensive elliptic curve operations outside the MPC protocol.
- PCI-All (BLS-based) – Leverages BLS signature aggregation to efficiently validate certificates over all claims with minimal elliptic curve pairing operations.
- Optimized Implementation: We extended MP-SPDZ with OpenSSL and RELIC libraries to implement PCI protocols efficiently using a black-box approach for elliptic curve operations.
- Performance Evaluation and Real-World Feasibility: We benchmarked the protocols in both LAN and WAN settings, placing parties in three geographic regions across two continents. In an intercontinental WAN setup, the PCI-Any-DC and PCI-All protocols execute in under a minute for input sets of size 40. The evaluation highlights the scalability and efficiency of the protocols, demonstrating their applicability to real-world decentralized trust scenarios, including Web 3.0 and verifiable credentials.
Publications
- Bishakh Chandra Ghosh, Sikhar Patranabis, Dhinakaran Vinayagamurthy, Venkatraman Ramakrishna, Krishnasuri Narayanam, and Sandip Chakraborty. "Private certifier intersection." NDSS, 2023.
- Bishakh Chandra Ghosh, Dhinakaran Vinayagamurthy, Venkatraman Ramakrishna, Krishnasuri Narayanam, and Sandip Chakraborty. "Privacy-Preserving Negotiation of Common Trust Anchors Across Blockchain Networks." In 2022 IEEE International Conference on Blockchain and Cryptocurrency (ICBC), pp. 1-5. IEEE, 2022.