Our construction relies on a new primitive which we define and study, called $\ell$-more extractable hash functions. This notion, which may be of independent interest, guarantees that any adversary that is given access to $\ell \in \mathbb{N}$ precomputed hash values $v_{1},\dots, v_{\ell}$, and produces a new valid hash value $\tilde v$, then it must know a pre-image of $\tilde v$. This is a stronger notion that the one by Bitansky et al. (Eprint '11) and Goldwasser et al. (ITCS '12, Eprint '14), which considers adversaries that get no access to precomputed hash values prior to producing their own value. By appropriately relaxing the extractability requirement (without hurting the applicability of the primitive) we instantiate $\ell$-more extractable hash functions under the same assumptions used for the previous extractable hash functions by Bitansky et al. and Goldwasser et al. (a variant of the Knowledge of Exponent Assumption).
Category / Keywords: Non-malleable codes, hash functions, split-state model Original Publication (with minor differences): ACM Conference on Computer and Communications Security 2016 Date: received 17 Jan 2017, last revised 20 May 2018 Contact author: tselekounis at sians org Available format(s): PDF | BibTeX Citation Note: Extended abstract and minor intro changes. Version: 20180520:160437 (All versions of this report) Short URL: ia.cr/2017/040 Discussion forum: Show discussion | Start new discussion