Re: [Cfrg] RGLC on draft-irtf-cfrg-pairing-friendly-curves-07

[Armando Faz <[e-mail]>]

Dear authors,

The following comments are about the current pairing-friendly-curves-07.

I have two main observations, one regarding the choice of curves and the
other
is about hashing to curves. I also left some minor comments. Feel free to
reach
me if something is unclear.

First, I invite the authors to reconsider the curve recommended for the
128-bit level.
My suggestion is to use a BLS12 curve with a 461-bit prime replacing the BN
curve with a 462-bit prime.
This choice is motivated by:
1) both of them provide the same security levels as according to the last
column of Table 1 in [GMT19]

Curve log(p) log(r) Sec-Estimate
---------------------------------
BN    462    462    2^134
BLS12 461    308    2^134

Also, the fact that log(r) is shorter for the BLS12 instance impacts on
shorter scalars.

2) The operation counts to compute a pairing favor the BLS12 instance. The
conclusion arrived in [BD19] mentions that both BLS12 and KSS16 have
shorter
operation counts for the 128-bit level:

   "Finally, for the curves ensuring 128 bits of security, we estimated the
   complexity of the optimal ate pairing for each proposed curve and
concluded
   that BLS12 and, more surprisingly, KSS16 are the most efficient choices."

The operation counts appear in Table 14.
      cy-sqr     | com-sqr     | log(p)
-----------------------------------------
BN    19553M + I | 17774M + 4I | 461 bits
BLS12 16003M + I | 14028M + 6I | 461 bits
KSS16 26076M + I | –           | 340 bits

Another advantage of using a BLS12 instance is that implementations can
move
from BLS12-381 to BLS12-461 just by replacing the field arithmetic layer.
According to Table 1 of the draft, the curve BLS12-461 is currently
supported by
Miracl and can be easily included in RELIC. Any application already
implementing BLS12-381 can switch to BLS12-461 with small changes in the
code.
A generic BLS12 implementation can support both fields, allowing reuse code
bases.

Moreover, I encourage the use of the subgroup-secure BLS12 instance,
(i.e. the one reported in Sec 7.5 of [BD19]. The Hamming weight is increased
in 5 bits, which is approximately 200 more multiplications (using rough
estimations), it does seem to have a big penalty regarding performance.
This is also noted in Section A.3 of https://eprint.iacr.org/2015/247.

   "In the case of PBC, achieving subgroup security introduces a small but
    noticeable overhead in the pairing (see Section 4). On the other hand,
    the potential savings offered by subgroup-secure curves are far greater
    in the context of PBC; here we can possibly save large elliptic curve
    or finite field group exponentiations".


My second suggestion is to include suites for hashing to G1 and G2 because
this
is a common requirement in cryptographic protocols. (Methods are already
defined in the hash_to_curve draft, so it might just require to define the
corresponding suites).


Finally, your selection policy excludes curves at 192-bit level, however,
the
fact that there are few implementations of these instances does not seem a
sufficient motivator for not recommending secure instances. Some instances
have
already proposed. For example, [BD19] and https://eprint.iacr.org/2019/485
list a number of instances. Also, cryptographic libraries such as RELIC and
Miracl are mature enough to include the new instances easily.


Minor comments:

Section 2.2: You can start by defining what a bilinear pairing is and its
properties with respect to abstract groups. After that you can describe how
these groups are instantiated using the torsion-r subgroups of elliptic
curves.


Note the distinction between:
F_q-rational points are those with coordinates in F_q.
and F_q^k-rational points are those with coordinates in F_q^k.

    E(F_q^k):  the group of rational points of E.
   #E(F_q^k):  the number of rational points of E.


Both BN, BLS, and KSS are families of pairing-friendly curves. Consider to
rewrite sentences like this one: "A BN curve [BN05] is one of the
instantiations of pairing-friendly curves proposed in 2005".

This sentence is redundant as p is prime.
 " b is an element of a multiplicative group (F_p)^* of order (p - 1)"

order 6 twists. -> order-6 twists.

embeddiing -> embedding

paiting-based crytography -> pairing-based cryptography

rewrite: the only known attacks thus far attack the discrete logarithm
problem
directly, so we focus on the discrete logarithm in this memo.

rewrite: There has since been research into the minimum bit length of the
parameters of pairing-friendly curves

In Appendix A, make explicit the isomorphism between E and E' as this helps
implementers. There is a subtle distinction when computing the pairing
entirely with both points on the twist.
(see Theorem 1 of https://eprint.iacr.org/2009/615).

Armand -> Armando

-- 
Armando Faz
Cloudflare Inc.