Paper 2012/367
On Continual Leakage of Discrete Log Representations
Shweta Agrawal, Yevgeniy Dodis, 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 leakageresilience} 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 nonnegligible probability, as long as the leakage on each representation is bounded by $L\approx (n2)\log q = (1\frac{2}{n})\cdot \vecx$. As direct extensions of this property, we design very simple continuous leakageresilient (CLR) oneway function (OWF) and publickey encryption (PKE) schemes in the so called ``invisible key update'' model introduced by Alwen et al. at CRYPTO'09. Our CLROWF is based on the standard Discrete Log assumption and our CLRPKE is based on the standard Decisional DiffieHellman 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 leakageresilient {\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.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 Leakage Resilience
 Contact author(s)
 wichs @ cs nyu edu
 History
 20120629: received
 Short URL
 https://ia.cr/2012/367
 License

CC BY
BibTeX
@misc{cryptoeprint:2012/367, author = {Shweta Agrawal and Yevgeniy Dodis and Vinod Vaikuntanathan and Daniel Wichs}, title = {On Continual Leakage of Discrete Log Representations}, howpublished = {Cryptology ePrint Archive, Paper 2012/367}, year = {2012}, note = {\url{https://eprint.iacr.org/2012/367}}, url = {https://eprint.iacr.org/2012/367} }