Computer Science – Cryptography and Security
Scientific paper
2011-06-27
Computer Science
Cryptography and Security
In Russian and English: English text follows the Russian one
Scientific paper
This paper contains some results of An.A.Muchnik (1958-2007) reported in his talks at the Kolmogorov seminar (Moscow State Lomonosov University, Math. Department, Logic and Algorithms theory division, March 11, 2003 and April 8, 2003) but not published at that time. These results were stated (without proofs) in the joint talk of Andrej Muchnik and Alexei Semenov at Dagstuhl Seminar 03181, 27.04.2003-03.05.2003. This text was prepared by Alexey Chernov and Alexander Shen in 2008-2009. 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 the recipient knows some string $a$, and we want to send her some information that allows her 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$. It 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 be our message? 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.
No associations
LandOfFree
Kolmogorov complexity and cryptography does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Kolmogorov complexity and cryptography, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Kolmogorov complexity and cryptography will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-638840