Taxonomy of pairing-related assumptions

Definitions and mathematical statement

The source asks for an update of Joux's 2002 work through a systematic taxonomy of pairing-related computational assumptions. The relevant setting has finite groups $G_1,G_2,G_T$ and a bilinear pairing $e:G_1\times G_2\to G_T$, with security parameter and public group-generation data specified for each assumption.

A formal computational assumption requires a distribution of challenge instances, a relation describing acceptable outputs, and resource/success bounds for adversaries. A decisional assumption instead specifies two challenge distributions and bounds distinguishing advantage. A comparison by reduction must record direction, running time, success loss, oracle/model restrictions, and the pairing setting; symmetric and asymmetric source groups or available homomorphisms can change the implications.

Develop an organized classification of the intended assumptions, their variants, and proved or conjectured relations, improving the particular baseline intended by the source. The excerpt supplies neither Joux's exact 2002 reference nor a list of assumptions, chosen adversary model, reduction notion, scope or completion criterion. Thus this is a survey/classification program, not a single fully specified hardness or equivalence theorem. Names such as BDH, DLIN, $k$-BDH and co-BDH require exact challenge definitions before they can be identified across papers.

The research summary says the task was largely addressed by Galbraith--Paterson--Smart (2008) and subsequent surveys, while the registry still has an open label. It gives no exhaustive taxonomy or theorem proving completeness. The historical request and later survey-progress assessment are retained without treating the open label as a precise unresolved proposition or independently verifying current coverage.

Short English statement

Organize pairing-based computational and decisional assumptions and their reductions, updating the intended 2002 baseline. The source reports later survey progress but does not fix a list, model or criterion for an exhaustive taxonomy.

Sources

• Local registry: data/unsolvedmath/problems.json, permanent UnsolvedMath ID $8800058$, source code catalogue entry; supplied statement, background, and research summary, updated 2026-08-06. Attributed to Tanja Lange.
• IPAM, Workshop on Number Theory and Cryptography---Open Problems (2006), attachment 6239, PDF page 42, printed slide 40: https://www.ipam.ucla.edu/programs/workshops/workshop-i-number-theory-and-cryptography-open-problems/?tab=schedule. Supplied PDF/legacy-PPT visual audit accessed 2026-07-29; it reports 19 inspected surviving attachments.
• Joux (2002), referenced by the statement without title or publication details.
• Galbraith--Paterson--Smart, "Pairings for cryptographers" (2008), cited by the summary. Its reference to later "Security of the BDH-schemes" literature gives no identifiable complete citation.