authored by Premmi
The Story of Total Variation Distance.
Part 1
Introduction
Before we dive into cryptography, we need to understand the concept of distance as a way to distinguish between entities.
In the first part, we will explore how we can use distance to differentiate between entities in a deterministic world. In the next part we will expatiate upon distance as a distinguisher in a probabilistic world. From there on we will proceed to discuss why in cryptography distinguishability between entities (i.e., between two probability distributions or two random variables) matters; and, finally we close the discussion with different ways to measure this distance.
Distance as a Distinguisher in the Real World
John has two identical twin sisters, Ann and Kelly who live in New York and Los Angeles respectively. John has no other siblings. All three of them are my friends.While talking to John I mention that I had met his sister in New York the previous week. John without any doubt (or with 100\% certainty) will know that I’m talking about Ann. Since both Ann and Kelly live in different cities, the distance between them acts as a distinguisher in telling them apart.
Three months later Kelly gets a job as a developer in a tech startup and moves to New York. She lives in Brooklyn while Ann who works as a hedge fund manager in Wall Street, lives in Manhattan. One weekend I bump into Kelly at the MoMA and we have a good time together. Again while talking to John, I mention that I met his sister in New York. Now John is no longer sure which one it is, since both his sisters live in New York. So he can only make a random guess and be 50\% sure which of his sisters I met. Put another way, his advantage in guessing which of his sisters’ I had met has gone down since he is now only 50\% sure compared with his 100\% certainty before. This implies that as the distance between them decreases, their distinguishability also decreases.
Ann is flourishing well at her job and has a fantastic year leaving her with a fat bonus. She moves into 432 Park Avenue on Billionaires’ Row, Manhattan, while Kelly is endlessly grinding away at her job hoping for that IPO event which seems ever more phantasmagorical with each passing year. So one day as an act of resipiscence she quits her job and becomes a social media fashion influencer. She impresses a real estate mogul and she too moves into 432 Park Avenue, though 10 floors higher than self made Ann.
On a lazy Saturday afternoon Ann and I go shopping, commencing at Moschino in Wooster Street, Manhattan. When I meet John for dinner, I recount to him the fabulous afternoon I had with his sister in Manhattan. If he has to guess which sister I’m talking about, even though I’m more specific than the previous occasion (when I just told him that I met one of his sisters in New York), he still has to make a random guess since both now live in the same apartment in Manhattan, separated only by 10 floors. So as the distance between them reduces, they become almost indistinguishable.
So what is the point of this fairy tale like story (those tales generally repeat the same situation thrice 😀)?
The two main takeaways from this story are
- The smaller the distance between two entities, the harder it is to tell them apart or distinguish them since you need more information.
- When the distance between two entities cannot be sensed by you, then for all practical purposes they are indistinguishable to you. For example, our naked eye cannot distinguish individual stars in the Milky Way because they are so far away and can only see the overall illumination from them. (As we will see later, we will exploit the inability of our computers, due to computational limitations, to distinguish two distributions to build secure systems.)
We humans, for various mostly frivolous reasons, don’t stay put at the same place for the entirety of our lives. So what happens when Ann and Kelly both decide to split their time between New York and Los Angeles? How does the story pan out?
This situation mirrors a move from a deterministic world to a probabilistic one. Our distances will now incorporate probabilistic information and we will see how John fares in this world.
You can view the next part of the story here.