[curves] CryptoNote and equivalent points

[Tim Ruffing]

On Mon, 2017-05-22 at 02:47 +0000, Trevor Perrin wrote:
> If anyone understands this algorithm in depth feel free to explain
> more.

As this came up in the other thread as well:
What they need is that the attacker cannot find two "spends" created
using the same secret key but with different key images. [1]

Then the verifiers can reject double-spends by just keeping a set of
already used key images. 

If I'm not entirely mistaken, this should be possible if the verifier
just multiplies the key image by the cofactor and stores the result in
the set. 

However, as nicely explained in the other thread, this "clears" the 8-
torsion component but modifies the l-torsion component. So if Monero
had implemented that fix, verifiers would have had to upgrade their
databases before they can continue (by going through the set of key
images and multiplying each key image by the cofactor). 

So in an existing system, the simpler fix is to just reject points that
are not in the right subgroup. This is particularly true as they wanted
to deploy a fix without anybody noticing...

(Without warranty, I thought no more than a few minutes about it.)

Tim


[1] You can use proofs of knowledge to make that formal.