What is a white-box implementation of a cryptographic algorithm? What is a white-box implementation?

Does a white-box implementation have specific properties?
This article is a nice introduction to the concept of white-box cryptography. It can be viewed as the devious cousin of code obfuscation.

In simpler words: usually, security of a cryptographic algorithm is studied in the "black-box" model: e.g., for symmetric encryption, the attacker is given access to a "device" which runs the encryption algorithm with a given key, and can submit plaintexts and ciphertexts, the goal of the attacker being to be able to decrypt a given block without submitting that exact block as ciphertext. In the "grey-box" model, the attacker also has access to some partial side-channel information; this is where power analysis fits. In the "white-box" model, the attacker has full access to the internal state. The white-box model is meant for: "the algorithm runs as software on the attacker's own computer".

White-box cryptography is less ambitious, and correspondingly a bit less impossible, than the Holy Grail of video game vendors, namely preventing any kind of reverse engineering; WBC aims at protecting "just" cryptographic keys. WBC studies techniques by which a white-box implementation could be made, and also what security characteristics could be achieved assuming that a white-box implementation exists.

Brecht Wyseur wrote a PhD thesis on white-box cryptography (there is also a downloadable presentation). See also this site (from B. Wyseur).