Geodesic
Kolmogorov complexity and cryptography
Trudy Matematicheskogo Instituta imeni V.A. Steklova, Algorithmic aspects of algebra and logic, Tome 274 (2011), pp. 210-221 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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. 
@article{TM_2011_274_a11,
     author = {Andrej A. Muchnik},
     title = {Kolmogorov complexity and cryptography},
     journal = {Trudy Matematicheskogo Instituta imeni V.A. Steklova},
     pages = {210--221},
     year = {2011},
     volume = {274},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TM_2011_274_a11/}
}
TY  - JOUR
AU  - Andrej A. Muchnik
TI  - Kolmogorov complexity and cryptography
JO  - Trudy Matematicheskogo Instituta imeni V.A. Steklova
PY  - 2011
SP  - 210
EP  - 221
VL  - 274
UR  - http://geodesic.mathdoc.fr/item/TM_2011_274_a11/
LA  - ru
ID  - TM_2011_274_a11
ER  - 
%0 Journal Article
%A Andrej A. Muchnik
%T Kolmogorov complexity and cryptography
%J Trudy Matematicheskogo Instituta imeni V.A. Steklova
%D 2011
%P 210-221
%V 274
%U http://geodesic.mathdoc.fr/item/TM_2011_274_a11/
%G ru
%F TM_2011_274_a11
Andrej A. Muchnik. Kolmogorov complexity and cryptography. Trudy Matematicheskogo Instituta imeni V.A. Steklova, Algorithmic aspects of algebra and logic, Tome 274 (2011), pp. 210-221. http://geodesic.mathdoc.fr/item/TM_2011_274_a11/

[1] Muchnik An.A., “Conditional complexity and codes”, Theor. Comput. Sci., 271:1–2 (2002), 97–109 ; Muchnik An., Semenov A., Multi-conditional descriptions and codes in Kolmogorov complexity, Tech. Rep. N 15, Jan. 27, 2000 | DOI | MR | Zbl

[2] Shen A., Vereshchagin N., “Logical operations and Kolmogorov complexity”, Theor. Comput. Sci., 271:1–2 (2002), 125–129 | DOI | MR | Zbl