Matrix PRFs: Constructions, Attacks, and Applications to Obfuscation
© 2019, International Association for Cryptologic Research. 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 c...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Book |
| Language: | English |
| Published: |
Springer International Publishing
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137165 |
| _version_ | 1811071681972666368 |
|---|---|
| author | Chen, Yilei Hhan, Minki Vaikuntanathan, Vinod Wee, Hoeteck |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Chen, Yilei Hhan, Minki Vaikuntanathan, Vinod Wee, Hoeteck |
| author_sort | Chen, Yilei |
| collection | MIT |
| description | © 2019, International Association for Cryptologic Research. 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 this means that any matrix PRF based on constant-width matrices must read each input bit ωc 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. |
| first_indexed | 2024-09-23T08:54:59Z |
| format | Book |
| id | mit-1721.1/137165 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T08:54:59Z |
| publishDate | 2021 |
| publisher | Springer International Publishing |
| record_format | dspace |
| spelling | mit-1721.1/1371652023-04-14T17:58:28Z Matrix PRFs: Constructions, Attacks, and Applications to Obfuscation Chen, Yilei Hhan, Minki Vaikuntanathan, Vinod Wee, Hoeteck Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © 2019, International Association for Cryptologic Research. 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 this means that any matrix PRF based on constant-width matrices must read each input bit ωc 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. 2021-11-02T18:48:07Z 2021-11-02T18:48:07Z 2019 2021-04-15T18:30:17Z Book http://purl.org/eprint/type/ConferencePaper 0302-9743 1611-3349 https://hdl.handle.net/1721.1/137165 Chen, Yilei, Hhan, Minki, Vaikuntanathan, Vinod and Wee, Hoeteck. 2019. "Matrix PRFs: Constructions, Attacks, and Applications to Obfuscation." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 11891. en 10.1007/978-3-030-36030-6_3 Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer International Publishing Other repository |
| spellingShingle | Chen, Yilei Hhan, Minki Vaikuntanathan, Vinod Wee, Hoeteck Matrix PRFs: Constructions, Attacks, and Applications to Obfuscation |
| title | Matrix PRFs: Constructions, Attacks, and Applications to Obfuscation |
| title_full | Matrix PRFs: Constructions, Attacks, and Applications to Obfuscation |
| title_fullStr | Matrix PRFs: Constructions, Attacks, and Applications to Obfuscation |
| title_full_unstemmed | Matrix PRFs: Constructions, Attacks, and Applications to Obfuscation |
| title_short | Matrix PRFs: Constructions, Attacks, and Applications to Obfuscation |
| title_sort | matrix prfs constructions attacks and applications to obfuscation |
| url | https://hdl.handle.net/1721.1/137165 |
| work_keys_str_mv | AT chenyilei matrixprfsconstructionsattacksandapplicationstoobfuscation AT hhanminki matrixprfsconstructionsattacksandapplicationstoobfuscation AT vaikuntanathanvinod matrixprfsconstructionsattacksandapplicationstoobfuscation AT weehoeteck matrixprfsconstructionsattacksandapplicationstoobfuscation |