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.

Relations Among Notions of Security for Public-Key Encryption 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.

Bounded CCA2-Secure Encryption:

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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.