#  Distributed Source Coding with Encryption Using Correlated Keys

Yasutada Oohama and Bagus Santoso  University of Electro-Communications,
Tokyo, Japan
Email<EMAIL_ADDRESS>
###### Abstract

We pose and investigate the distributed secure source coding based on the
common key cryptosystem. This cryptosystem includes the secrecy amplification
problem for distributed encrypted sources with correlated keys using post-
encryption-compression, which was posed investigated by Santoso and Oohama. In
this paper we propose another new security criterion which is generally more
strict compared to the commonly used security criterion which is based on the
upper-bound of mutual information between the plaintext and the ciphertext.
Under this criterion, we establish the necessary and sufficient condition for
the secure transmission of correlated sources.

##  I Introduction

In this paper we pose and investigate the distributed secure source coding
based on the common key cryptosystem. This cryptosystem includes the secrecy
amplification problem for distributed encrypted sources with correlated keys
using post-encryption-compression (PEC), which was posed investigated by
Santoso and Oohama in [1], [2].

In this paper we propose another new security criterion which is generally
more strict compared with the commonly used security criterion based on the
upper-bound of mutual information between the plaintext and the ciphertext.
For the proposed new metric we prove its validity. Concreatly we establish the
following two results:

  * a)

We prove that if the mutual information is zero, then the proosed criterion is
strictly zero.

  * b)

The mutual information is upper bounded by the proposed criterion implying
that the proposed criterion is more strict than the widely-used security
metric based mutual information.

Those resuls are stated in Propostion 1. For the proposed sequrity criterion,
the part a) is quite essential. Without this condtion, the criterion is
meaningless.

Under the proposed sequrity criterion we prove the strong converse theorem.
This result is stated in Theorem 3. Due to the introduction of this criterion
the proof of the strong converse theorem is quite simple. We further derive a
sufficient condition to achieve security. This sufficient condition matches
the necessary condition. In our previous works of Santoso and Oohama [1], [2],
we have derived a sufficient condition under the security critrion measured by
the mutual information. To derive the sufficient condition we use the coding
scheme proposed by Santoso and Oohama. We obtain the same sufficient condition
as that of Santoso and Oohama [1], [2] under even more strict condition than
the mutual information. This result is stated in Theorem 1.

Our study in this paper has a closely related to several previous works on the
PEC, e.g., Johnson et al.[3], Klinc et al. [4]. Our study also has a close
connection with several previous works on the Shannon cipher system, e.g. [5],
[6] [7].

##  II Secure Source Coding Problem

###  II-A Preliminaries

In this subsection, we show the basic notations and related consensus used in
this paper.

Random Sources of Information and Keys:  Let $(X_{1},X_{2})$ be a pair of
random variables from a finite set $\mathcal{X}_{1}\times\mathcal{X}_{2}$. Let
$\\{(X_{1,t},X_{2,t})\\}_{t=1}^{\infty}$ be a stationary _discrete memoryless
source_ (DMS) such that for each $t=1,2,\ldots$, the pair $(X_{1,t},X_{2,t})$
takes values in finite set $\mathcal{X}_{1}\times\mathcal{X}_{2}$ and obeys
the same distribution as that of $(X_{1},X_{2})$ denoted by
$p_{X_{1}X_{2}}=\\{p_{X_{1}X_{2}}(x_{1},x_{2})\\}_{(x_{1},x_{2})\in\mathcal{X}_{1}\times\mathcal{X}_{2}}$.
The stationary DMS $\\{(X_{1,t},X_{2,t})\\}_{t=1}^{\infty}$ is specified with
$p_{X_{1}X_{2}}$. Also, let $(K_{1},K_{2})$ be a pair of random variables
taken from the same finite set $\mathcal{X}_{1}\times\mathcal{X}_{2}$
representing the pair of keys used for encryption at two separate terminals,
of which the detailed description will be presented later. Similarly, let
$\\{(K_{1,t},K_{2,t})\\}_{t=1}^{\infty}$ be a stationary discrete memoryless
source such that for each $t=1,2,\ldots$, the pair $(K_{1,t},K_{2,t})$ takes
values in finite set $\mathcal{X}_{1}\times\mathcal{X}_{2}$ and obeys the same
distribution as that of $(K_{1},K_{2})$ denoted by
$p_{K_{1}K_{2}}=\\{p_{K_{1}K_{2}}(k_{1},k_{2})\\}_{(k_{1},k_{2})\in\mathcal{X}_{1}\times\mathcal{X}_{2}}$.
The stationary DMS $\\{(K_{1,t},K_{2,t})\\}_{t=1}^{\infty}$ is specified with
$p_{K_{1}K_{2}}$.

Random Variables and Sequences:  We write the sequence of random variables
with length $n$ from the information source as follows:
${{\mbox{\boldmath$X$}}_{1}}:=X_{1,1}X_{1,2}\cdots X_{1,n}$,
${{\mbox{\boldmath$X$}}_{2}}:=X_{2,1}X_{2,2}\cdots X_{2,n}$. Similarly, the
strings with length $n$ of $\mathcal{X}_{1}^{n}$ and $\mathcal{X}_{2}^{n}$ are
written as ${{\mbox{\boldmath$x$}}_{1}}:=x_{1,1}x_{1,2}\cdots
x_{1,n}\in\mathcal{X}_{1}^{n}$ and
${{\mbox{\boldmath$x$}}_{2}}:=x_{2,1}x_{2,2}\cdots
x_{2,n}\in\mathcal{X}_{2}^{n}$ respectively. For
$({{\mbox{\boldmath$x$}}_{1}},{{\mbox{\boldmath$x$}}_{2}})\in\mathcal{X}_{1}^{n}\times\mathcal{X}_{2}^{n}$,
$p_{{{\mbox{\scriptsize\boldmath$X$}}_{1}}{{\mbox{\scriptsize\boldmath$X$}}_{2}}}({{\mbox{\boldmath$x$}}_{1}},{{\mbox{\boldmath$x$}}_{2}})$
stands for the probability of the occurrence of
$({{\mbox{\boldmath$x$}}_{1}},{{\mbox{\boldmath$x$}}_{2}})$. When the
information source is memoryless specified with $p_{X_{1}X_{2}}$, we have the
following equation holds:
$p_{{{\mbox{\scriptsize\boldmath$X$}}_{1}}{{\mbox{\scriptsize\boldmath$X$}}_{2}}}({{\mbox{\boldmath$x$}}_{1}},{{\mbox{\boldmath$x$}}_{2}})=\prod_{t=1}^{n}p_{X_{1}X_{2}}(x_{1,t},x_{2,t})$.
In this case we write
$p_{{{\mbox{\scriptsize\boldmath$X$}}_{1}}{{\mbox{\scriptsize\boldmath$X$}}_{2}}}({{\mbox{\boldmath$x$}}_{1}},{{\mbox{\boldmath$x$}}_{2}})$
as
$p_{X_{1}X_{2}}^{n}({{\mbox{\boldmath$x$}}_{1}},{{\mbox{\boldmath$x$}}_{2}})$.
Similar notations are used for other random variables and sequences.

_Consensus and Notations:_ Without loss of generality, throughout this paper,
we assume that $\mathcal{X}_{1}$ and $\mathcal{X}_{2}$ are finite fields. The
notation $\oplus$ is used to denote the field addition operation, while the
notation $\ominus$ is used to denote the field subtraction operation, i.e.,
$a\ominus b=a\oplus(-b)$ for any elements $a,b$ of a same finite field. For
the sake of simplicity, we use the same notation for field addition and
subtraction for both $\mathcal{X}_{1}$ and $\mathcal{X}_{2}$. Throughout this
paper all logarithms are taken to the base 2.

###  II-B Basic System Description

First, let the information sources and keys be generated independently by
different parties $\mathcal{S}_{\mathsf{gen}}$ and
$\mathcal{K}_{\mathsf{gen}}$ respectively. In our setting, we assume the
followings.

  * •

The random keys ${{\mbox{\boldmath$K$}}_{1}}$ and
${{\mbox{\boldmath$K$}}_{2}}$ are generated by $\mathcal{K}_{\mathsf{gen}}$.

  * •

The key ${{\mbox{\boldmath$K$}}_{1}}$ is correlated to
${{\mbox{\boldmath$K$}}_{2}}$.

  * •

The sources ${{\mbox{\boldmath$X$}}_{1}}$ and ${{\mbox{\boldmath$X$}}_{2}}$
are generated by $\mathcal{S}_{\mathsf{gen}}$ and are correlated to each
other.

  * •

The sources are independent to the keys.

Source coding without encryption: The two correlated random sources
${{\mbox{\boldmath$X$}}_{1}}$ and ${{\mbox{\boldmath$X$}}_{2}}$ from
$\mathcal{S}_{\mathsf{gen}}$ be sent to two separated nodes $\mathsf{E}_{1}$
and $\mathsf{E}_{2}$ respectively. Further settings of the system are
described as follows. Those are also shown in Fig. 1.

  1. 1.

_Encoding Process:_ For each $i=1,2$, at the node $\mathsf{E}_{i}$, the
encoder function $\phi_{i}^{(n)}:{\cal X}_{i}^{n}$ $\to{\cal X}_{i}^{m_{i}}$
observes ${{\mbox{\boldmath$X$}}_{i}}$ to generate
$\tilde{X}_{i}^{m_{i}}=\phi_{i}^{(n)}({{\mbox{\boldmath$X$}}_{i}})$. Without
loss of generality we may assume that $\phi_{i}^{(n)}$ is surjective.

  2. 2.

_Transmission:_ Next, the encoded sources $\tilde{X}_{i}^{m_{i}}$, $i=1,2$ are
sent to the information processing center $\mathsf{D}$ through two _noiseless_
channels.

  3. 3.

_Decoding Process:_ In $\mathsf{D}$, the decoder function observes
$\tilde{X}^{m_{i}},i=1,2$ to output
$(\widehat{{\mbox{\boldmath$X$}}}_{1},\widehat{{\mbox{\boldmath$X$}}}_{2})$,
using the one-to-one mapping $\psi^{(n)}$ defined by $\psi^{(n)}:{\cal
X}_{1}^{m_{1}}\times{\cal X}_{2}^{m_{2}}\to{\cal X}_{1}^{n}\times{\cal
X}_{2}^{n}$. Here we set

$\displaystyle(\widehat{{\mbox{\boldmath$X$}}}_{1},\widehat{{\mbox{\boldmath$X$}}}_{2}):=$
$\displaystyle\psi^{(n)}(\tilde{X}^{m_{1}}_{1},\tilde{X}^{m_{2}}_{2})$
$\displaystyle=$
$\displaystyle\psi^{(n)}\left(\phi^{(n)}_{1}({\mbox{\boldmath$X$}}_{1}),\phi^{(n)}_{2}({\mbox{\boldmath$X$}}_{2})\right).$

More concretely, the decoder outputs the unique pair
$(\widehat{{\mbox{\boldmath$X$}}}_{1},\widehat{{\mbox{\boldmath$X$}}}_{2})$
from
$(\phi_{1}^{(n)})^{-1}(\tilde{X}_{1}^{m_{1}})\times(\phi_{2}^{(n)})^{-1}(\tilde{X}_{2}^{m_{2}})$
in a proper manner.

Figure 1: Distributed source coding without encryption.  Figure 2: Distributed
source coding with encryption.

For the above $(\phi_{1}^{(n)},\phi_{2}^{(n)},\psi^{(n)})$, we define the set
$\mathcal{D}^{(n)}$ of correct decoding by

