COSIC seminar 'On the Arithmetic Challenges of FHE' (Paulo Sergio Alves Martins)

COSIC seminar – On the Arithmetic Challenges of FHE – Paulo Sergio Alves Martins (Technical University of Lisbon)

Fully Homomorphic Encryption (FHE) is one of the major advances in computer science of the 21st century. Associated with its discovery, major arithmetic challenges have been raised. Firstly, FHE relies on primitives different from those of number-theoretic cryptography, which the cryptographic community hasn’t yet investigated in depth. Secondly, the users of such systems need to map their applications onto operations over cyclotomic rings, a process that differs from traditional programming. Thirdly, while FHE offers the secrecy of data, one might also need to protect the confidentiality of the processing algorithm. In this talk, these topics will be addressed one by one. A novel method to represent ciphertexts is proposed, reducing the complexity of the homomorphic multiplication of Fan-Vercauteren (FV) from O(n^3 log n) to O(n^3). It is furthermore argued that stochastic computing provides for a natural way to map real inputs onto the batching slots of FHE. Finally, an automatic and methodical approach to approximate a wide range of functions homomorphically is proposed, while providing for algorithm secrecy efficiently.