Non-Malleable Codes for Space-Bounded Tampering
Non-Malleable Codes for Space-Bounded Tampering
复制标题
用于空间限制篡改的不可延展代码
DOI：
10.1007/978-3-319-63715-0_4
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
D. Venturi
中科院分区：
文献类型：
--
作者：
S. Faust;K. Hostáková;P. Mukherjee;D. Venturi
非延展性代码-由Dziembowski，Pietrzak和Wichs在ICS 2010上介绍-是无密钥编码方案，其中Mauling试图对给定消息进行编码，w.r.t.某些类别的篡改对手导致与原始消息相同或不相关的解码值。这种代码对于保护任意密码原语免受针对存储器的篡改攻击非常有用。显然，如果篡改对手的类别包括解码和编码算法，那么不可延展性是无望的。为了绕过这一障碍，过去的大多数研究都集中在为各种篡改类别设计不可延展的代码，尽管假设对手无法解码。然而，在许多具体的设置，这种假设是不现实的。在本文中，我们探讨了一个特定的情况下，篡改对手的类自然包括解码（但不是编码）算法。特别是，我们考虑一类的对手，在内存/空间方面的限制。我们的主要贡献可以概括如下：我们发起了一个一般性的研究不可延展的代码抵抗空间有界篡改。在我们的模型中，编码过程需要很大的空间，但解码可以在很小的空间中完成，因此也可以由对手执行。不幸的是，在这样的环境中，不可能实现标准意义上的不可延展性，我们需要以稍微弱一些的安全保证为目标。简而言之，我们的主要概念（dubbedleaky空间有界的不可延展性）确保这是最好的对手可以做的，在空间有界的篡改攻击可以模拟给定少量的泄漏的编码值。我们的计划是基于任何空间证明（PoS）-最近提出的Atenieseet等人的概念。(SCN 2014）和Dziembowskiet al.（2015年）-满足健全性的变体。正如我们所展示的，我们的范例可以通过扩展Ren和Devadas（TCC 2016-A）对PoS构造的分析来实例化，基于所谓的局部扩展图堆栈。最后，我们展示了我们的不可延展性风格产生了对内存篡改攻击的自然安全保证，其中可以用密钥上的少量泄漏来保护免受空间限制的篡改攻击。
Non-malleable codes—introduced by Dziembowski, Pietrzak and Wichs at ICS 2010—are key-less coding schemes in which mauling attempts to an encoding of a given message, w.r.t. some class of tampering adversaries, result in a decoded value that is either identical or unrelated to the original message. Such codes are very useful for protecting arbitrary cryptographic primitives against tampering attacks against the memory. Clearly, non-malleability is hopeless if the class of tampering adversaries includes the decoding and encoding algorithm. To circumvent this obstacle, the majority of past research focused on designing non-malleable codes for various tampering classes, albeit assuming that the adversary is unable to decode. Nonetheless, in many concrete settings, this assumption is not realistic.In this paper, we explore one particular such scenario where the class of tampering adversaries naturally includes the decoding (but not the encoding) algorithm. In particular, we consider the class of adversaries that are restricted in terms of memory/space. Our main contributions can be summarized as follows:We initiate a general study of non-malleable codes resisting space-bounded tampering. In our model, the encoding procedure requires large space, but decoding can be done in small space, and thus can be also performed by the adversary. Unfortunately, in such a setting it is impossible to achieve non-malleability in the standard sense, and we need to aim for slightly weaker security guarantees. In a nutshell, our main notion (dubbedleaky space-bounded non-malleability) ensures that this is the best the adversary can do, in that space-bounded tampering attacks can be simulated given a small amount of leakage on the encoded value.We provide a simple construction of a leaky space-bounded non-malleable code. Our scheme is based on any Proof of Space (PoS)—a concept recently put forward by Atenieseet al.(SCN 2014) and Dziembowskiet al.(CRYPTO 2015)—satisfying a variant of soundness. As we show, our paradigm can be instantiated by extending the analysis of the PoS construction by Ren and Devadas (TCC 2016-A), based on so-called stacks of localized expander graphs.Finally, we show that our flavor of non-malleability yields a natural security guarantee against memory tampering attacks, where one can trade a small amount of leakage on the secret key for protection against space-bounded tampering attacks.
登录
查看更多内容
DOI：
10.1016/j.tcs.2015.05.026
发表时间：
2015-08
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
Rishiraj Bhattacharyya;Pratyay Mukherjee
通讯作者：
Rishiraj Bhattacharyya;Pratyay Mukherjee
防篡改和泄漏的冯诺依曼架构
DOI：
10.1007/978-3-662-46447-2_26
发表时间：
2015
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Sebastian Faust;Pratyay Mukherjee;J. Nielsen;D. Venturi
通讯作者：
D. Venturi
不可延展代码的容量
影响因子：
2.5
作者：
Mahdi Cheraghchi;V. Guruswami
通讯作者：
V. Guruswami
DOI：
10.1007/978-3-642-32009-5_30
发表时间：
2012-08
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
Feng-Hao Liu;Anna Lysyanskaya
通讯作者：
Feng-Hao Liu;Anna Lysyanskaya
DOI：
10.1016/j.tcs.2016.11.016
发表时间：
2017-01
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
Antonio Faonio;J. Nielsen;D. Venturi
通讯作者：
Antonio Faonio;J. Nielsen;D. Venturi