Kolmogorov complexity and cryptography
Andrej Muchnik · Proceedings of the Steklov Institute of Mathematics · 2011
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.