* 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.
Category / Keywords: digital signatures, CDH assumption, pairing-friendly groups, RSA assumption, SIS assumption Original Publication (in the same form): A merge of this paper and http://eprint.iacr.org/2012/480 appeared in Proc. EUROCRYPT 2013, LNCS 7881, pp. 461-485, Springer 2013. Date: received 25 Mar 2013, last revised 4 Feb 2014 Contact author: florian boehl at kit edu Available format(s): PDF | BibTeX Citation Version: 20140204:161646 (All versions of this report) Short URL: ia.cr/2013/171