Paper 2022/1302

Private Certifier Intersection

Bishakh Chandra Ghosh, Indian Institute of Technology Kharagpur
Sikhar Patranabis, IBM Research - India
Dhinakaran Vinayagamurthy, IBM Research - India
Venkatraman Ramakrishna, IBM Research - India
Krishnasuri Narayanam, IBM Research - India
Sandip Chakraborty, Indian Institute of Technology Kharagpur

We initiate the study 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. A PCI protocol allows two or more parties holding certificates to identify a common set of certifiers while additionally validating the certificates issued by such certifiers, without leaking any information about the certifiers not in the output intersection. In this paper, we formally define the notion of multi-party PCI in the Simplified-UC framework for two different settings depending on whether certificates are required for any of the claims (called PCI-Any) or all of the claims (called PCI-All). We then design and implement two provably secure and practically efficient PCI protocols supporting validation of digital signature-based certificates: a PCI-Any protocol for ECDSA-based certificates and a PCI-All protocol for BLS-based certificates. The technical centerpiece of our proposals is the first secretsharing-based MPC framework supporting efficient computation of elliptic curve-based arithmetic operations, including elliptic curve pairings, in a black-box way. We implement this framework by building on top of the well-known MP-SPDZ library using OpenSSL and RELIC for elliptic curve operations, and use this implementation to benchmark our proposed PCI protocols in the LAN and WAN settings. In an intercontinental WAN setup with parties located in different continents, our protocols execute in less than a minute on input sets of size 40, which demonstrates the practicality of our proposed solutions.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Network and Distributed System Security Symposium 2023 (NDSS 2023)
identity blockchain web3.0 mpc
Contact author(s)
ghoshbishakh @ gmail com
sikhar patranabis @ ibm com
dvinaya1 @ in ibm com
vramakr2 @ in ibm com
knaraya3 @ in ibm com
sandipc @ cse iitkgp ac in
2022-09-30: approved
2022-09-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Bishakh Chandra Ghosh and Sikhar Patranabis and Dhinakaran Vinayagamurthy and Venkatraman Ramakrishna and Krishnasuri Narayanam and Sandip Chakraborty},
      title = {Private Certifier Intersection},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1302},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.