On the optimality of non-linear computations for symmetric key primitives.

A block is an n-bit string, and a (possibly keyed) block-function is a non-linear mapping that maps one block to another, e.g., a block-cipher. In this paper, we consider various symmetric key primitives with ℓ {\ell} block inputs and raise the following question: what is the minimum number of block-function invocations required for a mode to be secure? We begin with encryption modes that generate ℓ ′ {\ell^{\prime}} block outputs and show that at least (ℓ + ℓ ′ - 1) {(\ell+\ell^{\prime}-1)} block-function invocations are necessary to achieve the PRF security. In presence of a nonce, the requirement of block-functions reduces to ℓ ′ {\ell^{\prime}} blocks only. If ℓ = ℓ ′ {\ell=\ell^{\prime}} , in order to achieve SPRP security, the mode requires at least 2 ⁢ ℓ {2\ell} many block-function invocations. We next consider length preserving r-block (called chunk) online encryption modes and show that, to achieve online PRP security, each chunk should have at least 2 ⁢ r - 1 {2r-1} many and overall at least 2 ⁢ r ⁢ ℓ - 1 {2r\ell-1} many block-functions for ℓ {\ell} many chunks. Moreover, we show that it can achieve online SPRP security if each chunk contains at least 2 ⁢ r {2r} non-linear block-functions. We next analyze affine MAC modes and show that an integrity-secure affine MAC mode requires at least ℓ {\ell} many block-function invocations to process an ℓ {\ell} block message. Finally, we consider affine mode authenticated encryption and show that in order to achieve INT-RUP security or integrity security under a nonce-misuse scenario, either (i) the number of non-linear block-functions required to generate the ciphertext is more than ℓ {\ell} or (ii) the number of extra non-linear block-functions required to generate the tag depends on ℓ {\ell}. [ABSTRACT FROM AUTHOR]