Paper 2020/736

Combining Forward-Security and Leakage-Resilience, Revisited

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


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.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Continual LeakageForward SecurityDeterministic UpdateNon-Interactive Key ExchangePublic Key Encryption
Contact author(s)
suvradip1111 @ gmail com
hk2617 @ nyu edu
amoneill @ gmail com
prangan55 @ gmail com
2022-05-03: last of 3 revisions
2020-06-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Suvradip Chakraborty and Harish Karthikeyan and Adam O'Neill and C.  Pandu Rangan},
      title = {Combining Forward-Security and Leakage-Resilience, Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2020/736},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.