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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 4:24


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.