TY - GEN
T1 - Overcoming weak expectations
AU - Dodis, Yevgeniy
AU - Yu, Yu
PY - 2013
Y1 - 2013
N2 - Recently, there has been renewed interest in basing cryptographic primitives on weak secrets, where the only information about the secret is some non-trivial amount of (min-) entropy. From a formal point of view, such results require to upper bound the expectation of some function f(X), where X is a weak source in question. We show an elementary inequality which essentially upper bounds such 'weak expectation' by two terms, the first of which is independent of f, while the second only depends on the 'variance' of f under uniform distribution. Quite remarkably, as relatively simple corollaries of this elementary inequality, we obtain some 'unexpected' results, in several cases noticeably simplifying/improving prior techniques for the same problem. Examples include non-malleable extractors, leakage-resilient symmetric encryption, alternative to the dense model theorem, seed-dependent condensers and improved entropy loss for the leftover hash lemma.
AB - Recently, there has been renewed interest in basing cryptographic primitives on weak secrets, where the only information about the secret is some non-trivial amount of (min-) entropy. From a formal point of view, such results require to upper bound the expectation of some function f(X), where X is a weak source in question. We show an elementary inequality which essentially upper bounds such 'weak expectation' by two terms, the first of which is independent of f, while the second only depends on the 'variance' of f under uniform distribution. Quite remarkably, as relatively simple corollaries of this elementary inequality, we obtain some 'unexpected' results, in several cases noticeably simplifying/improving prior techniques for the same problem. Examples include non-malleable extractors, leakage-resilient symmetric encryption, alternative to the dense model theorem, seed-dependent condensers and improved entropy loss for the leftover hash lemma.
UR - http://www.scopus.com/inward/record.url?scp=84873970779&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84873970779&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-36594-2_1
DO - 10.1007/978-3-642-36594-2_1
M3 - Conference contribution
AN - SCOPUS:84873970779
SN - 9783642365935
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 1
EP - 22
BT - Theory of Cryptography - 10th Theory of Cryptography Conference, TCC 2013, Proceedings
PB - Springer Verlag
T2 - 10th Theory of Cryptography Conference, TCC 2013
Y2 - 3 March 2013 through 6 March 2013
ER -