Hardness of the Pairing Inversion Problem

Definitions and mathematical statement

In a common prime-order pairing setting, let $G_1,G_2$ be additive cyclic groups of order $r$, let $G_T$ be a multiplicative cyclic group of order $r$, and let an efficiently computable nondegenerate bilinear map satisfy \[ e:G_1\times G_2\to G_T,\qquad e(aP,bQ)=e(P,Q)^{ab}. \] The fixed-first-argument inversion problem is: given $P\in G_1\setminus\{0\}$ and $z\in G_T$, find $Q\in G_2$ such that \[ e(P,Q)=z. \] Nondegeneracy and prime order make this preimage unique. Fixing the second argument gives another version; asking for both arguments to be found is a different formulation.

Lange asks to determine the computational hardness of the intended Pairing Inversion Problem. A precise claim must specify the pairing family and group encodings, fixed/free arguments, instance distribution, size parameter, deterministic/randomized or quantum adversaries, and whether hardness means a reduction to a standard problem, a model lower bound, or an average-case assumption. Nondegeneracy alone is an algebraic property, not a uniform computational hardness statement.

For orientation, if $Q_0$ generates $G_2$, a discrete-logarithm solver in $G_T$ can write $z=e(P,Q_0)^a$ and return $aQ_0$. That direction does not show that pairing inversion is as hard as discrete logarithms. A claimed hardness reduction must have its actual direction and hypotheses stated.

The supplied research summary attributes a systematic 2008 study and special-case algorithms to Galbraith--Hess--Vercauteren. It uses broad hardness language while also saying no general polynomial-time algorithm or hardness proof is known. Without a fixed variant, model, and theorem those phrases cannot be reconciled as an unconditional general hardness result; they are retained as a qualified partial-progress assessment.

Short English statement

Determine the complexity of recovering a pairing argument from a target value, with the pairing family, inversion variant, encoding, and hardness notion explicit. Bilinearity and a discrete-log upper reduction alone do not establish a hardness theorem.

Sources

• Local UnsolvedMath registry, permanent ID $8800061$, exact source code catalogue entry, "Hardness of the Pairing Inversion Problem." Proposer Tanja Lange.
• IPAM Workshop on Number Theory and Cryptography --- Open Problems (2006), attachment 6239, recorded PDF page 50, printed slide 48; https://www.ipam.ucla.edu/programs/workshops/workshop-i-number-theory-and-cryptography-open-problems/?tab=schedule. Recorded access 2026-07-29; pdf-and-legacy-ppt visual-audit extraction.
• Supplied PARTIAL-PROGRESS research summary cites Galbraith--Hess--Vercauteren (2008), without title, publication details, exact variant, or the unnamed factor governing its reported special-case algorithms.