IACR News item: 26 August 2015
Dario Catalano, Dario Fiore, Luca Nizzardo
ePrint Report(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 {\\em 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 {\\em first} linearly-homomorphic signature (in the standard
model) whose public key is {\\em 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).
Additional news items may be found on the IACR news page.