Cryptology ePrint Archive: Report 2013/313

Reducing Pairing Inversion to Exponentiation Inversion using Non-degenerate Auxiliary Pairing

Seunghwan Chang and Hoon Hong and Eunjeong Lee and Hyang-Sook Lee

Abstract: The security of pairing-based cryptosystems is closely related to the difficulty of the pairing inversion problem. Building on previous works, we provide further contributions on the difficulty of pairing inversion. In particular, we revisit the approach of Kanayama-Okamoto who modified exponentiation inversion and Miller inversion by considering an ``auxiliary'' pairing. First, by generalizing and simplifying Kanayama-Okamoto's approach, we provide a simpler approach for inverting generalized ate pairings of Vercauteren. Then we provide a complexity of the modified Miller inversion, showing that the complexity depends on the sum-norm of the integer vector defining the auxiliary pairing. Next, we observe that the auxiliary pairings (choice of integer vectors) suggested by Kanayama-Okamoto are degenerate and thus the modified exponentiation inversion is expected to be harder than the original exponentiation inversion. We provide a sufficient condition on the integer vector, in terms of its max norm, so that the corresponding auxiliary paring is non-degenerate. Finally, we define an infinite set of curve parameters, which includes those of typical pairing friendly curves, and we show that, within those parameters, pairing inversion of arbitrarily given generalized ate pairing can be reduced to exponentiation inversion in polynomial time.

Category / Keywords: public-key cryptography / Ate pairing, elliptic curve, exponentiation inversion, Miller inversion, pairing inversion

Date: received 24 May 2013, last revised 30 May 2013

Contact author: ejlee127 at ewha ac kr

Available format(s): PDF | BibTeX Citation

Version: 20130531:025955 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]