Moreover, our schemes can be flexibly extended to the Bounded-Retrieval Model, allowing us to tolerate very large absolute amount of adversarial leakage $\ell$ (potentially many gigabytes of information), only by increasing the size of the secret key and without any other loss of efficiency in communication or computation. Concretely, given any leakage parameter $\ell$, security parameter $\lambda$, and any desired fraction $0< \delta \leq 1$, our schemes have the following properties:
(1) Secret key size is $\ell(1+\delta)+O(\lambda)$. In particular, the attacker can learn an approximately $(1-\delta)$ fraction of the secret key.
(2) Public key size is $O(\lambda)$, and independent of $\ell$.
(3) Communication complexity is $O(\lambda/\delta)$, and independent of $\ell$.
(4) All computation reads at most $O(\lambda/\delta^2)$ locations of the secret key, independently of $\ell$.
Lastly, we show that our schemes allow for repeated ``invisible updates'' of the secret key, allowing us to tolerate up to $\ell$ bits of leakage in between any two updates, and an unlimited amount of leakage overall. These updates require that the parties can securely store a short ``master update key'' (e.g. on a separate secure device protected against leakage), which is only used for updates and not during protocol execution. The updates are invisible in the sense that a party can update its secret key at any point in time, without modifying the public key or notifying the other users.
Category / Keywords: public-key cryptography / Side-Channel Attacks, Bounded Retrieval Model, Key Leakage Date: received 6 Apr 2009, last revised 20 May 2009 Contact author: wichs at cs nyu edu Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20090520:083606 (All versions of this report) Short URL: ia.cr/2009/160 Discussion forum: Show discussion | Start new discussion