$\displaystyle\mathcal{D}^{(n)}$
$\displaystyle:=\\{({\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})\in\mathcal{X}_{1}^{n}\times\mathcal{X}_{2}^{n}:$
$\displaystyle\psi^{(n)}(\varphi_{1}^{(n)}({\mbox{\boldmath$x$}}_{1}),\varphi_{2}^{(n)}({\mbox{\boldmath$x$}}_{2}))=({\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})\\}.$

On $|{\cal D}^{(n)}|$, we have the following property.

###### Property 1

We have the following.

$\displaystyle|{\cal D}^{(n)}|=|{\cal X}_{1}^{m_{1}}||{\cal X}_{2}^{m_{2}}|.$
(1)

Proof of Property 1 is given in Appendix -A.

Distributed source coding with encryption:

The two correlated random sources ${{\mbox{\boldmath$X$}}_{1}}$ and
${{\mbox{\boldmath$X$}}_{2}}$ from $\mathcal{S}_{\mathsf{gen}}$ are sent to
two separated nodes $\mathsf{L}_{1}$ and $\mathsf{L}_{2}$, respectively. The
two random keys ${{\mbox{\boldmath$K$}}_{1}}$ and
${{\mbox{\boldmath$K$}}_{2}}$ from $\mathcal{K}_{\mathsf{gen}}$, are also sent
to $\mathsf{L}_{1}$ and and $\mathsf{L}_{2}$, respectively. Further settings
of our system are described as follows. Those are also shown in Fig. 2.

  1. 1.

_Source Processing:_ For each $i=1,2$, at the node $\mathsf{L}_{i}$,
${{\mbox{\boldmath$X$}}}_{i}$ is encrypted with the key
${{\mbox{\boldmath$K$}}}_{i}$ using the encryption function
$\Phi_{i}^{(n)}:{\cal X}_{i}^{n}\times{\cal X}_{i}^{n}$ $\to{\cal
X}_{i}^{m_{i}}$. For each $i=1,2$, the ciphertext $C_{i}^{m_{i}}$ of
${{\mbox{\boldmath$X$}}}_{i}$ is given by
$C_{i}^{m_{i}}=\Phi_{i}^{(n)}({{\mbox{\boldmath$K$}}}_{i},{{\mbox{\boldmath$X$}}}_{i})$.
On the encryption function $\Phi_{i}^{(n)},i=1,2$, we use the folloiwng
notation:

$\Phi_{i}^{(n)}({{\mbox{\boldmath$K$}}}_{i},{{\mbox{\boldmath$X$}}}_{i})=\Phi^{(n)}_{i,{{\mbox{\scriptsize\boldmath$K$}}}_{i}}({{\mbox{\boldmath$X$}}}_{i})=\Phi^{(n)}_{i,{{\mbox{\scriptsize\boldmath$X$}}}_{i}}({{\mbox{\boldmath$K$}}}_{i}).$

  2. 2.

_Transmission:_ Next, the ciphertext $C_{i}^{m_{i}},i=1,2$ are sent to the
information processing center $\mathsf{D}$ through two _public_ communication
channels. Meanwhile, the key ${{\mbox{\boldmath$K$}}}_{i},i=1,2$, are sent to
$\mathsf{D}$ through two _private_ communication channels.

  3. 3.

_Sink Node Processing:_ In $\mathsf{D}$, we decrypt the ciphertext
$(\widehat{{\mbox{\boldmath$X$}}}_{1},\widehat{{\mbox{\boldmath$X$}}}_{2})$
from $C_{i}^{m_{i}},i=1,2,$ using the key ${{\mbox{\boldmath$K$}}}_{i},i=1,2$,
through the corresponding decryption procedure $\Psi^{(n)}$ defined by
$\Psi^{(n)}:{\cal X}_{1}^{n}\times{\cal X}_{2}^{n}\times{\cal
X}_{1}^{m_{1}}\times{\cal X}_{2}^{m_{2}}\to{\cal X}_{1}^{n}\times{\cal
X}_{2}^{n}.$ Here we set

$(\widehat{{\mbox{\boldmath$X$}}}_{1},\widehat{{\mbox{\boldmath$X$}}}_{2}):=\Psi^{(n)}({{\mbox{\boldmath$K$}}_{1}},{{\mbox{\boldmath$K$}}_{2}},C_{1}^{m_{1}},C_{2}^{m_{2}}).$

More concretely, the decoder outputs the unique pair
$(\widehat{{\mbox{\boldmath$X$}}}_{1},\widehat{{\mbox{\boldmath$X$}}}_{2})$
from
$(\Phi_{1,{\mbox{\scriptsize\boldmath$K$}}_{1}}^{(n)})^{-1}({C}_{1}^{m_{1}})\times(\Phi_{2,{\mbox{\scriptsize\boldmath$K$}}_{1}}^{(n)})^{-1}({C}_{2}^{m_{2}})$
in a proper manner. On the decryption function $\Psi^{(n)}$, we use the
following notation:

$\displaystyle\Psi^{(n)}({{\mbox{\boldmath$K$}}}_{1},{{\mbox{\boldmath$K$}}}_{2},C_{1}^{m_{1}},C_{2}^{m_{2}})=\Psi^{(n)}_{{\mbox{\scriptsize\boldmath$K$}}_{1},{\mbox{\scriptsize\boldmath$K$}}_{2}}(C_{1}^{m_{1}},C_{2}^{m_{2}})$
$\displaystyle=\Psi^{(n)}_{C_{1}^{m_{1}},C_{2}^{m_{2}}}({{\mbox{\boldmath$K$}}_{1}},{{\mbox{\boldmath$K$}}_{2}}).$

Fix any
$({\mbox{\boldmath$K$}}_{1},{\mbox{\boldmath$K$}}_{2})=({\mbox{\boldmath$k$}}_{1},{\mbox{\boldmath$k$}}_{2})\in\mathcal{X}_{1}^{n}\times\mathcal{X}_{2}^{n}$.
For this $({\mbox{\boldmath$K$}}_{1},{\mbox{\boldmath$K$}}_{2})$ and for
$(\Phi_{1}^{(n)},\Phi_{2}^{(n)},\Psi^{(n)})$, we define the set
$\mathcal{D}^{(n)}_{{\mbox{\scriptsize\boldmath$k$}}_{1},{\mbox{\scriptsize\boldmath$k$}}_{2}}$
of correct decoding by

$\displaystyle\mathcal{D}^{(n)}_{{\mbox{\scriptsize\boldmath$k$}}_{1},{\mbox{\scriptsize\boldmath$k$}}_{2}}$
$\displaystyle:=\\{({\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})\in\mathcal{X}_{1}^{n}\times\mathcal{X}_{2}^{n}:$
$\displaystyle\Psi^{(n)}(\Phi_{1}^{(n)}({\mbox{\boldmath$k$}}_{1},{\mbox{\boldmath$x$}}_{1}),(\Phi_{2}^{(n)}({\mbox{\boldmath$k$}}_{2},{\mbox{\boldmath$x$}}_{2}))=({\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})\\}.$

We require that the cryptosystem $(\Phi_{1}^{(n)},\Phi_{2}^{(n)},\Psi^{(n)})$
must satisfy the following condition.

Condition: For each distributed source encryption sysytem
$(\Phi_{1}^{(n)},\Phi_{2}^{(n)},\Psi^{(n)})$, there exists a distributed
source coding system $(\phi_{1}^{(n)},\phi_{2}^{(n)},\psi^{(n)})$ such that
for any
$({\mbox{\boldmath$k$}}_{1},{\mbox{\boldmath$k$}}_{2})\in\mathcal{X}_{1}^{n}\times\mathcal{X}_{1}^{n}$
and for any
$({\mbox{\boldmath$k$}}_{1},{\mbox{\boldmath$k$}}_{2})\in\mathcal{X}_{2}^{n}\times\mathcal{X}_{2}^{n}$,

$\displaystyle\Psi_{{\mbox{\scriptsize\boldmath$k$}}_{1},{\mbox{\scriptsize\boldmath$k$}}_{2}}^{(n)}(\Phi_{1,{\mbox{\scriptsize\boldmath$k$}}_{1}}^{(n)}({\mbox{\boldmath$x$}}_{1}),\Phi_{2,{\mbox{\scriptsize\boldmath$k$}}_{2}}^{(n)}({\mbox{\boldmath$x$}}_{2}))$
$\displaystyle=\psi^{(n)}(\phi_{1}^{(n)}({\mbox{\boldmath$x$}}_{1}),\phi_{2}^{(n)}({\mbox{\boldmath$x$}}_{2})).$

The above condition implies that

${\cal D}^{(n)}={\cal
D}^{(n)}_{{\mbox{\scriptsize\boldmath$k$}}_{1},{\mbox{\scriptsize\boldmath$k$}}_{2}},\forall({\mbox{\boldmath$k$}}_{1},{\mbox{\boldmath$k$}}_{2})\in{\cal
X}_{1}^{n}\times{\cal X}_{2}^{n}.$

We have the following properties on ${\cal D}^{(n)}$.

###### Property 2

  * a)

If
$({\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2}),({\mbox{\boldmath$x$}}^{\prime}_{1},{\mbox{\boldmath$x$}}^{\prime}_{2})\in{\cal
D}^{(n)}$ and
$({\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})\neq({\mbox{\boldmath$x$}}^{\prime}_{1},{\mbox{\boldmath$x$}}^{\prime}_{2})$,
then

$(\Phi^{(n)}_{1,{\mbox{\scriptsize\boldmath$k$}}_{1}}({\mbox{\boldmath$x$}}_{1}),\Phi^{(n)}_{2,{\mbox{\scriptsize\boldmath$k$}}_{2}}({\mbox{\boldmath$x$}}_{2}))\neq(\Phi^{(n)}_{1,{\mbox{\scriptsize\boldmath$k$}}_{1}}({\mbox{\boldmath$x$}}^{\prime}_{1}),\Phi^{(n)}_{2,{\mbox{\scriptsize\boldmath$k$}}_{2}}({\mbox{\boldmath$x$}}^{\prime}_{2})).$

  * b)

$\forall({\mbox{\boldmath$k$}}_{1},{\mbox{\boldmath$k$}}_{2})$ and
$\forall(c_{1}^{m_{1}},c_{2}^{m_{2}})$,
$\exists({\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})$ $\in{\cal
D}^{(n)}$ such that

$(\Phi^{(n)}_{1,{\mbox{\scriptsize\boldmath$k$}}_{1}}({\mbox{\boldmath$x$}}_{1}),\Phi^{(n)}_{2,{\mbox{\scriptsize\boldmath$k$}}_{2}}({\mbox{\boldmath$x$}}_{2}))=(c_{1}^{m_{1}},c_{2}^{m_{2}}).$

Proof of Property 2 is given in Appendix -B. From Property 2, we have the
following result, which is a key result of this paper.

###### Lemma 1

$\forall(c_{1}^{m_{1}},c_{2}^{m_{2}})\in{\cal X}_{1}^{m_{1}}\times{\cal
X}_{2}^{m_{2}}$, we have

$\displaystyle\sum_{({\mbox{\scriptsize\boldmath$x$}}_{1},{\mbox{\scriptsize\boldmath$x$}}_{2})\in{\cal
D}^{(n)}}p_{C_{1}^{m_{1}}C_{2}^{m_{2}}|{\mbox{\scriptsize\boldmath$X$}}_{1}{\mbox{\scriptsize\boldmath$X$}}_{2}}(c_{1}^{m_{1}},c_{2}^{m_{2}}|{\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})=1.$

