Homomorphic Encryption of delegated DPC computations (based on enclaves)

[jon-chuang]

As a wild idea, I would like to suggest the possibility of a privacy-preserving version of delegated DPC. Although most would be willing to trust a cloud server for DPC, there may be some who might want to initiate transactions from their mobile phone who would want greater privacy yet reap the benefits of lower latency.

I can suggest the option using the BFV scheme to perform relatively efficient homomorphically encrypted modular arithmetic for MSM (I will give a think to FFTs later on). It is not clear a priori whether delegating computation in this way will help achieve low latencies desired (1-2s?).

For the MSMs, we perform EC operations given an n-bit EC group in projective coordinates. The delegating party encrypts their polynomial's coefficients a_k in the following way. If the a given bit of a_k is 1, they encode it as a pair of triples, (a, b) = (1, 1, 1), (0, 0, 0). Else, they encode (0, 0, 0), (0, 1, 0) (a more efficient way of doing things is encoding the bit values themselves, and deriving the above representations homomorphically. This is cheap as it's plaintext-ciphertext mult.)

However, the communication cost of this is 2^m*n. Concrete numbers look like 2^20*256, which given a 1280-bit encoding of each bit, stands at about 44GB. So this is already an arrow to the knee.

For the jth bit, the server obtains an element representing P = (x:y:z) = [2^j*k]tau by repeated doubling, and then encodes this as a BFV value. Then, the server performs the following operation element-wise on the triples homomorphically: P*a + b. One can check this either gives the element at infinity if the bit was set to 0 and returns P otherwise.

Then, the server will perform elliptic curve point additions homomorphically on all the encoded points. It remains to be seen what depths of circuit can be utilised - complexity for BFV goes as at least n^2 in the depth.

There is an issue here in that formulas differ for point doubling and point addition. One could get around this issue by using an equality check (check that all coordinates are the same) and choose the appropriate condition based on this (perform both operations and multiply one by 0 and one by 1, similar to above). However, the method I know to do this is exceedingly expensive (Fermat's little theorem) and I think impractical. Alternatively, one can assume it exceedingly unlikely that two points not equal to zero are equal to one another. Hence, one should keep the original encrypted bit-values handy, propogating a point at infinity if and only if the operands are both points at infinity (this can all be done homomorphically) and returning the point addition otherwise.

Overall, I think this idea is ill-conceived as one cannot expand the computation homomorphically from a small piece of data, as is done for neural network inference, for instance, due to the memory-intensivity of polynomial commitments.

Nonetheless, it is plausible that a method using enclaves to perform computations on sensitive data be performed side by side a powerful parallel machine. Enclaves, however have the downside of having limited memory (~90MB). Nevertheless, an enclave can emit ciphertexts of partial transcripts of computation or coefficients of a polynomial piece by piece, delegate the FFTs/point additions to a nearby machine, and refresh ciphertexts whenever required.

Due to the computational overhead (50-100x), I estimate that at least 20 64 logical core machines will be needed to bring prover times to acceptable speeds (10s). Utilising GPUs or more machines can help bring this down further. This seems equitable if one has many users opting for (and willing to pay for) private computation. If one is aiming for 100 tx/s, this method may be economically viable if at least 1 in 1000 users opt for additional privacy (this is in order to provide the service on demand. I am not sure how long it takes to spin up a prover on a service like AWS px large). 32 GPUs on EC2 costs $40/hr. So it could cost less than $0.1 to homomorphically prove a private transaction (with the help of enclaves). Nonetheless there is a lot of uncertainty about how much security an enclave actually provides.

Note that there is additional overhead as the algorithm considered above is just parallel scalar multiplication, not MSM. I don't think there is a privacy-preserving version of MSM.