Paper 2022/571

Entropically secure cipher for messages generated by Markov chains with unknown statistics

Boris Ryabko

Abstract

In 2002, Russell and Wang proposed a definition of entropic security, which was developed within the framework of secret-key cryptography. An entropically secure system is unconditionally secure, that is, unbreakable regardless of the adversary’s computing power. The notion of an entropically secure symmetric encryption scheme is important for cryptography because one can construct entropically secure symmetric encryption schemes with keys much shorter than the length of the input, thus circumventing Shannon’s famous lower bound on key length. In this report we suggest an entropically secure scheme for the case where the encrypted message is generated by a Markov chain with unknown statistics. The length of the required secret key is proportional to the logarithm of the message length (as opposed to the length of the message itself for the one-time pad). keywords: Information Theory, entropy security, indistinguishability, symmetric encryption scheme, unconditionally secure, Markov chain, unknown statistics.