Proof of Lemma 1 is given in Appendix -C. This lemma can be regarded as an
extension of the Birkhoff-von Neumann theorem [8].

Let
$(\check{C}_{1}^{m_{1}},\check{C}_{2}^{m_{2}},\check{{\mbox{\boldmath$X$}}}_{1}^{n},\check{{\mbox{\boldmath$X$}}}_{2}^{n})$
be a quadruple of random variables. We assume that
$p_{\check{C}_{1}^{m_{1}}\check{C}_{2}^{m_{2}}|\check{{\mbox{\scriptsize\boldmath$X$}}}_{1}\check{{\mbox{\scriptsize\boldmath$X$}}}_{2}}=p_{C_{1}^{m_{1}}C_{2}^{m_{2}}|{\mbox{\scriptsize\boldmath$X$}}_{1}{\mbox{\scriptsize\boldmath$X$}}_{2}}$.
We further assume that
$p_{\check{{\mbox{\scriptsize\boldmath$X$}}}_{1}\check{{\mbox{\scriptsize\boldmath$X$}}}_{2}}$
is the uniform distribution over ${\cal D}^{(n)}$. Then by Lemma 1 we have
that

$\displaystyle\sum_{\scriptstyle({\mbox{\scriptsize\boldmath$x$}}_{1},{\mbox{\scriptsize\boldmath$x$}}_{2}){\scriptstyle\in{\cal
D}^{(n)}}}p_{\check{C}_{1}^{m_{1}}\check{C}_{2}^{m_{2}}\check{{\mbox{\scriptsize\boldmath$X$}}}_{1}\check{{\mbox{\scriptsize\boldmath$X$}}}_{2}}(c_{1}^{m_{1}},c_{2}^{m_{2}},{\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})=\frac{1}{|{\cal
X}_{1}^{m_{1}}||{\cal X}_{2}^{m_{2}}|}.$

Hence $p_{\check{C}_{1}^{m_{1}}\check{C}_{2}^{m_{2}}}$ is the uniform
distribution over ${\cal X}_{1}^{m_{1}}\times{\cal X}_{2}^{m_{2}}$.

##  III Main Results

###  III-A Proposed Security Criterion

In this section, we introduce our proposed security criterion. We first
provide several definitions.

Definitions of Random variables: For each $i=1,2$, let
$C_{{{\mbox{\scriptsize\boldmath$x$}}}_{i}}$ be a random variable with having
a distribution $p_{C_{i}|{\mbox{\scriptsize\boldmath$X$}}_{i}}^{m_{i}}$
$(\cdot|{\mbox{\boldmath$x$}}_{i}).$ We assume that for
$({\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})\in{\cal X}_{1}^{n}$
$\times{\cal X}_{2}^{n}$, the pair
$(C^{m_{1}}_{1,{\mbox{\scriptsize\boldmath$x$}}_{1}},C^{m_{2}}_{2,{\mbox{\scriptsize\boldmath$x$}}_{1}})$
has a joint distribution
$p_{C_{1}^{m_{1}}C_{2}^{m_{2}}|{\mbox{\scriptsize\boldmath$X$}}_{1}{\mbox{\scriptsize\boldmath$X$}}_{2}}$
$(\cdot,\cdot|{\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2}).$

###### Definition 1

For any
$({\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})\in\mathcal{X}_{1}^{n}\times\mathcal{X}_{2}^{n}$,
we define the following:

$\displaystyle\Delta^{(n)}({\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2}):=\sum_{\scriptstyle(c_{1}^{m_{1}},c_{2}^{m_{2}})\atop{\scriptstyle\in\mathcal{X}_{1}^{m_{1}}\times\mathcal{X}_{2}^{m_{2}}}}p_{C_{1}^{m_{1}}C_{2}^{m_{2}}|{\mbox{\scriptsize\boldmath$X$}}_{1}{\mbox{\scriptsize\boldmath$X$}}_{2}}(c_{1}^{m_{1}},c_{2}^{m_{2}}|{\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})$
$\displaystyle\quad\times\log\frac{p_{C_{1}^{m_{1}}C_{2}^{m_{2}}|{\mbox{\scriptsize\boldmath$X$}}_{1}{\mbox{\scriptsize\boldmath$X$}}_{2}}(c_{1}^{m_{1}},c_{2}^{m_{2}}|{\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})}{p_{\check{C}_{1}^{m_{1}}\check{C}_{2}^{m_{2}}}(c_{1}^{m_{1}},c_{2}^{m_{2}})}$
$\displaystyle=D(C_{{\mbox{\scriptsize\boldmath$x$}}_{1}}^{m_{1}}C_{{\mbox{\scriptsize\boldmath$x$}}_{2}}^{m_{2}}||\check{C}_{1}^{m_{1}}\check{C}_{2}^{m_{2}})$
$\displaystyle=D(p_{C_{1}^{m_{1}}C_{2}^{m_{2}}|{\mbox{\scriptsize\boldmath$X$}}_{1}{\mbox{\scriptsize\boldmath$X$}}_{2}}(\cdot,\cdot|{\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})||p_{\check{C}_{1}^{m_{1}}\check{C}_{2}^{m_{2}}}).$

Furthermore define:

$\displaystyle\Delta^{(n)}:=\sum_{\scriptstyle({\mbox{\scriptsize\boldmath$x$}}_{1},{\mbox{\scriptsize\boldmath$x$}}_{2})\atop{\scriptstyle\in\mathcal{X}_{1}^{n}\times\mathcal{X}_{2}^{n}}}p_{{\mbox{\scriptsize\boldmath$X$}}_{1}{\mbox{\scriptsize\boldmath$X$}}_{2}}({\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})\Delta^{(n)}({\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})$
$\displaystyle=D(p_{C^{m_{1}}C^{m_{2}}|{\mbox{\scriptsize\boldmath$X$}}_{1}{\mbox{\scriptsize\boldmath$X$}}_{2}}\|p_{\check{C}_{1}^{m_{1}}\check{C}_{2}^{m_{2}}}|p_{{\mbox{\scriptsize\boldmath$X$}}_{1}{\mbox{\scriptsize\boldmath$X$}}_{2}}).$

On $\Delta^{(n)}$, we have the following proposition which is the most
essential part in the proof of the strong converse theorem.

###### Proposition 1

  * a)

By the definition of $\Delta^{(n)}$, we have

$\displaystyle\Delta^{(n)}=I(C_{1}^{m_{1}}C_{2}^{m_{2}};{\mbox{\boldmath$X$}}_{1}{\mbox{\boldmath$X$}}_{2})+D(p_{C_{1}^{m_{1}}C_{2}^{m_{2}}}||p_{\check{C}_{1}^{m_{1}}\check{C}_{2}^{m_{2}}})$
$\displaystyle\geq
I(C_{1}^{m_{1}}C_{2}^{m_{2}};{\mbox{\boldmath$X$}}_{1}{\mbox{\boldmath$X$}}_{2}).$

This implies that the security measure $\Delta^{(n)}$ is stronger than the
mutual information security measure $\Delta_{\rm
MI}^{(n)}:=I(C_{1}^{m_{1}}C_{2}^{m_{2}};{\mbox{\boldmath$X$}}_{1}{\mbox{\boldmath$X$}}_{2})$.

  * b)

If
$I(C_{1}^{m_{1}}C_{2}^{m_{2}};{\mbox{\boldmath$X$}}_{1}{\mbox{\boldmath$X$}}_{2})=0$,
then, we have $\Delta^{(n)}=0$. This implies that the quantity $\Delta^{(n)}$
is valid as a measure of information leakage.

###### Proof:

The part a) is obvious. We prove the part b). When
$I(C_{1}^{m_{1}}C_{2}^{m_{2}};{\mbox{\boldmath$X$}}_{1}$
${\mbox{\boldmath$X$}}_{2})=0$, we have that

$\displaystyle
p_{C_{1}^{m_{1}}C_{2}^{m_{2}}|{\mbox{\scriptsize\boldmath$X$}}_{1}{\mbox{\scriptsize\boldmath$X$}}_{2}}(c_{1}^{m_{1}},c_{2}^{m_{2}}|{\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})=p_{C_{1}^{m_{1}}C_{2}^{m_{2}}}(c_{1}^{m_{1}},c_{2}^{m_{2}}),$
$\displaystyle\quad\forall(c_{1}^{m_{1}},c_{2}^{m_{2}})\in{\cal
X}_{1}^{m_{1}}\times{\cal X}_{2}^{m_{2}}\mbox{ and
}({\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})\in{\cal D}^{(n)}.$

Then by Lemma 1, we have that

$\displaystyle\sum_{({\mbox{\scriptsize\boldmath$x$}}_{1},{\mbox{\scriptsize\boldmath$x$}}_{2})\in{\cal
D}^{(n)}}p_{C_{1}^{m_{1}}C_{2}^{m_{2}}|{\mbox{\scriptsize\boldmath$X$}}_{1}{\mbox{\scriptsize\boldmath$X$}}_{2}}(c_{1}^{m_{1}},c_{2}^{m_{2}}|{\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})$
$\displaystyle=p_{C_{1}^{m_{1}}C_{2}^{m_{2}}}(c_{1}^{m_{1}},c_{2}^{m_{2}})|{\cal
D}^{(n)}|$
$\displaystyle\stackrel{{\scriptstyle{\rm(a)}}}{{=}}p_{C_{1}^{m_{1}}C_{2}^{m_{2}}}(c_{1}^{m_{1}},c_{2}^{m_{2}}){|{\cal
X}_{1}^{m_{1}}||{\cal X}_{2}^{m_{2}}|}=1,$
$\displaystyle\forall(c_{1}^{m_{1}},c_{2}^{m_{2}})\in{\cal
X}_{1}^{m_{1}}\times{\cal X}_{2}^{m_{2}}.$

Step (a) follows from Property 1. Hence we have

$\displaystyle
p_{C_{1}^{m_{1}}C_{2}^{m_{2}}}(c_{1}^{m_{1}},c_{2}^{m_{2}})=\frac{1}{|{\cal
X}_{1}^{m_{1}}||{\cal X}_{2}^{m_{2}}|},$
$\displaystyle\forall(c_{1}^{m_{1}},c_{2}^{m_{2}})\in{\cal
X}_{1}^{m_{1}}\times{\cal X}_{2}^{m_{2}},$

implying that
$D(p_{C_{1}^{m_{1}}C_{2}^{m_{2}}}||p_{\check{C}_{1}^{m_{1}}\check{C}_{2}^{m_{2}}})=0.$
Hence, we have

$\displaystyle\Delta^{(n)}=I(C_{1}^{m_{1}}C_{2}^{m_{2}};{\mbox{\boldmath$X$}}_{1}{\mbox{\boldmath$X$}}_{2})+D(p_{C_{1}^{m_{1}}C_{2}^{m_{2}}}||p_{\check{C}_{1}^{m_{1}}\check{C}_{2}^{m_{2}}})=0,$

completing the proof. ∎

###### Remark 1

The part a) in the above property is quite essential. Without this condition
it may happen that $\Delta_{\rm
MI}^{(n)}=I(C_{1}^{m_{1}}C_{2}^{m_{2}};{\mbox{\boldmath$X$}}_{1}{\mbox{\boldmath$X$}}_{2})=0,$
but

$\displaystyle\Delta^{(n)}=I(C_{1}^{m_{1}}C_{2}^{m_{2}};{\mbox{\boldmath$X$}}_{1}{\mbox{\boldmath$X$}}_{2})+D(p_{C_{1}^{m_{1}}C_{2}^{m_{2}}}||p_{\check{C}_{1}^{m_{1}}\check{C}_{2}^{m_{2}}})$
$\displaystyle=D(p_{C_{1}^{m_{1}}C_{2}^{m_{2}}}||p_{\check{C}_{1}^{m_{1}}\check{C}_{2}^{m_{2}}})>0.$

