4
$\begingroup$

As per the Schnorr's original paper (1991),

The Security Complexity $2^t$: We wish to choose the parameters $p$, $q$ so that forging a signature or an authentication requires about $2^t$ steps by known methods. For this we choose $q > 2^{2t}$ and $p$ such that $2^t$ is about $e^{\sqrt{\ln(p)\ln(\ln(p))}}$. ... For $p > 2^{512}$ and $q > 2^{140}$ the discrete logarithm problem requires at least $2^{72}$ steps by known algorithms.

Now I have three questions regarding this.

  1. How does value of $p$ comes to $2^{512}$ for security complexity of $2^{72}$?
  2. What is the equivalent AES and RSA key-lengths if we use $p$ of $1024$ bits and $q$ of $512$ bits?
  3. Since Schnorr is finite field signature scheme, what is the 'field size', 'group size' and 'subgroup size' in case of schnorr signature scheme?

Thanks in advance.

$\endgroup$
3
$\begingroup$

How does value of $p$ comes to $2^{512}$ for security complexity of $2^{72}$?

Personally, I couldn't connfirm this number, but rather landed at $2^{66}$. If you don't know how to find this number, just plug the $2^{512}$ into the complexity equation given and take the logarithm to the base two for better readability.

Note that Schnorr's complexity estimate for the field is based on the Index-Calculus Algorithm and doesn't yet take into account the Number Field Sieve (original paper as PDF) against discrete logarithms, which would give a different expression, namely $L_p[1/3,3^{2/3}]=e^{(3^{2/3}+o(1))(\ln p)^{1/3}(\ln\ln p)^{2/3}}$, that would yield a much lower required attack complexity.

What is the equivalent AES and RSA key-lengths if we use $p$ of $1024$ bits and $q$ of $512$ bits?

$q$ is the subgroup order and if you get a 512-bit subgroup you'll have roughly 256-bit security for this subgroup. $p$ is the field prime and with it being 1024-bit, you'll get roughly 80-bit security against NFS-based attacks. So the answer is: A 1024-bit RSA modulus will have a comparable security along with AES-128, where 48 key bits are constant zero'ed out. Note that just plugging-in $2^{1024}$ into the complexity equations is a dangerous business, as $o(1)$ hides an implementation-dependenant (constant) factor that was not accounted for. Rather you need a concrete data point as a basis for further extrapolation. Here's a more detailed treatment of keylengths: (simple) (complex) by Lenstra and Verheul.

Since Schnorr is finite field signature scheme, what is the 'field size', 'group size' and 'subgroup size' in case of schnorr signature scheme?

$p$ is the field prime and its bitlength is the field size.
$q$ is the subgroup order and its bitlength is the subgroup size.
There's no relevant "group size" in this case (maybe one could say that's equivalent to the field size though)

$\endgroup$
  • $\begingroup$ I'm not 100% sure I got everything right, so complain as usual if something is wrong ;) $\endgroup$ – SEJPM Apr 11 '16 at 20:11
  • $\begingroup$ I didn't get why you told to get log to base 2 (ln means base should be e). If I'm right, you considered lowest of 256 and 80-bit (i.e. 80-bit) as resultant security level. But as per schnorr's formula 1024-bit should give security level of 98-bits. What is the formula to calculate security level against NFS-based attacks in case of p? $\endgroup$ – mk09 Apr 12 '16 at 8:32
  • $\begingroup$ Now I understood what you intended to say when you told to take log to base 2. Its for final result of exponentiation which will give value of t directly. Please clarify about my second doubt in above comment. $\endgroup$ – mk09 Apr 12 '16 at 8:42
  • $\begingroup$ @Maheshk, I used "take the logarithm to the base two for better readability." so you see $66$ and not $7.3789*10^{19}$ which is rather unhelpful in cryptography, the result of the logarithm will also be the $t$ value. I've added some treatment of NFS run-time. $\endgroup$ – SEJPM Apr 12 '16 at 20:55
  • $\begingroup$ I think in equation of Lp[1/3, 3^2/3], power of ln(p) should be 1/3 and power of ln(ln(p)) should be 2/3 as per formula of Lp in ccrwest.org/gordon/log.pdf. One more thing, I didn't find anything on O(1). How can I find value of O(1) based on my implementation? $\endgroup$ – mk09 Apr 13 '16 at 10:30

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.