How should $\rho(b,b')$ be interpreted in the context of classical-quantum state

Question

I’m trying to understand the concept of a classical-quantum state as it is used in the context of quantum cryptography. In particular, I’m looking at the expression $CL.Enc_{pk}(\rho^M)$ from page 16 of this paper:

$$CL.Enc_{pk}(\rho^M) = \sum\limits_{a,b \in \{0,1 \}} \frac{1}{4} \rho(HE.Enc_{pk}(a), HE.Enc_{pk}(b)) \otimes QEnc_{a,b}(\rho^M)$$

For context, earlier in the paper, on page 6, the authors define

$$ \rho(X) = \sum\limits_{x \in \sum_X} \text{Pr}[X=x]|x\rangle \langle x| $$ for a random variable $X$.

I am having difficulty interpreting $\rho(HE.Enc_{pk}(a), HE.Enc_{pk}(b))$ and the expression as the whole. The outputs of $HE.Enc_{pk}(a)$ and $HE.Enc_{pk}(b)$ are simply two bits. Suppose the outputs are $0$ and $1$ respectively. How should $\rho(0,1)$ be interpreted? Does it have an explicit expression? Any help in understanding the expression as a whole is appreciated.

Answer 1

First of all, the authors define on page 6 that:

A density matrix that is diagonal in the computational basis corresponds to a classical random variable.

and

A classical-quantum state is a state of the form $\rho^{\mathcal{MA}}=\sum_x\mathrm{Pr}[X=x]|x\rangle\langle x|^{\mathcal{M}}\otimes\rho_x^{\mathcal{A}}$

The name "classical-quantum" state thus makes sense: the first part of $\rho^{\mathcal{MA}}$ can be thought of as a classical random variable, while the second part is quantum, hence the name.

In the definition you're interested in, it is mentioned that $\mathsf{CL.Enc}_{pk}\left(\rho^{\mathcal{M}}\right)$ is a classical-quantum state. We thus know that the term $$\rho\left(\mathsf{HE.Enc}_{pk}(a),\mathsf{HE.Enc}_{pk}(b)\right)$$ represents a density matrix that is diagonal in the computational basis, that is, a classical random variable. Using the definition you've mentioned, and as explained in @SimonYin's answer, we actually have: $$\rho\left(\mathsf{HE.Enc}_{pk}(a),\mathsf{HE.Enc}_{pk}(b)\right)=\sum_{x,y}\mathrm{Pr}[(\mathsf{HE.Enc}_{pk}(a)=x)\cap(\mathsf{HE.Enc}_{pk}(b)=y)]|x,y\rangle\langle x,y|$$ This is essentially due to the fact that $\mathsf{HE.Enc}_{pk}$ is randomized, which is a necessary condition for it to be secure. Indeed, note that in Definition 3.1 page 8, we have:

A classical homomorphic encryption scheme $\mathsf{HE}$ is q-IND-CPA secure if for any polynomial-time adversary $\mathscr{A}$, there exists a negligible function $\eta$ such that for $(pk,evk,sk)\leftarrow\mathsf{HE.Keygen}\left(1^\kappa\right)$: $$\left|\mathrm{Pr}\left[\mathscr{A}(pk,evk,\mathsf{HE.Enc}_{pk}(0))=1\right]-\mathrm{Pr}\left[\mathscr{A}(pk,evk,\mathsf{HE.Enc}_{pk}(1))=1\right]\right|\leqslant\eta(\kappa).$$

Now, suppose $\mathsf{HE.Enc}_{pk}$ is not randomized. Then it's very easy for $\mathscr{A}$ to break the q-IND-CPA security of this scheme while still running in polynomial time: simply query $\mathsf{HE.Enc}_{pk}(0)$ and return $0$ if it matches the ciphertext they've been given. If the encryption is randomized however, then this strategy can't work. As a reminder, the output of $\mathsf{HE.Enc}_{pk}$ is not a single bit but an arbitrary long ciphertext, as per the Definition A.1. page 33. In order for the classical-quantum state to be well-defined however, it is required that all the outputs have the same length (say, $n$-bit outputs).

Thus, $\mathsf{HE.Enc}_{pk}(0)$ can be seen as a random variable taking values in the ciphertexts space, where the different values it can take come from the fact that the encryption is randomized (and this is of course also true for $\mathsf{HE.Enc}_{pk}(1)$).

All in all, if we denote $\mathcal{C_0}$ the output space of $\mathsf{HE.Enc}_{pk}(0)$ and $\mathcal{C_1}$ the output space of $\mathsf{HE.Enc}_{pk}(1)$, unfolding the expression you're interested in yields: $$\mathsf{CL.Enc}_{pk}\left(\rho^{\mathcal{M}}\right)= \begin{array}{l} &\frac14\sum\limits_{x\in\mathcal{C}_0}\mathrm{Pr}[\mathsf{HE.Enc}_{pk}(0)=x]|x,x\rangle\langle x,x|\otimes\rho^{\mathcal{M}}\\ +&\frac14\sum\limits_{\substack{x\in\mathcal{C}_0\\y\in\mathcal{C}_1}}\mathrm{Pr}[\mathsf{HE.Enc}_{pk}(0)=x]\mathrm{Pr}[\mathsf{HE.Enc}_{pk}(1)=y]|x,y\rangle\langle x,y|\otimes\mathsf{Z}\rho^{\mathcal{M}}\mathsf{Z}\\ +&\frac14\sum\limits_{\substack{x\in\mathcal{C}_0\\y\in\mathcal{C}_1}}\mathrm{Pr}[\mathsf{HE.Enc}_{pk}(0)=x]\mathrm{Pr}[\mathsf{HE.Enc}_{pk}(1)=y]|y,x\rangle\langle y,x|\otimes\mathsf{X}\rho^{\mathcal{M}}\mathsf{X}\\ +&\frac14\sum\limits_{y\in\mathcal{C}_1}\mathrm{Pr}[\mathsf{HE.Enc}_{pk}(1)=y]|y,y\rangle\langle y,y|\otimes\mathsf{X}\mathsf{Z}\rho^{\mathcal{M}}\mathsf{Z}\mathsf{X}\\ \end{array}$$

Answer 2

$\rho$ is a probability distribution.

$\rho(X)$ is a probability distribution with support of a single random variable, $X$.

$\rho(X,Y)$ then is a probability distribution with support of two random variables, $X$, $Y$.

An explicit expression: $$\rho(X,Y) = \sum_{x,y}Pr(X=x,Y=y)|x\rangle\otimes|y\rangle\langle y|\otimes\langle x|$$