Paper 2013/773

CBEAM: Efficient Authenticated Encryption from Feebly One-Way $\phi$ Functions

Markku-Juhani O. Saarinen


We show how efficient and secure cryptographic mixing functions can be constructed from low-degree rotation-invariant $\phi$ functions rather than conventional S-Boxes. These novel functions have surprising properties; many exhibit inherent feeble (Boolean circuit) one-wayness and offer speed/area tradeoffs unobtainable 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 \times 1$-bit Boolean function. This simple nonlinear function is used to construct a 16-bit rotation-invariant$\phi$ 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 implementation strategies exist for software platforms ranging from low-end microcontrollers to the very latest x86-64 AVX2 instruction set. A rotational bit-sliced software implementation offers not only comparable speeds to AES but also increased 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.

Note: Accepted to Cryptographers' Track, RSA Conference USA 2014 (CT-RSA 2014), 25--28 February 2014, San Francisco, US.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Minor revision. CT-RSA 2014
CBEAMAuthenticated EncryptionCryptographic Sponge FunctionsTrapdoor $\phi$ functionsLightweight Cryptography
Contact author(s)
mjos @ iki fi
2013-12-12: last of 3 revisions
2013-11-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Markku-Juhani O.  Saarinen},
      title = {{CBEAM}: Efficient Authenticated Encryption from Feebly One-Way $\phi$ Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2013/773},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.