Next generation file systems like ZFS and BtrFs allow storing snapshots with no additional costs. Calculating diffs is also extremely cheap.
Is it possible to use duplicity with an alternative diff backend?
Instead of maintaining a file signature cache or downloading these informations, one could use create a snapshot use easily get this information from these file systems. The rest (create tar, sign, transfer and even restore) would be the same.