2026-07-22T12:15:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11771 2024-03-06T10:48:40Z ddc:004 open_access

On the Complexity of Decomposable Randomized Encodings, Or: How Friendly Can a Garbling-Friendly PRF Be? Ball, Marshall Holmgren, Justin Ishai, Yuval Liu, Tianren Malkin, Tal Randomized Encoding Private Simultaneous Messages Garbling schemes, also known as decomposable randomized encodings (DRE), have found many applications in cryptography. However, despite a large body of work on constructing such schemes, very little is known about their limitations. We initiate a systematic study of the DRE complexity of Boolean functions, obtaining the following main results: - Near-quadratic lower bounds. We use a classical lower bound technique of Nečiporuk [Dokl. Akad. Nauk SSSR '66] to show an Ω(n²/log n) lower bound on the size of any DRE for many explicit Boolean functions. For some natural functions, we obtain a corresponding upper bound, thus settling their DRE complexity up to polylogarithmic factors. Prior to our work, no superlinear lower bounds were known, even for non-explicit functions. - Garbling-friendly PRFs. We show that any exponentially secure PRF has Ω(n²/log n) DRE size, and present a plausible candidate for a "garbling-optimal" PRF that nearly meets this bound. This candidate establishes a barrier for super-quadratic DRE lower bounds via natural proof techniques. In contrast, we show a candidate for a weak PRF with near-exponential security and linear DRE size. Our results establish several qualitative separations, including near-quadratic separations between computational and information-theoretic DRE size of Boolean functions, and between DRE size of weak vs. strong PRFs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marshall Ball and Justin Holmgren and Yuval Ishai and Tianren Liu and Tal Malkin 2020 Is Part Of LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2020.86 urn:nbn:de:0030-drops-117714 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.86 eng https://creativecommons.org/licenses/by/3.0/legalcode