LOW_LATENCY_DESIGN

===============================================================================
Roadmap
===============================================================================
I.    Abstract
II.   Overview
III.  Trustee / Relay Interaction
IV.   Client / Relay Interaction
V.    Relay / Relay Interaction
VI.   Client / Relay Interaction
VII.  Configurations
VII. Terms
E.    Tasks

===============================================================================
I.    Abstract
===============================================================================

Low latency Dissent has the appearance of a 1-hop proxy: clients transmit
ciphertext to a server, who decrypts the ciphertext, and forwards the resulting
cleartext.  In LLD, a set of clients transmit ciphertext upstream to a single
relay who processes the ciphertexts into a set of cleartext messages.  The
relay then returns the output to the clients and acts as an Internet relay for
any cleartext packets transmitted to Internet services.  This document
discusses a specific approach to performing these interactions that retains the
strong security parameters of accountable DC-nets like Dissent.

===============================================================================
II.   Overview
===============================================================================
Background: This document only describes the events after a shuffle has
completed.  In this model, only a single client transmits cleartext data, in
other words, there is only one slot.  The shuffle outputs an anonymous DH / DSA
key The approach naturally expands to multiple transmitters / slot owners by
producing additional sets of cipher as described later.

Setup: Prior to beginning exchanges, clients, relays, and trustees perform
session setup.  The session setup consists of registration followed by
scheduling.  During registration, each client, relay, and trustee authenticates
and provides a public DH key that can be used for verifying signatures and
producing shared DH secrets.  During scheduling, each clients introduce an
anonymous DH key into a shuffle performed by the trustees.  The resulting order
of the shuffle defines slots owned by the pseudonym keys.  After session setup,
sessions begin.  A session consists of many intervals or a series of exchanges
with a fixed set of online clients.

Each client takes each trustee's key, provided during registration, and
performs a DiffieHellman key exchange producing a shared secret.  Likewise each
trustee takes each client's key in order to construct a matching set of shared
secrets.  Clients and trustees uses these seeds to generate random strings.
Each participant Xors his set of strings together to produce cover traffic or
the participants ciphertext.  Within a ciphertext, the anonymous slot owner
Xors in his message.  Xoring all ciphertext messages together reveals this
message, because all the random strings cancel out, as each string would be
included twice, once by the trustee and once by the client.

In LLD, slots have a fundamental unit of cells.  Trustees use the
client/trustee shared secrets, the current interval index, the current cell
index, and the slot DH key as seeds to random number generators -- hash(secret
| interval index | cell index | slot index) -- producing a ciphertext for each
client.  Trustees generate these shared ciphertexts in batches, at a minimum of
a cell size, Xor them together, and deliver the resulting byte array to the
relay.

Similarly, the clients use the client/trustee shared secrets as seeds to random
number generators producing a ciphertext for each trustee.  The client then
Xors these together and transmits an appropriate number of cells to the
upstream relay.  The number of cells can depend on a many number of things,
such as fairness, policy, and the number of cells requested by the slot. This
document, for now, only considers the number of cells requested by the slot,
such that the output of exchange i specifies the number of cells requested in
exchange i+1. This specific details of slot format are defined in the section
discussing slot format.

The relay accumulates trustee ciphertext and reserves it for later use.  After
receiving a ciphertext from all clients for the given interval, the relay
combines all the client ciphertexts with sufficient trustee ciphertext in order
to produce a cleartext message and transmits that to the clients.  The relay
does not progress to the next exchange until all clients have submitted or an
interval has concluded.  The relay delays an exchange if he lacks sufficient
trustee ciphertext.

======================
Certifying the Output
======================

We propose three methods for certifyiing the output of a slot: 1) each client
signing off on the previous cleartext, 2) a shared secret among the clients
that decrypts their ciphertext to reveal DC-net ciphertext, and 3) a per-nym
verifiable DC-net that unclocks the nyms ciphertext using a similar shared
secret between the anonymous owner and all clients.

In the first approach, clients produce a signature using the previous exchanges
cleartext, the session, interval, and exchange identifiers, ensuring that even
if the same cleartext results for each exchange the client will be signing
unique data. The relay accumulates the client signature from each client and
transmits them back to all clients.

