ICS 2010

Welcome to ICS2010
Innovations in Computer Science  ICS 2010, Tsinghua University, Beijing, China, January 57, 2010. Proceedings, 230240,
9787302217527
Tsinghua University Press
Starting with the work of IshaiSahaiWagner and MicaliReyzin, a new goal has been set within the theory of cryptography community, to design cryptographic primitives that are secure against large classes of sidechannel attacks. Recently, many works have focused on designing various cryptographic primitives that are robust (retain security) even when the secret key is “leaky”, under various intractability assumptions. In this work we propose to take a step back and ask a more basic question: which of our cryptographic assumptions (rather than cryptographic schemes) are robust in presence of leakage of their underlying secrets? Our main result is that the hardness of the learning with error (LWE) problem implies its hardness with leaky secrets. More generally, we show that the standard LWE assumption implies that LWE is secure even if the secret is taken from an arbitrary distribution with sufficient entropy, and even in the presence of hardtoinvert auxiliary inputs. We exhibit various applications of this result. 1. Under the standard LWE assumption, we construct a symmetrickey encryption scheme that is robust to secret key leakage, and more generally maintains security even if the secret key is taken from an arbitrary distribution with sufficient entropy (and even in the presence of hardtoinvert auxiliary inputs). 2. Under the standard LWE assumption, we construct a (weak) obfuscator for the class of point functions with multibit output. We note that in most schemes that are known to be robust to leakage, the parameters of the scheme depend on the maximum leakage the system can tolerate, and hence the efficiency degrades with the maximum anticipated leakage, even if no leakage occurs at all! In contrast, the fact that we rely on a robust assumption allows us to construct a single symmetrickey encryption scheme, with parameters that are independent of the anticipated leakage, that is robust to any leakage (as long as the secret key has sufficient entropy left over). Namely, for any k < n (where n is the size of the secret key), if the secret key has only entropy k, then the security relies on the LWE assumption with secret size roughly k. Preview:

Copyright 20092010, Institute for Computer Science, Tsinghua University, All Rights Reserved.