After a quarter century of impetuous development, complexity-theoretic cryptography has succeeded in finding rigorous definitions of security and provably secure schemes. In complexity-theoretic cryptography, however, computation has been "abstracted away": an adversary may attack a cryptographic algorithm essentially only by exchanging messages with it. Consequently, this theory cannot protect against attacks that exploit the information leakage (via EM fields, power consumption, etc.) that is inherent in the PHYSICAL execution of any cryptographic algorithm. Such "physical observation attacks" have successfully broken mathematically impregnable systems, thus threatening the relevance of complexity-theoretic cryptography. To respond to the present crisis, we eliminate the mathematically convenient but physically unrealistic separation between the adversary and cryptographic computations. Specifically, we

(1) put forward a powerful, comprehensive, and precise model for delivering cryptographic security when an adversary has full access to any information leaked from the physical execution of cryptographic algorithms;

(2) show that some of the basic theorems and intuitions of traditional cryptography no longer hold in a physically observable setting; and

(3) construct schemes (such as pseudorandom generators and digital signatures) that are provably secure against ALL physical-observation attacks.

Joint work with Silvio Micali, MIT.