I'm looking at the De Feo, Jao, and Plût 2014 paper:
My understanding of section 3.2 Key Exchange, is that Alice's private key is the isogeny $\phi_A : E \rightarrow E_A$, which can be represented by 2 integers; private key: $(m_A, n_A)$.
Her public key consists of the curve $E_A$, represented by the polynomials $a,b$ from its Weierstrass equation $E_A: y^2 = x^3 + ax + b$, and the images of the two torsion bases $P_B, Q_B$ under her private isogeny, which appear to be 2 complex points each = 8 integers. Public key: $(E_A, \phi_A(P_B), \phi_A(Q_B) )$. So my fuzzy understanding thinks that the public key should contain around 10 - 16 pieces of information, depending on how those polynomials are represented.
In the experimental section, section 7, there's a table comparing runtimes of the key exchange algorithm for key sizes of 512 bits, 768 bits, and 1024 bits.
My question: Where do those key sizes come from? Do they ever state the bit widths of the different components of the public key, and which one(s) they are varying to change the key size? Better yet, did I miss an analysis of the relationship between the key size and the security level of the system?