Băhēm: Provably Secure Symmetric Cipher

Abstract

This paper proposes Băhēm; a symmetric cipher that, when given a random-looking key k, a true random number generator (TRNG) and a cleartext message m to encrypt, no cryptanalysis can degrade its security below min[H(m), H(k)] bits of entropy, even under Grover's algorithm or even if it turned out that P = NP.

Aside from the cost of memory access and input/output processing, Băhēm requires only three additions (one per-session, two per-block) and one XOR operation in order to encrypt or decrypt, and is also highly parallelise-able.

Despite Băhēm's 1-bit overhead per cleartext bit, its early prototype, Alyal, achieved similar run-time speeds to OpenSSL's ChaCha20; slightly faster decryption, while slightly slower encryption when the TRNG was prepared in a file in advance. This demonstrates that Băhēm is practicality usable for many real-world application scenarios.

Later implementations, with better TRNG optimisations and parallelism, must allow the prototype a faster run-time for both, encryption and decryption.