I have been looking for a good way to back up my files, without much luck. My requirements are:

Encrypted (on the original machine).
Fast/bandwidth-efficient (deduplication is a plus).
Open-source.
Cheap.

Every single piece of software I have ever tried fails in at least one of the above. I currently use SpiderOak, which is everything except open-source, so that fails too.

However, my quest is finally over. I have discovered the Holy Grail of backups, and its name is Attic.
UPDATE: I have now switched over to Borg, which is a fork of Attic that seems better-maintained. This article still mostly applies to Borg, though.