[KMag]

I should point out that I would suggest using the solution to the quadratic residue problem as a key for a Blum Blum Shub stream cipher to encrypt the hash chains and the message, so that portion of the system only relies on square roots and quadratic residues modulo a Blum integer. (Using the quadratic residue solution as a key for AES-GCM or ChaCha20-Poly1035 would open you up to weaknesses in those ciphers, and in this case the slowness of Blum Blum Shub isn't a problem.)

Then, for the inner puzzle, I would use hash chains using a hash in the Blake family to generate a ChaCha20-Poly1305 key to encrypt the plaintext. Since Blake's round function is based on ChaCha20, this also reduces the number of different primitives you're relying on.

In the end, the cipher text would be doubly encrypted with Blum Blum Shub and ChaCha20-Poly1305, with keys being the solutions to repeated quadratic residue modulo a Blum integer and repeated hash chains using a hash from the Blake family. This minimizes the number of possible points of failure.