International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 26 August 2015

Dario Catalano, Dario Fiore, Luca Nizzardo
ePrint Report ePrint Report
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 {\\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).

Expand

Additional news items may be found on the IACR news page.