Paper 2020/736

Combining Forward-Security and Leakage-Resilience, Revisited

Suvradip Chakraborty, Harish Karthikeyan, Adam O'Neill, and C. Pandu Rangan

Abstract

We revisit the combining of forward and leakage resilience, the study of which was initiated by Bellare \emph{et al.} (CANS 2017). Bellare \emph{et al.} combine forward security with continual leakage resilience, dubbed FS+CL. In particular, they construct a FS+CL public-key encryption (PKE) and signatures, but with various shortcomings in terms of leakage rate and assumptions. Our first result significantly improve on Bellare \emph{et al.}'s FS+CL PKE scheme, building a FS+CL PKE from any continuous leakage-resilient binary-tree encryption scheme (in contrast Bellare \emph{et al.} required extractable witness encryption which is a suspect assumption). Our construction preserves the leakage rate and hence yield FS+CL PKE with optimal leakage rate from standard assumption. \ind We next explore alternative combinations of forward security and leakage resilience. As argued by Dziembowski \emph{et al.} (CRYPTO 2011), it is desirable to have a model allowing a deterministic key-update procedure, which FS+CL does not. We put forth a combination of forward security with \emph{entropy bounded} leakage (FS+EBL) that allows such key updates. Then we construct FS+EBL non-interactive key exchange (NIKE) based on indistinguishability obfuscation ($\iO$), and DDH or LWE. Additionally, to make the public keys constant size, we rely on the Superfluous Padding Assumption (SuPA) of Brzuska and Mittelbach (Eprint 2015). Crucially, we \emph{do not} use auxiliary information in SuPA. SuPA notwithstanding, our scheme improves on the recent bounded leakage-resilient NIKE of Li \emph{et al.} (CRYPTO 2020) and also the FS NIKE construction of Pointcheval and Sanders (SCN 2014) from generic multilinear maps. Finally, we argue that using \emph{computational entropy} (FS+CEBL) is more compelling in the context of deterministic updates. We pose achieving a FS+CEBL NIKE as an important open problem.