Skip to content

Instantly share code, notes, and snippets.

@hdevalence

hdevalence/arb.md

Created March 25, 2020 06:22
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save hdevalence/fefba3153b30e60537e84f7d2551b295 to your computer and use it in GitHub Desktop.
Save hdevalence/fefba3153b30e60537e84f7d2551b295 to your computer and use it in GitHub Desktop.
Download ZIP
Anonymous Retrospective Broadcasts
Raw
arb.md
  • Anonymous Retrospective Broadcasts
    • If we don't assume a centralized party that can be trusted to verify information, what we're left with is not really a contact tracing application but a particular kind of messaging application, where users create tracks through space and time, and can retrospectively broadcast anonymous messages to users whose tracks were spatially nearby to theirs in a particular time range.
    • This messaging system should be privacy-preserving, in the sense that:
      • Server Privacy: An honest-but-curious server should not learn information about any user's space-time tracks;
      • Locality Integrity: A user should not be able to broadcast messages to users who were not nearby to them;
      • User Privacy:
        • A passive adversary cannot not learn any information about a user's space-time track outside of the segments they have broadcast messages to. This means that users who do not broadcast reveal no information about their movements.
        • Users who broadcast messages to segments of their space-time track reveal only the existence and content of a message to users whose tracks were not adjacent to theirs. This means that the messages themselves are public; what's private is the addressing/matching.
        • Users who receive messages learn only the fact that their track was nearby to the user's track at some time. This means that passive adversaries must cover space and time or else recruit users to collude to reconstruct the track of a user who broadcasts a message.
        • Users who receive messages reveal no information to the users who broadcast them.
    • For efficiency reasons, it would be ideal to create a protocol whose interactions could fit into the following model:
      • Registration Phase: users register with the server and perform some setup.
      • Gossip Phase: users broadcast 26-byte data packets over [[BLE]] to nearby users.
      • Broadcast Phase: a user uploads a packet of data to the server to broadcast a message to a particular segment of their track.
      • Scan Phase: users monitor data published by the server to learn whether a message has been broadcast to them.
      • Fetch Phase: users who learn of a message addressed to them can download it.
    • This system can be used to implement decentralized contact tracing, by allowing users who test positive to anonymously broadcast a message to inform their past contacts of their test. Users who receive a message can make an informed judgement based on its contents.
      • For instance, a user could publish a photo of a test result with their name redacted, or reveal their identity by linking to a social media post, or post a link to some institutional verification mechanism, if one existed.
      • Separating the messaging part from the contact tracing problem and allowing users (or user-agents) to make decisions of their own is significantly more flexible and practical.
    • This system has other potential applications beyond contact tracing, such as building a system like Craigslist's Missed Connections with notifications.
    • This system's communication flow is compatible with a moderation / karma system that can be used to ban accounts that post spam or abusive messages.
      • This would work by reporting bad messages to the server, which would prevent them from being downloaded by other users, and/or ban the user that uploaded them.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment