[claudius]

Let the user create a private/public key on the device and allow them to store the file somewhere safe with only the public key remaining on the device. It can then easily do the backup (and even store the public key on Google’s servers, if required) whenever required, and if the user gets a new phone, he’ll be prompted to feed his private key into it again to decrypt the backup. This can be done over the network, from an SD card/usb key or maybe even with a QR code.