Paper 2015/826

Programmable Hash Functions go Private:Constructions and Applications to (Homomorphic) Signatures with Shorter Public Keys

Dario Catalano, Dario Fiore, and Luca Nizzardo


We introduce the notion of asymmetric programmable hash functions (APHFs, for short), which adapts Programmable Hash Functions, introduced by Hofheinz and Kiltz at Crypto 2008, with two main differences. First, an APHF works over bilinear groups, and it is asymmetric in the sense that, while only {\em secretly} computable, it admits an isomorphic copy which is publicly computable. Second, in addition to the usual programmability, APHFs may have an alternative property that we call programmable pseudorandomness. In a nutshell, this property states that it is possible to embed a pseudorandom value as part of the function's output, akin to a random oracle. In spite of the apparent limitation of being only secretly computable, APHFs turn out to be surprisingly powerful objects. We show that they can be used to generically implement both regular and linearly-homomorphic signature schemes in a simple and elegant way. More importantly, when instantiating these generic constructions with our concrete realizations of APHFs, we obtain: (1) the first linearly-homomorphic signature (in the standard model) whose public key is sub-linear in both the dataset size and the dimension of the signed vectors; (2) short signatures (in the standard model) whose public key is shorter than those by Hofheinz-Jager-Kiltz from Asiacrypt 2011, and essentially the same as those by Yamada, Hannoka, Kunihiro, (CT-RSA 2012).

Available format(s)
Publication info
A major revision of an IACR publication in CRYPTO 2015
Public-Key CryptographyProgrammable Hash FunctionsDigital SignaturesHomomorphic Signatures
Contact author(s)
luca nizzardo @ imdea org
2016-05-16: last of 2 revisions
2015-08-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dario Catalano and Dario Fiore and Luca Nizzardo},
      title = {Programmable Hash Functions go Private:Constructions and Applications to (Homomorphic) Signatures with Shorter Public Keys},
      howpublished = {Cryptology ePrint Archive, Paper 2015/826},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.