mix-nets
========

Goal:  You want to send an untraceable message
mix-nets [Chaum]:  Use a trusted "mix" server
  Idea:  Pad/break up all messages into fixed-size blocks
  Mix process messages in batches, so can't match inputs and outputs
  Server has public key K1, recipient KA.  Server input and output:
    {{M}_KA, A}_K1 => {M}_KA, A
Is this good enough?
  No: Replay attacks, can repeat input, see same output many times
    mix must remember all previous messages (or tag messages with day number)
  No: If one node doesn't send traffic very frequently, easier to track
    inject dummy messages when no traffic
What can you do about a cheating server?
  Make server sign receipts for input
    {Client, {{M}_KA, A}_K1}_{K1^{-1}}
  Server signs entire output batch
What about return addresses?
  Can create a pseudonym:  Kx, {R1, A}_K1
  Now server maps:  {R1, A}_K1, {M}_Kx => A, {{M}_Kx}_R1
But central server is single point of failure--would kill everyone's privacy
  Can instead cascade (chain) multiple mixes, so only one need be honest
  Efficient implementation:
    Break message up into chunks
    First chunk contains next mix address
    Pop it off the front, push it on the back
  Note:  dummy messages can now be dropped earlier

dc-nets
=======
Mix-net relies on public key cryptography
  Attacker could later crack public/symmetric keys, or compromise mix server
  Can we build anonymous system that's unconditionally secure?

3 cryptographers sitting around a table at dinner
  Maitre d' says one of them has anonymously paid for the meal
    They want to know if this is true, or if NSA is in fact paying for the meal
    How to do while preserving anonymity if cryptographer is paying?
  Algorithm:
    Each cryptographer flips a coin behind his/her menu
    Shows the result to the cryptographer to his/her right
    Each cryptographer sees two coins--his/her own, and the one to the left
      Announces "same" if both are the same, or "different" otherwise,
        Except if the cryptographer has bought dinner, then says opposite
    Odd number of "different" answers => Cryptographer is paying
    Even number of "different" answers => NSA is paying

Generalizing the approach to N parties
  Each party shares one bit with the N-1 other parties
  Outputs XOR of all bits shared with N-1 other parties
    Invert output to transmit a bit
  XOR all of the outputs:  0 => no one xmitted, 1 => one person xmitted
    Proof:  Each shared bit counted exactly twice (once by each party)

Generalizing to longer messages
  One approach:  Like shared media networks
    Transmit message with checksum
    If message garbled, back off for random periods
    Can use fewer secret shared bits when no one is sending
      Someone transmits a one bit when they want to start a packet
  Another approach:  Reservation
    Run protocol for a number of bits in reservation period
    To transmit a message, pick random bit to transmit in reservation period
    If you set the ith bit in reservation period, send packet in ith slot

Efficiency:  Does every pair of nodes need to share a bit?
  Probably not, depending on security requirements
  Picture system as a graph:
    Nodes are vertices in the graph
    Edges represent shared bits between two nodes
  Define:  ANONYMITY SET seen by set S of key bits
    Remove all edges in graph corresponding to keys in S
    Anonymity sets are remaining connected components
  If attacker knows keys in S, will only know parity of each anonymity set
    Example:  If all pairs of nodes share key bits, don't learn anything
    Example:  If two sets separated, know which one transmitted a bit
  Possible topology:
    Have fully connected subgraph of nodes one of which is honest
      (for example, nodes could have conflicting goals)
    Each node must then share a key with every member of the subgraph
    Security can only be compromised if all nodes in subgraph are bad

How to deal with disruption?  Bad node could constantly transmit
  Suppose:
    1. Everyone agrees on key sharing graph
    2. Outputs agreed on and can depend on other people's
       (e.g., sign outputs, place in sealed envelope, open all at once)
    3. Can expose some rounds without hurting privacy
  Then you can trace attacker by revealing key bits
    Attacker could lie about a key bit, but node sharing key will know
      At least the honest node knows the other is dishonest
      So will refuse to share bits with disruptor
      Eventually disruptor gets completely isolated
  How to achieve property 3 (can expose some rounds)?
    Trace people who disrupt reservation portion
      Limit # of reservations/node, disruptor increases #slots, then trace all
    Set message traps:
      Node publishes encrypted reservation slot # and random message
      Then opens publishes key to catch disruptor