Once again this year I find myself back in sunny Cambridge; this time for another workshop consisting of a series of invited talks, followed of course by Eurocrypt next week. The second talk of the first day was by Vinod Vaikuntanathan, presenting a new work on Multikey Fully Homomorphic Encryption and its applications.
The application scenario is one of outsourcing computation, whilst preserving privacy of inputs. The standard way to achieve this in a single user setting is with FHE. However, when faced with a large pool of users who wish to compute a function on all their private inputs, FHE cannot be applied so easily.
They create a new primitive, called Multi-key Fully Homomorphic Encryption, to deal with this situation. Each client has a key pair (ski, pki), and there is a single high-powered server used to evaluate the desired function, f. When given some ciphertexts c1 = Enc(pk1, x1), ..., cn = Enc(pkn, xn), the server can compute y = Eval(f,c1,...,cn). The clients then perform an interactive decryption protocol to jointly recover f(x1,...,xn) = Dec(sk1,...,skn,y). It is stressed that this decryption phase is the only part of the process requiring interactivity. The number of clients and the function to be evaluated are completely dynamic and can be chosen on-the-fly. This is pretty much the best outcome we can hope for, as it was shown recently (HLP'11) that a completely non-interactive solution to the problem is impossible.
The construction itself is based on the NTRU cryptosystem. Specifically, they adapt a recent variant due to Stehle and Steinfeld (2011) that guarantees hardness based on worst-case problems in ideal lattices. With a minor adjustment to this scheme, the speaker explained how NTRU is in fact multi-key somewhat homomorphic. Those interested in the specifics should look at the paper, but I must say that the technique for transforming it in this way is surprisingly elegant: given two ciphertexts encrypted under different secret keys, they can simply be added or multiplied together, giving a new ciphertext decryptable under the product of the two keys. (Note that, regardless of whether you add or multiply the ciphertexts, the keys are always multiplied - the final decryption key is simply the product of all secret keys.)
Vinod used a nice "reservoir analogy" to explain how to deal with the increase of error terms after homomorphic operations. By adapting the modulus switching technique from previous FHE schemes, the reservoir level can be kept nicely under control for an a priori bounded depth of circuits. To achieve true (unbounded depth) FHE, they give a multi-key analogue of Gentry's bootstrapping theorem.
However, it must be mentioned that allowing homomorphic operations comes with an added cost: a random polynomial chosen during encryption has to be much smaller than the lower bound in the security proof of Stehle & Steinfeld. This introduces an additional assumption (on top of ring-LWE), namely that the quotient of two small polynomials is indistinguishable from uniform. For large enough polynomials this is actually statistically true, but the nature of the problem is very much open for the situation at hand.
Two other open issues with the scheme were mentioned: firstly, security is only guaranteed against honest-but-curious adversaries. It would be interesting to see how this could be extended to the malicious case. Secondly, the final ciphertext must be decrypted in 'layers', passed around for each client to unpeel one layer of encryption. It would be nicer to have a true threshold decryption to reduce communication overhead.
Overall, this is a groundbreaking work in both the fields of MPC and FHE. The flexibility of the resulting protocol seems to have good potential, and the construction of FHE from NTRU is also an exciting new result. NTRU is known for its efficiency, and although of course the fully homomorphic transformation incurs significant overhead, it will be interesting to see how it stacks up against the current state of the art.
It would be interesting to see how this could be extended to the malicious case. Secondly, the final ciphertext must be decrypted in 'layers', passed around for each client to unpeel one layer of encryption.
ReplyDeletePgp software
Given that FHE schemes are to evaluate public functions on encrypted data.
ReplyDeleteAny idea of FHE schemes can be used for hiding the function too ? for example if the user wants to run private programs on public/private inputs .
This is a property called function privacy which is addressed in a few FHE works. The idea is that the decryptor should not learn what function has been evaluated. A basic technique to achieve this would be to perform a form of re-randomization. But clearly this only works for FHE schemes, as all known SHE schemes leak the depth of the circuit via the noise within the partially decrypted ciphertext
ReplyDeleteActually, function privacy in FHE should define that the server that evaluates should not know the function itself . Imagine somebody wants to outsource their applications to Amazon web services (AWS) but don't want AWS to learn the operations from their binaries or jar files, the question was using FHE can this be achieved ? from what i understand from FHE literature is , only few specialized operations like encrypted polynomials can be done but not general functions . If general functions could be encrypted too then it would contradict the paper , "On the impossibility of obfuscating programs"
Delete