However, things can be improved over time. Some examples of what could be possible:
Pay to public key:
Output:
Input:
Pay to vanity public key:
Output:
Input:
Pay to public key hash:
Output: OP_DUP OP_HASH160 OP_EQUALVERIFY OP_CHECKSIG
Input:
Pay to vanity address:
Output: OP_TOALTSTACK OP_DUP OP_HASH160 OP_FROMALTSTACK
Input:
Another solution is to stick with what we have, and build some homomorphic encryption on top of that, with no consensus changes. Then, it may be possible to create a puzzle, where even the creator knows nothing about the keys, but after applying some operations (like modulo or taking N bits) it could be possible to guarantee that the solution is in some predefined range. When it comes to existing puzzles, their creators could add some range proof for that, it would be a good idea if it would not make it much easier to solve.