Non-malleable Codes, Extractors and Secret Sharing for Interleaved Tampering and Composition of Tampering
Non-malleable Codes, Extractors and Secret Sharing for Interleaved Tampering and Composition of Tampering
复制标题
用于交错篡改和篡改组合的不可延展代码、提取器和秘密共享
DOI：
10.1007/978-3-030-64381-2_21
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Li, Xin
中科院分区：
文献类型：
--
作者：
Chattopadhyay, Eshan;Li, Xin
不可延展码由Dziembowski，Pietrzak和Wichs（JACM 2018）引入，作为标准纠错码的推广，以处理码字上严重形式的篡改。这个概念吸引了大量的研究，导致了各种显式构造，这些构造在防篡改密码学中得到了应用，并与理论计算机科学中的其他伪随机对象建立了联系。我们继续在信息论环境下对非延展码的显式构造进行研究，并给出了几类新的篡改函数的显式构造。这些类严格概括了几个以前研究过的篡改函数类，特别是扩展了研究得很好的分裂状态模型，这是一个“划分”的模型，在这个意义上说，码字是partitioneda priorinto不相交的区间篡改。具体来说，我们给出了以下几类篡改函数的显式不可延展码：交织分裂状态篡改：攻击者以未知的方式对码字进行划分，然后通过分裂状态篡改函数进行篡改。在该模型中，码字首先被分裂状态攻击者篡改，然后整个篡改码字被仿射函数进一步篡改。事实上，我们的结果更强，我们可以处理仿射篡改与交织分裂状态篡改组成。我们的结果是第一个明确的结构，不可延展的代码在任何这些篡改模型。作为应用，他们还直接给出了分裂状态联合篡改模型和分裂状态联合篡改与仿射篡改组合的强模型中的不可延展的二进制秘密共享方案。所有这些结果都来自于无籽不可延展提取器的显式构造，我们相信这些结果是独立的。使用我们的技术，我们还给出了一个改进的无籽提取器，用于两个独立源的未知交织。
Non-malleable codes were introduced by Dziembowski, Pietrzak, and Wichs (JACM 2018) as a generalization of standard error correcting codes to handle severe forms of tampering on codewords. This notion has attracted a lot of recent research, resulting in various explicit constructions, which have found applications in tamper-resilient cryptography and connections to other pseudorandom objects in theoretical computer science. We continue the line of investigation on explicit constructions of non-malleable codes in the information theoretic setting, and give explicit constructions for several new classes of tampering functions. These classes strictly generalize several previously studied classes of tampering functions, and in particular extend the well studied split-state model which is a “compartmentalized” model in the sense that the codeword is partitioneda priorinto disjoint intervals for tampering. Specifically, we give explicit non-malleable codes for the following classes of tampering functions.Interleaved split-state tampering: Here the codeword is partitioned in an unknown way by an adversary, and then tampered with by a split-state tampering function.Affine tampering composed with split-state tampering: In this model, the codeword is first tampered with by a split-state adversary, and then the whole tampered codeword is further tampered with by an affine function. In fact our results are stronger, and we can handle affine tampering composed with interleaved split-state tampering.Our results are the first explicit constructions of non-malleable codes in any of these tampering models. As applications, they also directly give non-malleable secret-sharing schemes withbinary sharesin the split-state joint tampering model and the stronger model of affine tampering composed with split-state joint tampering. We derive all these results from explicit constructions of seedless non-malleable extractors, which we believe are of independent interest.Using our techniques, we also give an improved seedless extractor for an unknown interleaving of two independent sources.
登录
查看更多内容
mathsf AC^0 AC 0 中的近最优秘密共享和纠错码
DOI：
10.1007/978-3-319-70503-3_14
发表时间：
2017
期刊：
Biomedicine & pharmacotherapy = Biomedecine & pharmacotherapie
影响因子：
--
作者：
Kuan Cheng;Yuval Ishai;Xin Li
通讯作者：
Xin Li
低权重仿射源提取器
DOI：
10.1109/ccc.2009.36
发表时间：
2009
期刊：
2009 24th Annual IEEE Conference on Computational Complexity
影响因子：
--
作者：
Anup Rao
通讯作者：
Anup Rao
不可延展代码的容量
影响因子：
2.5
作者：
Mahdi Cheraghchi;V. Guruswami
通讯作者：
V. Guruswami
与二进制共享的秘密共享
DOI：
10.4230/lipics.itcs.2019.53
发表时间：
2018
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
Fuchun Lin;Mahdi Cheraghchi;V. Guruswami;R. Safavi;Huaxiong Wang
通讯作者：
Huaxiong Wang
DOI：
10.1145/3055399.3055486
发表时间：
2016-07
期刊：
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Xin Li
通讯作者：
Xin Li