Cryptology ePrint Archive: Report 2017/723

An Equivalence Between Attribute-Based Signatures and Homomorphic Signatures, and New Constructions for Both

Rotem Tsabary

Abstract: In Attribute-Based Signatures (ABS; first defined by Maji, Prabhakaran and Rosulek, CT-RSA 2011) an authority can generate multiple signing keys, where each key is associated with an attribute $x$. Messages are signed with respect to a constraint $f$, such that a key for $x$ can sign messages respective to $f$ only if $f(x) = 0$. The security requirements are unforgeability and key privacy (signatures should not expose the specific signing key used). In (single-hop) Homomorphic Signatures (HS; first defined by Boneh and Freeman, PKC 2011), given a signature for a data-set $x$, one can evaluate a signature for the pair $(f(x),f)$, for functions $f$. In context-hiding HS, evaluated signatures do not reveal information about the original (pre-evaluated) signatures. In this work we start by showing that these two notions are in fact equivalent. The first implication of this equivalence is a new lattice-based ABS scheme for polynomial-depth circuits, based on the HS construction of Gorbunov, Vaikuntanathan and Wichs (GVW; STOC 2015). We then construct a new ABS candidate from a worst case lattice assumption (SIS), with different parameters. Using our equivalence again, now in the opposite direction, our new ABS implies a new lattice-based HS scheme with different parameter trade-off, compared to the aforementioned GVW.

Category / Keywords: digital signatures, homomorphic signatures, attribute-based signatures, policy-based signatures, ABS, PBS, lattice techniques

Date: received 25 Jul 2017, last revised 26 Sep 2017

Contact author: rotem ts0 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20170926:104237 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]