As I said: Choosing a prime power q<=x and an elliptic curve E over F_q up to isomorphism produces about x^2/log x choices of curves. Only about x^2/(log x)^2 of those curves have prime or near-prime group order. Johnston is fundamentally limited to a vastly smaller set of about x/log x curves (all of which were already prohibited by the ECC standards), and within those has actually written down only about x^(1/2)/log x "bad" curves, far fewer than previous Weil-descent papers.
I have no idea which statement Johnston thinks he's disputing, and I have no idea why he claims that this perfectly clear (q,E) distribution is "wrong." Of course, it's not the distribution used in elliptic-curve cryptography, but that's exactly my point: ECC does _not_ allow general curves E over general finite fields F_q. In particular, the ECC standards prohibit curves with far-from-prime group order, curves vulnerable to Weil descent (contrary to Johnston's claims), et al.
As for isogenies versus isomorphisms: One can, of course, ignore cryptographic reality and count isogeny classes instead of isomorphism classes. There are about x^(3/2)/(log x)^2 isogeny classes that have prime or near-prime group order, and Johnston is fundamentally limited to a vastly smaller set of about x^(1/2)/(log x) isogeny classes.
There are two reasons that counting isogeny classes is ignoring cryptographic reality. First, applications that generate "random" elliptic curves normally do it by generating uniform random Weierstrass coefficients a4,a6, or something very similar. (See, e.g., FIPS 186-3.) This is almost identical to generating a uniform random isomorphism class, and quite far from generating a uniform random isogeny class. Probabilities that are concentrated near the ends of the Hasse interval are then quite horribly misrepresented by isogeny-class statistics. I'm not saying that there's a big change for Weil descent; I'm just saying that the isogeny-class question is asking about a quite different distribution from the distribution actually used in the applications.
The second reason is more important, and does have an effect on Weil descent: counting isogeny classes obviously can't see the difference between a "bad" curve and other curves in the same isogeny class. The standards prohibit entire isogeny classes (and fields), but this doesn't mean that security is an isogeny invariant. There are some well-known examples of curves E where we know fast ECDL algorithms for E (by Weil descent) but we _don't_ know fast ECDL algorithms for most isogenous curves.
One might naively think that the _existence_ of fast isogenies (in most cases; see [arxiv.org
] for proofs in the typical case, and [eprint.iacr.org
] to understand the exceptional cases) implies that ECDL difficulty is an isogeny invariant. This logic is erroneous, because it ignores effectivity; it's just like leaping from the trivial _existence_ of collisions in SHA-512 to the completely unjustified claim that collisions in SHA-512 are easy to find.
---D. J. Bernstein
Research Professor, Computer Science, University of Illinois at Chicago