In the next approach, each client shares a secret with every other client and
computes a group-wide shared secret. The clients submit two ciphertexts along
with their ciphertext: an encrypted key used encrypt their ciphertext and their
portion of the decryption key.  Each client i has a private key, x_i, and a
shared public key, g^x_i. In order to compute , and computes their portion of
the shared secret as s_i = multi(g^x_j^x_i, j < i) * multi(-1 * g^x_j^x_i -1, j
> i). The portion of the decryption key, d_i, is computed as g^(hash(m))^s_i,
where m is the set of messages from the previous exchange concatenated with the
current session, interval, and exchange identifiers. Multiplying all the d_i
together results in a value of 1. Hence, the encrypted key, e_i, takes the form
of key_i * d_i. To derive the key, multiply d_i * multi(e_j, j != i). The
ciphertext transmitted with this is then encrypted using this key and can be
decrypted by the relay using this key. At the conclusion of each interval,
clients provide a proof of correctness of the form...

In this approach, we introduce a verifiable DC-net (Verdict) slot for each
active symmetric DC-net slot. After the shuffle, each client j obtains a shared
secret, s_j, with the anonymous slot owner using their respective well-known DH
keys. The slot owner, client i, sets his s_i = -SUM(s_j, j).  In exchange k, a
verdict slot will be encrypted with a generator, g_k, derived from the hash of
the cleartext from exchange k-1.  Specifically, client j computes a verdict
element x_j = g_k^s_j.  If client j owns the slot, he can then multiply in a
message, m: x_j = m * x_j.  Upon receiving all x_j, the server multiplies them
together revealing m, each s_j cancels out if g_k is the same for all.  The
message m contains a seed used to encrypt the symmetric DC-net ciphertext in
the same exchange. In addition to transmitting x_j, clients transmit a proof of
knowledge, proving that either they own the DH key associated with the slot or
their m = 1, a null encryption.

======================
Preventing Disruption
======================

In order to prevent disruption, the anonymous slot owner and trustees introduce
an additional trap layer to the owner's cleartext message.  The slot owner
shares a secret with each trustee to produce an additional ciphertext stream.
The secret derives from the slot owner's DH key revealed during the shuffle and
a per-interval DH key provided by the trustee prior to the start of an
interval.  The client produces two seeds: one for generating ciphertext and
another for selecting a trap bits.  Both seeds consist of a hash of the shared
secrets, cell index, and a 0 for generating ciphertexts or a 1 for selecting
trap bits -- hash(secret_1 | ... | secret_n | cell index | 0/1).  The client
picks one bit out of every n-bits to be a trap bit.  The trap bit remains
unchanged while every other bit is set to 0.

After selecting the trap bits, the client embeds messages without modifying the
trap bits.  To do so, the client splits his cleartext message into n-bit blocks
and prepends a header equal with the number of bits equal to the number of
n-bit blocks.  Each bit in the header belongs to the set of n-bits at the same
index within the message.  The header bit is used as an inversion flag.  If the
flag is 0, then the data can be stored without toggling the trap bit.
Otherwise he chooses a 1 bit and uses the complement of those n-bits in order
to avoid toggling the trap bit.

At the end of an interval, the relay transmits the output of each exchange to
the trustees.  The trustees then reveal their trap secrets in order to
determine the trap bits.  If no trap bits have been triggered, they continue on
to the next interval.  If a trap bit has been triggered, the trustees perform
the blame analysis as described in Dissent in Numbers.

==========
Intervals
==========

In order to support client dynamics or churn, the trustees and relay will form
a new online client set, or interval, at a fixed period that works within the
current session.  Clients gracefully leave by registering to do so prior to the
conclusion of an interval.  Clients that leave without registering and waiting
for the conclusion of an interval are exceptions, There exist two cases: a
client announces its intention to leave without waiting for an interval and a
client disappears without notice.  In both cases, the relay waits until the end
of the current interval, at which point, the relays and servers perform a
re-configuration.

There are two conditions for being included in an interval.  A client already
in a current interval will automatically be included in the upcoming interval.
A client that misses all exchanges in an entire interval will be considered
disconnected from the upcoming interval.  A disconnected or offline client who
was not in the current interval must register for two upcoming intervals prior
to be included as online in the second of the two intervals.  Effectively, we
require cycle users offline and online over the course of an entire interval.

============================
Extending to Multiple Slots
============================

