5
$\begingroup$

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?

$\endgroup$

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.