But how could he have avoided this attack? I'm only familiar with Bitcoin's blockchain on a begginner level. But I assume the only way would be to avoid revealing the answer key (public) when sending the transaction to get the reward?
It's essentially MitM all the way down.
even the private mempool can attempt a double-spend with a larger fee, get one transaction ahead, then try to maintain an edge long enough to be the "longest branch" for consensus - the 51% attack only needs 33% in reality, much less when your the private mempool that can take advantage of the birthday paradox to jump two blocks ahead.
you have to literally mine your own coin with the reward transaction included.
of course, zpk+ would solve this issue entirely.
Alice and Bob wouldn't ever doubt each other again.
The attack itself can't be mitigated because there's the incentive to try to force the blockchain with your own theft block because your fee is much higher for what appears to be the same transaction. But this attack, like you said, is only feasible for this niche domain of low entropy private keys.
No other transactions are subject to this weakness, and it's this puzzle which proves that.
Look up MEV