Multiparty computation and the hallucinated server

Vision

In the Programmable Cryptography blog post we described the idea of a hallucinated server: that is, a simulated virtual server which no one person can access. To recap, right now, if a group of friends wanted to set up a forum, they might do something like rent a cloud server (e.g. AWS) to run their site. But then this trusts the hosting service to not look at the website’s data. In contrast, a hallucinated server would instead be distributed among the network participants themselves in such a way that no one user has access to data they shouldn’t see.

Mathematical toolbox

The math that makes this idea possible comes from the ideas of multi-party computation (MPC) and fully homomorphic encryption (FHE). The Three Easy Pieces novella covers a blueprint of some traditional constructions for this, but to give a brief advertisement for each:

• MPC allows people to collaboratively evaluate a program on individually secret inputs and learn only the common output.
• FHE makes it possible to run programs on encrypted inputs, such that the output can only be read by the provider of the encrypted input.

Research priorities

At 0xPARC, we’re less interested in traditional MPC (garbled circuits, Shamir secret sharing, and so on) because the communication cost of these techniques is too high. Since these costs scale quadratically in the number of network participants, scaling to a large network would be impossible.

Instead, we’re exploring what we can do when we combine multiparty ideas with fully homomorphic encryption.

• How can a secure computation (running inside FHE or MPC) perform memory access efficiently? The direct approach requires a linear scan of memory for each read and write access, which is too inefficient for a stateful server.

  How can we build a system that performs efficient secure computation with memory access? We require time complexity sublinear in the size of the memory: memory accesses must be faster than simple linear scan. We want to optimize along the following parameters:

  • Computational overhead.
    How much time does the system require to perform a secure computation, compared to running it natively on a server or CPU? For example, traditional approaches to multiparty computation might incur a 1000x overhead; for fully homomorhic encryption, the factor is in the high millions.
  • Rounds of communication. How many rounds of communication does a computation require? At the high end, MPC protocols based on secret sharing need one round per gate, so that the total communication complexity is proportional to the depth of the circuit. At the opposite extreme, noninteractive multiparty FHE can perform a full computation in just two rounds, one “encryption” round at the beginning, and one “decryption” round at the end. (But at the moment we do not know how to perform sublinear memory access in noninteractive multiparty FHE.)
  • Communication bandwidth. How much data must be exchanged between parties? Multiparty FHE is expensive along this axis as well: key sizes range in the hundreds of gigabytes.

• How can we optimize multiparty FHE?

  For example: Can we build an FHE scheme that is robust to some number of parties entering and leaving in the middle of the computation?

  We know how to do this with secret sharing-based threshold schemes: Using polynomials, we can share a secret among $n$ parties, so that any $k$ of them can recover the secret. Furthermore, there are protocols to “re-share” a shared secret, to change the threshold from $k$ to some other value $k'$. So if some of the original $n$ parties go offline, the remaining parties can agree to “re-share” the secret with a smaller threshold $k'$, making the scheme robust.

  Can we do something similar for multiparty FHE?

• Are there other useful “gadgets” for FHE?

  In zero-knowledge proofs, a handful of higher-level “gadgets” (sumcheck, lookup arguments, …) turn out to be useful in practice. Are there similar devices in FHE?

  One promising approach is blind rotation, which uses polynomial multiplication to “look up values in a table”: Given an LWE encryption of some value $a$, blind rotation allows you to extract the $x^a$ coefficient of any polynomial, again in LWE encryption. Due to error growth and the high cost of computing on polynomials, blind rotation is most useful for lookup tables of small size (e.g. 4).

  Can we build efficient lookup tables of size $2^8$ or $2^{16}$? (This is equivalent to read-only memory, where we require that the memory accesses be secret, but the contents of the memory can be public.)

• Can we build efficient verifiable FHE?

  We want all parties in an FHE computation to be able to verify that the computation was done honestly. One naive approach is to require the FHE server to provide a succinct ZK proof of the full FHE computation. The computational cost of this approach makes it completely impractical. How can we make it more efficient?

As a longer-term goal: How far can we bring down the computational overhead?

• Can we find an FHE scheme based on something other than lattices?
• Can we find an efficient alternative to bootstrapping?