\begin{itemize} \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
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. \end{itemize}
All our results can be based on the only assumption that collision-resistant function ensembles exist.
Category / Keywords: cryptographic protocols / leakage resilience, adaptive security Original Publication (with minor differences): IACR-PKC-2013 Date: received 2 Jul 2014, last revised 12 Mar 2015 Contact author: jbn at cs au dk Available format(s): PDF | BibTeX Citation Note: Slightly revised version. Updated bibliography. Version: 20150312:095326 (All versions of this report) Short URL: ia.cr/2014/517 Discussion forum: Show discussion | Start new discussion