Succinct Randomized Encodings and their Applications
Succinct Randomized Encodings and their Applications
复制标题
简洁随机编码及其应用
DOI：
10.1145/2746539.2746574
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Sidharth Telang
中科院分区：
文献类型：
--
作者：
Nir Bitansky;Sanjam Garg;Sidharth Telang
随机编码允许通过函数f和输入X给出的“复杂”计算，该计算是通过“易于计算”随机表示的“易于计算”的随机表示F（x），其分布编码f（x），而对F和x则没有透露其他任何内容现有的随机编码主要允许使用低平行复杂性编码，已证明在多方计算和平行密码学等各种强大的应用中起着作用。测量：我们构建简洁的随机编码所需的时间，在该编码的时间π和输入X给出的时间基本上独立于π的时间复杂性，并且仅取决于其空间的复杂性以及该方案保证了（π，x）的计算隐私，并且基于相对简单的电路类别的不可区分性混淆，基于该类别存在实例化多项式硬度假设对多线性图。然后，我们调用简洁的随机编码以获得多个强大的应用，包括：简洁的不可区分性混淆，其中混淆的程序IOBF（{π}）计算了与Apriori-founded的输入x的功能相同的功能大小，混淆的π大致与任何此类输入x的计算一样快。电路。简洁的功能加密，其中一个功能性的解密密钥对应于π的π（x）从APRIORI键的任何明文X的加密中，就像编码相应的comportation一样快。在任何数量的输入x的随机编码中，可以分别编码π，而不是π的时间和空间复杂性如果验证π和输入X的长度计算的结果与编码相应的计算一样快简洁的随机编码或任何上述应用仅基于各种非标准知识假设而知道。乱七八糟的计算，没有揭示有关用于垃圾的秘密随机性的任何内容。
A randomized encoding allows to express a "complex" computation, given by a function f and input x, by a "simple to compute" randomized representation f(x) whose distribution encodes f(x), while revealing nothing else regarding f and x. Existing randomized encodings, geared mostly to allow encoding with low parallel-complexity, have proven instrumental in various strong applications such as multiparty computation and parallel cryptography. This work focuses on another natural complexity measure: the time required to encode. We construct succinct randomized encodings where the time to encode a computation, given by a program Π and input x, is essentially independent of Π's time complexity, and only depends on its space complexity, as well as the size of its input, output, and description. The scheme guarantees computational privacy of (Π,x), and is based on indistinguishability obfuscation for a relatively simple circuit class, for which there exist instantiations based on polynomial hardness assumptions on multi-linear maps. We then invoke succinct randomized encodings to obtain several strong applications, including: Succinct indistinguishability obfuscation, where the obfuscated program IObf({Π}) computes the same function as Π for inputs x of apriori-bounded size. Obfuscating Π is roughly as fast as encoding the computation of Π on any such input x. Here we also require subexponentially-secure indistinguishability obfuscation for circuits. Succinct functional encryption, where a functional decryption key corresponding to Π allows decrypting Π(x) from encryptions of any plaintext x of apriori-bounded size. Key derivation is as fast as encoding the corresponding computation. Succinct reusable garbling, a stronger form of randomized encodings where any number of inputs x can be encoded separately of Π, independently of Π's time and space complexity. Publicly-verifiable 2-message delegation where verifying the result of a long computation given by Π and input x is as fast as encoding the corresponding computation. We also show how to transform any 2-message delegation scheme to an essentially non-interactive system where the verifier message is reusable. Previously, succinct randomized encodings or any of the above applications were only known based on various non-standard knowledge assumptions. At the heart of our techniques is a generic method of compressing a piecemeal garbled computation, without revealing anything about the secret randomness utilized for garbling.