ROS problem

The $\ell$-ROS (Random inhomogeneities in an Overdetermined Solvable system of linear equations) problem asks, given a random oracle $H_{\mathrm{ros}}:{\mathbb{Z}}_p^{\ell }\to {\mathbb{Z}}_p$, for $\ell +1$ distinct vectors ${\rho }_i\in {\mathbb{Z}}_p^{\ell }$ and one vector $c\in {\mathbb{Z}}_p^{\ell }$ with $H_{\mathrm{ros}}({\rho }_i)=⟨{\rho }_i,c⟩$ for every $i$. The problem goes back to Sch01; this is the formulation of FPS20 and BLLOR21.

Assumption

The problem is parameterized by a prime $p=p(\lambda )$, the order of the group of the blind signature scheme it is used for, and the number $\ell =\ell (\lambda )$ of signing sessions.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\text{ros}}_{p,\ell,\calA}(\secpar)$}
\begin{algorithmic}
\State $H_{\mathrm{ros}} \getsr \Funcs(\ZZ_p^\ell, \ZZ_p)$
\Comment{sampled lazily}
\State $(\rho_1, \ldots, \rho_{\ell+1}, c) \gets \calA^{H_{\mathrm{ros}}}(1^\secpar)$
\Return $\big[\rho_1, \ldots, \rho_{\ell+1} \text{ distinct} \land \forall_{i \in [\ell+1]}~H_{\mathrm{ros}}(\rho_i) = \langle \rho_i, c \rangle\big]$
\end{algorithmic}
\end{algorithm}

$\ell$-ROS is hard for $p$ if for all efficient $\mathcal{A}$,

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

is negligible. ROS is hard for $p$ if $\ell$-ROS is hard for $p$ for every polynomial $\ell$.

Known Results

• In the algebraic group model with a random oracle, blind Schnorr signatures are one-more unforgeable against $\ell$ concurrent sessions if OMDL and $\ell$-ROS are hard (OMDL + ROS ⇒ Blind Schnorr signatures) — FPS20.

Variations

The clause variant of blind Schnorr signatures of FPS20 is proved secure under a problem related to ROS that appears much harder — FPS20.

Attacks

• Polynomial time for $\ell >\log p$: $\ell$-ROS is solvable in polynomial time when $\ell >\log p$, so ROS is not hard, and blind Schnorr signatures are forgeable with $\ell$ concurrent sessions — BLLOR21.
• Sub-exponential time for smaller $\ell$: combining this attack with the generalized-birthday algorithm of Wag02 gives sub-exponential algorithms for $\ell$-ROS in every dimension $\ell$ — BLLOR21.

Participates in

Builds on ROS problem

• OMDL + ROS ⇒ Blind Schnorr signatures