Mathematical Methods of Cryptography

Probability space for the NCPA attack

D. B. Fomin, A. B. Chuhno


Abstract: This paper presents a rigorous mathematical analysis of the NCPA (Non-adaptive Chosen Plaintext Attack) model in the context of block cipher security evaluation. A formal probabilistic space is introduced to describe the interaction between an adversary $\mathcal{A}$ and an oracle that either implements a block cipher $ \mathcal{E}_K $ or a random permutation $ \mathcal{P} $. The distinguishing task, i.e., the problem of determining whether the oracle is a real cipher or an ideal one, is reformulated as a statistical hypothesis testing problem. The advantage $\mathsf{Adv}_{\mathcal{E}}^{\textrm{NCPA}}(\mathcal{A})$ is defined as the maximum absolute difference between the probabilities of the adversary outputting $1$ under the two hypotheses: $\mathsf{Adv}_\mathcal{E}^{\textrm{NCPA}}(\mathcal{A}) = \max_{\mathcal{A}} \left| \Pr_1[b' = 1] - \Pr_0[b' = 1] \right|$. It is demonstrated that this advantage can be expressed via the total variation distance $d_{\mathrm{TV}}(Y_1, Y_0)$ between the distributions of the ciphertext vectors $Y_1$ and $Y_0$ corresponding to the cipher and the random permutation models, respectively. In particular, it is shown that when the adversary uses only statistical properties of the outputs $Y = Y(X)$ for a fixed set of distinct plaintexts $X \in M^{[q]}$, the following equality holds: $\mathsf{Adv}_\mathcal{E}^{\textrm{NCPA}}(\mathcal{A}) = d_{\mathrm{TV}}(Y_1, Y_0)$. This result follows from a decision rule based on the likelihood ratio $ l(Y) = {\Pr_1[Y]}/{\Pr_0[Y]} $, where the adversary decides $b' = 1$ if $l(Y) \geq 1$, and $b' = 0$ otherwise. In this case, the advantage becomes directly related to the sum of Type I and Type II error probabilities: $\mathsf{Adv}_{\mathcal{E}}^{\text{NCPA}}(q) = \max_{\mathcal{A}} \left| 1 - (\alpha_\mathcal{A} + \beta_\mathcal{A}) \right|$. However, we highlight a crucial limitation of using the total variation distance alone as a measure of cipher security. It is shown that while small $d_{\mathrm{TV}}(Y_1, Y_0)$ indicates good statistical indistinguishability, it does not guarantee computational security. There may exist constructive attacks exploiting the internal structure of the cipher that remain effective even when the statistical distance is negligible.

Keywords: cipher security, NCPA, Neyman — Pearson lemma, statistical distance.

UDC: 519.7

DOI: 10.17223/2226308X/18/35