We initiate a systematic study of pseudorandom functions (PRFs) that are
computable by simple matrix branching programs; we refer to these objects as
“matrix PRFs”. Matrix PRFs are attractive due to their simplicity, strong
connections to complexity theory and group theory, and recent applications in
program obfuscation. Our main results are: * We present constructions of matrix PRFs based on the conjectured hardness of
some simple computational problems pertaining to matrix products. * We show that any matrix PRF that is computable by a read-c, width w
branching program can be broken in time poly(w^c); this means that any matrix
PRF based on constant-width matrices must read each input bit omega(log
lambda) times. Along the way, we simplify the “tensor switching lemmas”
introduced in previous IO attacks. * We show that a subclass of the candidate local-PRG proposed by Barak et al.
[Eurocrypt 2018] can be broken using simple matrix algebra. * We show that augmenting the CVW18 IO candidate with a matrix PRF provably
immunizes the candidate against all known algebraic and statistical zeroizing
attacks, as captured by a new and simple adversarial model.