Such $\Delta^{(n)}$ is invalid for the security criterion.

###### Remark 2

Now we will explain the relationship between the above statement of Propostion
1 part a) and the result of Santoso and Oohama in [1], [2]. In [1], [2],
Santoso and Oohama used the mutual information as the security metric.
Informally, Santoso and Oohama use a certain compression function to flat the
distribution of ciphertexts in each encryption node before they are released
to the public channel such that even in the case that the encryption keys
between distributed sources are correlated, the security is guaranteed.
However, it has not been clear whether the flattening of the ciphertexts is
the only possible method to guarantee the security of the scheme. In short,
the above statement of Propostion 1 part a) said that in the perfect case, the
flattening of the ciphertexts into a perfect uniform distribution is the only
way to make the scheme achieve perfect security.

Defining Reliability and Security: The decoding process is successful if
$(\widehat{{\mbox{\boldmath$X$}}}_{1},\widehat{{\mbox{\boldmath$X$}}}_{2})=({\mbox{\boldmath$X$}}_{1},$
${\mbox{\boldmath$X$}}_{2})$ holds. Hence the decoding error probability is
given by

$\displaystyle\Pr[\Psi^{(n)}({\mbox{\boldmath$K$}}_{1},{\mbox{\boldmath$K$}}_{2},\phi_{1}^{(n)}({{\mbox{\boldmath$K$}}_{1},{\mbox{\boldmath$X$}}_{1}}),\phi_{2}^{(n)}({{\mbox{\boldmath$K$}}_{2},{\mbox{\boldmath$X$}}_{2}}))$
$\displaystyle\qquad\neq({{\mbox{\boldmath$X$}}_{1}},{{\mbox{\boldmath$X$}}_{2}})]$
$\displaystyle=\Pr[\Psi^{(n)}_{{\mbox{\scriptsize\boldmath$K$}}_{1},{\mbox{\scriptsize\boldmath$K$}}_{2}}(\Phi_{1,{\mbox{\scriptsize\boldmath$K$}}_{1}}^{(n)}({\mbox{\boldmath$X$}}_{1}),\Phi_{2,{\mbox{\scriptsize\boldmath$K$}}_{2}}^{(n)}({\mbox{\boldmath$X$}}_{2}))\neq({{\mbox{\boldmath$X$}}_{1}},{{\mbox{\boldmath$X$}}_{2}})]$
$\displaystyle=\Pr[\psi^{(n)}(\phi_{1}^{(n)}({\mbox{\boldmath$X$}}_{1}),\phi_{2}^{(n)}({\mbox{\boldmath$X$}}_{2}))\neq({\mbox{\boldmath$X$}}_{1},{\mbox{\boldmath$X$}}_{2})]$
$\displaystyle=\Pr[({\mbox{\boldmath$X$}}_{1},{\mbox{\boldmath$X$}}_{2})\notin{\cal
D}^{(n)})].$

Since the above quantity depends only on
$(\phi_{1}^{(n)},\phi_{2}^{(n)},\psi^{(n)})$, we wirte the error probability
$p_{{\rm e}}$ of decoding as

$\displaystyle p_{{\rm e}}=$ $\displaystyle p_{{\rm
e}}(\phi_{1}^{(n)},\phi_{2}^{(n)},\psi^{(n)}|{p}_{X_{1}X_{2}}^{n},{p}_{K_{1}K_{2}}^{n})$
$\displaystyle:=$
$\displaystyle\Pr[({\mbox{\boldmath$X$}}_{1},{\mbox{\boldmath$X$}}_{2})\notin{\cal
D}^{(n)})].$

Since $\Delta^{(n)}$ depends on $(\Phi_{1}^{(n)},\Phi_{2}^{(n)},\Psi^{(n)})$,
we write this quantity as

$\Delta^{(n)}=\Delta^{(n)}(\Phi_{1}^{(n)},\Phi_{2}^{(n)},\Psi^{(n)}|{p}_{X_{1}X_{2}}^{n},{p}_{K_{1}K_{2}}^{n}).$

###### Definition 2

We fix some positive constant $\varepsilon_{0}$. For a fixed pair
$(\varepsilon,\delta)\in[0,\varepsilon_{0}]\times(0,1)$, $(R_{1},R_{2})$ is
$(\varepsilon,\delta)$-admissible if there exists a sequence
$\\{(\Phi_{1}^{(n)},\Phi_{2}^{(n)},$ $\Psi^{(n)})\\}_{n\geq 1}$ such that
$\forall\gamma>0$, $\exists n_{0}=n_{0}(\gamma)\in\mathbb{N}$, $\forall n\geq
n_{0}$, we have

$\displaystyle\frac{1}{n}\log|{\cal X}_{i}^{m_{i}}|=\frac{m_{i}}{n}\log|{\cal
X}_{i}|\in\left[R_{i}-\gamma,R_{i}+\gamma\right],i=1,2,$ $\displaystyle
p_{{\rm
e}}(\phi_{1}^{(n)},\phi_{2}^{(n)},\psi^{(n)}|{p}_{X_{1}X_{2}}^{n},{p}_{K_{1}K_{2}}^{n})\leq\delta,$
$\displaystyle\Delta^{(n)}(\Phi_{1}^{(n)},\Phi_{2}^{(n)},\Psi^{(n)}|{p}_{X_{1}X_{2}}^{n},{p}_{K_{1}K_{2}}^{n})\leq\varepsilon.$

###### Definition 3

(Reliable and Secure Rate Set) Let $\mathcal{R}(\varepsilon,$
$\delta|p_{X_{1}X_{2}},$ $p_{K_{1}K_{2}})$ denote the set of all
$(R_{1},R_{2})$ such that $(R_{1},$ $R_{2})$ is
$(\varepsilon,\delta)$-admissible. Furthermore, set

$\mathcal{R}(p_{X_{1}X_{1}},p_{K_{1}K_{2}}):=\bigcap_{\scriptstyle(\varepsilon,\delta)\in(0,\varepsilon_{0}]\atop{\scriptstyle\times(0,1)}}\mathcal{R}(\varepsilon,\delta|p_{X_{1}X_{2}},p_{K_{1}K_{2}})$

We call $\mathcal{R}(p_{X_{1}X_{2}},p_{K_{1}K_{2}})$ the _reliable and secure
rate_ set.

###  III-B Strong Converse for the Distributed Source Encryption

To state our results on
$\mathcal{R}(\varepsilon,\delta|p_{X_{1}X_{2}},p_{K_{1}K_{2}})$ for
$(\varepsilon,\delta)\in[0,\varepsilon_{0}]\times(0,1)$, define the following
two regions:

$\displaystyle\mathcal{R}_{\mathrm{sw}}(p_{X_{1}X_{2}}):=\\{(R_{1},R_{2}):\ $
$\displaystyle R_{1}\geq H(X_{1}|X_{2}),$ $\displaystyle R_{2}\geq
H(X_{2}|X_{1}),$ $\displaystyle R_{1}+R_{2}\geq H(X_{1}X_{2})\\},$
$\displaystyle\mathcal{R}_{\mathrm{key}}(p_{K_{1}K_{2}}):=\\{(R_{1},R_{2}):\ $
$\displaystyle R_{1}\leq H(K_{1}),R_{2}\leq H(K_{2}),$ $\displaystyle
R_{1}+R_{2}\leq H(K_{1}K_{2})\\}.$

Santoso and Oohama [1], [2] proved that the bound
$\mathcal{R}_{\mathrm{key}}(p_{K_{1}K_{2}})$ $\cap$
$\mathcal{R}_{\mathrm{sw}}(p_{X_{1}X_{2}})$ serves as an inner bound of
$\mathcal{R}(p_{X_{1}X_{2}}$, $p_{K_{1}K_{2}})$ in the case where the security
criterion is measured by the mutual information $\Delta_{\rm MI}^{(n)}$. By a
simple observation we can see that their post encryption compression scheme
yields the same bound in the present case of security criterion mesured by
$\Delta^{(n)}$. Hence we have the following theorem:

###### Theorem 1

For each $(\varepsilon,\delta)\in(0,\varepsilon_{0}]\times(0,1)$, we have

$\displaystyle\mathcal{R}_{\mathrm{key}}(p_{K_{1}K_{2}})\cap\mathcal{R}_{\mathrm{sw}}(p_{X_{1}X_{2}})$
$\displaystyle\subseteq\mathcal{R}(p_{X_{1}X_{2}},p_{K_{1}K_{2}})\subseteq\mathcal{R}(\varepsilon,\delta|p_{X_{1}X_{2}},p_{K_{1}K_{2}}).$

Outline of the proof of this theorem will be given in the next section. We
next derive one outer bound by a simple observation based on previous works on
the distributed source coding for correlted sources. From the communication
scheme we can see that the common key cryptosysytem can be regarded as the
data compression system, where for each $i=1,2$, the encoder $\Phi_{i}^{(n)}$
and the decoder $\Psi^{(n)}$ can use the common side information
${\mbox{\boldmath$K$}}_{i}$. By the strong converse coding theorem for this
data compression system [9], we have that if

$\displaystyle R_{1}<H(X_{1}|X_{2}K_{1}K_{2})=H(X_{1}|X_{2})\mbox{ or }$
$\displaystyle R_{2}<H(X_{2}|X_{1}K_{1}K_{2})=H(X_{2}|X_{1})\mbox{ or }$
$\displaystyle R_{1}+R_{2}<H(X_{1}X_{2}|K_{1}K_{2})=H(X_{1}X_{2})$

then $\forall\tau\in(0,1)$, $\forall\gamma>0$, and
$\forall\\{(\phi_{1}^{(n)},\phi_{2}^{(n)},$ $\psi^{(n)})\\}_{n\geq 1}$,
$\exists n_{0}=n_{0}(\tau,\gamma)\in\mathbb{N}$, $\forall n\geq n_{0}$, we
have the following:

$\displaystyle\frac{m}{n}\log|{\cal X}_{i}|\leq R_{i}+\gamma,i=1,2,\>$
$\displaystyle p_{{\rm
e}}(\phi_{1}^{(n)},\phi_{2}^{(n)},\psi^{(n)}|p^{n}_{X_{1}X_{2}},p^{n}_{K_{1}K_{2}})\geq
1-\tau.$

Hence we have the following theorem.

###### Theorem 2

For each $(\varepsilon,\delta)\in(0,\varepsilon_{0}]\times(0,1)$, we have

$\displaystyle\mathcal{R}(\varepsilon,\delta|p_{X_{1}X_{2}},p_{K_{1}K_{2}})\subseteq\mathcal{R}_{\mathrm{sw}}(p_{X_{1}X_{2}}).$

In this paper we prove that for some $\varepsilon_{0}>0$, the set
$\mathcal{R}_{\mathrm{key}}($ $p_{K_{1}K_{2}})$ serves as an outer bound of
$\mathcal{R}(\varepsilon,\delta|p_{X_{1}X_{2}},$ $p_{K_{1}K_{2}})$ for
$(\varepsilon,\delta)\in(0,\varepsilon_{0}]\times(0,1)$. The following is the
key lemma to derive the above result.

###### Lemma 2

