<jupyter_start><jupyter_text>Highlights*Securely trace patient location history to privately notify those who may have been near.*1. A plan to provide contact tracing using apps and devices people already trust.   1. Users only need to opt-in, trusting partner app providers (e.g. Apple Maps, Google Maps, phone carriers, WeChat), to handle sensitive data.  1. For added privacy, users can keep identifying information on their device only.1. Details a distributed solution, using strong encryption.  1. Single-use numbers, cryptographically random, would function as person ID for each location history entry. Users can specify which agencies/authorities to trust with the ability to decrypt subsets of their data. Newly diagnosed patients can choose to share encrypted person IDs stored temporarily on their devices, to identify overlap in recent locations (encrypted and stored in the cloud).   1. Users who were also at those locations at the same time could only be notified by *polling*; it should be possible for them and only them to know that they were at some undisclosed locations that overlapped with a patient.1. Estimates monthly storage costs (USD) for 7B people:  1. No outbreak, logging every 15 minutes: &0036;150K (7 Petabytes)  1. 10K active patients, logging every minute: &0036;2.5M (120 Petabytes)  1. 100K active patients, logging every minute: &0036;3.3M (150 Petabytes)  Update: 4/2/2020 - Code open-sourced1. Python library shared on [ninja-pad-python repo](https://github.com/dantam/ninja-pad-python)  1. Demonstrates feasibility simulating people movement.  1. Creates public/private keys, sqlite databases, and config files for full cycle demo.  Main differences from actual contact tracing ([Apple and Google](https://techcrunch.com/2020/04/10/apple-and-google-are-launching-a-joint-covid-19-tracing-tool/))1. Ability to opt-in retroactively - location data can be shared after the fact, but anonymized contacts cannot.1. Ability to handle environmental contamination - indirect infections can be estimated from location data.1. Ability to use existing location data, without new apps or operating system updates.  BackgroundTo prevent a virus from spreading, one important component is to notify people who have a high chance of being recently infected, to self-quarantine and/or get tested. This is known as contact tracing. People who have come into contact with diagnosed persons are more likely to be also infected. One way to contact trace is to trace the locations a new patient has been in.However, most people do not want their location history public. This notebook is a proposal to share location in a cryptographically strong way, while making it likely that a high percentage of people who should be notified would be. They would be notified by *polling*, their true identification being strongly encrypted.See nytimes story for more background: https://www.nytimes.com/2020/03/19/us/coronavirus-location-tracking.html Privacy highlightsThe proposal would make both location and personal identification mostly private:1. Trusted location and personal "authorities" could separately decrypt some of the information. (More than one authority could be used by each person for each type of information).1. Full personal identification is possible only with encrypted information on the device. 1. The on-device store would destroy entries older than a set time, such that data from earlier than some number of days would be untraceable.1. Only when trusted medical providers indicate a person has been infected, would it be possible for "authorities" to link that particular person to their location history.1. Unless "location authority" is the same as "personal authority" for a particular log entry, the "authorities" would not know who appeared where.If a user already trusts a provider (e.g. map app) with their location data, the provider could act as an "on-device store". That way a user could opt in to this service by simply opting in from their existing trusted app(s). Note, if the trusted provider acts as an on-device store, the user would be essentially *push-notified* by the trusted provider.See [architectural diagram](files/ninja_pad.png) (also included below).  Related Work1. Private Kit  1. From [MIT](http://privatekit.mit.edu/); open sourced: [github](https://github.com/tripleblindmarket/private-kit)  1. Logs location once every five minutes, stores 28 days of data in under 100KB. Location data can only be accessed on device. Data transfer occurs only if the user chooses to share using a QR code.  1. Main differences:     1. location privacy - accessible on device    1. location privacy - requires redacted publication1. Trace Together  1. [Singapore Government official page](https://www.tracetogether.gov.sg/); [FAQ on data protection](https://tracetogether.zendesk.com/hc/en-sg/articles/360043234694-How-is-my-data-protected-)  1. Records proximity via Bluetooth of nearby app users, logs contact using secret ID provided by Government.  1. Main differences:     1. personal privacy - requires centralized ID mapping    1. location efficiency - requires human tracers to obtain location information    1. location privacy - requires broadcast to identify possible transmission through items in location    1. bluetooth may work not work for [environmental contamination](https://www.ncbi.nlm.nih.gov/pmc/articles/PMC539564/)1. Many other groups are also working on this:    1. [Pepp-PT](https://www.pepp-pt.org/)    1. [CoEpi](https://github.com/Co-Epi/CEN/blob/main/protocol.md)    1. [Covid Watch - Stanford](https://www.covid-watch.org/articlecontactTracing)    1. [OpenMined](https://blog.openmined.org/covid-app-privacy-advice/)1. Two promising techniques that should be explored more are [private set intersection and homomorphic encryption](https://security.googleblog.com/2019/06/helping-organizations-do-more-without-collecting-more-data.html)  Non-private illustrationA pseudocode scratch of a non-privacy-aware module would help illustrate how people tracking could work. Privacy issues and solutions would follow.<jupyter_code># pseudo code to show basic notification workflow, using location and time

from collections import defaultdict

class NonPrivateTracker:
    def __init__(self, time_interval_to_keep='2 weeks'):
        self.location_log = defaultdict(list)
        self.person_to_spacetimes = defaultdict(list)
        self.spacetimes_to_persons = defaultdict(list)
        self.time_interval_to_keep = time_interval_to_keep
        
    def log(person, location, time):
        self.location_log[time].append((person, location))
        
    def process_log(time_window):
        # truncate entries older than time_interval_to_keep
        for time in time_window:
            for person, location in self.location_log[time]: 
                self.person_to_spacetimes[person].append((time, location))
                self.spacetimes_to_persons[(time, location)].append(person)

    def notify(new_carrier, time_window):
        spacetimes = self.person_to_spacetimes[new_carrier]
        to_notify = set()
        for log_time, location in spacetimes:
            if log_time in time_window:
                persons = self.spacetimes_to_persons[(log_time, location)]
                to_notify.add(persons)
        return to_notify - new_carrier<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.0675437406754374, 'fraction_numerical': 0.017496270174962702, 'mean_word_length': 4.25962910128388, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 12, 'lorem ipsum': 0, 'www.': 5, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '573162', 'license': 'MIT', 'n_tokens_mistral': 1954, 'n_tokens_neox': 1822, 'n_words': 861, 'path': 'Private Location Tracker.ipynb', 'repo_name': 'dantam/DataRocks', 'size': '7373'}