How to do cryptography on non-trusted machines?

Most of the real-life attacks on cryptographic devices do not break their mathematical foundations, but exploit vulnerabilities of their implementations. This concerns both the cryptographic software executed on PCs (that can be attacked by viruses), and the implementations on hardware (that can be subject to the side-channel attacks). Traditionally fixing this problem was left to the practitioners, since it was a common belief that theory cannot be of any help here. However, new exciting results in cryptography suggest that this view was too pessimistic: there exist methods to design cryptographic protocols in such a way that they are secure even if the hardware on which they are executed cannot be fully trusted. We will give a brief overview of some of those methods, concentrating on the theory of the bounded-retrieval model (see e.g. [1,2]) [1] S. Dziembowski and K. Pietrzak. Intrusion-Resilient Secret Sharing, FOCS 2007. [1] S. Dziembowski and K. Pietrzak. Leakage-Resilient Cryptography in the Standard Model, accepted to FOCS 2008.