$\displaystyle\max\\{\begin{array}[t]{l}m_{1}\log|{\cal
X}_{1}|-nH(K_{1}),m_{2}\log|{\cal X}_{2}|-nH(K_{2}),\\\ m_{1}\log|{\cal
X}_{1}|+m_{2}\log|{\cal X}_{2}|-nH(K_{2}K_{2})\\}\end{array}$ (4)
$\displaystyle\leq\Delta^{(n)}.$ (5)

Proof of this lemma is given in Appendix -D. As an immediate consequence of
the above lemma, we have the following proposition.

###### Proposition 2

If
$(R_{1},R_{2})\in\mathcal{R}(\varepsilon,\delta|p_{X_{1}X_{2}},p_{K_{1}K_{2}})$,
then we have that $\forall\gamma>0$, $\exists n_{0}(\gamma)$, $\forall n\geq
n_{0}(\gamma)$, we have

$\displaystyle R_{i}\leq H(K_{i})+\gamma+\frac{\varepsilon}{n},i=1,2,$
$\displaystyle R_{1}+R_{2}\leq H(K_{1}K_{2})+\gamma+\frac{\varepsilon}{n}.$

From this proposition we have the following theorem.

###### Theorem 3

For each $(\varepsilon,\delta)\in(0,\varepsilon_{0}]\times(0,1)$, we have

$\displaystyle\mathcal{R}(\varepsilon,\delta|p_{X_{1}X_{2}},p_{K_{1}K_{2}})\subseteq\mathcal{R}_{\mathrm{key}}(p_{K_{1}K_{2}}).$

Combining Theorems 1, 2, and 3, we establish the following:

###### Theorem 4

For each $(\varepsilon,\delta)\in(0,\varepsilon_{0}]\times(0,1)$, we have

$\displaystyle\mathcal{R}_{\mathrm{key}}(p_{K_{1}K_{2}})\cap\mathcal{R}_{\mathrm{sw}}(p_{X_{1}X_{2}})$
$\displaystyle=\mathcal{R}(p_{X_{1}X_{2}},p_{K_{1}K_{2}})=\mathcal{R}(\varepsilon,\delta|p_{X_{1}X_{2}},p_{K_{1}K_{2}}).$

##  IV Outline of the Proof of Theorem 1

Figure 3: Our proposed solution: linear encoders as privacy amplifiers.

In this section we outline the proof of Theorem 1. Our construction of
$(\Phi_{1}^{(n)},\Phi_{2}^{(n)},\Psi^{(n)})$ is the same as that of Santoso
and Oohama [1], [2] for the post encryption commpression scheme.

Let $\phi^{(n)}:=(\phi_{1}^{(n)},\phi_{2}^{(n)})$ be a pair of linear mappings
$\phi_{1}^{(n)}:\mathcal{X}_{1}^{n}\rightarrow\mathcal{X}_{1}^{m_{1}}$ and
$\phi_{2}^{(n)}:\mathcal{X}_{2}^{n}\rightarrow\mathcal{X}_{2}^{m_{2}}$. For
each $i=1,2$, we define the mapping $\phi_{i}^{(n)}{\cal X}_{i}^{n}\to{\cal
X}_{i}^{m_{i}}$ by

$\phi_{i}^{(n)}({{\mbox{\boldmath$x$}}_{i}})={{\mbox{\boldmath$x$}}_{i}}A_{i}\mbox{
for }{{\mbox{\boldmath$x$}}_{i}}\in{\cal X}_{i}^{n},$ (6)

where $A_{i}$ is a matrix with $n$ rows and $m_{i}$ columns. For each $i=1,2$,
entries of $A_{i}$ are from ${\cal X}_{i}$. We fix
$b_{i}^{m_{i}}\in\mathcal{X}_{i}^{m_{i}},$ $i=1,2$. For each $i=1,2$, define
the mapping $\varphi^{(n)}_{i}:{\cal X}_{i}^{n}\to{\cal X}_{i}^{m_{i}}$ by

$\displaystyle\varphi_{i}^{(n)}({{\mbox{\boldmath$k$}}_{i}}):=\phi_{i}^{(n)}({{\mbox{\boldmath$k$}}_{i}})\oplus
b_{i}^{m_{i}}={{\mbox{\boldmath$k$}}_{i}}A_{i}\oplus b_{i}^{m_{i}},$ (7)

for ${{\mbox{\boldmath$k$}}_{i}}\in\mathcal{X}^{n}_{i}$. For each $i=1,2$, the
mapping $\varphi_{i}^{(n)}$ is called the affine mapping induced by the linear
mapping $\phi_{i}^{(n)}$ and constant vector $b_{i}^{m_{i}}$ $\in{\cal
X}^{m_{i}}$. For each $i=1,2$, define $\Phi_{i}^{(n)}$ by

$\Phi_{i}^{(n)}({\mbox{\boldmath$k$}}_{i},{\mbox{\boldmath$x$}}_{i})=\varphi_{i}^{(n)}({{\mbox{\boldmath$k$}}}_{i}\oplus{\mbox{\boldmath$x$}}_{i}).$

By the definition (7) of $\varphi_{i}^{(n)}$, $i=1,2$, we have

$\displaystyle\Phi_{i}^{(n)}({\mbox{\boldmath$k$}}_{i},{\mbox{\boldmath$x$}}_{i})=\varphi_{i}^{(n)}({{\mbox{\boldmath$x$}}_{i}}\oplus{{\mbox{\boldmath$k$}}_{i}})$
$\displaystyle=({{\mbox{\boldmath$x$}}_{i}}\oplus{{\mbox{\boldmath$k$}}_{i}})A_{i}\oplus
b_{i}^{m_{i}}={{\mbox{\boldmath$x$}}_{i}}A_{i}\oplus({{\mbox{\boldmath$k$}}_{i}}A_{i}\oplus
b_{i}^{m_{i}})$
$\displaystyle=\phi_{i}^{(n)}({{\mbox{\boldmath$x$}}_{i}})\oplus\varphi_{i}^{(n)}({{\mbox{\boldmath$k$}}_{i}}),\mbox{
for }{{\mbox{\boldmath$x$}}_{i}},{{\mbox{\boldmath$k$}}_{i}}\in{\cal
X}_{i}^{n}.$ (8)

Set $\varphi^{(n)}:=(\varphi_{1}^{(n)},\varphi_{2}^{(n)})$. Next, let
$\psi^{(n)}$ be the corresponding joint decoder for $\phi^{(n)}$ such that
$\psi^{(n)}:\mathcal{X}_{1}^{m_{1}}\times\mathcal{X}_{2}^{m_{2}}\rightarrow\mathcal{X}_{1}^{n}\times\mathcal{X}_{2}^{n}.$
Note that $\psi^{(n)}$ does not have a linear structure in general.

#### Description of Proposed procedure

We describe the procedure of our privacy amplified system as follows.

  1. 1.

_Encoding of Ciphertexts:_ First, we use $\varphi_{1}^{(n)}$ and
$\varphi_{2}^{(n)}$ to encode the ciphertexts
${\mbox{\boldmath$X$}}_{1}\oplus{\mbox{\boldmath$K$}}_{1}$ and
${\mbox{\boldmath$X$}}_{2}\oplus{\mbox{\boldmath$K$}}_{2}$. Let
$C_{i}^{m_{i}}=\varphi_{i}^{(n)}({\mbox{\boldmath$X$}}_{i}\oplus{{\mbox{\boldmath$K$}}}_{i})$
for $i=1,2$. By the affine structure (8) of encoders we have that for each
$i=1,2$,

$\displaystyle\Phi_{i}^{(n)}({{\mbox{\boldmath$K$}}_{i}}),{{\mbox{\boldmath$X$}}_{i}})={C}_{i}^{m_{i}}=\varphi_{i}^{(n)}({{\mbox{\boldmath$X$}}_{i}}\oplus{{\mbox{\boldmath$K$}}_{i}})$
$\displaystyle=\phi_{i}^{(n)}({{\mbox{\boldmath$X$}}_{i}})\oplus\varphi_{i}^{(n)}({{\mbox{\boldmath$K$}}_{i}})=\widetilde{X}_{i}^{m_{i}}\oplus\widetilde{K}_{i}^{m_{i}},$
(9)

where
$\widetilde{X}_{i}^{m_{i}}:=\phi_{i}^{(n)}({{\mbox{\boldmath$X$}}_{i}}),\widetilde{K}_{i}^{m_{i}}:=\varphi_{i}^{(n)}({{\mbox{\boldmath$K$}}_{i}}).$

  2. 2.

_Decoding at Joint Sink Node $\mathsf{D}$:_ First, using the pair of linear
encoders $(\varphi_{1}^{(n)},\varphi_{2}^{(n)})$, $\mathsf{D}$ encodes the
keys $({{\mbox{\boldmath$K$}}_{1}},{{\mbox{\boldmath$K$}}_{2}})$ which are
received through private channel into
$(\widetilde{K}_{1}^{m_{1}},\widetilde{K}_{2}^{m_{2}})=$
$(\varphi_{1}^{(n)}({{\mbox{\boldmath$K$}}_{1}}),\varphi_{2}^{(n)}({{\mbox{\boldmath$K$}}_{2}}))$.
Receiving $({C}_{1}^{m_{1}},{C}_{2}^{m_{2}})$ from public communication
channel, $\mathsf{D}$ computes $\widetilde{X}_{i}^{m_{i}},i=1,2$ in the
following way. From (9), we have that for each $i=1,2$, the decoder
$\mathsf{D}$ can obtain
$\widetilde{X}_{i}^{m_{i}}=\phi_{i}^{(n)}({{\mbox{\boldmath$X$}}_{i}})$ by
subtracting
$\widetilde{K}_{i}^{m_{i}}=\varphi_{i}^{(n)}({{\mbox{\boldmath$K$}}_{i}})$
from ${C}_{i}^{m_{i}}$. Finally, $\mathsf{D}$ outputs
$(\widehat{\mbox{\boldmath$X$}}_{1},\widehat{\mbox{\boldmath$X$}}_{2})$ by
applying the joint decoder $\psi^{(n)}$ to
$(\widetilde{X}_{1}^{m_{1}},\widetilde{X}_{2}^{m_{2}})$ as follows:

