Cryptology ePrint Archive: Report 2015/1253

Non-Malleable Functions and Their Applications

Yu Chen and Baodong Qin and Jiang Zhang and Yi Deng and Sherman S. M. Chow

Abstract: We formally study non-malleable functions'' (NMFs), a general cryptographic primitive which simplifies and relaxes non-malleable one-way/hash functions'' (NMOWHFs) introduced by Boldyreva et al. (Asiacrypt 2009) and refined by Baecher et al. (CT-RSA 2010). NMFs focus on basic functions, rather than one-way/hash functions considered in the literature of NMOWHFs.

We mainly follow Baecher et al. to formalize a game-based definition for NMFs. Roughly, a function $f$ is non-malleable if given an image $y^* \leftarrow f(x^*)$ for a randomly chosen $x^*$, it is hard to output a mauled image $y$ with a transformation $\phi$ from some prefixed transformation class s.t. $y = f(\phi(x^*))$. A distinctive strengthening of our non-malleable notion is that $\phi$ such that $\phi(x^*) = x^*$ is allowed. We also consider adaptive non-malleability, which stipulates that non-malleability holds even when an inversion oracle is available.

We investigate the relations between non-malleability and one-wayness in depth. In non-adaptive setting, we show that for any achievable transformation class, non-malleability implies one-wayness for poly-to-one functions but not vise versa.In adaptive setting, we show that for most algebra-induced transformation class, adaptive non-malleability (ANM) is equivalent to adaptive one-wayness (AOW) for injective functions. These results establish theoretical connections between non-malleability and one-wayness for functions, which extend to trapdoor functions as well, and thus resolve the open problems left by Kiltz et al. (Eurocrypt 2010). We also study the relations between standard OW/NM and hinted OW/NM, where the latter notions are typically more useful in practice. Towards efficient realizations of NMFs, we give a deterministic construction from adaptive trapdoor functions and a randomized construction from all-but-one lossy functions and one-time signature. This partially solves an open problem posed by Boldyreva et al. (Asiacrypt 2009).

Finally, we explore applications of NMFs in security against related-key attacks (RKA). We first show that the implication AOW $\Rightarrow$ ANM provides key conceptual insight into addressing non-trivial copy attacks in RKA security. We then show that NMFs give rise to a generic construction of continuous non-malleable key derivation functions, which have proven to be very useful in achieving RKA security for numerous cryptographic primitives. Particularly, our construction simplifies and clarifies the construction by Qin et al. (PKC 2015).

Category / Keywords: foundations / non-malleable functions, one-way functions, algebra-induced transformations, related-key attacks copy attacks, authenticated key derivation function

Original Publication (with major differences): IACR-PKC-2016

Date: received 1 Jan 2016, last revised 21 Nov 2017

Contact author: cycosmic at gmail com

Available format(s): PDF | BibTeX Citation

Note: This version contains many improvements over the conference version in PKC 2016. In the conference version, we only focus on non-malleable deterministic functions. In this version we consider non-malleability for general functions, which could be randomized. Besides, our non-malleable notion is also strengthened by including identity transformation in the admissible transformation class. We give a deterministic realization from adaptive TDFs as well as a randomized realization from all-but-one lossy functions, one-time signature and universal hash functions. We also refined the results of relations between hinted notions and hint-free notions, and presented a generic construction of RKA-secure authenticated key derivation functions (AKDFs) from hinted NMFs in a modular and simple way. By instantiating the generic construction with our randomized NMFs, we simplifies and clarifies the construction of continuously non-malleable KDFs due to Qin et al. in PKC 2015.

Short URL: ia.cr/2015/1253

[ Cryptology ePrint archive ]