Decision Linear versus DDH

Definitions and mathematical statement

For a cyclic group $G=\langle g\rangle$ of prime order $\ell$, decisional Diffie--Hellman (DDH) asks to distinguish \[ (g,g^a,g^b,g^{ab})\quad\text{from}\quad(g,g^a,g^b,g^c), \] where $a,b,c$ are independent uniform elements of ${\mathbb{Z}}/\ell{\mathbb{Z}}$. A standard Decision Linear (DLIN) formulation, with independent random generators $u,v,h$, asks to distinguish \[ (u,v,h,u^r,v^s,h^{r+s})\quad\text{from}\quad (u,v,h,u^r,v^s,h^t), \] where $r,s,t$ are independent uniform exponents. Computational hardness concerns an efficiently represented group family indexed by a security parameter, and efficient distinguishers' advantage between these distributions.

Lange asks whether DLIN is strictly harder than DDH in the relevant pairing groups. The group family, pairing type and available operations, computational model, and meaning of strict hardness are not specified. A reduction comparison, a generic-group separation, and a concrete group family in which DDH is efficiently decidable but DLIN remains computationally hard are different claims.

The supplied summary notes that pairings can make DDH easy while DLIN is still conjectured hard, and describes DLIN as a more conservative assumption. This does not establish unconditional DLIN hardness or a strict separation in actual groups. Calling a hardness assumption weaker must also be distinguished from calling its decision problem easier; the source's question is retained in its stated harder direction. The displayed DLIN experiment is the customary prime-order version, not a definition supplied by the short excerpt.

Short English statement

In the intended pairing-group model, is distinguishing Decision Linear tuples strictly harder than distinguishing DDH tuples? The source does not specify the group family or whether strictness means reductions, generic-model bounds, or a concrete computational separation.

Sources

• Local UnsolvedMath registry, permanent ID 8800059, source code catalogue entry; attributed to Tanja Lange; no proposal year supplied; update 2026-08-06.
• IPAM, Workshop on Number Theory and Cryptography --- Open Problems (2006), attachment 6239, PDF page 46, printed slide 44: https://www.ipam.ucla.edu/programs/workshops/workshop-i-number-theory-and-cryptography-open-problems/?tab=schedule. Registry access date 2026-07-29; PDF and legacy-PPT visual audit. Provenance reports 19 attachments, 17 PDFs and two legacy PPT decks, with repetitions and solved definitions excluded. Present status and redistribution terms require review.
• The supplied summary credits Boneh--Boyen--Shacham (2004) with DLIN and mentions generic-group analyses without full bibliographic references or exact separation theorems. Its status assessment is unverified.