You are looking at a specific version 20130531:025955 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Ate pairingelliptic curveexponentiation inversionMiller inversionpairing inversion
Contact author(s)
ejlee127 @ ewha ac kr
History
2013-11-05: last of 6 revisions
2013-05-28: received
See all versions
Short URL
https://ia.cr/2013/313
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.