We introduce the notion of asymmetric programmable hash functions (APHFs, for short), which adapts Programmable hash functions, introduced by Hofheinz and Kiltz (Crypto 2008, Springer, 2008), with two main differences. First, an APHF works over bilinear groups, and it is asymmetric in the sense that, while only 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 (Asiacrypt 2011, Springer, 2011) and essentially the same as those by Yamada et al. (CT-RSA 2012, Springer, 2012).

Homomorphic signatures with sublinear public keys via asymmetric programmable hash functions

Catalano, Dario;Fiore, Dario;
2018-01-01

Abstract

We introduce the notion of asymmetric programmable hash functions (APHFs, for short), which adapts Programmable hash functions, introduced by Hofheinz and Kiltz (Crypto 2008, Springer, 2008), with two main differences. First, an APHF works over bilinear groups, and it is asymmetric in the sense that, while only 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 (Asiacrypt 2011, Springer, 2011) and essentially the same as those by Yamada et al. (CT-RSA 2012, Springer, 2012).
2018
Digital Signatures; Homomorphic Signatures; Programmable Hash Functions; Public-Key Cryptography; Computer Science Applications1707 Computer Vision and Pattern Recognition; Applied Mathematics
File in questo prodotto:
File Dimensione Formato  
Homomorphic signatures.pdf

solo gestori archivio

Tipologia: Versione Editoriale (PDF)
Dimensione 860.97 kB
Formato Adobe PDF
860.97 kB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11769/365673
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact