4
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Is it normal, if you are wrting $P(C)$, with $C$ a ciphertext? $\endgroup$
    – Ievgeni
    Sep 15 '20 at 15:31
  • $\begingroup$ @levgeni $C$ is a random variable ranging over the cipher text space. $C\in Y$ is an event, and $P(C\in Y)$ is the probability of that event, i.e. the probability that a randomly chosen ciphertext will be an element of the set $Y$. I’m not doing anything unusual in that part. $\endgroup$ Sep 15 '20 at 15:34
  • $\begingroup$ I'm agree it makes sense. But you say that $P$ is a probability measure over the message space. So it works because message space = ciphertext space, but if there is no error, why don't you write that $P$ is a probability measure over integers? $\endgroup$
    – Ievgeni
    Sep 15 '20 at 15:39
  • 1
    $\begingroup$ Can you edit your message to make it clearer please? $\endgroup$
    – Ievgeni
    Sep 15 '20 at 15:55
  • 1
    $\begingroup$ @tylo You can apply the measure to events that a number is in the set or not. $\endgroup$ Sep 19 '20 at 20:24
1
+50
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ It's fairly irrelevant, that the measure is translation invariant. That measure can not be used to draw from it (it works on sets, and the additive property only hold for disjunct subsets of the natural numbers). It doesn't even apply to the initially defined message space, cipher text space and key space. $\endgroup$
    – tylo
    Sep 19 '20 at 13:31
  • 3
    $\begingroup$ @tylo: All measures in measure theory measure sets. For probability measures, we interpret $m(S)$ as the probability that a random variable distributed according to $m$ happens to belong to the set $S$. You're correct in saying that we cannot draw samples from this particular measure in practice, but that's hardly a unique issue. We also cannot actually draw samples from e.g. the uniform measure on $[0,1]$, either, or indeed from any continuous probability measure (although we can approximate a sample drawn from such a measure). $\endgroup$ Sep 19 '20 at 16:45
  • $\begingroup$ @Mark Good catch. $\endgroup$
    – qbt937
    Sep 19 '20 at 20:19
1
$\begingroup$

"…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.)

$\endgroup$
5
  • $\begingroup$ Yes, I’m asking a purely mathematical question. And you’re off-base on the two envelopes paradox, it is not promised on taking the expected value of the ratio of two random variables. $\endgroup$ Sep 19 '20 at 20:22
  • 1
    $\begingroup$ @KeshavSrinivasan: It's a bit of a tangent, but taking the expected value of the ratio (and confusing it for the ratio of the expected values) is exactly what one is doing when one argues, as the paper does in its introduction, that "there is a 50% chance that the other envelope contains one-half the amount we hold, and there is a 50% chance that the other envelope contains twice the amount we hold. That is [sic], the other envelope has an expected value of 1.25 times the amount in the envelope we hold." $\endgroup$ Sep 19 '20 at 21:14
  • $\begingroup$ @IlmariKaronen That doesn't require conflating the expected value of the ratio with the ratio of expected values. The only assumption needed is that what the current envelope contains provides no information about whether the other envelope has more or less than this envelope. This is not possible with any probability measure, but if you allow non-normalized distributions (or finitely-additive measures instead) then its true if you use the density function $p(x) = \frac 1 x$ for $x > 0$. (I think this is the right distribution, but I'm not certain.) $\endgroup$
    – qbt937
    Sep 23 '20 at 22:44
  • $\begingroup$ If it is true that the current envelope gives no information about whether the other contains more or less, then if I see e.g. \$10 in my envolope then there is a 50% chance of the other containing \$5 and 50% chance of containing \$20, which means that the expected value of the other envelope is $12.5 and I should switch. $\endgroup$
    – qbt937
    Sep 23 '20 at 22:46
  • $\begingroup$ Now if instead I'm given the opportunity to switch before seeing what's in the envelope, I should switch because I was going to want to later when I see what's in the current envelope, no matter what is in it. $\endgroup$
    – qbt937
    Sep 23 '20 at 22:51
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.