Can you have perfect secrecy with countable message/key spaces by dropping countable additivity?

Question

This classic paper by Chor and Kushilevitz shows that if the key space and the message space are both countably infinite, then it is impossible to have a perfectly secure private-key encryption scheme. Their proof relies on the fact there exists no uniform probability measure on the set of natural numbers, which in turn relies on the fact that probability measures are countably additive.

But there’s a generalized notion of measure that only requires finite additivity and not countable additivity. In particular this paper talks about how the asymptotic density of a set of natural numbers constitutes a finitely additive probability measure that is “uniform” in the sense of translation invariance.

I’m wondering whether that could be used to recover some notion of perfect security. So let the message space, key space, and ciphertext space all equal $\mathbb{N}$, let the family of measurable sets be the family $F$ of all subsets of $\mathbb{N}$ which have a well-defined asymptotic density, let the key be chosen using the asymptotic density measure, and let the adversary have some finitely additive probability measure $P$ over the message space. Then my question is, does there exist an encryption scheme such that for all $X,Y\in F$ for which $P(C\in Y)\neq 0$, we have $P(M\in X | C\in Y) = P(M\in X)$? (Note that I’m using the same letter $P$ for bother he probability measure over the message space and the probability measure of the ciphertext.)

Of course dropping countable additivity may make this all unrealistic, but I’m just asking a theoretical question.

Answer 1

Let the key, message, and ciphertext spaces all be $\mathbb{Z}$, which is in bijection with $\mathbb N$. I'm going to pick a specific bijection by making the non-negative integers map to evens and the negative integers map to odds, and let $\mu$ be the asymptotic density measure applied to $\mathbb{Z}$ using this bijection. We can then construct a one-time pad by setting $c = m + k$. For any (possibly finitely-additive) probability measure $\mu_M$ chosen by the adversary on $m$, and any set $Y \in F$, $(\mu_M \times \mu)(\{(m, k) \in \mathbb Z^2 \mid m + k \in Y\}) = \mu(Y)$. That is, the resulting measure on the ciphertext is uniform, no matter what measure $m$ comes from. I am stating it this way so as to avoid the division inherent in the $P(m \in X | c \in Y)$ expression in your question.

Details: First, we need to show that $\mu$ is translation invariant on $\mathbb Z$. $\mu(A)$ could equivalently be defined as $\lim_{n \to \infty} \frac{A \cap [-n, n]}{2n + 1}$. To see that translation invariance holds, notice that $|[-n, n] \cap A|$ and $|[-n, n] \cap (A - x)|$ only differ by at most $2 x$, since $[-n, n]$ and $[-n + x, n + x]$ overlap everywhere except for $x$ points at either end. This becomes irrelevant in the limit as $n \to \infty$.

Next, we need to evaluate the product measure. Unfortunately product measures do not seem to be very well defined for finitely additive measures. I will pick one product measure, but in general it is not unique. \begin{align*} (\mu_M \times \mu)(\{(m, k) \in \mathbb Z^2 \mid m + k \in Y\}) &= \int_{\mathbb Z} \mu(\{k \in \mathbb Z \mid m + k \in Y\}) d\mu_M(m) \\ &= \int_{\mathbb Z} \mu(Y - m) d\mu_M(m) \\ &= \int_{\mathbb Z} \mu(Y) d\mu_M(m) \\ &= \mu(Y) \\ \end{align*}

Here we have used that $\mu$ is translation invariant on $\mathbb Z$ and that $\mu_M$ is a probability measure, so the integral (i.e., expected value) of a constant is that constant.

However, none of this is physically realizable, at least with a digital computer. Any way of generating a random key is going to give a distribution that has countable additivity, since it can always be broken down into discrete choices, with each outcome having paths leading to it with only have a finite number of choices. I don't think it is physically possible in general, but I have less justification for that.

Answer 2

"…let the key be chosen using the asymptotic density measure…"

Well, as far as practicality goes, there's your first problem. The asymptotic density of any bounded set of integers is, by definition, zero.

So, the probability of your key being shorter than one gigabyte? Zero.

The probability of you owning enough disk space to store the key? Zero.

The probability of there being enough atoms in the observable universe to store the key (assuming a finite number of bits stored per atom)? Again, zero.

As far as pure mathematics goes, it's indeed interesting that one can (apparently) make some non-trivial subset of probability theory work using such crazy measures. One might even wonder if those measures could be reinterpreted in some fashion (say, by mapping them to measures on a bounded subset of the reals) to turn them into something one could approximately sample from, or if they're somehow fundamentally impossible to approximate using conventional probability measures. But as far as practicality goes, well, they don't really seem to have any.

(Oh, and the "two envelopes paradox" discussed in the paper? More directly resolved by noting that the expected value of the ratio of two random variables does not equal the ratio of their expected values, and that it's the latter, not the former, that determines whether it's advantageous to switch or not. No weird pseudo-probability measures needed.)

Answer 3

I don't think the question makes much sense.

Let's look at the measure a bit closer:

• First, the measure is the limit of the density. That means, the things measured by this are infinite subsets of the natural numbers. It does not measure single elements in any way. And all finite sets have measure 0.
• The additive property only holds for disjunct subsets of the natural numbers. It does not give you a constructive way to create those subsets.
• This is not a uniform distribution. The translation invariance is a necessary but not sufficient property.
• I would not call it a probability distribution at all: If the measured set is a variable over all subsets of the natural numbers, then the sum over all $P(X)$ is infinite.

Now let's look at your idea:

I’m wondering whether that could be used to recover some notion of perfect security. So let the message space, key space, and ciphertext space all equal N,

So the messages, keys and cipher texts are single elements of the $\mathbb{N}$. You can not use the measure in any meaningful way here. The definitions don't match. And perfect security requires some kind of measure over one specific message or cipher text.

let the family of measurable sets be the family F of all subsets of N which have a well-defined asymptotic density, let the key be chosen using the asymptotic density measure,

How would that work? The measure does not give you a constructive way to use it to draw elements at random.

and let the adversary have some finitely additive probability measure P over the message space.

Since the measure is defined in general, it doesn't make sense to only give it to the adversary.

Then my question is, does there exist an encryption scheme such that for all X,Y∈F for which P(C∈Y)≠0, we have P(M∈X|C∈Y)=P(M∈X)? (Note that I’m using the same letter P for bother he probability measure over the message space and the probability measure of the ciphertext.)

That definition does not make any sense. The measure does not change by adding single elements. You try to measure some kind of difference whether single elements are in those subsets or not. So the question can not be answered. But even if you used infinite sets as messages, cipher texts and keys, the definition doesn't really make sense - the finite additive property only works if the sets are disjunct. I can't see a way to give any meaningful definition over the entire message or cipher text space.