Paper 2019/1391

Are These Pairing Elements Correct? Automated Verification and Applications

Susan Hohenberger and Satyanarayana Vusirikala


Using a set of pairing product equations (PPEs) to verify the correctness of an untrusted set of pairing elements with respect to another set of trusted elements has numerous cryptographic applications. These include the design of basic and structure-preserving signature schemes, building oblivious transfer schemes from “blind” IBE, finding new verifiable random functions and keeping the IBE/ABE authority “accountable” to the user. A natural question to ask is: are all trusted-untrusted pairing element groups in the literature PPE testable? We provide original observations demonstrating that the answer is no, and moreover, it can be non-trivial to determine whether or not there exists a set of PPEs that can verify some pairing elements with respect to others. Many IBE schemes have PPE-testable private keys (with respect to the public parameters), while others, such as those based on dual-system encryption, provably do not. To aid those wishing to use PPE-based element verification in their cryptosystems, we devised rules to systematically search for a set of PPEs that can verify untrusted elements with respect to a set of trusted elements. We prove the correctness of each rule and combine them into a main searching algorithm for which we also prove correctness. We implemented this algorithm in a new software tool, called AutoPPE. Tested on over two dozen case studies, AutoPPE found a set of PPEs (on schemes where they exist) usually in just a matter of seconds. This work represents an important step towards the larger goal of improving the speed and accuracy of pairing-based cryptographic design via computer automation.

Available format(s)
Publication info
Published elsewhere. Minor revision. ACM CCS 2019
formal analysisautomating crypto
Contact author(s)
susan @ cs jhu edu
satya @ cs utexas edu
2019-12-04: received
Short URL
Creative Commons Attribution


      author = {Susan Hohenberger and Satyanarayana Vusirikala},
      title = {Are These Pairing Elements Correct? Automated Verification and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1391},
      year = {2019},
      doi = {10.1145/3319535.3339808},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.