Security Strength of BigInteger vs elliptic curve parameter value

Question

Choosing 512 bit prime biginteger as secret value as in RSA
Choosing TypeA curve (rbits=256,qbits=512) and setting secret value by randomly selecting from $Z_r$ value
I wanna know which one has more security strength even though I know 128 bit security can be obtained with 256 bit elliptic curve and 3072-bit RSA keys.I need some detailed explanation.
When we set rbits=256 bits, is it 256 bit elliptic curve? Or when we set qbits=256 bits, is it 256 bit elliptic curve?

Answer 1

A Type A curve has embedding degree 2. That means via the pairing we get an homomorphism from an ECC curve of bit length k to a finite field with 2 k bits (i.e. qbits).

You have to compare the complexity of:

1. calculating the discrete logarithm in the EC group with k bits and without using the paring homomorphism (i.e. by a generic algorithm)
2. calculating the discrete logarithm in the finite field with 2k bits by the number field sieve.

and take the minimum of both.

The complexity of a generic ECC DL algorithm is $2^{k/2}$

The complexity of the number field sieve for a finite field with k bits is approximately
$$\lambda (k) := \exp(1.9 (k \log (2))^{1/3} \log(k \log (2))^{2/3})$$

Therefore we have to compare $2^{k/2}$ with $\lambda (2k)$.

For big values of k, surely the factorisation in the finite field is faster then the generic ECC algorithm. So let us calculate the break-even point:

$$min_k (\lambda (2 k) = 2^{k/2})$$

This gives $k \approx 65$.
From that value of k on we can calculate the running time complexity as $\lambda (2k)$

For instance, an elliptic Type A curve with 256 bits gives you a strength of 63 bits only .

Please take this result with a grain of salt, because I have omitted the $o(1)$ term.

For real cryptographic use its maybe a better idea to use the table from the NIST SP 800-57 document:

Strength  RSA modulus size
      80        1024
     112        2048
     128        3072
     192        7680
     256       15360

For instance, that would have the following security implication:
In order to get a strong security (i.e. strength >100) type A curve, you need a finite field size of 2048 bits. This means your type A curve must have rbits=1024 and qbits=2048.