k-Lin ⇒ VRF

Standard model · HJ16 · security loss: polynomial

Statement

In symmetric bilinear groups, the $k$-linear assumption for any $k\ge 2$, in particular decision linear (DLIN, $k=2$), implies a VRF with exponential-size input space and full adaptive security — HJ16.

Notes

• Under DLIN, proofs shrink to $\ell$ group elements for any $\ell \in \omega (1)$, down from $\Omega (L)$ for input length $L$ — Koh19.