Paper 2017/366

BitFlip: A Randomness-Rich Cipher

Gideon Samid and Serguei Popov

Abstract

We present a cipher that represents a novel strategy: replacing algorithmic complexity with computational simplicity while generating cryptographic efficacy through large as desired quantities of randomness. The BitFlip cipher allows its user to defend herself with credibly appraised mathematical intractability, well-hinged on solid combinatorics. This is the situation when the amount of randomness is small relative to the accumulated amount of processed plaintext. Deploying more randomness, BitFlip will frustrate its cryptanalyst with terminal equivocation among two or more plausible message candidates. This equivocation defense can be increased by simply increasing the amount of deployed randomness, coming at-will close to Vernam’s perfect secrecy. BitFlip is structured as a super polyalphabetic cipher where a letter comprised of 2n bits is pointed-to by any 2n bits string with a Hamming distance of n from it. When a passed 2n bits string is found to have no n-valued Hamming distance from any letter in the reader’s alphabet, it is regarded as null. This allows for co-encryption of several messages each over its respective alphabet; thereby offering a powerful equivocation defense because the ciphertext does not indicate which alphabet the intended reader is using. BitFlip becomes increasingly timely and practical, exploiting the advent of high quality non-algorithmic randomness, as well as the effect of Moore’s law on the cost of handling large amounts of memory. BitFlip is a natural fit for what fast emerges as the biggest customer of cryptography: the Internet of Things