Paper 2013/313
Pairing Inversion via Non-degenerate Auxiliary Pairings
Seunghwan Chang, Hoon Hong, Eunjeong Lee, and Hyang-Sook Lee
Abstract
The security of pairing-based cryptosystems is closely related to the difficulty of the pairing inversion problem(PI). In this paper, we discuss the difficulty of pairing inversion on the generalized ate pairings of Vercauteren. First, we provide a simpler approach for PI by generalizing and simplifying Kanayama-Okamoto’s approach; our approach involves modifications of exponentiation inversion(EI) and Miller inversion(MI), via an “auxiliary” pairing. Then we provide a complexity of the modified MI, showing that the complexity depends on the sum-norm of the integer vector defining the auxiliary pairing. Next, we observe that degenerate auxiliary pairings expect to make modified EI harder. 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, PI of arbitrarily given generalized ate pairing can be reduced to modified EI in polynomial time.
Metadata
- Available format(s)
-
PDF
- Publication info
- Published elsewhere. Unknown status
- Keywords
- elliptic curveexponentiation inversionMiller inversionpairing inversionpairing-based cryptosystem
- Contact author(s)
- ejlee127 @ gmail com
- History
- 2013-11-05: last of 6 revisions
- 2013-05-28: received
- See all versions
- Short URL
- https://ia.cr/2013/313
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2013/313,
author = {Seunghwan Chang and Hoon Hong and Eunjeong Lee and Hyang-Sook Lee},
title = {Pairing Inversion via Non-degenerate Auxiliary Pairings},
howpublished = {Cryptology {ePrint} Archive, Paper 2013/313},
year = {2013},
url = {https://eprint.iacr.org/2013/313}
}