Non-malleable Codes for Bounded Parallel-Time Tampering
Non-malleable Codes for Bounded Parallel-Time Tampering
复制标题
用于有界并行时间篡改的不可延展代码
DOI：
10.1007/978-3-030-84252-9_18
复制
发表时间：
2021
影响因子：
--
通讯作者：
R. Pass
中科院分区：
文献类型：
--
作者：
Dana Dachman;Ilan Komargodski;R. Pass
不可延展的代码允许人们以这样一种方式对数据进行编码：一旦码字被篡改，修改后的码字要么是原始消息的编码，要么是完全不相关的编码。自从 Dziembowski、Pietrzak 和 Wichs（ICS '10 和 J. ACM '18）引入这一概念以来，已经有大量的工作实现了此类编码方案，以防止各种类型的篡改功能。众所周知，不存在能够抵御所有多项式大小篡改函数的有效的不可延展代码。然而，没有已知的不可延展的有界多项式大小攻击者的代码，并且获取这样的代码一直是一个主要的开放问题。我们提出了第一个构造的不可延展的代码，该代码可以安全地抵御具有有限并行时间的所有多项式大小篡改函数。这是一个比所有有界多项式大小函数更大的类。特别是，此类包括非统一的所有函数（以及更多）。我们的构建是在普通模型（即无可信设置）中进行的，并且依赖于多种加密假设，例如无密钥哈希函数、时间锁定谜题以及其他标准假设。此外，我们的构造具有几个吸引人的特性：编码的复杂性与篡改函数的类别无关，并且我们可以获得（亚）指数级的小误差。
Non-malleable codes allow one to encode data in such a way that once a codeword is being tampered with, the modified codeword is either an encoding of the original message, or a completely unrelated one. Since the introduction of this notion by Dziembowski, Pietrzak, and Wichs (ICS ’10 and J. ACM ’18), there has been a large body of works realizing such coding schemes secure against various classes of tampering functions. It is well known that there is no efficient non-malleable code secure against all polynomial size tampering functions. Nevertheless, no code which is non-malleable forboundedpolynomial size attackers is known and obtaining such a code has been a major open problem.We present the first construction of a non-malleable code secure against all polynomial size tampering functions that have bounded parallel time. This is an even larger class than all bounded polynomial size functions. In particular, this class includes all functions in non-uniform(and much more). Our construction is in the plain model (i.e., no trusted setup) and relies on several cryptographic assumptions such as keyless hash functions, time-lock puzzles, as well as other standard assumptions. Additionally, our construction has several appealing properties: the complexity of encoding is independent of the class of tampering functions and we can obtain (sub-)exponentially small error.
用于空间限制篡改的不可延展代码
DOI：
10.1007/978-3-319-63715-0_4
发表时间：
2017
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
S. Faust;K. Hostáková;P. Mukherjee;D. Venturi
通讯作者：
D. Venturi