Paper 2019/1085

Matrix PRFs: Constructions, Attacks, and Applications to Obfuscation

Yilei Chen, Minki Hhan, Vinod Vaikuntanathan, and Hoeteck Wee

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 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in Tcc 2019
Keywords
Pseudorandom FunctionsObfuscation
Contact author(s)
chenyilei ra @ gmail com
hhan_ @ snu ac kr
vinodv @ csail mit edu
wee @ di ens fr
History
2019-09-25: received
Short URL
https://ia.cr/2019/1085
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1085,
      author = {Yilei Chen and Minki Hhan and Vinod Vaikuntanathan and Hoeteck Wee},
      title = {Matrix PRFs: Constructions, Attacks, and Applications to Obfuscation},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1085},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1085}},
      url = {https://eprint.iacr.org/2019/1085}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.