Cryptology ePrint Archive: Report 2014/517

On the Connection between Leakage Tolerance and Adaptive Security

Jesper Buus Nielsen and Daniele Venturi and Angela Zottarel

Abstract: We revisit the context of leakage-tolerant interactive protocols as defined by Bitanski, Canetti and Halevi (TCC 2012). Our contributions can be summarized as follows:

\begin{enumerate} \item

For the purpose of secure message transmission, any encryption protocol with message space $\cM$ and secret key space $\cSK$ tolerating poly-logarithmic leakage on the secret state of the receiver must satisfy $|\cSK| \ge (1-\epsilon)|\cM|$, for every $0 < \epsilon \le 1$, and if $|\cSK| = |\cM|$, then the scheme must use a fresh key pair to encrypt each message.

\item \label{item:2}

More generally, we show that any $n$ party protocol tolerates leakage of $\approx\poly(\log\spar)$ bits from one party at the end of the protocol execution, \emph{if and only if} the protocol has passive adaptive security against an adaptive corruption of one party at the end of the protocol execution. This shows that as soon as a little leakage is tolerated, one needs full adaptive security.


In case more than one party can be corrupted, we get that leakage tolerance is equivalent to a weaker form of adaptivity, which we call \emph{semi-adaptivity}. Roughly, a protocol has semi-adaptive security if there exist a simulator which can simulate the internal state of corrupted parties, however, such a state is not required to be indistinguishable from a real state, only that it would have lead to the simulated communication.


All our results can be based on the solely assumption that collision-resistant function ensembles exist.

Category / Keywords: cryptographic protocols / leakage resilience, adaptive security

Original Publication (in the same form): IACR-PKC-2013

Date: received 2 Jul 2014, last revised 8 Jul 2014

Contact author: jbn at cs au dk

Available format(s): PDF | BibTeX Citation

Version: 20140708:134839 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]