Non-Malleable Functions and their Applications

Yu Chen; Baodong Qin; Jiang ZhangYi DengSherman 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. (in: Advances in cryptology—ASIACRYPT 2009, pp 524–541, 2009) and refined by Baecher et al. (in: CT-RSA 2011, pp 268–283, 2011). NMFs focus on basic functions, rather than one-way/hash functions considered in the literature of NMOWHFs. We formalize a game-based definition for NMFs. Roughly, a function f is non-malleable if given an image y?←f(x?)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$y^* leftarrow f(x^*)$$end{document} for a randomly chosen x?documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$x^*$$end{document}, it is hard to output a value y together with a transformation ?documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$phi $$end{document} from some prefixed transformation class such that y is an image of ?(x?)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$phi (x^*)$$end{document} under f. Our non-malleable notion is strong in the sense that only trivial copy solution (id,y?)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$(mathsf {id}, y^*)$$end{document} is forbidden, where iddocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} begin{document}$$mathsf {id}$$end{document} is the identity transformation. We also consider the adaptive notion, 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 non-malleability generally implies one-wayness for poly-to-one functions but not vice versa. In the adaptive setting, we show that for most algebra-induced transformation classes, 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 and extend to trapdoor functions as well, resolving the open problems left by Kiltz et al. (in: Advances in cryptology—EUROCRYPT 2010, pp 673–692, 2010). We also study the relations between standard OW/NM and hinting OW/NM, where the latter notions are typically more useful in practice. Toward efficient realizations of NMFs, we give a deterministic construction from adaptive trapdoor functions as well as a randomized construction from all-but-one lossy functions and one-time signature. This partially solves an open problem posed by Boldyreva et al. (in: Advances in cryptology—ASIACRYPT 2009, pp 524–541, 2009). Finally, we explore applications of NMFs in security against related-key attacks (RKA). We first show that, somewhat surprisingly, the implication AOW ?documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setl

Non-Malleable Functions and their Applications

摘要

著录项

相关主题

期刊订阅