The first afternoon session of day 2 was on homomorphic cryptography. There were three talks: the first was on fully homomorphic encryption, and the next two on the slightly lesser-known topics of homomorphic MACs and authenticated data structures. In this post I will talk about the first two talks, which captivated me the most.
Tancrède Lepoint gave the first talk, on integer-based fully homomorphic encryption, which was a merge of two papers. Much recent work on FHE has focussed on constructions based on ring-LWE, whilst Gentry's scheme and the integer-based DGHV variant are often ignored due to large parameter sizes. The talk aimed to bridge this gap and show that actually, the integer scheme can be competitive with ring-LWE. Following on from last year's Eurocrypt paper, which allowed for better 'noise control' using modulus switching, Tancrède described how batching techniques can be used to perform parallel homomorphic operations on ciphertexts. Batching allows multiple plaintexts to be 'packed' into a single ciphertext, so that when a homomorphic operation is performed on a ciphertext, it is applied to every plaintext element in parallel. These techniques were originally developed by Smart and Vercauteren, for plaintext spaces of polynomial rings, and it turns out that the CRT can similarly be used for the scheme over the integers. The use of batching makes a huge practical difference: previously a ciphertext of size 20 million bits could only encrypt a single bit; now the same-sized ciphertext can encrypt around 300 bits.
In addition to parallel operations, effective use of batching also requires the ability to permute plaintext elements within a single ciphertext. This is possible with ring-LWE based schemes because of their nice algebraic structure, however it seems more difficult over the integers. Instead, they take advantage of the bootstrapping step, which homomorphically decrypts a ciphertext, to perform a permutation. Using these techniques, they present an implementation of homomorphic AES that takes 12 minutes per block on average, compared with 5 minutes per block for the implementation from Crypto last year. This shows that integer-based FHE is still a viable option, although it is worth noting that the Crypto implementation did not use bootstrapping; it would be interesting to see if adding bootstrapping could put it much further ahead or not.
The second talk of the session was given by Dario Catalano, on homomorphic MACs for arithmetic circuits. In the scenario of delegating computation to a server, it is often important to be able to verify that the computation was carried out on the correct data, which was previously authenticated by the client. Using homomorphic MACs allows the client to verify the server's output, with respect to the function computed and the original, authenticated inputs. The key element is a mechanism whereby anyone can take a set of MAC'd messages and compute a MAC valid for the output of any function of the messages. Previous work in this area was only homomorphic for linear functions, or required the use of FHE, which is undesirable. Their construction allows homomorphism for polynomially sized circuits, is secure based only on the existence of PRFs, and is very efficient to compute the MACs. However, the complexity of verification grows with the degree of the circuit, which seems unfortunate, especially for the application of outsourced computation. Another open problem Dario mentioned was to construct a fully homomorphic MAC, for circuits of arbitrary size.
No comments:
Post a Comment