# Oblivious message retrieval

Aztec aims to bring privacy to Ethereum ecosystem and achieves that with its privacy preserving layer 2 which enables confidential transactions. A typical user-flow for transactions on Aztec layer-2 looks similar to user-flow on any other chain, but with an added benefit that transactions don’t reveal any information.

In privacy preserving chains, like Aztec, it’s important to preserve privacy of transaction throughout the transaction flow. This includes preventing leakage of information from the source till the receiver. Senders can hide themselves behind networks such as Tor, preventing any leakage, however, on receiver end the situation does not look as good.

To identify transactions pertaining to them, a receiver must download all broadcasted transactions and perform trial decryption. However, a light client (i.e. mobile wallets, etc.) would want to outsource detection service to a third party server. Ideally, the light client wants to receive all transactions addressed to them from the server without the server learning anything about the transactions. This, at an application level, remains an unsolved problem.

With new schemes for oblivious message detection/retrieval, the server can compute a digest containing transactions pertaining to a user while remaining oblivious to digest’s content. Thus enabling light clients to outsource transactions detection service to 3rd party server without risking information leakage. Typically, the user flow looks like following

1. User that wants to outsource detection, generates detection key and clue key. They upload detection key to 3rd party server. They reveal their clue key publicly, so that others can address transactions to them.
2. To address transaction to a user, transaction sender uses user’s publicly available clue key to generate clue, after which they send transaction, along with clue, to the server.
3. Server maintains a database of transactions and their corresponding clues. Upon receiving a new transaction and its clue, server adds it to this database.
4. User can now query the server for digest. Server processes the database to first identify database rows, using clues and user's detection key, containing transactions addressed to user. After which, server generates a digest containing detected transactions and send it back to the user. Note that all computations are performed homomorphically on encrypted data, thus server learns nothing about the digest.
5. User has the secret key to decrypt the digest and learn about transactions addressed to them.

The aim of this grant is to implement oblivious message retrieval for Aztec and test its feasibility for real-world deployment. The scope of grant includes, but not limited to, the following:

1. Implementation of OMRp1 scheme from [https://eprint.iacr.org/2021/1256.pdf](https://eprint.iacr.org/2021/1256.pdf). In results OMRp1 exhibits lowest bandwidth communication and lowest recipient computation, thus appears to be best suited for low processing power devices.
2. Prototyping and benchmarking OMRp1 scheme for messages with a size of 256 bytes (typical of an Aztec L2 transaction).
3. Identifying and implementing optimisations to the implementation of the scheme. For example (1) Does a combination of fuzzy message detection and OMR has better trade-offs ?
Moreover, several suggestions for improving the scheme are given section 12 of [https://eprint.iacr.org/2021/1256.pdf](https://eprint.iacr.org/2021/1256.pdf).
4. Integrating the scheme with Aztec probably on on-going basis (since this is sometime in the future, I am unsure of what the exact interface of integration will look like. Please give your suggestions here).

## Areas to improve, guidance, risks

1. OMRp1 scheme uses levelled BFV Homomorphic encryption and PVW encryption. Both schemes heavily make use of polynomial operations. Even though the implementation will leverage double CRT, plus other necessary optimisations specific to homomorphic operations, it will be great help if Aztec team can support in optimising such operations.
2. Selecting the right parameters for BFV is hard. Even though we can simply get started with parameters given in the paper, real-life scenario might differ. Thus figuring out right parameters might take a bit of time. Help from Aztec in setting up environment for testing, plus suggestions on testing will be great help.
3. Guidance on what are the right trade-offs for Aztec will aid in coming up with right design. For example, it’s possible to reduce detection key size by replacing BFV scheme with some other FHE scheme, which is favourable in situations client is unable to upload data greater than few MBs to servers. But this change penalises the server with additional computation cost.
4. General guidance on integration will aid development. For example
a. How to embed clues (each clue is of 956 bytes)
b. Process to upload detection keys to server
c. How to share clue keys (133 kb)
d. Server either supports single shot requests or subscribe + finalise. In single shot, client asks the server to process their respective digest in a query. Such requests take time, since server computes everything from scratch after receiving client query.
In subscribe + finalise, server already has client’s detection keys, using which it pre-processes computation intensive part periodically. Whenever client sends a request, server simply finalises the last step to generate digest and sends it back. This is much faster than single-shot.
Subscribe + finalise seems better from client’s perspective, but testing will be required to figure out right trade offs between how much to pre-process
5. Suggestions on handling DoS attacks will be helpful

## Expected performance metrics
| N (no. of messages) | Server Processing | Digest size (cts: BFV ciphertexts) | User Processing (decryption of BFV ciphertexts + gaussian elimination) |Total|
| -------- | -------- | -------- | -------- |-------- |
| <= 500,000| 175s | 2 cts ~ 550kb|20ms |175.02s |
| 1,000,000| 350s | 3 cts ~ 823kb|22ms | 350.022s |
| 2,000,000| 700s | 5 cts ~ 1373kb|26ms | 700.026s |

Points to note:
1. Using BFV parameters given in the paper there's no benefit setting N with values other than multiples of 500000.
2. All values are repsentative of single-threaded computation. I think we can improve upon user side processing as well as phase 2 of server with parallel processing.
3. Server processing can be divided into two phases - Phase 1 and Phase 2. Phase 1 is pre-preprocessing. It generates the pertinency vector (PV) using user's detection key. It comprises of 95% of total server-side computation. Phase 2 takes PV and generates the digest for user. Phase 2 is performed upon receiving user query. Since generating digest after phase 1 involves only homomorphic additions, phase 2 is a lot cheaper than phase 1. It takes 0.00035 sec/msg (single-thread) in phase 2. Note that values in "Server processing" column are 0.00035 * N.
4. Digest consists of BFV ciphertexts (cts). You can split them into two sets ~ (1) cts containing PV (2) cts containing message. Using BFV parameters from the paper, the maximum information a ct can pack is 524,288 bits. So when N = 500,000 we only need 2 cts (one for representing PV and another for messages).
5. Values above assume a maximum cap on no. of pertinent messages a user can have ~ k = 50. With k uptill 128 (message size: 256 bytes) we only need one ct in digest to represent messages.
6. User processing consists of decryption of BFV ciphertexts and gaussian elimination. Decryption comprises majority of computation cost. So with increased message digest we can notice computation time increases.
7. Values above are for when message size is 612 bytes. In our case message size is 256 bytes. Since in both cases one ct is required for representing messages, we don't benefit much from having smaller message size. We can expect some improvement in gaussian elimination (smaller size translates to lesser equations), but considering the majority cost is from decryption I don't think it will amount to much.
8. The above values are for OMRp1 scheme. In OMRp2 scheme, which uses randomized digest compression to keep digest size compact (i.e. digest size grows only mildly with N), the numbers for user processing and digest size stay constant for large N (i.e N <= 10^8). But we take hit on the constant values for user processing & digest size. User processing increases to 63ms and digest size increases to ~1800kb. The computation time for phase 1 of server processing is also increased, but phase 2 (only phase 2 matters in response latency) remains the same ~ 0.00035 sec/msg.
9. Digest size and user processing numbers are better for OMRp1 till N <= 10^7, beyond which OMRp2 is better. Another thing to note is we have assumed k = 50. If we reduce k then values for both schemes will improve (linearly).