$\displaystyle(\widehat{\mbox{\boldmath$X$}}_{1},\widehat{\mbox{\boldmath$X$}}_{2})$
$\displaystyle=(\psi^{(n)}(\widetilde{X}_{1}^{m_{1}},\widetilde{X}_{2}^{m_{2}}))$
$\displaystyle=(\psi^{(n)}(\phi_{1}^{(n)}({{\mbox{\boldmath$X$}}_{1}}),\phi_{2}^{(n)}({{\mbox{\boldmath$X$}}_{2}})).$
(10)

We summarize the above argument. For
$({\mbox{\boldmath$K$}}_{1},{\mbox{\boldmath$K$}}_{2})$ and
$(C_{1}^{m_{1}},C_{2}^{m_{2}})$, define $\Psi^{(n)}$ by

$\displaystyle\Psi^{(n)}({\mbox{\boldmath$K$}}_{1},{\mbox{\boldmath$K$}}_{2},C_{1}^{m_{1}},C_{2}^{m_{2}})=\Psi^{(n)}_{{\mbox{\scriptsize\boldmath$K$}}_{1},{\mbox{\scriptsize\boldmath$K$}}_{2}}(C_{1}^{m_{1}},C_{2}^{m_{2}})$
$\displaystyle:=\psi^{(n)}({C}_{1}^{m_{1}}\ominus\widetilde{K}_{1}^{m_{1}},{C}_{2}^{m_{2}}\ominus\widetilde{K}_{2}^{m_{2}})$
$\displaystyle=\psi^{(n)}(\widetilde{X}_{1}^{m_{1}},\widetilde{X}_{2}^{m_{2}}).$

By the above definition and
$C_{i}^{m_{i}}=\Phi^{(n)}_{i,{{\mbox{\scriptsize\boldmath$K$}}}_{i}}({\mbox{\boldmath$X$}}_{i}),i=1,2,$
we have

$\displaystyle\Psi^{(n)}_{{\mbox{\scriptsize\boldmath$K$}}_{1},{\mbox{\scriptsize\boldmath$K$}}_{2}}(\Phi^{(n)}_{1,{\mbox{\scriptsize\boldmath$K$}}_{1}}({\mbox{\boldmath$X$}}_{1}),\Phi^{(n)}_{2,{\mbox{\scriptsize\boldmath$K$}}_{2}}({\mbox{\boldmath$X$}}_{2}))$
$\displaystyle=\psi^{(n)}(\widetilde{X}_{1}^{m_{1}},\widetilde{X}_{2}^{m_{2}})=\psi^{(n)}(\phi_{1}^{(n)}({\mbox{\boldmath$X$}}_{1}),\phi_{2}^{(n)}({\mbox{\boldmath$X$}}_{2})).$

Hence we have the condition which $(\Phi^{(n)}_{1},\Phi^{(n)}_{2},\Psi^{(n)})$
must satisfy.

In this paper, we use the _minimum entropy decoder_ for our joint decoder
$\psi^{(n)}$.
Minimum Entropy Decoder: For
$\phi_{i}^{(n)}({\mbox{\boldmath$x$}}_{i})=\widetilde{x}_{i}^{m_{i}},i=1,2$,
$\psi^{(n)}:{\cal X}_{1}^{m_{1}}\times{\cal X}_{2}^{m_{2}}\to{\cal
X}_{1}^{n}\times{\cal X}_{2}^{n}$ is defined as follows:

$\displaystyle\psi^{(n)}(\widetilde{x}_{1}^{m_{1}},\widetilde{x}_{2}^{m_{2}})$
$\displaystyle:=\left\\{\begin{array}[]{cl}({\widehat{\mbox{\boldmath$x$}}_{1}},{\widehat{\mbox{\boldmath$x$}}_{2}})&\mbox{if
}\phi_{i}^{(n)}({\widehat{\mbox{\boldmath$x$}}_{i}})=\widetilde{x}_{i}^{m_{i}},i=1,2,\\\
&\mbox{and
}H({\widehat{\mbox{\boldmath$x$}}_{1}}{\widehat{\mbox{\boldmath$x$}}_{2}})<H({\check{\mbox{\boldmath$x$}}_{1}}{\check{\mbox{\boldmath$x$}}_{2}})\\\
&\mbox{for all
}({\check{\mbox{\boldmath$x$}}_{1}},{\check{\mbox{\boldmath$x$}}_{2}})\mbox{
such that }\\\
&\>\phi_{i}^{(n)}({\check{\mbox{\boldmath$x$}}_{i}})=\widetilde{x}_{i}^{m_{i}},i=1,2,\\\
&\mbox{and
}\>({\check{\mbox{\boldmath$x$}}_{1}},{\check{\mbox{\boldmath$x$}}_{2}})\neq({\widehat{\mbox{\boldmath$x$}}_{1}},{\widehat{\mbox{\boldmath$x$}}_{2}}),\vspace{0.2cm}\\\
\mbox{arbitrary}&\mbox{if there is no such
}({\widehat{\mbox{\boldmath$x$}}_{1}},{\widehat{\mbox{\boldmath$x$}}_{2}})\in{\cal
X}_{1}^{n}\times{\cal X}_{2}^{n}.\end{array}\right.$

Our privacy amplified system described above is illustrated in Fig. 3.

Evaluations of the reliablility and security: On the error probability $p_{\rm
e}$ of decoding we have

$\displaystyle p_{\rm
e}=\Pr[\Psi^{(n)}({\mbox{\boldmath$K$}}_{1},{\mbox{\boldmath$K$}}_{2},\phi_{1}^{(n)}({{\mbox{\boldmath$K$}}_{1},{\mbox{\boldmath$X$}}_{1}}),\phi_{2}^{(n)}({{\mbox{\boldmath$K$}}_{2},{\mbox{\boldmath$X$}}_{2}}))$
$\displaystyle\qquad\neq({{\mbox{\boldmath$X$}}_{1}},{{\mbox{\boldmath$X$}}_{2}})]$
$\displaystyle=\Pr[\Psi^{(n)}_{{\mbox{\scriptsize\boldmath$K$}}_{1},{\mbox{\scriptsize\boldmath$K$}}_{2}}(\Phi_{1,{\mbox{\scriptsize\boldmath$K$}}_{1}}^{(n)}({\mbox{\boldmath$X$}}_{1}),\Phi_{2,{\mbox{\scriptsize\boldmath$K$}}_{2}}^{(n)}({\mbox{\boldmath$X$}}_{2}))\neq({{\mbox{\boldmath$X$}}_{1}},{{\mbox{\boldmath$X$}}_{2}})]$
$\displaystyle=\Pr[\psi^{(n)}(\phi_{1}^{(n)}({\mbox{\boldmath$X$}}_{1}),\phi_{2}^{(n)}({\mbox{\boldmath$X$}}_{2}))\neq({\mbox{\boldmath$X$}}_{1},{\mbox{\boldmath$X$}}_{2})].$

Computing $\Delta^{(n)}$, we have

$\displaystyle\Delta^{(n)}=D(p_{C^{m_{1}}C^{m_{2}}|{\mbox{\scriptsize\boldmath$X$}}_{1}{\mbox{\scriptsize\boldmath$X$}}_{2}}\|p_{\check{C}_{1}^{m_{1}}\check{C}_{2}^{m_{2}}}|p_{{\mbox{\scriptsize\boldmath$X$}}_{1}{\mbox{\scriptsize\boldmath$X$}}_{2}})$
$\displaystyle=m_{1}\log|{\cal X}_{1}|+m_{2}\log|{\cal
X}_{2}|-H(C_{1}^{m_{1}}C_{2}^{m_{2}}|{\mbox{\boldmath$X$}}_{1}{\mbox{\boldmath$X$}}_{2})$
$\displaystyle=m_{1}\log|{\cal X}_{1}|+m_{2}\log|{\cal X}_{2}|$
$\displaystyle\quad-H(\widetilde{K}_{1}^{m_{1}}\oplus\widetilde{X}_{1}^{m_{1}},\widetilde{K}_{2}^{m_{2}}\oplus\widetilde{X}_{2}^{m_{2}}|{\mbox{\boldmath$X$}}_{1}{\mbox{\boldmath$X$}}_{2})$
$\displaystyle=m_{1}\log|{\cal X}_{1}|+m_{2}\log|{\cal
X}_{2}|-H(\widetilde{K}_{1}^{m_{1}}\widetilde{K}_{2}^{m_{2}})$
$\displaystyle=D(p_{\widetilde{K}_{1}^{m_{1}}\widetilde{K}_{2}^{m_{2}}}\|p_{{U}_{1}^{m_{1}}{U}_{2}^{m_{2}}}).$

Here $p_{{U}_{1}^{m_{1}}{U}_{2}^{m_{2}}}$ is the uniform distribution over
${\cal X}_{1}^{m_{1}}\times{\cal X}_{2}^{m_{2}}$. According to Santoso and
Oohama [2], $\exists\\{(\Phi_{1}^{(n)},\Phi_{2}^{(n)},$ $\Psi^{(n)})\\}_{n\geq
1}$ such that for any $(p_{X_{1}X_{2}},p_{K_{1}K_{2}})$ satisfying

$\displaystyle\left(\frac{m_{1}}{n}\log|{\cal
X}_{1}|,\frac{m_{2}}{n}\log|{\cal X}_{2}|\right)$
$\displaystyle\in\mathcal{R}_{\mathrm{key}}(p_{K_{1}K_{2}})\cap\mathcal{R}_{\mathrm{sw}}(p_{X_{1}X_{2}}),$

the two quantities

$\displaystyle\Pr[\psi^{(n)}(\phi_{1}^{(n)}({\mbox{\boldmath$X$}}_{1}),\phi_{2}^{(n)}({\mbox{\boldmath$X$}}_{2}))\neq({\mbox{\boldmath$X$}}_{1},{\mbox{\boldmath$X$}}_{2})]\mbox{
and }$ $\displaystyle
D(p_{\widetilde{K}_{1}^{m_{1}}\widetilde{K}_{2}^{m_{2}}}\|p_{{U}_{1}^{m_{1}}{U}_{2}^{m_{2}}})$

decay exponentially as $n$ tends to infinity. Hence we have Theorem 1.

###### Remark 3

In [1], [2], on the surface, Santoso and Oohama stated that their distributed
encryption scheme is secure under the security metric based on $\Delta_{\rm
MI}^{(n)}$. However, if one looks underneath a little bit, one can easily
discover that actually Santoso and Oohama proved the security of their scheme
based on a metric that is more strict than $\Delta_{\rm MI}^{(n)}$. And one
can easily see that the more strict security metric they used is equal to our
new proposed metric $\Delta^{(n)}$. Thus, $\Delta^{(n)}$ is not a mere
theoretical concept, but an achievable security requirement which appears
naturally in the secure analysis of the communication system treated here.

###  -A Proof of Property 1

###### Proof:

We have the following:

$\displaystyle{\cal D}^{(n)}\stackrel{{\scriptstyle{\rm(a)}}}{{=}}$
$\displaystyle\\{({\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})=\psi^{(n)}(\tilde{x}_{1}^{m_{1}},\tilde{x}_{2}^{m_{2}}):$
$\displaystyle\quad(\tilde{x}_{1}^{m_{1}},\tilde{x}_{2}^{m_{2}})\in\phi_{1}^{(n)}({\cal
X}_{1}^{n})\times\phi_{2}^{(n)}({\cal X}_{2}^{n})\\}$
$\displaystyle\stackrel{{\scriptstyle{\rm(b)}}}{{=}}$
$\displaystyle\\{({\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})=\psi^{(n)}(\tilde{x}_{1}^{m_{1}},\tilde{x}_{2}^{m_{2}}):$
$\displaystyle\quad(\tilde{x}_{1}^{m_{1}},\tilde{x}_{2}^{m_{2}})\in{\cal
X}_{1}^{m_{1}}\times{\cal X}_{2}^{m_{2}}\\}.$ (11)

Step (a) follows from that every pair
$(\tilde{x}_{1}^{m_{1}},\tilde{x}_{2}^{m_{2}})\in\phi_{1}^{(n)}({\cal
X}_{1}^{n})\times\phi_{2}^{(n)}({\cal X}_{2}^{n})\\}$ uniquely determines
$({\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})\in{\cal D}^{(n)}$. Step
(b) follows from that $\phi_{i}^{(n)},i=1,2$ are surjective. Since
$\psi^{(n)}:{\cal X}_{1}^{m_{1}}\times{\cal X}_{2}^{m_{2}}\to{\cal
X}_{1}^{n}\times{\cal X}_{2}^{n}$ is a one-to-one mapping and (11), we have
$|{\cal D}^{(n)}|=|{\cal X}_{1}^{m_{1}}||{\cal X}_{2}^{m_{2}}|.$ ∎

###  -B Proof of Property 2

We frist prove the part a) and next prove the part b).

###### Proof:

Under
$({\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2}),({\mbox{\boldmath$x$}}_{1}^{\prime},{\mbox{\boldmath$x$}}_{2}^{\prime})\in{\cal
D}^{(n)}$ and $({\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})\neq$
$({\mbox{\boldmath$x$}}_{1}^{\prime},{\mbox{\boldmath$x$}}_{2}^{\prime})$, we
assume that

$(\Phi^{(n)}_{1,{\mbox{\scriptsize\boldmath$k$}}_{1}}({{\mbox{\boldmath$x$}}_{1}}),\Phi^{(n)}_{2,{\mbox{\scriptsize\boldmath$k$}}_{2}}({{\mbox{\boldmath$x$}}_{2}}))=(\Phi^{(n)}_{1,{\mbox{\scriptsize\boldmath$k$}}_{1}}({{\mbox{\boldmath$x$}}}_{1}^{\prime}),\Phi^{(n)}_{2,{\mbox{\scriptsize\boldmath$k$}}_{2}}({{\mbox{\boldmath$x$}}}_{2}^{\prime})).$
(12)

Then we have the following

$\displaystyle({\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})\stackrel{{\scriptstyle{\rm(a)}}}{{=}}\psi^{(n)}(\phi_{1}^{(n)}({\mbox{\boldmath$k$}}_{1}),\phi_{2}^{(n)}({\mbox{\boldmath$k$}}_{2}),$
$\displaystyle\stackrel{{\scriptstyle{\rm(b)}}}{{=}}\Psi^{(n)}_{{\mbox{\scriptsize\boldmath$k$}}_{1},{\mbox{\scriptsize\boldmath$k$}}_{2}}(\Phi^{(n)}_{1,{\mbox{\scriptsize\boldmath$k$}}_{1}}({{\mbox{\boldmath$x$}}_{1}}),\Phi^{(n)}_{2,{\mbox{\scriptsize\boldmath$k$}}_{2}}({{\mbox{\boldmath$x$}}_{2}}))$
$\displaystyle\stackrel{{\scriptstyle{\rm(c)}}}{{=}}\Psi^{(n)}_{{\mbox{\scriptsize\boldmath$k$}}_{1},{\mbox{\scriptsize\boldmath$k$}}_{2}}(\Phi^{(n)}_{1,{\mbox{\scriptsize\boldmath$k$}}_{1}}({{\mbox{\boldmath$x$}}}_{1}^{\prime}),\Phi^{(n)}_{2,{\mbox{\scriptsize\boldmath$k$}}_{2}}({{\mbox{\boldmath$x$}}}_{2}^{\prime}))$
$\displaystyle\stackrel{{\scriptstyle{\rm(d)}}}{{=}}\psi^{(n)}(\phi^{(n)}_{1}({{\mbox{\boldmath$x$}}}_{1}^{\prime}),\phi^{(n)}_{2}({{\mbox{\boldmath$x$}}}_{2}^{\prime}))\stackrel{{\scriptstyle{\rm(e)}}}{{=}}({{\mbox{\boldmath$x$}}}_{1}^{\prime},{{\mbox{\boldmath$x$}}}_{2}^{\prime}).$
(13)

Steps (a) and (e) follow from the definition of ${\cal D}^{(n)}$. Step (c)
follows from 12. Steps (b) and (d) follow from the relationship between
$(\phi^{(n)}_{1},\phi^{(n)}_{2},\psi^{(n)})$ and
$(\Phi^{(n)}_{1,{\mbox{\scriptsize\boldmath$k$}}_{1}},\Phi^{(n)}_{2,{\mbox{\scriptsize\boldmath$k$}}_{2}},\Psi^{(n)}_{{\mbox{\scriptsize\boldmath$k$}}_{1},{\mbox{\scriptsize\boldmath$k$}}_{2}}).$
The equality (13) contradics the first assumption. Hence we must have Property
2 part a). ∎

###### Proof:

We assume that $\exists({\mbox{\boldmath$k$}}_{1},{\mbox{\boldmath$k$}}_{2})$
and $\exists(c_{1}^{m_{1}},c_{2}^{m_{2}})$ such that
$\forall({\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})\in{\cal
D}^{(n)}$,
$(\Phi^{(n)}_{1,{\mbox{\scriptsize\boldmath$k$}}_{1}}({\mbox{\boldmath$x$}}_{1}),$
$\Phi^{(n)}_{2,{\mbox{\scriptsize\boldmath$k$}}_{2}}({\mbox{\boldmath$x$}}_{2}))$
$\neq$ $(c_{1}^{m_{1}},c_{2}^{m_{2}})$. Set

${\cal
B}:=\left\\{(\Phi^{(n)}_{1,{\mbox{\scriptsize\boldmath$k$}}_{1}}({\mbox{\boldmath$x$}}_{1}),\Phi^{(n)}_{2,{\mbox{\scriptsize\boldmath$x$}}_{2}}({\mbox{\boldmath$x$}}_{2})):({\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})\in{\cal
D}^{(n)}\right\\}.$

Then by the above assumption we have

$\displaystyle{\cal B}\subseteq{\cal X}_{1}^{m_{1}}\times{\cal
X}_{2}^{m_{2}}-\left\\{(c_{1}^{m_{1}},c_{2}^{m_{2}})\right\\}.$ (14)

On the other hand we have

$\displaystyle\Psi^{(n)}_{{\mbox{\scriptsize\boldmath$k$}}_{1},{\mbox{\scriptsize\boldmath$k$}}_{2}}({\cal
B})$
$\displaystyle=\left\\{\Psi^{(n)}_{{\mbox{\scriptsize\boldmath$k$}}_{1},{\mbox{\scriptsize\boldmath$k$}}_{2}}(\Phi^{(n)}_{1,{\mbox{\scriptsize\boldmath$k$}}_{1}}({\mbox{\boldmath$x$}}_{1}),\Phi^{(n)}_{2,{\mbox{\scriptsize\boldmath$k$}}_{2}}({\mbox{\boldmath$x$}}_{2})):({\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})\in{\cal
D}^{(n)}\right\\}$
$\displaystyle=\left\\{\psi^{(n)}(\phi^{(n)}_{1}({\mbox{\boldmath$x$}}_{1}),\phi^{(n)}_{2}({\mbox{\boldmath$x$}}_{2})):({\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})\in{\cal
D}^{(n)}\right\\}={\cal D}^{(n)},$

which together with that
$\Psi_{{\mbox{\scriptsize\boldmath$k$}}_{1},{\mbox{\scriptsize\boldmath$k$}}_{2}}^{(n)}:$
${\cal X}_{1}^{m_{1}}\times{\cal X}_{2}^{m_{2}}$$\to$ ${\cal
X}_{1}^{n}\times{\cal X}_{2}^{n}$ is a one-to-one mapping yields that

$\displaystyle|{\cal
B}|=|\Psi^{(n)}_{{\mbox{\scriptsize\boldmath$k$}}_{1},{\mbox{\scriptsize\boldmath$k$}}_{2}}({\cal
B})|=|{\cal D}^{(n)}|=|{\cal X}_{1}^{m_{1}}||{\cal X}_{2}^{m_{2}}|.$

The above equality contradicts (14). Hence we must have that
$\forall({\mbox{\boldmath$k$}}_{1},{\mbox{\boldmath$k$}}_{2}),$
$\forall(c_{1}^{m_{1}},c_{2}^{m_{2}}),$
$\exists({\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})\in{\cal
D}^{(n)}$ such that
$\Phi^{(n)}_{i,{{\mbox{\scriptsize\boldmath$k$}}}_{i}}({\mbox{\boldmath$x$}}_{i})=c_{i}^{m_{i}},i=1,2$.
∎

###  -C Proof of Lemma 1

We first define a set necessary for the proof. For
$({\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})\in{\cal
X}_{1}^{n}\times{\cal X}_{2}^{n}$, we set

$\displaystyle{\cal
A}_{{\mbox{\scriptsize\boldmath$x$}}_{1},{\mbox{\scriptsize\boldmath$x$}}_{2}}(c_{1}^{m_{1}},c_{2}^{m_{2}})$
$\displaystyle:=\left\\{({\mbox{\boldmath$k$}}_{1},{\mbox{\boldmath$k$}}_{2}):\Phi^{(n)}_{i,{\mbox{\scriptsize\boldmath$x$}}_{i}}({{\mbox{\boldmath$k$}}}_{i})=c_{i}^{m_{i}},i=1,2\right\\}.$

###### Proof:

By definition we have

$\displaystyle
p_{C_{1}^{m_{1}}C_{2}^{m_{2}}|{\mbox{\scriptsize\boldmath$X$}}_{1}{\mbox{\scriptsize\boldmath$X$}}_{2}}(c_{1}^{m_{1}},c_{2}^{m_{2}}|{\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})$
$\displaystyle={\rm
Pr}\left\\{({\mbox{\boldmath$K$}}_{1},{\mbox{\boldmath$K$}}_{2})\in{\cal
A}_{{\mbox{\scriptsize\boldmath$x$}}_{1},{\mbox{\scriptsize\boldmath$x$}}_{2}}(c_{1}^{m_{1}},c_{2}^{m_{2}})\Bigl{|}{\mbox{\boldmath$X$}}_{1}={\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$X$}}_{2}={\mbox{\boldmath$x$}}_{2}\right\\}$
$\displaystyle\stackrel{{\scriptstyle{\rm(a)}}}{{=}}{\rm
Pr}\left\\{({\mbox{\boldmath$K$}}_{1},{\mbox{\boldmath$K$}}_{2})\in{\cal
A}_{{\mbox{\scriptsize\boldmath$x$}}_{1},{\mbox{\scriptsize\boldmath$x$}}_{2}}(c_{1}^{m_{1}},c_{2}^{m_{2}})\right\\}.$
(15)

Step (a) follows from
$({\mbox{\boldmath$K$}}_{1},{\mbox{\boldmath$K$}}_{2})\perp({\mbox{\boldmath$X$}}_{1},{\mbox{\boldmath$X$}}_{2})$.
On the other hand, Property 2 part a) implies that

$\displaystyle{\cal
A}_{{\mbox{\scriptsize\boldmath$x$}}_{1},{\mbox{\scriptsize\boldmath$x$}}_{2}}(c_{1}^{m_{1}},c_{2}^{m_{2}})\cap{\cal
A}_{{{\mbox{\scriptsize\boldmath$x$}}}^{\prime}_{1},{{\mbox{\scriptsize\boldmath$x$}}}^{\prime}_{2}}(c_{1}^{m_{1}},c_{2}^{m_{2}})=\emptyset$
$\displaystyle\mbox{ for
}({\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})\neq({{\mbox{\boldmath$x$}}}^{\prime}_{1},{{\mbox{\boldmath$x$}}}^{\prime}_{2})\in{\cal
D}^{(n)}.$ (16)

Furthermore, Property 2 part b) implies that

$\displaystyle\bigcup_{({\mbox{\scriptsize\boldmath$x$}}_{1},{\mbox{\scriptsize\boldmath$x$}}_{2})\in{\cal
D}^{(n)}}{\cal
A}_{{\mbox{\scriptsize\boldmath$x$}}_{1},{\mbox{\scriptsize\boldmath$x$}}_{2}}(c_{1}^{m_{1}},c_{2}^{m_{2}})={\cal
X}_{1}^{n}\times{\cal X}_{2}^{n}.$ (17)

From (15), we have the following chain of equalities:

