On Continual Leakage of Discrete Log Representations
Shweta Agrawal, Yevgeniy Dodis, Vinod Vaikuntanathan, and Daniel Wichs
Abstract
Let be a group of prime order , and let be
random elements of . We say that a vector is a {\em discrete log representation} of
some some element (with respect to ) if
. Any element has many discrete log
representations, forming an affine subspace of . We show
that these representations have a nice {\em continuous leakage-resilience} property as follows. Assume some attacker
can repeatedly learn bits of information on arbitrarily many random representations of .
That is, adaptively chooses polynomially many leakage functions
, and learns the value
, where is a {\em fresh and random}
discrete log representation of . wins the game if it eventually outputs a
valid discrete log representation of . We show that if
the discrete log assumption holds in , then no polynomially
bounded can win this game with non-negligible probability, as
long as the leakage on each representation is bounded by .
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.
@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},
url = {https://eprint.iacr.org/2012/367}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.