System Parameters
=================

1. k is a large public prime.
2. The server S publishes a public key for RSA signing.

Joining the System
==================

1. Generate two RSA key-pairs, one for signing and one for encryption. Publish both public keys to AFS.
2. Download the list of other people in the system and get their public keys. For each person P:
  1. Generate 512-bit primes p, q (for Paillier), c (the "yes" value for matching)
  2. Encrypt (p, q, c) with P's RSA public key, sign with your private key.
  3. Send n = pq and Enc\_P(p, q, c) to the server

Submitting Preferences
==================

To submit preferences as person A:

1. For each person:
  1. Get the (p, q, c) for the person (either we generated it, or it's on the server encrypted with our public key).
  2. Make sure c is prime and not p or q if we didn't generate it.
  3. To send "yes", send c + sp for random s. To send "no", send a random number d (that is not c mod p or q)

Computing Matches
=================

Once preferences (a, b) for people A and B are received:

1. Compute Enc(ra + (k-r)b) for random prime r.
2. Send o = Enc(ra + (k-r)b) to each person.

Opening and Validating Matches
==============================

Without loss of generality, suppose we are person A.

1. Receive and decrypt o to get z = ra + (k-r)b.
2. If z == kc (mod p) then A and B both submitted c (mod p), so this is a match.

Extension to Detect Malicious Servers
=====================================

TODO