Welcome to the resource topic for 2012/367
Title:
On Continual Leakage of Discrete Log Representations
Authors: Shweta Agrawal, Yevgeniy Dodis, Vinod Vaikuntanathan, 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.
ePrint: https://eprint.iacr.org/2012/367
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .