LRSW assumption

Given $X=g^x$, $Y=g^y$ and an oracle that answers each query $m$ with $(a,a^y,a^{x+mxy})$ for a fresh random $a$, no efficient adversary can output such a triple, with $a\ne 1$, for a nonzero $m$ it never queried.

Assumption

The assumption concerns a group generator $\mathsf{GrGen}$ that on input $1^{\lambda }$ outputs $(\mathbb{G},p,g)$, a cyclic group $\mathbb{G}$ of prime order $p$ with generator $g$.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\text{lrsw}}_{\GrGen,\calA}(\secpar)$}
\begin{algorithmic}
\State $(\GG, p, g) \gets \GrGen(1^\secpar)$; $x, y \getsr \ZZ_p$; $\calQ \gets \{\}$
\State $(m, a, b, c) \gets \calA^{\calO}(1^\secpar, \GG, p, g, g^x, g^y)$
\Return $[m \notin \calQ \wedge m \ne 0 \wedge a \ne 1 \wedge b = a^y \wedge c = a^{x + mxy}]$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\algname{Oracle}
\caption{$\calO(m)$}
\begin{algorithmic}
\State $a \getsr \GG$; $\calQ \gets \calQ \cup \{m\}$
\Return $(a, a^y, a^{x + mxy})$
\end{algorithmic}
\end{algorithm}

LRSW is hard for $\mathsf{GrGen}$ if for all efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\mathsf{GrGen},\mathcal{A}}^{\text{lrsw}}(\lambda ):=\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{GrGen},\mathcal{A}}^{\text{lrsw}}(\lambda )=1\right]$$

is negligible.

The assumption is from LRSW99, and CL04 use it in groups with a bilinear map. It is interactive: the adversary queries an oracle. Both exclusions in the winning condition are needed, since $(g,g^y,g^x)$ is a valid triple for $m=0$ and $(1,1,1)$ for every $m$ — standard.

Participates in

Builds on LRSW assumption

• Type 1 pairing + LRSW ⇒ DS (Camenisch–Lysyanskaya)

Produces LRSW assumption

• GGM ⇒ LRSW