:: Deepquest ::

Is it possible to generate an Ed25519 keypair that has a very similar public key as another keypair (fooling a casual visual comparison) or is this
as hard as solving one of SHA-512 or the discrete logarithm problem?

The core of the problem is finding a near first pre-image on the function $A = aB$ on an elliptic curve, where $A$ is the public key, and $a$ the private key¹.

For a normal hash function you $ 2^m $ operations to fix $m$ specific bits.² In particular a full pre-image takes $ 2^n $ hash function calls.

A full pre-image on $A = aB$ is equivalent to solving the discrete logarithm problem on that curve. This problem only needs $ 2^{n/2} $ operations, which is something around $ 2^{126} $ for Ed25519³. i.e. much faster than for a hash function, but still prohibitively slow.

Now the interesting question is, if you want to find only $ m < 126 $ matching bits, how much work do you need? And I can't answer that, so this doesn't really answer your question. I know of no way to do this faster than brute-force, but I'm certainly no expert on this matter. ¹ The standard implementation of Ed25519 does use a different private key $k$ from which $a$ is derived via hashing, but an attacker would simply skip that step, so we can ignore it. It does not affect security. ² If you don't care about which bits you fix, then the problem becomes a bit easier than $ 2^m $ but it doesn't matter that much. ³ I believe Curve25519 has a small subgroup, reducing security by a few bits, so I assumed a 126 bit security level. A few bits more or less don't matter, especially since one "operation" can be much more expensive for some primitives than for others.