On the Complexity of Decomposable Randomized Encodings, Or: How Friendly Can a Garbling-Friendly PRF Be?
On the Complexity of Decomposable Randomized Encodings, Or: How Friendly Can a Garbling-Friendly PRF Be?
复制标题
关于可分解随机编码的复杂性，或者：对乱码友好的 PRF 能有多友好？
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
T. Malkin
中科院分区：
文献类型：
--
作者：
Marshall Ball;Justin Holmgren;Yuval Ishai;Tianren Liu;T. Malkin
乱码方案，也被称为可分解随机编码（DRE），在密码学中有许多应用。然而，尽管在构建这样的方案方面做了大量的工作，21人们对它们的局限性知之甚少。22我们对布尔函数的DRE复杂度进行了系统的研究，得到了以下23个主要结果：我们使用了经典的ne<e:1> iporuk 25下限技术。Akad。Nauk SSSR ' 66]显示了26个显式布尔函数的任意DRE大小的Ω（n 2 / log n）下界。对于一些自然函数，我们得到了一个相应的27上界，从而使它们的DRE复杂度达到多对数因子。在我们的工作之前，即使是非显式函数，也没有已知的28个超线性下界。29防乱码prf。我们证明了任何指数安全PRF都具有Ω（n 2 / log n） DRE 30大小，并提出了一个似是而非的“乱码最优”PRF，它几乎满足这个31界。这个候选者通过自然32证明技术建立了超二次DRE下界的障碍。相反，我们展示了一个具有近指数安全性33和线性DRE大小的弱PRF的候选。34我们的结果建立了几个定性分离，包括布尔函数的35个计算和信息论DRE大小之间的近二次分离，以及36个弱PRFs和强PRFs的DRE大小之间的近二次分离。37
19 Garbling schemes, also known as decomposable randomized encodings (DRE), have found many 20 applications in cryptography. However, despite a large body of work on constructing such schemes, 21 very little is known about their limitations. 22 We initiate a systematic study of the DRE complexity of Boolean functions, obtaining the 23 following main results: 24 Near-quadratic lower bounds . We use a classical lower bound technique of Nečiporuk 25 [Dokl. Akad. Nauk SSSR ’66] to show an Ω( n 2 / log n ) lower bound on the size of any DRE for 26 many explicit Boolean functions. For some natural functions, we obtain a corresponding upper 27 bound, thus settling their DRE complexity up to polylogarithmic factors. Prior to our work, no 28 superlinear lower bounds were known, even for non-explicit functions. 29 Garbling-friendly PRFs. We show that any exponentially secure PRF has Ω( n 2 / log n ) DRE 30 size, and present a plausible candidate for a “garbling-optimal” PRF that nearly meets this 31 bound. This candidate establishes a barrier for super-quadratic DRE lower bounds via natural 32 proof techniques. In contrast, we show a candidate for a weak PRF with near-exponential security 33 and linear DRE size. 34 Our results establish several qualitative separations, including near-quadratic separations between 35 computational and information-theoretic DRE size of Boolean functions, and between DRE size of 36 weak vs. strong PRFs. 37