Computer Science – Information Theory
Scientific paper
2011-12-10
Computer Science
Information Theory
21 pages; Submitted to IEEE Trans. on Inform. Theory; Subsection 4.3 rewritten
Scientific paper
In analogy to the well-known notion of finite--state compressibility of individual sequences, due to Lempel and Ziv, we define a similar notion of "finite-state encryptability" of an individual plaintext sequence, as the minimum asymptotic key rate that must be consumed by finite-state encrypters so as to guarantee perfect secrecy in a well-defined sense. Our main basic result is that the finite-state encryptability is equal to the finite-state compressibility for every individual sequence. This is in parallelism to Shannon's classical probabilistic counterpart result, asserting that the minimum required key rate is equal to the entropy rate of the source. However, the redundancy, defined as the gap between the upper bound (direct part) and the lower bound (converse part) in the encryption problem, turns out to decay at a different rate (in fact, much slower) than the analogous redundancy associated with the compression problem. We also extend our main theorem in several directions, allowing: (i) availability of side information (SI) at the encrypter/decrypter/eavesdropper, (ii) lossy reconstruction at the decrypter, and (iii) the combination of both lossy reconstruction and SI, in the spirit of the Wyner--Ziv problem.
No associations
LandOfFree
Perfectly secure encryption of individual sequences 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 Perfectly secure encryption of individual sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Perfectly secure encryption of individual sequences will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-381477