Paper 2015/019

Strongly-Optimal Structure Preserving Signatures from Type II Pairings: Synthesis and Lower Bounds

Gilles Barthe, Edvard Fagerholm, Dario Fiore, Andre Scedrov, Benedikt Schmidt, and Mehdi Tibouchi


Recent work on structure-preserving signatures studies optimality of these schemes in terms of the number of group elements needed in the verification key and the signature, and the number of pairing-product equations in the verification algorithm. While the size of keys and signatures is crucial for many applications, another important aspect to consider for performance is the time it takes to verify a given signature. By far, the most expensive operation during verification is the computation of pairings. However, the concrete number of pairings that one needs to compute is not captured by the number of pairing-product equations considered in earlier work. To fill this gap, we consider the question of what is the minimal number of pairings that one needs to compute in the verification of structure-preserving signatures. First, we prove lower bounds for schemes in the Type~II setting that are secure under chosen message attacks in the generic group model, and we show that three pairings are necessary and that at most one of these pairings can be precomputed. We also extend our lower bound proof to schemes secure under random message attacks and show that in this case two pairings are still necessary. Second, we build an automated tool to search for schemes matching our lower bounds. The tool can generate automatically and exhaustively all valid structure-preserving signatures within a user-specified search space, and analyze their (bounded) security in the generic group model. Interestingly, using this tool, we find a new randomizable structure-preserving signature scheme in the Type~II setting that is optimal with respect to the lower bound on the number of pairings, and also minimal with respect to the number of group operations that have to be computed during verification.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in PKC 2015
Structure-Preserving SignaturesGeneric Group ModelBilinear GroupsFormal Methods
Contact author(s)
dario fiore @ imdea org
2015-01-12: received
Short URL
Creative Commons Attribution


      author = {Gilles Barthe and Edvard Fagerholm and Dario Fiore and Andre Scedrov and Benedikt Schmidt and Mehdi Tibouchi},
      title = {Strongly-Optimal Structure Preserving Signatures from Type II Pairings: Synthesis and Lower Bounds},
      howpublished = {Cryptology ePrint Archive, Paper 2015/019},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.