No they don't need the encryption key just like you don't if you get a new phone. They just need to know your password, send it to Authy, and Authy will decrypt the backup and send it to them.
Edit: I can't reply to the comments on this but they contain the exact procedure an attacker would have to go through, which, if correct, is much more difficult than just knowing the password.