I'm quite bad at information theory, but I'd like to understand it at some point, and more precisely the links it has with cryptography. I have a general idea/intuition of what is entropy, but usually when I try to formalize something... I'm just stuck.

So for example, one of the problem I'd like to solve is the following. Let's first state it informally in one line:

Informal problem: If I don't know "well enough" a sequence of secret bits $s_1,\dots,s_n$ for a "large enough" $n$ (but still polynomial), then I have no information on $\sum_i s_i \mod m$, with m being a small constant.

NB: I'm not sure how to define "well enough", but you can for example say that the probability to guess this sequence is bounded by $(2/3)^n$. Actually,you can even assume uniformity and independance of the elements of the sequence.

Now, for people willing to read more, here is a bit more precise definition of my problem:

  • Step 0: Let's imagine that Alice has a 3-bits secret $s := s[0]s[1]s[2]$ (I'm using brackets because I'll use $s_i$ for another purpose), that are chosen uniformly at random.
  • Step 1: Then, she "hides" this secret into an object $E(s)$ (that is not deterministic) that will be given to Bob. At that step, I have a proof that no matter what Bob does, as soon as he is computationally bounded, he has no way to find s with probability better than a random guess.
  • Step 2: Then, Bob will do some stuff with this $E(s)$, and gives back an answer to Alice.
  • Step 3: Alice says if she accept or reject this answer, and sends a bit $r$ for that purpose to Bob.

The thing is that I want to show that this accept/reject does not leak information about $s$. But I have no idea for now how to prove that the probability of accept/reject cannot depend on $s$, so to avoid that I would like to use an argument based on information theory to say that Bob cannot know "to much things" about $s$.

Indeed, after step 1, Bob know nothing about $s$, so "intuitively" (I don't even know if it makes sense to talk about entropy in a computational setting), the entropy for Bob about $s$ is 3 (the number of bits). But then Bob receive only one bit of information between Step 2 and Step 3, so intuitively, after that, from Bob's point of view the entropy of $s$ is at least 2 (let me know if what I say is nonsense), so "he does not fully know $s$".

So now, let's imagine that after the accept/reject, Alice also picks and sends a uniformly random $j \in \{0,1,2\}$ in order to say that the relevant bit for the rest of the protocol is the bit $\hat{s} := s[j]$. Because the $j$ was unknown to Bob, it's unlikely that the bit $r$ leaked exactly the bit of $s[j]$, so intuitively I can say that the probability (yes sorry, for me only probability makes sense) for Bob to guess a correct value for $\hat{s} := s[j]$ is different from one. So first I'm not sure how to compute this probability, because Bob may have several strategies to "spread" the information... But let's say for now that this probability is bounded by the constant $2/3 < 1$.

Then, we repeat this same protocol (by taking only instances where the answer of Alice was accept), and we get a list of secrets $[\hat{s}_1, \dots, \hat{s}_n]$, that Bob cannot completely describe (because of this $2/3$ proba on each $\hat{s_i}$) using the previous argument, and what I want to show is that if $n$ is "big enough" (how big?), Bob has now way to guess $\sum_i \hat{s}_i \mod 8$ with probability better than random (8 is just chosen as an example for simplicity, and actually the sum could also contain some minus, but for now let's stick to the simpler case). This seems pretty natural as this sum is more or less like a "one direction" random walk on a circle, and as soon as you don't perfectly know the value of each step, after a big number of steps you shouldn't know where you will arrive...

But I don't know how to formalize this intuition, because this mixes probabilities, entropy, computational security...

Any idea, sketch of proof, or reference (even if it's just covering one part of the problem) would be greatly appreciated! Thanks in advance!

  • $\begingroup$ It's not a quick answer, but I think your best route is a textbook such as the first part of Cover and Thomas "Elements of Information Theory". $\endgroup$ – usul Jan 31 at 14:03
  • $\begingroup$ The case $m=2$ is en.wikipedia.org/wiki/Piling-up_lemma (I think). $\endgroup$ – D.W. Feb 1 at 18:18
  • $\begingroup$ @usul ok thanks for the book reference I'll give it a try! $\endgroup$ – tobiasBora Feb 2 at 9:39
  • $\begingroup$ @D.W. Thanks, but this theorem is more about the probability of biased distributions. In my case the distribution appears to be uniform and independant so I know the final probability (1/2), but the knowledge of the adversary may be greater than for a random guess as he has some information about the value of this bit. But meantime I found the great Yao Xor lemma, and it's closer to my needs, except that I need an extension to protocols instead of functions. $\endgroup$ – tobiasBora Feb 2 at 9:44

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.