Weak alternating moduli ⇒ weak PRF

Fully-black-box reduction · standard model · BIP+18 · security loss: additive $q^2/2^{n+1}$ for $q$ samples (repeated inputs)

Statement

The weak alternating moduli assumption asserts that for $f_A(x)=B(Ax\mathrm{mod}2)\mathrm{mod}3$, with secret key $A\stackrel{\$}{\leftarrow }{\mathbb{Z}}_2^{m\times n}$ and public $B\stackrel{\$}{\leftarrow }{\mathbb{Z}}_3^{\ell \times m}$, samples $(x,f_A(x))$ for uniform $x\stackrel{\$}{\leftarrow }\{0,1{\}}^n$ are indistinguishable from $(x,y)$ for uniform $y\stackrel{\$}{\leftarrow }{\mathbb{Z}}_3^{\ell }$. Under it, the family with $\mathsf{KeyGen}$ sampling $A$ and $\mathsf{Eval}(A,x)=f_A(x)$ is a weak PRF — BIP+18.

Sketch

The weak-AM game for $f_A$ and the weak-PRF game for $(\mathsf{KeyGen},\mathsf{Eval})$ coincide in world 0. In world 1 they differ only when a sampled input repeats: the weak-PRF oracle answers a repeated $x$ with the same $R(x)$, the weak-AM oracle with a fresh $y$. Over $q$ samples this costs an additive $q^2/2^{n+1}$, negligible for $n=\omega (\log \lambda )$.

Notes

• BIP+18 conjecture only this random-input form — BIP+18. The chosen-input variant fails for $f_A$, since $f_A(0^n)=0$ for every key.