#StackBounty: #symmetric #secret-sharing #perfect-secrecy #information-theory #probability Can you have perfect secrecy with countable …

Bounty: 50

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,Yin F$ for which $P(Cin Y)neq 0$, we have $P(Min X | Cin Y) = P(Min 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.


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.