[General Question] Existence of HE Scheme with more powerful properties

Question

Is it conceivable that there exists a HE scheme in which a computation can be decrypted by a server only after a predesignated series of operations have been performed?

Meaning to say, that somehow, the operations themselves become infused with a public key, such that their precise alignment leads to their being able to be decrypted under a public key as a plaintext? CPA security must be maintained for every operation prior to a final operation.

Under the current paradigm, we are interested in CPA security, but what if we want to relax it to a differentially private security, that also has an element of verifiability, in the form of verifying the server has performed the correct operations? One reveals precisely the information one would like to reveal.

For instance, this would be of use to training a deep learning model entirely on the cloud based on data from multiple parties without the communication overhead associated with multiparty computation, as the gradients can be averaged, masked with a noise and then decrypted directly in the server. These gradients can be combined with gradients from other data sources and update a central learner.

该提问来源于开源项目：microsoft/SEAL

Answer 1

This is certainly an important point in the solution space for federated learning (see, for instance, http://papers.nips.cc/paper/7984-cpsgd-communication-efficient-and-differentially-private-distributed-sgd.pdf), where such a scheme would enable the training of very large models than what federated learning would presumably allow (due to naively, several GB per single weight update communication cost per user, though it seems efforts are into cutting down, I don't know the SOTA) from the encrypted data of many users.

The problem of course is that the server would have be holding N copies of keys in the server memory, or perform communication with disk. So it is more suited to the scenario when the number of users is still small, due to the need to store KSKs in memory.

If data is accumulated and processed in a batched fashion, this could still be of great use. Of course, the batches here would not be real minibatches, they are rather minibatches of clusters of data following their own distribution (corresponding to a single data provider). However, communication could naively still be better than in the federated learning case, since the communication of KSKs from disk to device memory could be favourable to that of gradients over internet.

KSK sizes go as l^2 in the levels due to depth. Gradient sizes go as l. So there should be a nice tradeoff in the middle. Hopefully this tradeoff would favour ksk sizes for the sizes of models we care about.