# zbMATH — the first resource for mathematics

An efficient residue group multiplication for the $$\eta _{T }$$ pairing over $${\mathbb F}_{3^m}$$. (English) Zbl 1267.94094
Jacobson, Michael J. jun. (ed.) et al., Selected areas in cryptography. 16th annual international workshop, SAC 2009, Calgary, Alberta, Canada, August 13–14, 2009. Revised selected papers. Berlin: Springer (ISBN 978-3-642-05443-3/pbk). Lecture Notes in Computer Science 5867, 364-375 (2009).
Summary: When we implement the $$\eta _{T }$$ pairing, which is one of the fastest pairings, we need multiplications in a base field $${\mathbb F}_{3^m}$$ and in a group $$G$$. We have previously regarded elements in $$G$$ as those in $${\mathbb F}_{3^{6m}}$$ to implement the $$\eta _{T }$$ pairing. Gorla et al. proposed a multiplication algorithm in $${\mathbb F}_{3^{6m}}$$ that takes 5 multiplications in $${\mathbb F}_{3^{2m}}$$, namely 15 multiplications in $${\mathbb F}_{3^{m}}$$. This algorithm then reaches the theoretical lower bound of the number of multiplications. On the other hand, we may also regard elements in $$G$$ as those in the residue group $${\mathbb F}_{3^{6m}}^{\,*}\,/\,{\mathbb F}_{3^{m}}^{\,*}$$ in which $$\beta a$$ is equivalent to $$a$$ for $$a \in {\mathbb F}_{3^{6m}}^{\,*}$$ and $$\beta \in {\mathbb F}_{3^{m}}^{\,*}$$. This paper proposes an algorithm for computing a multiplication in the residue group. Its cost is asymptotically 12 multiplications in $${\mathbb F}_{3^{m}}$$ as $$m \rightarrow \infty$$, which reaches beyond the lower bound the algorithm of Gorla et al. reaches. The proposed algorithm is especially effective when multiplication in the finite field is implemented using a basic method such as shift-and-add.
For the entire collection see [Zbl 1177.94012].
##### MSC:
 94A60 Cryptography 11T71 Algebraic coding theory; cryptography (number-theoretic aspects) 11Y16 Number-theoretic algorithms; complexity
Full Text: