0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ A "TypeA curve", do you mean a curve that is designed to do a so-called "Type A pairing"? Unless you actually need to do a pairing operation, selecting such a curve is silly, as it is a deliberately weak curve (compared to a random elliptic curve of the same size) $\endgroup$ – poncho Oct 5 '16 at 12:50
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.