Switch branches/tags
Nothing to show
Find file
Fetching contributors…
Cannot retrieve contributors at this time
158 lines (94 sloc) 31.8 KB
title: Death Note: L, Anonymity & Eluding Entropy
description: Applied Computer Science: On Murder Considered as one of the Hard Sciences
tags: anime, criticism, computer science, cryptography
> This essay assumes a familiarity with the early plot of _[Death Note](!Wikipedia)_ and [Light Yagami](!Wikipedia); if you are unfamiliar with it, see my [_Death Note_ Ending](Death Note Ending) essay or consult [Wikipedia](!Wikipedia "Death Note#Plot").
I have elsewhere called Light 'hubristic' and said he made mistakes. So I am obliged to explain what he did wrong and how he could do better.
While Light starts scheming and taking serious risks as early as the arrival of the FBI team in Japan, he has fundamentally already screwed up. L should never have gotten that close to Light. The Death Note kills flawlessly without forensic trace and over arbitrary distances; _Death Note_ is almost a thought-experiment - given the *perfect* murder weapon, how can you screw up *anyway*?
Some of the other Death Note users highlight the problem. The user in the [Yotsuba Group](!Wikipedia "List of Death Note characters#Yotsuba Group") carries out the normal executions, but *also* kills a number of prominent competitors. The killings directly point to the Yotsuba Group and eventually the user's death. The moral of the story is that indirect relationships can be fatal in narrowing down the possibilities from 'everyone' to 'these 8 men'.
# Detective stories as optimization problems
In Light's case, L starts with the world's entire population of 7 billion people and needs to narrow it down to 1 person. It's a search problem. It maps fairly directly onto basic [information theory](!Wikipedia), in fact. (See also [Copyright](), [Simulation inferences](), and [The 3 Grenades]().) To uniquely specify one item out of 7 billion, you need 33 bits of information because $log_2(7000000000) = ~32.7$; to use an analogy, your 32-bit computer can only address one unique location in memory out of *4* billion locations, and adding another bit doubles the capacity to >8 billion. Is 33 bits of information a lot?
Not really. L could get one bit just by looking at history or crime statistics, and noting that mass murderers are, to an astonishing degree, *male*^[In fact, every single person mentioned in my [Terrorism is not Effective](Terrorism is not Effective#competent-murders) is male, and this seems to be true of the full [Wikipedia list of mass murderers](!Wikipedia "List of rampage killers") as well.], thereby ruling out half the world population and actually starting L off with a requirement to obtain only 32 bits to break Light's anonymity.[^misa] If Death Note users were sufficiently rational & knowledgeable, they could draw on concepts like [superrationality](!Wikipedia) to acausally cooperate^[Acausality is an odd sort of new concept in [decision theory](!Wikipedia), primarily discussed in [Gary Drescher](!Wikipedia)'s _[Good and Real]( chapters 5-7, and on [](] to avoid this information leakage... by arranging to pass on Death Notes to females^[My first solution involved sex reassignment surgery, but that makes the situation worse, as transsexuals are so rare that an L intelligent enough to anticipate these ultra-rational Death Note users would instantly gain a huge clue: just check everyone on the surgery lists. Anyway, most Death Note users would probably prefer the passing-it-on solution.] to restore a 50:50 gender ratio - for example, if for every female who obtained a Death note there were 3 males with Death Notes, then all users could roll a 1d3 dice and if 1 keep it and if 2 or 3 pass it on to someone of the opposite gender.
[^misa]: This reasoning would be wrong in the case of [Misa Amane](!Wikipedia), but Misa is an absurd character - a Gothic lolita pop star who falls in love with Light through an extraordinary coincidence and doesn't flinch at anything, even sacrificing 75% of her lifespan or her memories; hence it's not surprising to learn that the motivation for her character was to avoid a "boring" all-male cast and be "a cute female". (_Death Note_ is not immune to the [Rule of Cool]( or [Sexy](
We should first point out that Light is always going to leak *some* bits. The only way he could remain perfectly hidden is to not use the Death Note at all. If you change the world in even the slightest way, then you have leaked information about yourself in principle. Everything is connected in some sense; you cannot magically wave away the existence of fire without creating a cascade of consequences that result in [every living thing dying]( For example, the fundamental point of Light executing criminals is to *shorten their lifespan* - there's no way to hide that. You can't shorten their lives and *not* shorten their lives. He is going to reveal himself this way, at the very least to the actuaries and statisticians.
So there is a real challenge here: one party is trying to infer as much as possible from observed effects, and the other is trying to minimize how much the former can observe while not stopping entirely. How well does Light balance the competing demands?
# Mistakes
## Mistake 1
However, he can try to reduce the leakage and make his [anonymity set](!Wikipedia "Degree of anonymity") as large as possible. For example, killing every criminal with a heart attack is a dead give-away. Criminals do not die of heart attacks that often. (The point is more dramatic if you replace 'heart attack' with 'lupus'; as we all know, in real life it's never lupus.) Heart attacks are a subset of all deaths, and by restricting himself, Light makes it easier to detect his activities. 1000 deaths of lupus are a blaring red alarm; 1000 deaths of heart attacks are an oddity; and 1000 deaths distributed over the statistically likely suspects of cancer and heart disease etc. are almost invisible (but still noticeable in principle).
So, Light's fundamental mistake is to kill in ways unrelated to his goal. Killing through heart attacks does not just make him visible early on, but the deaths reveals that his assassination method is supernaturally precise. L has been tipped off that Kira exists. First mistake.
## Mistake 2
Worse, the deaths are non-random in other ways - they tend to occur at particular times! Graphed, there are obvious patterns.
L was able to narrow down the active times of the presumable student or worker to a particular range of longitude, say 125-150° out of 180°; and what country is most obvious in that range? Japan. So that cut down the 7 billion people to around 0.128 billion; 0.128 billion requires 27 bits ($log_2 (128000000) = ~26.93$) so just the scheduling of deaths cost Light 6 bits of anonymity!
### De-anonymization
On a side-note, some might be skeptical that one can infer much of anything from the graph and that _Death Note_ was just glossing over this part. "How can anyone infer that it was someone living in Japan just from 2 clumpy lines at morning and evening in Japan?" But actually, such a graph is surprisingly precise. I learned this years before I watched _Death Note_, when I was heavily active on Wikipedia; often I would wonder if two editors were the same person or roughly where an editor lived. What I would do if their edits or user page did not reveal anything useful is I would go to "Kate's [edit counter](!Wikipedia "Wikipedia:WikiProject edit counters")" and I would examine the times of day all their hundreds or thousands of edits were made at. Typically, what one would see was ~4 hours where there were no edits whatsoever, then ~4 hours with moderate to high activity, a trough, then another gradual rise to 8 hours later and a further decline down to the first 4 hours of no activity. These periods quite clearly corresponded to sleep (pretty much everyone is asleep at 4 AM), morning, lunch & work hours, evening, and then night with people occasionally staying up late and editing. There was noise, of course, from people staying up especially late or getting in a bunch of editing during their workday or occasionally traveling, but the overall patterns were clear - never did I discover that someone was actually a nightwatchman and my guess was an entire hemisphere off. (Academic estimates based on user editing patterns correlate well with what is predicted by on the basis of the geography of IP edits.^[See the 2011 paper, ["Circadian patterns of Wikipedia editorial activity: A demographic analysis"](])
Computer security research offers more scary results. There are an amazing number of ways to break someone's privacy and de-anonymize them (and [considerable financial incentive]( to do so to [price discriminate](!Wikipedia)):
1. small errors in their computer's [clock's time]( (even [over Tor](
2. [Web browsing history](^[You can steal information through [JS]( or [CSS](, and analyzing the history for [inferring demographics]( is [already patented](] or just the [version and plugins](^[You can try your own browser live at the [EFF](!Wikipedia "Electronic Frontier Foundation")'s [Panopticlick](]; and this is when random [Firefox]( or [Google Docs]( or [Facebook]( bugs don't leak your identity
3. [Timing attacks](!Wikipedia) based on how slow pages load^[Felten & Schneider 2000, ["Timing Attacks on Web Privacy"](] (how many [cache misses](!Wikipedia) there are; timing attacks can also be used to [learn website usernames or # of private photos](
4. Knowledge of what 'groups' a person was in could [uniquely identify 42%](^[See also the researchers' [blog](] of people on social networking site [XING](!Wikipedia), and possibly Facebook & 6 others
5. Similarly, [knowing just a few movies]( someone has watched^[Coverage of this de-anonymization algorithm generally linked it to [IMDb](!Wikipedia) ratings, but the authors are clear - you could have those ratings from *any* source, there's nothing special about IMDb aside from it being public and online.], popular or obscure, through [Netflix](!Wikipedia) often grants access to the rest of their profile if it was included in the [Netflix Prize](!Wikipedia). (This was more dramatic than the [AOL search data scandal](!Wikipedia) because AOL searches had a great deal of obviously personal information embedded in the search queries, but in contrast, the Netflix data seems impossibly impoverished - there's nothing obviously identifying about what anime one has watched unless one watches very obscure ones.)
6. The researchers [generalized their Netflix work]( to find isomorphisms between arbitrary graphs^[This sounds like something that ought to be [NP-complete](!Wikipedia), and while the [graph isomorphism problem](!Wikipedia) is known to be in NP, it is almost unique in being like [integer factorization](!Wikipedia) - it may be very easy or very hard, there is no proof either way. In practice, large real-world graphs tend to be [very efficient to solve](] (such as social networks stripped of *any and all* data *except* for the graph structure), [for example]( [Flickr](!Wikipedia) and [Twitter](!Wikipedia), and give many examples of [public datasets]( that could be de-anonymized[^abstract] - such as your [Amazon purchases]( ([PDF](; [blog]( These attacks are on just the data that is left after attempts to anonymize data; they don't exploit the observation that the choice of what data to remove is as interesting as what is left, what [Julian Sanchez](!Wikipedia) calls ["The Redactor's Dilemma"](
7. Usernames hardly [bear discussing](
8. Your hospital records can be [de-anonymized]( just by looking at public voting rolls^[eg. 97% of the Cambridge, Massachusetts voters could be identified with birth-date and zip code, and 29% by birth-date and just gender.] That researcher later went on [to run]( "experiments on the identifiability of de-identified survey data [[cite](], pharmacy data [[cite](], clinical trial data [[cite](], criminal data [State of Delaware v. Gannett Publishing], DNA [[cite](, [cite](, [cite](], tax data, public health registries [[cite]( (sealed by court), etc.], web logs, and partial Social Security numbers [[cite](]." (Whew.)
9. Your [typing](!Wikipedia "Keystroke dynamics#References") is surprisingly unique
10. Knowing your morning commute as loosely as to the individual blocks (or less granular) [uniquely identifies]( ([PDF]( you; knowing your commute to the zip code/census tract uniquely identifies 5% of people
11. Your handwriting is fairly unique, obviously - but so is how you fill in bubbles on tests[^bubbles]
12. Speaking of handwriting, your writing style can [be]( [pretty unique]( [too](
To summarize: [differential privacy](!Wikipedia) is [almost]( impossible[^faq] and privacy is dead[^brin].
[^abstract]: From the [paper's]( abstract:
> '...[we] develop a new re-identification algorithm targeting anonymized social-network graphs. To demonstrate its effectiveness on real-world networks, we show that a third of the users who can be verified to have accounts on both Twitter, a popular microblogging service, and Flickr, an online photo-sharing site, can be re-identified in the anonymous Twitter graph with only a 12% error rate. Our de-anonymization algorithm is based purely on the network topology, does not require creation of a large number of dummy "sybil" nodes, is robust to noise and all existing defenses, and works even when the overlap between the target network and the adversary's auxiliary information is small.'
[^faq]: Arvind Narayanan and Vitaly Shmatikov [brusquely summarize]( the implications of their de-anonymization:
> **So, what's the solution?**
> We do not believe that there exists a technical solution to the problem of anonymity in social networks. Specifically, we do not believe that any graph transformation can (a) satisfy a robust definition of privacy, (b) withstand de-anonymization attacks described in our paper, and (c) preserve the utility of the graph for common data-mining and advertising purposes. Therefore, we advocate non-technical solutions.
In general, there's no clear distinction between 'useful' and 'useless' information from the perspective of identifying/breaking privacy/reversing anonymization ([emphasis added](
> ‘Quasi-identifier’ is a notion that arises from attempting to see some attributes (such as ZIP code) but not others (such as tastes and behavior) as contributing to re-identifiability. However, the major lesson from the re-identification papers of the last few years has been that *any information at all about a person* can be potentially used to aid re-identification.
[^bubbles]: See ["Bubble Trouble: Off-Line De-Anonymization of Bubble Forms"](, USENIX 2011S Security Symposium; from ["New Research Result: Bubble Forms Not So Anonymous"](
> "If bubble marking patterns were completely random, a classifier could do no better than randomly guessing a test set’s creator, with an expected accuracy of 1/92 ≈ 1%. Our classifier achieves over 51% accuracy. The classifier is rarely far off: the correct answer falls in the classifier’s top three guesses 75% of the time (vs. 3% for random guessing) and its top ten guesses more than 92% of the time (vs. 11% for random guessing)."
[^brin]: But hey, at least the lack of privacy is two-way and the public can [keep an eye on](!Wikipedia "Transparency (social)") malefactors like the government, as [David Brin](!Wikipedia)'s _[The Transparent Society](!Wikipedia)_ argues is the best outcome. But wait, Wikileaks has revealed the massive expansion of American government secrecy due to the War on Terror and even the [supposed friend]( of transparency, President Obama, [has]( [presided]( [over]( [an]( [expansion]( of President George W. Bush's secrecy programs and crackdowns on [whistle-blowers](!Wikipedia) of all stripes? Oh. Too bad about that, I guess.
## Mistake 3
Light's third mistake was reacting to the provocation of Lind L. Tailor. Running the broadcast in 1 region was a gamble on L's part; he had no real reason to think Light was in [Kanto](!Wikipedia "Kanto region") and should have arranged for it to be broadcast to exactly half of Japan's population. But it was one that paid off; he narrowed his target down to $\frac{1}{3}$ the original Japanese population, for a gain of ~1.6 bits. (You can see it was a gamble by considering if Light had been outside Kanto; obviously he would not have reacted in any fashion, and all L would learn is that his suspect was in that other $\frac{2}{3}$ of the population, for a gain of only ~0.3 bits.)
But even this wasn't a *huge* mistake. He lost 6 bits to his schedule of killing, and lost another 1.6 bits to temperamentally killing Lind L. Tailor, but since the male population of Kanto is 21.5 million (43 million total), he still has ~24 bits of anonymity left ($log_2 (21500000) = ~24.36$). That's not too terrible.
This mistake also shows us that the important thing that information theory buys us, really, is not the *bit* (we could be using $log_10$ rather than $log_2$, and compares ["dits"](!Wikipedia "Ban (information)") rather than "bits") so much as comparing events in the plot on a *logarithmic* scale. If we simply looked at how the absolute number of how many people were ruled out at each step, we'd conclude that the very first mistake by Light was a debacle without compare in human history since it let L rule out >6 billion people, approximately 60x more people than all the other mistakes put together would let L rule out. Mistakes are relative to each other, not absolutes.
## Mistake 4
Light's fourth mistake was the largest. Interestingly, most _Death Note_ fans do not seem to regard this as his largest mistake, instead pointing to killing Lind L. Tailor or perhaps relying on Mikami. The information theoretical perspective strongly disagrees, and lets us quantify how large this mistake was.
Light's fourth mistake was to use confidential police information. When he acts on this information, he instantly cuts down his possible identity to one out of a few thousand people connected to the police. Let's be generous and say 10,000. It takes 14 bits to specify 1 person out of 10,000 ($log_2 (10000) = ~13.29$) - as compared to the 24-25 bits to specify a Kanto dweller.
This mistake cost him 11 bits of anonymity; in other words, this mistake cost him *twice* what his scheduling cost him and almost *8* times the murder of Tailor!
## Mistake 5
In comparison, the fifth mistake, murdering Ray Penbar's fiancee and focusing L's suspicion on Penbar's assigned targets was positively cheap. If we assume Penbar was tasked 200 leads out of the 10,000, then murdering him and the fiancee dropped Light from 14 bits to 8 bits ($log_2 (200) = ~7.64$) or just 6 bits or a little over half the fourth mistake and comparable to the original scheduling mistake.
## Endgame
At this point in the plot, L resorts to direct measures and enters Light's life directly, enrolling at the university. From this point on, Light is pretty much screwed. He frittered away >25 bits of anonymity and then L intuited the rest and suspected him all along. (We could justify L skipping over the remaining 8 bits by pointing out that L can analyze the deaths and infer psychological characteristics like arrogance, puzzle-solving, and great intelligence, which combined with heuristically searching the remaining candidates, could lead him to zero in on Light.)
From the theoretical point of view, the game was over at that point. The question became proving it to L's satisfaction.
# Security is Hard (Let's Go Shopping)
What *should* Light have done? That's easy to answer, but tricky to implement.
Even if we assume that Light was bound and determined to reveal the existence of Kira and gain publicity and international notoriety^[A major character flaw in its own right. Accomplishing things, taking credit - choose one.], he still did not have to reduce his anonymity much past 32 bits.
1. Each execution's time could be determined by a random dice roll (say, a 24-sided dice for hours and a 60-sided dice for minutes).
2. Selecting method of death could be done similarly based on easily researched demographic data, although perhaps irrelevant (serving mostly to conceal that a killing has taken place).
3. Selecting criminals could be based on internationally accessible periodicals that plausibly every human has access to, such as the _New York Times_, and deaths could be delayed by months or years to broaden the possibilities as to where the Kira learned of the victim (TV? books? the Internet?) and avoiding issues like killing a criminal only publicized on one obscure Japanese public television channel. And so on.
Randomization is the answer. Randomization and encryption scramble the correlations between input and output, and they would serve as well in _Death Note_ as they do in cryptography in the real world, at the cost of some efficiency.
Let's remember that all this is predicated on anonymity, and on Light using low-tech strategies; as one person asked me, "why doesn't Light set up an cryptographic [assassination market](!Wikipedia) or just take over the world? He would win without all this cleverness." Well, then it would not be _Death Note_.
# External links
- ["On Murder Considered as one of the Fine Arts"](!Wikipedia "On Murder Considered as one of the Fine Arts"), Thomas De Quincey
- [Discussion of this essay]( on LessWrong
- [Discussion on Hacker News](
- ["Who wrote the _Death Note_ script?"](Notes#who-wrote-the-death-note-script) (my discussion of the American movie's script)
# Appendix: Communicating with a Death Note
One might wonder how much information one could send *intentionally* with a Death Note, as opposed to inadvertently leak bits about one's identity. As deaths are by and large publicly known information, we'll assume the sender and recipient have some sort of pre-arranged key or one-time pad (although one would wonder why they'd use such an immoral and clumsy system as oppose to steganography or messages online).
A death inflicted by a Death has 3 main distinguishing traits which one can control:
1. the person
The 'who?' is already calculated for us: if it takes 33 bits to specify a unique human, then a particular human can convey 33 bits. Concerns about learnability (how would you learn of an Amazon tribesman's death?) imply that it's really <33 bits.
If you try some scheme to encode more bits into the choice of assassination, you either wind up with 33 bits or you wind up unable to convey certain combinations of bits and effectively 33 bits anyway - your scheme will tell you that to convey your desperately important message _X_ of 50 bits telling all about L's true identity and how you discovered it, you need to kill an Olafur Jacobs of Tanzania who weighs more than 200 pounds and is from Taiwan, but alas! Jacobs doesn't exist for you to kill.
2. the time
The time is handled by similar reasoning. There is a certain granularity to Death Note kills: even if *it* is capable of timing deaths down to the nanosecond, one can't actually witness this or receive records of this. Doctors may note time of death down to the minute, but no finer (and how do you get such precise medical records anyway?). News reports may be even less accurate, noting merely that it happened in the morning or in the late evening. In rare cases like live broadcasts, one may be able to do a little better, but even they tend to be delayed by a few seconds or minutes to allow for buffering, technical glitches be fixed, the stenographers produce the closed captioning, or simply to guard against embarrassing events (like Janet Jackson's nipple-slip). So we'll not assume the timing can be more accurate than the minute. But which minutes does a Death Note user have to choose from? Inasmuch as the Death Note is apparently incapable of influencing the past or causing Pratchettian[^Mort] superluminal effects, the past is off-limits; but messages also have to be sent in time for whatever they are supposed to influence, so one cannot afford to have a window of a century. If the message needs to affect something within the day, then the user has a window of only $60 \times 24 = 1440$ minutes, which is $log_2(1440) = 10.49$ bits; if the user has a window of a year, that's slightly better, as a death's timing down to the minute could embody as much as $log_2(60 \times 24 \times 365) = 19$ bits. (Over a decade then is 22.3 bits, etc.) If we allow timing down to the second, then a year would be 24.9 bits. In any case, it's clear that we're not going to get more than 33 bits from the date. On the plus side, an 'IP over Death' protocol would be superior to [some other protocols](!Wikipedia "IP over Avian Carriers") - here, the worse your latency, the more bits you could extract from the packet's timestamp!
3. the circumstances (such as the place)
[^Mort]: [Terry Pratchett](!Wikipedia), _[Mort](!Wikipedia)_:
> "The only things known to go faster than ordinary light is monarchy, according to the philosopher Ly Tin Weedle. He reasoned like this: you can't have more than one king, and tradition demands that there is no gap between kings, so when a king dies the succession must therefore pass to the heir *instantaneously*. Presumably, he said, there must be some elementary particles -- kingons, or possibly queons -- that do this job, but of course succession sometimes fails if, in mid-flight, they strike an anti-particle, or republicon. His ambitious plans to use his discovery to send messages, involving the careful torturing of a small king in order to modulate the signal, were never fully expanded because, at that point, the bar closed."
The circumstances is much more difficult to calculate. We can subdivide it in a lot of ways; here's one:
1. location (eg. latitude/longitude)
Earth has ~510,072,000,000 square meters of surface area; most of it is entirely useless from our perspective - if someone is in an airplane and dies, how on earth does one figure out the exact square meter he was above? Or on the oceans? Earth has ~148,940,000,000 square meters of *land*, which is more usable: the usual calculations gives us $log_2(148940000000) = 37.12$ bits. (Surprised at how similar to the 'who?' bit calculation this is? But $37.12 - 33 = 4.12$ and $2^{4.12} = 17.4$. The old SF classic _[Stand on Zanzibar](!Wikipedia)_ drew its name from the observation that the 7 billion people alive in 2010 would fit in Zanzibar only if they stood shoulder to shoulder - spread them out, and multiply that area by ~18...) This raises an issue that affects all 3: how much can the Death Note control? Can it move victims to arbitrary points in, say, Siberia? Or is it limited to within driving distance? etc. Any of those issues could shrink the 37 bits by a great deal.
2. cause of death
The [International Classification of Diseases]( lists upwards of 20,000 diseases, and we can imagine thousands of possible accidental or deliberate deaths. But what matters is what gets communicated: if there are 500 distinct brain cancers but the death is only reported as 'brain cancer', the 500 count as 1 for our purposes. But we'll be generous and go with 20,000 for reported diseases plus accidents, which is $log_2(20000) = 14.3$ bits.
3. action prior to death
Actions prior to death overlaps with accidental causes; here the series doesn't help us. Light's early experiments culminating in the "L, do you know death gods love apples?" seem to imply that actions are very limited in entropy as each word took a death (assuming the ordinary English vocabulary of 50,000 words, 16 bits), but other plot events imply that humans can undertake long complex plan at the order of Death Notes (like Mikami bringing the fake Death Note to the final confrontation with Near). Actions before death could be reported in great detail, or they could be hidden under official secrecy like the aforementioned death gods mentioned (Light uniquely privileged in learning it succeeded as part of L testing him). I can't begin to guess how many distinct narratives would survive transmission or what limits the Note would set. We must leave this one undefined: it's almost surely more than 10 bits, but how many?
Summing, we get $\lt33 + \lt19 + 17 + \lt37 + 14 + {?} = 120$ bits per death.