In order to support multiple slots, trustees and clients must produce a set of
ciphertexts for each slot.

======================
Handling Client Churn
======================

The relay and trustees can maintain a reputation for clients.  Clients that
frequently and abruptly leave may not even be included in intervals for certain
slots or a interval event may occur more quickly in order to make progress on
that slot.  Secondly, a client that is no longer in a possinymity set should
not be in a interval for that slot.

============
Slot Format
============

We could probably just reuse something similar to Dissent in Numbers without
the randomize function as the trap bit component proposed herein replaces it.

===============================================================================
III.  Trustee / Relay Interaction
===============================================================================

0) Before each interval, the relay informs the trustees about the current
online client set:

R -> T ([RELAY_INFORM | SessionId | IntervalId | ClientSet] | [Signature_R])
- RELAY_INFORM - int - The message type
- SessionId - bytes - The session identifier
- IntervalId - int - The current interval (starts at 0)
- ClientSet - bytes - Bit array, clients bit is set if they will participate
- Signature_R - bytes - The relay's signature using his well-known DH key

1) Before an interval, trustees sign off on the current configuration and offer
new per-interval DH keys:
T -> R ([TRUSTEE_CONFIRM | SessionId | IntervalId | ClientSet | IntervalKey] |
  [Signature_T])
- TRUSTEE_CONFIRM - int - The message type
- SessionId - bytes - The session identifier
- IntervalId - int - The current interval (starts at 0)
- ClientSet - bytes - Bit array, clients bit is set if they will participate
- IntervalKey - bytes - A DH Key for use in the specified interval
- Signature_T - bytes - The relay's signature using his well-known DH key

2) Before and throughout an interval, trustees will deliver ciphertext for
processing client ciphertext into cleartext messages:
T -> R ([TRUSTEE_CIPHERTEXT | SessionId | IntervalId | CiphertextId |
  Ciphertext] | [Signature_T])
- TRUSTEE_CIPHERTEXT - int - The message type
- SessionId - bytes - The session identifier
- IntervalId - int - The current interval (starts at 0)
- CiphertextId - int - The current ciphertext (starts at 0)
- Ciphertext - bytes - Set of bytes for each slot
- Signature_T - bytes - The relay's signature using his well-known DH key

3) Throughout an interval, the relay transfers the output of exchanges to the
trustees:
R -> C ([RELAY_CLEARTEXT | SessionId | IntervalId | ExchangeId | Cleartext |
  InternetTraffic] | [Signature_R])
- RELAY_CLEARTEXT - int - The message type
- SessionId - bytes - The session identifier
- IntervalId - int - The current interval (starts at 0)
- ExchangeId - int - The current exchange (starts at 0)
- Cleartext - bytes - A set of bytes for each cleartext
- InternetTraffic - bytes - A set of bytes for each incoming Internet packet
- Signature_R - bytes - The relay's signature using his well-known DH key

===============================================================================
IV.   Client / Relay Interaction
===============================================================================

0) A client in the roster though not in active in the interval must register
for two consecutive intervals by transmitting a CLIENT_REGISTER message:

C -> R ([CLIENT_REGISTER | SessionId | Timestamp] | [Signature_C])
- CLIENT_REGISTER - int - The message type
- SessionId - bytes - The session identifier
- Timestamp - int - Time since the Epoch
- Signature_C - bytes - The client's signature using his well-known DH key

1) At the conclusion of each interval and before the first, the relay transmits
a conclusion message, either containing configuration information for the
following interval or concluding the current session.

R -> C ([INTERVAL_CONCLUSION | SessionId | IntervalId | NextInterval |
  IntervalConfiguration] | [Signature_R])
- INTERVAL_CONCLUSION - int - The message type
- SessionId - bytes - The session identifier
- IntervalId - int - The current interval (starts at 0)
- NextInterval - bool - True if there is another interval and
IntervalConfiguration has valid information
- IntervalConfiguration - list of TRUSTEE_CONFIRM - The configuration for the
next interval
- Signature_R - bytes - The relay's signature using his well-known DH key

2) Clients actively involved in an interval transmit ciphertexts as quickly as
soon as they receive the INTERVAL_CONCLUSION message or a downstream ciphertext
from the relay:

C -> R ([CLIENT_CIPHERTEXT | SessionId | IntervalId | ExchangeId | Ciphertext] |
  [Signature_C])
