# Is there a standard definition of non-malleability for the encryption schemes?

I find some different definitions of non-malleability for the encryption schemes. They may be equivalent, but I am not sure which one is better or if there is a standard definition.

I give two definitions of NM-CCA2 for PKE schemes.

Def1 Let $$\Pi = (\text{Gen}, \text{Enc}, \text{Dec})$$ be a PKE scheme and let $$A = (A_{1}, A_{2})$$ be an adversary. For $$k \in \mathbb{N}$$, let $$\mathrm{Adv}^{\text{nm-cca2}}_{\Pi, A}(k) = \left| \Pr \left[ \mathrm{Exp}_{\Pi, A}^{\text{nm-cca2-1}} (k) = 1 \right] - \Pr \left[ \mathrm{Exp}_{\Pi, A}^{\text{nm-cca2-0}} (k) = 1 \right] \right|$$

where, for $$b \in \{ 0,1 \}$$,

Experiment $$\mathrm{Exp}_{\Pi, A}^{\text{nm-cca2-1}} (k)$$

$$(pk, sk) \gets \mathrm{Gen}(1^k);$$

$$(M, s) \gets A_{1}^{\mathrm{Dec}_{sk}(\cdot)}(pk);$$

$$(x_{0}, x_{1}) \gets M;~y \gets \mathrm{Enc}_{pk}(x_{1});$$

$$(R, Y) \gets A_{2}^{\mathrm{Dec}_{sk}(\cdot)}(M,s,y);$$

$$X \gets \mathrm{Dec}_{sk}(Y);$$

If $$(y \not\in Y) \wedge (\bot \not\in X) \wedge R(x_{b}, X)$$ then $$d \gets 1$$; else $$d \gets 0$$;

Return $$d$$

$$M$$ is a set such that $$|x| = |x'|$$ for any $$x, x' \in M$$. And $$X = (X_{1}, X_{2}, \ldots, X_{l})$$ and $$Y = (Y_{1}, Y_{2}, \ldots, Y_{l})$$ such that $$X_{i} = \mathrm{Dec}_{sk}(Y_{i})$$. $$\Pi$$ is secure in the sense of NM-CCA2 if for every P.P.T. algorithms $$A$$, $$\mathrm{Adv}_{\Pi, A}^{\text{nm-cca2}} (\cdot)$$ is negligible.

Def2 Let $$\Pi = (\text{Gen}, \text{Enc}, \text{Dec})$$ be a PKE scheme and let the random variable $$\text{NME-CCA2}_{\Pi, A, k, l}$$ where $$b \in \{ 0,1 \}$$, $$A = (A_{1}, A_{2})$$ and $$k,l \in \mathbb{N}$$ denote the result of the following probabilistic experiment:

Experiment $$\text{NME-CCA2-}b (\Pi, A, k, l)$$:

$$(pk, sk) \gets \mathrm{Gen}(1^k);$$

$$(x_{0}, x_{1}, s) \gets A_{1}^{\mathrm{Dec}_{sk}(\cdot)}(pk);$$

$$y \gets \mathrm{Enc}_{pk}(x_{b});$$

$$Y = (Y_{1}, Y_{2}, \ldots, Y_{l}) \gets A_{2}^{\mathrm{Dec}_{sk}(\cdot)}(y, s);$$

Output $$X = (X_{1}, X_{2}, \ldots, X_{l}) = \mathrm{Dec}_{sk}(Y)$$ (If $$Y_{i} = y$$, $$X_{i} = \text{COPY}$$)

It is mandated that $$|x_{0}| = |x_{1}|$$. $$\Pi$$ is secure in the sense of NM-CCA2 if for every P.P.T. algorithms $$A$$, any polynomial $$p(\cdot)$$, $$\left\{ \text{NME-CCA2-0} (\Pi, A, k, p(k)) \right\}_{k \in \mathbb{N}}$$ and $$\left\{ \text{NME-CCA2-1} (\Pi, A, k, p(k)) \right\}_{k \in \mathbb{N}}$$ are computationally indistinguishable.

In Def1, why does $$A_{1}$$ output a set $$M$$ instead $$(x_{0}, x_{1})$$?

Is every efficient relation can be the output of $$A_{1}$$?

Is every relation which is the output of $$A_{1}$$ efficient?

In Def2, can the distinguisher ask the access of $$\mathrm{Dec}_{sk}(\cdot)$$? (Or does the distinguisher know $$sk$$?)

Why are these definitions equivalent?