How is the cross-product transformation defined for binary features?
Let's do this in the opposite order of how you asked.  i.e. first:

How can I think of the cross-product transformation in general?

For me a cross-product comes from linear algebra, and it is a different transformation.  Therefore let's start by not confusing both.  The cross-product in the equation above is a transformation alright but is not related to what most of us call a cross product.

With that out of the way let's look at the formula.  Since both the index on the product and components of $\vec{x}$ and $\vec{c}$ are the same (they're all $i$), we can be rather confident that $d$ is the number of dimensions/features we are working with.  Therefore to make things a little easier to see let's work with $d = 4$:

$$
\phi_{k}(\vec{x})=\prod_{i=1}^{4} x_{i}^{c_{k i}} \quad c_{k i} \in\{0,1\}
$$

Now we can write an example vector to which we apply the transformation, say:

$$\vec{x} = [7, 5, -0.5, 0.2]$$

And an example vector which parametrizes the transformation:

$$\vec{c} = [0, 1, 1, 0]$$

And for a start let's evaluate the transformation:

$$\phi_k(\vec{x}) = 7^0 \cdot 5^1 \cdot -0.5^1 \cdot 0.2^0 = 5 \cdot -0.5 = -2.5$$

And that's it.  But now comes the important part, let's describe what this transformation just did: We took a vector in 4 dimensions, took it's 2nd and 3rd components and multiplied them together (whilst we ignored the 1st and 4th components).  In other words the transformation $\phi_k$ uses its parametrization $\vec{c}$ to decide which components of its argument to product together.

We can therefore use different parametrizations to achieve different transformations of the vector $\vec{x}$.

What this may be useful for? If you are confident that all components in the vector are $&gt; 1$ (or all are $&lt; 1$) then you have the combined magnitude of the selected dimensions.  Although keep reading below since this is really useful to binary features.



How does this relate to the given formula?

i.e. how the binary features can only be 1 if all (relevant) features are present.  I believe that this relates to the definition of $0^0$ and $0^1$.  Let's take a different vector:

$$\vec{x} = [0, 1, 0, 1]$$

Let's say that these are non-exclusive binary features: [male?, dog?, white?, fed?].  So we have a female dog which is not white and is currently well fed.

Now let's take the parametric vector to be:

$$\vec{c} = [0, 1, 1, 0]$$

And perform the transformation:

$$\phi_k(\vec{x}) = 0^0 \cdot 1^1 \cdot 0^1 \cdot 1^0 = 1 \cdot 1 \cdot 0 \cdot 1 = 0$$

A small note is now in order: $0^0 = 1$ is not true in all fields of mathematics, but since it is accepted in most fields and makes sense here we will use it here (and so I believe that the authors of the paper do use this assumption as such).

Wait!  So had we had the dog been white we would have had a $1$ as the result.  In other words, had $\vec{x}$ been $[0, 1, 1, 1]$ we would have gotten $1$ as the result of the transformation because the third term would be $1^1$.  Try it out!

This means that $\phi_k$ with $\vec{c} = [0, 1, 1, 0]$ will return $1$ (true) for all $\vec{x}$ that represents a white dog, does not matter if the dog is male or female or whether it is fed.  And will return $0$ for anything that is either not a dog or not white.

In other words, the parametric $\vec{c}$ defines the features that matter (the ones in the vector $\vec{c}$), and such a parametrized transformation $\phi_k$ return true if all the features that matter are true in the argument of the transformation ($\vec{x}$).

The big difference in the binary features is the fact that $0^1 = 0$, which binds the entire product to $0$.  Whilst $0^0 = 1$ and $1^1$, which results in a dimension/feature whose value does not matter for our transformation.



P.S. I prefer physics notation for vectors, a component of a vector is $x$ but a full vector is $\vec{x}$ instead of $\mathbf{x}$.  Please bear with the notation.