Here is another solution that pushes the work onto the sender rather than the receiver.
Input: List of recipients per epoch, by public key. \textsf{Roster:} \langle pk_A, pk_B, pk_C, pk_D, pk_E\rangle
Sender Protocol:
- Sender creates a list to represent which recipient(s) she is selecting from the \textsf{Roster}. To select the fourth user David (pk_D), she would create: \langle 0,0,0,1,0\rangle
- Encryption is exponential Elgamal (as in main post above). For notation, let [[m]]_{_A} be an encryption of message m under pk_A.
- Sender encrypts each bit of \langle 0,0,0,1,0\rangle with the public key that corresponds to \langle pk_A, pk_B, pk_C, pk_D, pk_E\rangle. Call this the \mathsf{Hint:}\langle [[0]]_{_A},[[0]]_{_B},[[0]]_{_C},[[1]]_{_D},[[0]]_{_E}\rangle
- Sender sends encrypted note along with \mathrm{Hint}.
Receiver Protocol:
- Receiver David fetches all \mathrm{Hints} from within an epoch:
| A | B | C | D | E | |
|---|---|---|---|---|---|
| Hint for Note 1 | [[0]]_{_A} | [[1]]_{_B} | [[0]]_{_C} | [[0]]_{_D} | [[0]]_{_E} |
| Hint for Note 2 | [[0]]_{_A} | [[0]]_{_B} | [[1]]_{_C} | [[0]]_{_D} | [[0]]_{_E} |
| Hint for Note 3 | [[0]]_{_A} | [[0]]_{_B} | [[0]]_{_C} | [[0]]_{_D} | [[1]]_{_E} |
| Hint for Note 4 | [[0]]_{_A} | [[0]]_{_B} | [[0]]_{_C} | [[0]]_{_D} | [[1]]_{_E} |
| Hint for Note 5 | [[0]]_{_A} | [[0]]_{_B} | [[0]]_{_C} | [[1]]_{_D} | [[0]]_{_E} |
| Hint for Note 6 | [[0]]_{_A} | [[1]]_{_B} | [[0]]_{_C} | [[0]]_{_D} | [[0]]_{_E} |
- David discards all columns except D.
- David takes the values in the D column and sums them homomorphically (one modular multiplication per homomorphic addition) and decrypts the resulting ciphertext. The integer will represent how many messages he received in the epoch.
- If zero, David is done for this round.
- If non-zero, David uses binary search to locate the Hint(s) that belong to him.
Analysis:
- Hints are large (n ciphertexts for n recipients) and probably kills this idea.
- Computation for sender is expensive (n encryption for n recipients) however a trusted server could help by generating empty hints for senders to use: \langle [[0]]_{_A},[[0]]_{_B},[[0]]_{_C},[[0]]_{_D},[[0]]_{_E}\rangle. The sender then replaces [[0]]_{_D} with [[1]]_{_D} to send a note to David. Of course, the server can trace this Note.
- However the sender could ask for empty hints from n semi-trusted (honest-but-curious) servers, add them together homomorphically (cheaper than an encryption), and then it is untraceable if 1 of the n servers is honest.
- Even though a malicious server cannot trace the Note anymore, it could provide a Hint with values other than 0. Note that the recipient will still recieve the note, it will just create grief for non-recepients who think the note is for them. Requiring a ZKP from the server can side-step this, but now the sender is verifying ZKPs to sidestep encrypting and the ZKPs would need to be succinct for it to be a net savings in computation. Note that any discovered malicious behaviour is independently verifiable so we could also use incentives/slashing to enforce correct behaviour.