CBEAM: Efficient Authenticated Encryption from Feebly One-Way φ Functions

Abstract. We show how efficient and secure cryptographic mixing functions can be constructed from low-degree rotation-invariant φ functions rather than conven-tional S-Boxes. These novel functions have surprising properties; many exhibit inherent feeble (Boolean circuit) one-wayness and offer speed/area tradeoffs un-obtainable with traditional constructs. Recent theoretical results indicate that even if the inverse is not explicitly computed in an implementation, its degree plays a fundamental role to the security of the iterated composition. To illustrate these properties, we present CBEAM, a Cryptographic Sponge Permutation based on a single 5 × 1-bit Boolean function. This simple nonlinear function is used to con-struct a 16-bit rotation-invariant φ function of Degree 4 (but with a very complex Degree 11 inverse), which in turn is expanded into an efficient 256-bit mixing function. In addition to flexible tradeoffs in hardware we show that efficient im-plementation strategies exist for software platforms ranging from low-end micro-controllers to the very latest x86-64 AVX2 instruction set. A rotational bit-sliced software implementation offers not only comparable speeds to AES but also in-creased security against cache side channel attacks. Our construction supports Sponge-based Authenticated Encryption, Hashing, and PRF/PRNG modes and is highly useful as a compact “all-in-one ” primitive for pervasive security