International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Matrix PRFs: Constructions, Attacks, and Applications to Obfuscation

Authors:
Yilei Chen
Minki Hhan
Vinod Vaikuntanathan
Hoeteck Wee
Download:
DOI: 10.1007/978-3-030-36030-6_3
Search ePrint
Search Google
Abstract: 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 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.
BibTeX
@article{tcc-2019-29967,
  title={Matrix PRFs: Constructions, Attacks, and Applications to Obfuscation},
  booktitle={Theory of Cryptography},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  volume={11891},
  pages={55-80},
  doi={10.1007/978-3-030-36030-6_3},
  author={Yilei Chen and Minki Hhan and Vinod Vaikuntanathan and Hoeteck Wee},
  year=2019
}