As disclosed herein a computer system for secure database backup and recovery in a secure database network has N distributed data nodes. The computer system includes program instructions that include instructions to receive a database backup file, fragment the file using a fragment engine, and associate each fragment with one node, where the fragment is not stored on the associated node. The program instructions further include instructions to encrypt each fragment using a first encryption key, and store, randomly, encrypted fragments on the distributed data nodes. The program instructions further include instructions to retrieve the encrypted fragments, decrypt the encrypted fragments using the first encryption key, re-encrypt the decrypted fragments using a different encryption key, and store, randomly, the re-encrypted fragments on the distributed data nodes. A computer program product and method corresponding to the above computer system are also disclosed herein.