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].
94A60 Cryptography
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
11Y16 Number-theoretic algorithms; complexity
Full Text: DOI