Due to unexpected failures of github's LaTeX parsing (which were not evident until I published this, but have persisted afterwards), and since the mathematical parts are important in this, I have migrated this proposal to a blog post with identical content, but correctly formatted equations.
Please continue to put any comments here.
Following up on the previous, here's my attempt at a simple proof of concept in Python: https://gist.github.com/AdamISZ/77651979025d16b778494047c86c3a7c
Basically you have about 1.9kB for a ring size of 256 secp256k1 keys, and 2.3kB for 1024 keys. The latter takes about 10-13 seconds (and the former, maybe 3 seconds), but my algorithms are laughably bad and it's in Python, I'd expect it to be about 2 orders of magnitude faster if done properly, and in C :) (also this is for sign + verify together, and of course, ignores any potential batching benefit verify side).
The paper, obviously, discusses the performance scaling in some detail.
(*edited because had got byte sizes wrong)
Editing to note: to go from ring signatures to linkable ring signatures, I should note, there is a simple transformation as explained in the paper: commit, instead of to 0 with randomness r, to S with randomness r, and then form a ring signature over each key in the ring added to C(-S, 0).
The idea here is that S are effectively 'serial numbers' of the 'coins' or tokens represented by the user's key, and therefore are one time and function like key images.
This is somewhat similar to Rate Limiting Nullifiers a zkSNARKs construct
Rate Limiting Nullifiers
Thanks @sambacha for that breadcrumb! Some pretty interesting ideas there.
Having spent some time reading it, I now think that Groth's 2014 construction as described in How to leak a secret and spend a coin would do the job of creating a logarithmic sized ring signature using only the ECDLP. Specifically, you can create a ring sig on$N$ keys of size roughly $32(7 log_{2}(N))$ bytes using that exact construction. Albeit, that is a specific construction using Pedersen commitments to a value of zero where the secret key is the randomness; I think that to translate it to our setting is likely trivial (for example, if you prove that 1 of $N$ of a set of commitments to zero, $C_i = 0H + r_{i}G$ , then those commitments are exactly public keys as we use), but I haven't checked that.
That could mean that figures of 1k-20k+ keys could be more practical, albeit one has to consider the computational cost of signing and verifying too.
Afaik Monero research here into sublinear ring signatures was based on similar ideas, though I haven't read and understood that paper yet.