Incompressible Encodings
Incompressible Encodings
复制标题
不可压缩编码
DOI：
10.1007/978-3-030-56784-2_17
复制
发表时间：
2020
影响因子：
11.1
通讯作者：
Daniel Wichs
中科院分区：
文献类型：
--
作者：
T. Moran;Daniel Wichs
.不可压缩编码可以概率性地将一些数据m编码成码字c，码字c不会大得多。任何人都可以解码码字c以恢复原始数据m。然而，码字c不能被有效地压缩，即使原始数据m被给予侧边的解压缩过程。换句话说，c是m的有效可解码表示，但即使给定m，也是计算上不可压缩的。如果许多编码不能同时压缩，则不可压缩编码是可组合的。Damg Bracard，Ganesh和Orlandi最近的工作（2019年）定义了一种不可压缩编码的变体，作为“复制存储证明”的构建块。他们在一个理想的置换模型中构造了不可压缩的编码，但如果它们可以在标准假设下构造，甚至在更基本的随机预言模型中构造，则仍然是开放的。在这项工作中，我们对不可压缩编码进行了全面的研究，作为独立兴趣的原语，并给出了新的构造，否定结果和应用：
. An incompressible encoding can probabilistically encode some data m into a codeword c , which is not much larger. Anyone can decode the codeword c to recover the original data m . However, the codeword c cannot be efficiently compressed, even if the original data m is given to the decompression procedure on the side. In other words, c is an efficiently decodable representation of m , yet is computationally incompressible even given m . An incompressible encoding is composable if many encodings cannot be simultaneously compressed. The recent work of Damg˚ard, Ganesh and Orlandi (CRYPTO ’19) de-fined a variant of incompressible encodings as a building block for “proofs of replicated storage”. They constructed incompressible encodings in an ideal permutation model, but it was left open if they can be constructed under standard assumptions, or even in the more basic random-oracle model. In this work, we undertake the comprehensive study of incompressible encodings as a primitive of independent interest and give new constructions, negative results and applications:
影响因子：
3
作者：
Eike Kiltz;Adam O'Neill;Adam D. Smith
通讯作者：
Eike Kiltz;Adam O'Neill;Adam D. Smith