I was reading 'Pinocchio Coin' paper by Danezis et al. where they have said,

"If we use the efficient pairing groups of Pinocchio, computing discrete logarithms in the exponent field $\mathbb{F}_p$ with p ≈ 256 is easy. We could switch to non-standard and larger pairing groups, but this seems undesirable as it would bring down the overall performance of the proof system. Instead we propose to compute C in an extension field $\mathbb{F}_{p^\mu}$ of size $p^\mu$ > 2048."

Here C is just a Pedersen commitment. My question is, to achieve 128 bits of security, what should be the size of $p^\mu$? Is there any source where I can find the relevant specifications?

  • $\begingroup$ $p^{\mu}$ is a generalization of the $2^m$ approach? In this case $log_2(p^{\mu})>3072$ $\endgroup$ – SEJPM May 25 '15 at 16:38
  • $\begingroup$ Yes, you are right about the generalization part, but how is it derived? A wild guess, does it have any relation to NIST standard for RSA? $\endgroup$ – Bitswazsky May 25 '15 at 17:57
  • $\begingroup$ No. This comes from the fact that RSA and the DLP can be solved with (sort of) the same algorithm: The general number field sieve (GNFS). It does apply to factoring and to DLP over prime fields, I'm not sure concerning extension fields, but as index-calculus is applicable I guess GNFS may be as well. Again I'm not sure if this really applies to extension fields but the general recommendations are the same for RSA and DLP and as it's well-known that 3072-bit RSA roughly equals 128-bit I just ported that here. $\endgroup$ – SEJPM May 25 '15 at 18:26
  • 1
    $\begingroup$ Actually, there's been a number of recent results about quickly computing Discrete Logs in extension fields of small characteristic, such as eprint.iacr.org/2013/400.pdf . While using $\mu$ prime would appear to be immune to these results, I'd still be cautious about it. If there any particular reason why you can't use a prime field? $\endgroup$ – poncho May 25 '15 at 20:01
  • $\begingroup$ @poncho Thank you. Unfortunately the paper is pretty sparse on these details and doesn't give any more reasoning other than what I've quoted in the question.. $\endgroup$ – Bitswazsky May 26 '15 at 4:24

Your Answer

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

Browse other questions tagged or ask your own question.