Kolmogorov complexity and cryptography

Andrej A. Muchnik

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Algorithmic aspects of algebra and logic, Tome 274 (2011), pp. 210-221

Résumé

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.