Cryptology ePrint Archive: Report 2012/367
On Continual Leakage of Discrete Log Representations
Shweta Agrawal and Yevgeniy Dodis and Vinod Vaikuntanathan and Daniel Wichs
Abstract: Let $\G$ be a group of prime order $q$, and let $g_1,\ldots,g_n$ be
random elements of $\G$. We say that a vector $\vecx =
(x_1,\ldots,x_n)\in \Z_q^n$ is a {\em discrete log representation} of
some some element $y\in\G$ (with respect to $g_1,\ldots,g_n$) if
$g_1^{x_1}\cdots g_n^{x_n} = y$. Any element $y$ has many discrete log
representations, forming an affine subspace of $\Z_q^n$. We show
that these representations have a nice {\em continuous leakage-resilience} property as follows. Assume some attacker
$\A(g_1,\ldots,g_n,y)$ can repeatedly learn $L$ bits of information on arbitrarily many random representations of $y$.
That is, $\A$ adaptively chooses polynomially many leakage functions
$f_i:\Z_q^n\rightarrow \{0,1\}^L$, and learns the value
$f_i(\vecx_i)$, where $\vecx_i$ is a {\em fresh and random}
discrete log representation of $y$. $\A$ wins the game if it eventually outputs a
valid discrete log representation $\vecx^*$ of $y$. We show that if
the discrete log assumption holds in $\G$, then no polynomially
bounded $\A$ can win this game with non-negligible probability, as
long as the leakage on each representation is bounded by $L\approx (n-2)\log q = (1-\frac{2}{n})\cdot |\vecx|$.
As direct extensions of this property, we design very simple continuous leakage-resilient (CLR) one-way function (OWF) and public-key encryption (PKE) schemes in the so called ``invisible key update'' model introduced by Alwen et al. at CRYPTO'09. Our CLR-OWF is based on the standard Discrete Log assumption and our CLR-PKE is based on the standard Decisional Diffie-Hellman assumption. Prior to our work, such schemes could only be constructed in groups with a bilinear pairing.
As another surprising application, we show how to design the first leakage-resilient {\em traitor tracing} scheme, where no attacker, getting the secret keys of a small subset of decoders (called ``traitors'') {\em and} bounded leakage on the secret keys of all other decoders, can create a valid decryption key which will not be traced back to at least one of the traitors.
Category / Keywords: foundations / Leakage Resilience
Date: received 28 Jun 2012
Contact author: wichs at cs nyu edu
Available format(s): PDF | BibTeX Citation
Version: 20120629:144636 (All versions of this report)
Short URL: ia.cr/2012/367
[ Cryptology ePrint archive ]