Paper 2013/171

Confined Guessing: New Signatures From Standard Assumptions

Florian Böhl, Dennis Hofheinz, Tibor Jager, Jessica Koch, and Christoph Striecks


We put forward a new technique to construct very efficient and compact signature schemes. Our technique combines several instances of an only mildly secure signature scheme to obtain a fully secure scheme. Since the mild security notion we require is much easier to achieve than full security, we can combine our strategy with existing techniques to obtain a number of interesting new (stateless and fully secure) signature schemes. Concretely, we get: * A scheme based on the computational Diffie-Hellman (CDH) assumption in pairing-friendly groups. Signatures contain O(1) and verification keys O(log(k)) group elements, where k is the security parameter. Our scheme is the first CDH-based scheme with such compact verification keys. * A scheme based on the (non-strong) RSA assumption in which both signatures and verification keys contain O(1) group elements. Our scheme is significantly more efficient than existing RSA-based schemes. * A scheme based on the Short Integer Solutions (SIS) assumption. Signatures contain O(log(k) m) and verification keys O(n m) Z_p-elements, where p may be polynomial in k, and n, m denote the usual SIS matrix dimensions. Compared to state-of-the-art SIS-based schemes, this gives very small verification keys, at the price of slightly larger signatures. In all cases, the involved constants are small, and the arising schemes provide significant improvements upon state-of-the-art schemes. The only price we pay is a rather large (polynomial) loss in the security reduction. However, this loss can be significantly reduced at the cost of an additive term in signature and verification key size.

Available format(s)
Publication info
Published elsewhere. A merge of this paper and appeared in Proc. EUROCRYPT 2013, LNCS 7881, pp. 461-485, Springer 2013.
digital signaturesCDH assumptionpairing-friendly groupsRSA assumptionSIS assumption
Contact author(s)
florian boehl @ kit edu
2014-02-04: revised
2013-03-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Florian Böhl and Dennis Hofheinz and Tibor Jager and Jessica Koch and Christoph Striecks},
      title = {Confined Guessing: New Signatures From Standard Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2013/171},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.