- CLIENT_CIPHERTEXT - int - The message type
- SessionId - bytes - The session identifier
- IntervalId - int - The current interval (starts at 0)
- ExchangeId - int - The current exchange (starts at 0)
- Ciphertext - bytes - A set of bytes for each of the active slots
- Signature_C - bytes - The client's signature using his well-known DH key

3) The relay accumulates all the client ciphertext and xors it with the
trustees' ciphertexts. This produces cleartext output, which the relay server
transmits back to the clients along with any relayed Internet traffic. At the
same time, it relays Internet destined packets from within the cleartext
Internet to their appropriate destinations.

R -> C ([RELAY_CLEARTEXT | SessionId | IntervalId | ExchangeId | Cleartext |
  InternetTraffic] | [Signature_R])
- RELAY_CLEARTEXT - int - The message type
- SessionId - bytes - The session identifier
- IntervalId - int - The current interval (starts at 0)
- ExchangeId - int - The current exchange (starts at 0)
- Cleartext - bytes - A set of bytes for each cleartext
- InternetTraffic - bytes - A set of bytes for each incoming Internet packet
- Signature_C - bytes - The relay's signature using his well-known DH key

===============================================================================
V.    Relay / Relay Interaction
===============================================================================

===============================================================================
VI.   Client / Relay Interaction
===============================================================================

===============================================================================
VII.  Configuration
===============================================================================
Each Dissent deployment has several configurable layers: system, session,
pseudonym and interval.

=====================
System Configuration
=====================

System configuration consists of the identities and keys of the set of possible
trustees, relays, and clients. It also contains the IP addresses for relays and
trustees. An identity is the sha-256 hash of a member's public key and used to
reference the member independent of their IP address.  The configuration file
also contains a version, to be included in certain messages, to ensure that two
Dissent software components are compatible and a group-id for similar reasons.

{
  "version" : int,
  "group-id" : int,
  "relays" : {
    { "id" : identity, "key" : key, "ip" : ip },
    ...
  },
  "servers" : {
    { "id" : identity, "key" : key, "ip" : ip },
    ...
  },
  "clients" : {
    { "id" : identity, "ip" : ip},
    ...
  }
}

======================
Session Configuration
======================

The session configuration includes the group-id listed within the system
configuration and consists of the participants for the upcoming session and a
DH key for each and a unique session nonce or id. The session configuration
also has a set of signatures, one for each trustee, attesting to the
correctness of the session configuration file.

{
  "group-id" : int,
  "session-id" : int,
  "relays" : {
    { "id" : identity, "dhkey" : dhkey },
    ...
  },
  "servers" : {
    { "id" : identity, "dhkey" : dhkey },
    ...
  },
  "clients" : {
    { "id" : identity, "dhkey" : dhkey },
    ...
  },
  "signatures" : {
    { "id" : identity, "sign" : signature },
    ...
  }
}

========================
Pseudonym Configuration
========================

The pseudonym configuration consists of anonymous DH keys in a fixed order
representing the order fo the communication slots during exchanges. This too
includes the signature from all trustees.

{
  "group-id" : int,
  "session-id" : int,
  "slots" : {
    dhkey0,
    ...
  },
  "signatures" : {
    { "id" : identity, "sign" : signature },
    ...
  }
}

=======================
Interval Configuration
=======================

At each interval, trustees will announce the set of online clients and a list
of new DH keys for generating trap bits.

{
  "group-id" : int,
  "session-id" : int,
  "trapkeys" : {
    dhkey0,
    ...
  },
  "signatures" : {
    { "id" : identity, "sign" : signature },
    ...
  }
}

===============================================================================
VIII.  Terms
===============================================================================
Clients - users of the service
Relays - data plane server
Trustees - control plane server
Interval - the online and active set of clients
Symmetric encryption cipher - AES128CTR

===============================================================================
E.   Tasks
===============================================================================
- DiffieHellman exchange, proof of knowledge, and verification
- Inversion coding
- Generating ciphertext
- Slot format / generation / parsing
- Trap bit generation / verification
- Trustee framework
- Client framework
- Server framework
- Communication model
- Socks server / proxy
- HTTP server / instant messanger
- Session bootstrap (Core Dissent Design Doc)
- Configuration format for session and interval