GGM ⇒ LRSW

Free reduction · generic group model · LRSW99

Statement

In the generic group model, the LRSW assumption holds in groups of prime order $p$: every generic algorithm that makes polynomially many group-oracle queries and queries to the LRSW oracle outputs a tuple $(m,a,a^y,a^{x+mxy})$ with $m\ne 0$, $a\ne 1$ and $m$ never queried only with negligible probability — LRSW99.

Notes

• The generic model of LRSW99 has no pairing oracle, so the bound says nothing about generic algorithms that may also evaluate a bilinear map — LRSW99.
• In groups with a symmetric pairing, LRSW gives Camenisch–Lysyanskaya signatures (Type 1 pairing + LRSW ⇒ DS) — CL04.