We consider a generalized construction of stream ciphers with forward security. The design framework is modular: it is built from a so-called layer function that updates the key and (optionally) the nonce and generates a new pseudorandom output stream. We analyze the generalized construction for four different instantiations: two possible layer functions that are in turn instantiated with either a block cipher or a pseudorandom function. We prove that each of these instantiations gives a stream cipher that is pseudorandom and forward secure in the multi-user setting with a very tight bound. A comprehensive analysis shows that the two block cipher based instantiations achieve very similar bounds. For the pseudorandom function based instantiations there is no clear winner: either layer can be beneficial over the other one, depending on the choice of parameters. By instantiating the pseudorandom function with a generic construction such as the sum of permutations, we obtain a highly efficient and competitive stream cipher based on an n-bit block cipher that is secure beyond the$2^{\text {n}/2}$birthday bound.

The Sponge function is known to achieve $$2^{c/2}$$ security, where c is its capacity. This bound was carried over to its keyed variants, such as SpongeWrap, to achieve a $$\min \{2^{c/2},2^\kappa \}$$ security bound, with $$\kappa $$ the key length. Similarly, many CAESAR competition submissions were designed to comply with the classical $$2^{c/2}$$ security bound. We show that Sponge-based constructions for authenticated encryption can achieve the significantly higher bound of $$\min \{2^{b/2},2^c,2^\kappa \}$$ , with $$b>c$$ the permutation size, by proving that the CAESAR submission NORX achieves this bound. The proof relies on rigorous computation of multi-collision probabilities, which may be of independent interest. We additionally derive a generic attack based on multi-collisions that matches the bound. We show how to apply the proof to five other Sponge-based CAESAR submissions: Ascon, CBEAM/STRIBOB, ICEPOLE, Keyak, and two out of the three PRIMATEs. A direct application of the result shows that the parameter choices of some of these submissions are overly conservative. Simple tweaks render the schemes considerably more efficient without sacrificing security. We finally consider the remaining one of the three PRIMATEs, APE, and derive a blockwise adaptive attack in the nonce-respecting setting with complexity $$2^{c/2}$$ , therewith demonstrating that the techniques cannot be applied to APE.

The significance of understanding blockcipher security in the multi-key setting is highlighted by the extensive literature on attacks, and how effective key size can be significantly reduced. Nevertheless, little attention has been paid in formally understanding the design of multi-key secure blockciphers. In this work, we formalize the multi-key security of tweakable blockciphers in case of general key derivation functions. We show an equivalence between blockcipher multi-key security and tweakable blockcipher security. Our equivalence connects two objects of study, the iterated Even–Mansour (EUROCRYPT 2012) and the iterated Tweakable Even–Mansour (CRYPTO 2015), which establishes that results in both areas are, to a certain extent, transferable. Using our novel equivalence relation, we derive new bounds for both constructions, pave the path towards the solution of two well-studied conjectures, and show that, contrary to common knowledge, key derivation functions need not necessarily be pseudorandom functions in order to provide security: for the iterated Even–Mansour universal hash functions suffice.