Tarsnap is entirely encrypted and the service provider can't see the keys. They run it on EC2 and S3: https://www.tarsnap.com/infrastructure.html