Paper 2023/1704

On Overidealizing Ideal Worlds: Xor of Two Permutations and its Applications

Abstract

Security proofs of symmetric-key primitives typically consider an idealized world with access to a (uniformly) random function. The starting point of our work is the observation that such an ideal world can lead to underestimating the actual security of certain primitives. As a demonstrating example, $\mathsf{XoP2}$, which relies on two independent random permutations, has been proven to exhibit superior concrete security compared to $\mathsf{XoP}$, which employs a single permutation with domain separation. But the main reason for this is an artifact of the idealized model used in the proof, in particular, that (in the random-function-ideal world) $\mathsf{XoP}$ might hit a trivially bad event (outputting $\mathbf{0}$), which does not occur in the real/domain-separated world. Motivated by this, we put forth the analysis of such primitives in an updated ideal world, which we call the {\it fine-tuned} setting, where the above artifact is eliminated. We provide fine-tuned (and enhanced) security analyses for $\mathsf{XoP}$ and $\mathsf{XoP}$-based MACs: $\mathsf{nEHtM}$ and $\mathsf{DbHtS}$, and demonstrate how the transition to the fine-tuned setting can also yield better privacy/authentication tradeoff in authenticated encryption via the generic composition of encryption and MAC. Our analyses demonstrate that the security of $\mathsf{XoP}$-based and $\mathsf{XoP2}$-based constructions are, in fact, far more similar than what was previously proven. Our security proofs rely on a fine-tuned and extended version of Mirror theory for both lower and upper bounds, which yields more versatile and improved security proofs. Of independent interest, this extension allows us to prove the multi-user MAC security of $\mathsf{nEHtM}$ in the nonce-misuse model, while the previous analysis only applied to the multi-user PRF security in the nonce-respecting model. As a side note, we also point out (and fix) a flaw in the original analysis of Chen et al. [CRYPTO'23].

Note: 1. Change the title. (the previous title was "Fine-Tuning Ideal Worlds for the Xor of Two Permutation Outputs") 2. Revise the overall structure and improve writing and figures. 3. Add Section 3.2 to discuss applications, including the generic compositions.