Paper 2014/590

Automated algebraic analysis of structure-preserving signature schemes

Joeri de Ruiter


Structure-preserving signature schemes can be very useful in the construction of new cryptographic operations like blind signatures. Recently several of these schemes have been proposed. The security of signature-preserving signature schemes is still proved by hand, which can be a laborious task. One of the ways to prove security of these schemes algebraic analysis can be used. We present an approach to perform this analysis and the first tool, CheckSPS, that can do an algebraic security analysis of these schemes, using SMT solvers as backend. This can help in constructing new schemes and analyse existing schemes. Our tool can handle all the common security objectives for signature schemes, i.e. existential unforgeability and strong existential unforgeability, and all the common capabilities for adversaries, i.e. random message attacks, non-adaptive chosen message attacks and adaptive chosen message attacks. The tool is sound, so if an attack is found it is actually possible to construct a forged signature.

Available format(s)
Publication info
Preprint. MINOR revision.
structure-preserving signature schemesautomated analysisalgebraic analysis
Contact author(s)
joeri @ cs ru nl
2014-07-31: received
Short URL
Creative Commons Attribution


      author = {Joeri de Ruiter},
      title = {Automated algebraic analysis of structure-preserving signature schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2014/590},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.