$\displaystyle\sum_{({\mbox{\scriptsize\boldmath$x$}}_{1},{\mbox{\scriptsize\boldmath$x$}}_{2})\in{\cal
D}^{(n)}}p_{C_{1}^{m_{1}}C_{2}^{m_{2}}|{\mbox{\scriptsize\boldmath$X$}}_{1}{\mbox{\scriptsize\boldmath$X$}}_{2}}(c_{1}^{m_{1}},c_{2}^{m_{2}}|{\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})$
$\displaystyle\stackrel{{\scriptstyle{\rm(a)}}}{{=}}\Pr\left\\{({\mbox{\boldmath$K$}}_{1},{\mbox{\boldmath$K$}}_{2})\in\bigcup_{({\mbox{\scriptsize\boldmath$x$}}_{1},{\mbox{\scriptsize\boldmath$x$}}_{2})\in{\cal
D}^{(n)}}{\cal
A}_{{\mbox{\scriptsize\boldmath$x$}}_{1},{\mbox{\scriptsize\boldmath$x$}}_{2}}(c_{1}^{m_{1}},c_{2}^{m_{2}})\right\\}\stackrel{{\scriptstyle{\rm(b)}}}{{=}}1.$

Step (a) follows from (16). Step (b) follows from (17). ∎

###  -D Proof of Lemma 2

In this appendix we prove Lemma 2. We first define quantities necessary for
the proof. For each $i=1,2$ and
${\mbox{\boldmath$x$}}_{i}\in\mathcal{X}_{i}^{n}$, we define the following:

$\displaystyle\Delta_{i}^{(n)}({\mbox{\boldmath$x$}}_{i}):=\sum_{\scriptstyle
c_{i}^{m_{i}}\in\mathcal{X}_{i}^{m_{i}}}\log\frac{p_{C_{i}^{m_{i}}|{\mbox{\scriptsize\boldmath$X$}}_{i}}(c_{i}^{m_{i}}|{\mbox{\boldmath$x$}}_{i})}{p_{\check{C}_{i}^{m_{i}}}(c_{i}^{m_{i}})}$
$\displaystyle=D(C^{m_{i}}_{{\mbox{\scriptsize\boldmath$x$}}_{i}}||\check{C}_{i}^{m_{i}})=D(p_{C_{i}^{m_{i}}|{\mbox{\scriptsize\boldmath$X$}}_{i}}(\cdot|{\mbox{\boldmath$x$}}_{i})||p_{\check{C}_{i}^{m_{i}}}).$

Furthermore for each $i=1,2$, define

$\displaystyle\Delta^{(n)}_{i}:=\sum_{\scriptstyle{\mbox{\scriptsize\boldmath$x$}}_{i}\in\mathcal{X}_{i}^{n}}p_{{\mbox{\scriptsize\boldmath$X$}}_{i}}({\mbox{\boldmath$x$}}_{i})\Delta_{i}^{(n)}({\mbox{\boldmath$x$}}_{i})=D(p_{C^{m_{i}}|{\mbox{\scriptsize\boldmath$X$}}_{i}}||p_{\check{C}_{1}^{m_{i}}}|p_{{\mbox{\scriptsize\boldmath$X$}}_{i}}).$

It is obvious that $\Delta^{(n)}\geq\Delta_{i}^{(n)},i=1,2.$

###### Proof:

By the definition of $C^{m_{i}}_{{{\mbox{\scriptsize\boldmath$x$}}}_{i}}$,
$i=1,2$, we have for $i=1,2$,

$\displaystyle\Pr\left\\{C_{i,{\mbox{\scriptsize\boldmath$x$}}_{i}}^{m_{i}}=c_{i}^{m_{i}}\right\\}=\Pr\left\\{C_{i}^{m_{i}}=c_{i}^{m_{i}}|{\mbox{\boldmath$X$}}_{i}={\mbox{\boldmath$x$}}_{i}\right\\}$
$\displaystyle=\Pr\Bigl{\\{}\Phi^{(n)}_{i,{\mbox{\scriptsize\boldmath$x$}}_{i}}({\mbox{\boldmath$K$}}_{i})=c_{i}^{m_{i}}\Bigl{|}{\mbox{\boldmath$X$}}_{i}={\mbox{\boldmath$x$}}_{i}\Bigr{\\}}$
$\displaystyle\stackrel{{\scriptstyle{\rm(a)}}}{{=}}\Pr\Bigl{\\{}\Phi^{(n)}_{i,{\mbox{\scriptsize\boldmath$x$}}_{i}}({\mbox{\boldmath$K$}}_{i})=c_{i}^{m_{i}}\Bigr{\\}}.$
(18)

Step (a) follows from that
${\mbox{\boldmath$K$}}_{i}\perp{\mbox{\boldmath$X$}}_{i},i=1,2.$ Then for
$i=1,2$, we have the following:

$\displaystyle\Delta_{i}^{(n)}({\mbox{\boldmath$x$}}_{i})=m_{i}\log|{\cal
X}_{i}|-H(C_{{\mbox{\scriptsize\boldmath$x$}}_{i}}^{m_{i}})$
$\displaystyle\stackrel{{\scriptstyle{\rm(a)}}}{{=}}m_{i}\log|{\cal
X}_{i}|-H(\Phi^{(n)}_{i,{\mbox{\scriptsize\boldmath$x$}}_{i}}({\mbox{\boldmath$K$}}_{i}))$
$\displaystyle\stackrel{{\scriptstyle{\rm(b)}}}{{\geq}}m_{i}\log|{\cal
X}_{i}|-H({\mbox{\boldmath$K$}}_{i})=m_{i}\log|{\cal X}_{i}|-nH(K_{i}).$ (19)

Step (a) follows from (18). Step (b) follows from the data processing
inequality. Hence from (19), we have

$\displaystyle\Delta_{i}^{(n)}\geq m_{i}\log|{\cal X}_{i}|-nH(K_{i})\mbox{ for
}i=1,2.$ (20)

Furthermore, we have

$\displaystyle\Pr\left\\{C_{{\mbox{\scriptsize\boldmath$x$}}_{1}}^{m_{1}}=c_{1}^{m_{1}},C_{{\mbox{\scriptsize\boldmath$x$}}_{2}}^{m_{2}}=c_{2}^{m_{2}}\right\\}$
$\displaystyle=\Pr\left\\{{C}^{m_{1}}=c_{1}^{m_{1}},{C}^{m_{2}}=c_{2}^{m_{2}}|{\mbox{\boldmath$X$}}_{1}={\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$X$}}_{2}={\mbox{\boldmath$x$}}_{2}\right\\}$
$\displaystyle=\Pr\Bigl{\\{}\Phi^{(n)}_{1,{\mbox{\scriptsize\boldmath$x$}}_{1}}({\mbox{\boldmath$K$}}_{1})=c_{1}^{m_{1}},\Phi^{(n)}_{2,{\mbox{\scriptsize\boldmath$x$}}_{2}}({\mbox{\boldmath$K$}}_{2})=c_{2}^{m_{2}}$
$\displaystyle\quad\qquad\Bigl{|}{\mbox{\boldmath$X$}}_{1}={\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$X$}}_{2}={\mbox{\boldmath$x$}}_{2}\Bigr{\\}}$
$\displaystyle\stackrel{{\scriptstyle{\rm(a)}}}{{=}}\Pr\Bigl{\\{}\Phi^{(n)}_{1,{\mbox{\scriptsize\boldmath$x$}}_{1}}({\mbox{\boldmath$K$}}_{1})=c_{1}^{m_{1}},\Phi^{(n)}_{2,{\mbox{\scriptsize\boldmath$x$}}_{2}}({\mbox{\boldmath$K$}}_{2})=c_{2}^{m_{2}}\Bigr{\\}}.$
(21)

Step (a) follows from that
$({\mbox{\boldmath$K$}}_{1},{\mbox{\boldmath$K$}}_{2})\perp({\mbox{\boldmath$X$}}_{1},{\mbox{\boldmath$X$}}_{2})$.
Then, we have the following:

$\displaystyle\Delta^{(n)}({\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2})=m_{1}\log|{\cal
X}_{1}|+m_{2}\log|{\cal
X}_{2}|-H(C_{{\mbox{\scriptsize\boldmath$x$}}_{1}}^{m_{1}}C_{{\mbox{\scriptsize\boldmath$x$}}_{2}}^{m_{2}})$
$\displaystyle=m_{1}\log|{\cal X}_{1}|+m_{2}\log|{\cal
X}_{2}|-H(\Phi^{(n)}_{1,{\mbox{\scriptsize\boldmath$x$}}_{1}}({\mbox{\boldmath$K$}}_{1})\Phi^{(n)}_{2,{\mbox{\scriptsize\boldmath$x$}}_{2}}({\mbox{\boldmath$K$}}_{2}))$
$\displaystyle\stackrel{{\scriptstyle{\rm(b)}}}{{\geq}}m_{1}\log|{\cal
X}_{1}|+m_{2}\log|{\cal
X}_{2}|-H({\mbox{\boldmath$K$}}_{1}{\mbox{\boldmath$K$}}_{2})$
$\displaystyle=m_{1}\log|{\cal X}_{1}|+m_{2}\log|{\cal
X}_{2}|-nH(K_{1}K_{2}).$ (22)

Step (a) follows from (21). Step (b) follows from the data processing
inequality. Hence from (22), we have

$\displaystyle\Delta^{(n)}\geq m_{1}\log|{\cal X}_{1}|+m_{2}\log|{\cal
X}_{2}|-nH(K_{1}K_{2}).$ (23)

From (20) and (23), we have the bound (5) in Lemma 2. ∎

## References

  * [1] B. Santoso and Y. Oohama, “Privacy amplification of distributed encrypted sources with correlated keys,” in _2017 IEEE International Symposium on Information Theory - ISIT_. IEEE, 2017, pp. 958–962.
  * [2] ——, “Secrecy amplification of distributed encrypted sources with correlated keys using post-encryption-compression,” _IEEE Trans. Information Forensics and Security_ , vol. 14, no. 11, pp. 3042–3056, November 2019.
  * [3] M. Johnson, P. Ishwar, V. Prabhakaran, D. Schonberg, and K. Ramchandran, “On compressing encrypted data,” _IEEE Transactions on Signal Processing_ , vol. 52, no. 10, pp. 2992–3006, Oct 2004.
  * [4] D. Klinc, C. Hazay, A. Jagmohan, H. Krawczyk, and T. Rabin, “On compression of data encrypted with block ciphers,” _IEEE Trans. Information Theory_ , vol. 58, no. 11, pp. 6989–7001, 2012. [Online]. Available: https://doi.org/10.1109/TIT.2012.2210752
  * [5] C. E. Shannon, “A mathematical theory of communication,” _Bell System Technical Journal_ , vol. 27, pp. 379–423, 623–656, July, October 1948.
  * [6] H. Yamamoto, “Information theory in cryptology,” _IEICE Transactions_ , vol. E.74, no. 9, pp. 2456–2464, September 1991.
  * [7] M. Iwamoto, K. Ohta, and J. Shikata, “Security formalizations and their relationships for encryption and key agreement in information-theoretic cryptography,” _IEEE Trans. Inf. Theory_ , vol. 64, no. 1, pp. 654–685, 2018. [Online]. Available: https://doi.org/10.1109/TIT.2017.2744650
  * [8] M. Iwamoto, “Security notions for information theoretically secure encryptions,” in _Proc. IEEE Int. Symp. Inf. Theory 2011_ , Saint-Petersburg, Russia,, 2011, pp. 1777–1781.
  * [9] Y. Oohama and T. S. Han, “Universal coding for the Slepian-Wolf data compression system and the strong converse theorem,” _IEEE Trans. Inform. Theory_ , vol. 40, no. 6, pp. 1908–1919, November 1994.