Kolmogorov complexity and cryptography
Kolmogorov complexity and cryptography
复制标题
柯尔莫哥洛夫复杂性和密码学
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
A. Muchnik
中科院分区：
文献类型：
--
作者：
A. Muchnik
我们考虑（在算法信息论的框架内）以下类型的问题：为具有（或不具有）特定先验信息的接收者构建包含不同数量信息的消息。例如，假设接收者知道某个字符串a，我们想向他发送一些信息，使他能够重构某个字符串b（使用a）。另一方面，这个信息本身不应该允许窃听者（他不知道a）重构b。这确实是可能的（如果字符串a和b不是太简单的话）。然后我们考虑这个问题更复杂的版本。如果窃听者知道某个字符串c呢？我们的信息应该有多长？我们提供了一些保证多项式大小消息存在的条件；我们证明，如果没有这些条件，这并不总是可能的。
We consider (in the framework of algorithmic information theory) questions of the following type: construct a message that contains different amounts of information for recipients that have (or do not have) certain a priori information. Assume, for example, that a recipient knows some string a and we want to send him some information that allows him to reconstruct some string b (using a). On the other hand, this information alone should not allow the eavesdropper (who does not know a) to reconstruct b. This is indeed possible (if the strings a and b are not too simple). Then we consider more complicated versions of this question. What if the eavesdropper knows some string c? How long should our message be? We provide some conditions that guarantee the existence of a polynomial-size message; we show then that without these conditions this is not always possible.