We mainly follow Baecher et al. to formalize a game-based definition. 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 $\phi$ from some transformation class s.t. $y = f(\phi(x^*))$. A distinctive strengthening of our non-malleable notion is that $\phi(x^*) = x^*$ is always 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 the 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 the 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 two results establish interesting theoretical connections between non-malleability and one-wayness for functions, which extend to trapdoor functions as well, and thus resolve some open problems left by Kiltz et al. (EUROCRYPT 2010). Notably, the implication AOW $\Rightarrow$ ANM not only yields constructions of NMFs from adaptive trapdoor functions, which partially solves an open problem posed by Boldyreva et al.(ASIACRYPT 2009), but also provides key conceptual insight into addressing non-trivial copy attacks in the context of related-key attacks (RKA).
Finally, we show that NMFs lead to a simple black-box construction of continuous non-malleable key derivation functions recently proposed by Qin et al. (PKC 2015), which have proven to be very useful in achieving RKA-security for numerous cryptographic primitives.Category / Keywords: foundations / non-malleable functions, one-way functions, algebra-induced transformations, related-key attacks copy attacks, authenticated key derivation function Original Publication (with minor differences): IACR-PKC-2016 Date: received 1 Jan 2016, last revised 8 Sep 2016 Contact author: cycosmic at gmail com Available format(s): PDF | BibTeX Citation Version: 20160908:085842 (All versions of this report) Short URL: ia.cr/2015/1253 Discussion forum: Show discussion | Start new discussion