Paper 2013/184

The Vernam cipher is robust to small deviations from randomness

Boris Ryabko

Abstract

The Vernam cipher (or one-time pad) has played an important rule in cryptography because it is a perfect secrecy system. For example, if an English text (presented in binary system) $X_1 X_2 ... $ is enciphered according to the formula $Z_i = (X_i + Y_i) \mod 2 $, where $Y_1 Y_2 ...$ is a key sequence generated by the Bernoulli source with equal probabilities of 0 and 1, anyone who knows $Z_1 Z_2 ... $ has no information about $X_1 X_2 ... $ without the knowledge of the key $Y_1 Y_2 ...$. (The best strategy is to guess $X_1 X_2 ... $ not paying attention to $Z_1 Z_2 ... $.) But what should one say about secrecy of an analogous method where the key sequence $Y_1 Y_2 ...$ is generated by the Bernoulli source with a small bias, say, $P(0) = 0.49, $ $ P(1) = 0.51$? To the best of our knowledge, there are no theoretical estimates for the secrecy of such a system, as well as for the general case where $X_1 X_2 ... $ (the plaintext) and key sequence are described by stationary ergodic processes. We consider the running-key ciphers where the plaintext and the key are generated by stationary ergodic sources and show how to estimate the secrecy of such systems. In particular, it is shown that, in a certain sense, the Vernam cipher is robust to small deviations from randomness.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
running-key cipherVernam cipherShannon entropyunconditional secrecy
Contact author(s)
boris @ ryabko net
History
2013-04-02: revised
2013-04-01: received
See all versions
Short URL
https://ia.cr/2013/184
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/184,
      author = {Boris Ryabko},
      title = {The Vernam cipher is  robust to small deviations from randomness},
      howpublished = {Cryptology ePrint Archive, Paper 2013/184},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/184}},
      url = {https://eprint.iacr.org/2013/184}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.