Cryptology ePrint Archive: Report 2020/736

Forward-Security Under Continual Leakage with Deterministic Key Updates

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

Abstract: In the setting of continual-leakage (CL) --- Brakerski \emph{et al.}, Dodis \emph{et al.}, FOCS 2010 --- the secret key of a cryptographic scheme evolves according to time periods; the adversary gets some bounded leakage function of its choice applied to the current secret key in each time period. This model necessitates a \emph{randomized} key update procedure, as otherwise the adversary can leak a future secret key bit by bit over time. Unfortunately, this is a major source of difficulty, for example in handling leakage on updates. On the other hand, the above reason why a randomized key update procedure is required is arguably unsatisfying, since in practice a leakage function will not continually compute the update procedure and leak a future key in whole. Our goal is to provide a general security model for continual leakage with deterministic key updates, and constructions that improve in various respects on prior work. In fact, as described below we incorporate forward security into our model as well. For our basic security model we take an \emph{entropy-based} approach, leading to a model we call \emph{entropic continual leakage} (ECL). In the ECL model, the adversary is allowed to make a limited total number of leakage queries that, as in CL, can depend arbitrarily on other keys (in particular, we do not completely bar the leakage function from ``computing the update procedure''), but an \emph{unlimited} total number of what we call ``local'' leakage queries. The latter does not decrease computational entropy of other keys. Hence, in some sense, the local leakage queries do not compute the key update procedure. Another major benefit of allowing deterministic key updates is that we can more readily incorporate forward security (FS) in our constructions, recently pointed out by Bellare \emph{et al.} (CANS 2017) to be an important security hedge in this context. This is because techniques for achieving FS often require deterministic updates. Accordingly, we also introduce the FS+ECL model (which is in fact incomparable to the CL model). We target this enhanced model for our constructions and provide constructions of public-key encryption (based on non-interactive key exchange) and digital signatures (based on identification schemes) that improve over the assumptions or leakage rates of the FS+CL schemes of Bellare \emph{et al.}. These results demonstrate the feasibility of improved constructions in our more realistic model. Finally, as a result of independent interest, we present a public-key encryption scheme in the FS+CL model (with randomized update) that improves on both the assumptions and leakage rates compared to the scheme of Bellare \emph{et al}.

Category / Keywords: public-key cryptography / Continual Leakage, Forward Security, Deterministic Update, Non-Interactive Key Exchange, Encryption, Signatures, Identification

Date: received 17 Jun 2020

Contact author: suvradip1111 at gmail com,hk2617@nyu edu,amoneill@gmail com,prangan55@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200618:154838 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]