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

From: Armando Faz <[email-masked]>
Date: Wed, 8 Jul 2020 05:21:43 -0700

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.

---

From: [email-masked]
Date: Wed, 8 Jul 2020 14:59:16 -0700

Hello CFRG,

Armando, thanks for the careful feedback.

One quick question for the whole group:

Armando Faz <armfazh=[email-masked]> wrote:
> 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).

Since neither hash-to-curve nor pairing-friendly-curves is finalized,
it seems like these hash-to-curve suites could go in either document.

Stating the obvious:

- one advantage of putting them in p-f-c is that it decouples the
  two documents somewhat---if p-f-c changes after h-2-c is finalized
  there's no problem updating the suites.

- on the other hand, putting the suites in h-2-c might make them
  slightly easier to discover down the road; but maybe this issue
  can be addressed by adding a pointer from h-2-c to p-f-c.

In either case, it seems like the BLS12-381 suite currently defined
in h-2-c ought to live in the same place as the suites for the other
curves that are defined in p-f-c, no?

Further thoughts would be appreciated!

Best regards,

-=rsw

---

From: Armando Faz <[email-masked]>
Date: Thu, 9 Jul 2020 13:45:07 -0700

> it seems like these hash-to-curve suites could go in either document.

Additionally to the list the suites (in either document). The pairing
draft should mention somewhere that hash to G1 and G2 are common
operations in several cryptographic protocols. Obviously, it should
point to the hash_to_curve draft, and reinforce the security dangers
of the try-and-increment method, which was popularized in the
pairing-crypto community.

-- 
Armando Faz
Cloudflare Inc.

---

From: Marek Jankowski <[email-masked]>
Date: Fri, 17 Jul 2020 08:53:53 +0200

I agree with Armando.
It seems to me that hash-to-curve's main use case is pairings, so defining
it in the pairings draft does not make much sense.
So the best practice would be to suggest suites and refer to the
hash-to-curve draft for more information.
As Armando says it is important to refer to the draft mainly to prevent
naive use of rejection sampling.

Other than that, I think it is a great draft and I support its adoption.

Marek

On Thu, Jul 9, 2020 at 10:46 PM Armando Faz <armfazh=
[email-masked]> wrote:

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>