the comment in the response about using stars going nova between the present and the travelled-from time was probably the best answer, but it requires accepting the paradox of the possibility of time travel while still ruling out faster than light travel- as you could get the key earlier than the set date by travelling light years toward where the stars were sampled from.<p>If you are protecting the secret from non-time travelers, you're probably fine, but if you are protecting it from <i>other</i> time travellers, your compute or proof of work has to be more expensive than <i>their</i> time-travel propulsion energy units.<p>We have this same problem with device attestation, where if the key exists in the same "universe" (hardware substrate) as the ciphertext, you're effectively fighting time travellers because they can run, re-run, use side channels, insert a breakpoint anywhere along the way. The current solutions are in the domains of physical tamper proofing, "white box" cryptography and other obfuscation schemes, and ultimately fully homomorphic encryption (FHE).<p>FHE would be the necessary solution against time travellers in this case because no matter where in time they were, they would have to be present at the instant the compute operation completes- and then you're into a race condition against Planck time to see who can grab the result of the computation first when it finishes. (assuming they can't infer or predict the result earlier than the completion of the FHE computation, that earlier decryption rounds don't reduce the time it takes to brute force the rest of it in a parallel stopped-timeline, and that Planck time still means anything in a universe where time isn't unidirectional and scalar)<p>Writing wise, there would have to be a hitch in their time travel scheme where to work it needed randomness and a lack of precision for some important quantum uncertainty reason, and the race to be present for the FHE decryption before the time travellers resolved their precision problem would drive the plot.<p>don't be discouraged though, a cursory reading of scientific discovery shows that impossible is mostly a convention, and cryptography historically reduces to a gentleman's agreement.