Subject: [Cfrg] Compression of tori in draft-irtf-cfrg-pairing-friendly-curves-02

From: Watson Ladd <[email-masked]>
Date: Thu, 19 Mar 2020 14:08:54 -0700

Dear all,

In the latest draft I see that F_{p^k} is represented directly as
polynomials modulo an irreducible of degree k, and GT is encoded
accordingly. This is space inefficient.

In most cases k is even. Let q=p^(k/2) Consider F_q[x]/(x^2+d), the
quadratic extension of F_{q }, and now consider the result of a
pairing in it. As in https://eprint.iacr.org/2004/032.pdf, it is clear
that the result satisfies a quadratic equation: a^2-db^2=1, where the
element is a+bx.

Therefore we can send only a, which is much smaller, and ecode b as a
single bit.

This technique is very useful in any protocol where an element of GT
must be sent.

Sincerely,
Watson Ladd

---

From: Yumi Sakemi <[email-masked]>
Date: Sat, 21 Mar 2020 16:29:36 +0900

Dear Dr. Watson,

Thank you for your comments.
I'm glad you to read our draft!!

The compress techniques are very interesting for us.
According to your comments, I will discuss with co-authors and
update our draft.

Best regards,
Yumi

---
Yumi Sakemi, Ph. D.
Lepidum Co. Ltd.
E-Mail: [email-masked]

2020年3月20日(金) 6:09 Watson Ladd <watson=[email-masked]>:

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

---

From: Yumi Sakemi <[email-masked]>
Date: Fri, 27 Mar 2020 20:39:40 +0900

Dear Dr. Watson,

Thank you for your comment!
We submitted revised version.
https://mailarchive.ietf.org/arch/msg/cfrg/n45h0G-rVI4lcXuIQKDOMceqBds/

There are many ways to represent an element in extension fields.
Among them, focusing on "interoperability", we adopted Rene's
representation convention as a standard and efficient method.
His method is published as I-D at
"https://tools.ietf.org/html/draft-ietf-lwig-curve-representations-09".

On the other hand, we understand that your recommended compression
method is more effective when application communicates elements in
extension fields.
So, we added about compression method as useful information to
developers in sec 2.5 of our draft.

Best regards,
Yumi

-- 
Yumi Sakemi, Ph. D.
Lepidum Co. Ltd.