A nova criptografia dos dados em repouso será proibitiva. 500M registros para atualizar irá gerar log enorme, um monte de dados IO, vai durar horas, se não dias, em geral, será bastante perturbador. Sem mencionar que um erro operacional pode deixar o banco de dados inteiro perfeitamente criptografado (ou seja, sem uma chave para descriptografá-lo).
O que eu recomendaria é girar as chaves mais acima na hierarquia de chaves:
- Use uma chave simétrica para criptografar os dados.
- Altere a chave simétrica periodicamente, por exemplo. uma vez por semana, gere um novo, criptografe novos dados com o novo, mas não altere os dados antigos
- criptografa as chaves simétricas com um certificado
- use DECRYPTBYKEYAUTOCERT para descriptografar os dados, que manipularão automaticamente a tecla simétrica correta
- quando necessário, gire o certificado que criptografa as chaves simétricas. A chave simétrica suporta múltiplas criptografias de certificados, portanto, é perfeitamente viável adicionar um novo certificado, adicionar criptografia pelo novo certificado a todas as chaves simétricas e, em seguida, descartar o certificado antigo
Esquemas semelhantes a isso são freqüentemente implantados por grandes empresas. A criptografia de todos os dados raramente é feita, porque é tão proibitiva. Usar várias chaves simétricas e gerar novas chaves de vez em quando reduzirá a quantidade de perda de privacidade possível se uma chave simétrica for comprometida. Girar o certificado usado para descriptografar as chaves simétricas fornece a atenuação desejada do comprometimento de certificado, pois um certificado comprometido não poderá acessar os dados após a rotação, mesmo que os dados ainda estejam criptografados com as mesmas chaves simétricas antigas.
É verdade que posso imaginar um ataque no qual, se eu tiver acesso ao certificado, posso extrair todo o material de chave simétrica, quando o certificado for rotacionado, posso, em teoria, usar o material de chave salvo para descriptografar os dados ( usando meios diferentes do SQL Server). Mas isso não é diferente de dizer que 'se eu tiver acesso a um certificado comprometido antes de ser rotacionado, posso descriptografar todos os dados e salvar os dados descriptografados', e isso coloca o ataque sob uma nova luz, já que nenhuma quantidade após o a rotação de chaves de fato recuperará dados que já foram perdidos para o invasor.