Cryptology ePrint Archive: Report 2016/1019

Faster Homomorphic Evaluation of Discrete Fourier Transforms

Anamaria Costache and Nigel P. Smart and Srinivas Vivek

Abstract: We present a methodology to achieve low latency homomorphic operations on approximations to complex numbers, by encoding a complex number as an evaluation of a polynomial at a root of unity. We then use this encoding to evaluate a Discrete Fourier Transform (DFT) on data which has been encrypted using a Somewhat Homomorphic Encryption (SHE) scheme, with up to three orders of magnitude improvement in latency over previous methods. We are also able to deal with much larger input sizes than previous methods. Due to the fact that the entire DFT algorithm is an algebraic operation over the underlying ring of the SHE scheme (for a suitably chosen ring), our method for the DFT utilizes exact arithmetic over the complex numbers, as opposed to approximations.

Category / Keywords: public-key cryptography / FHE

Original Publication (in the same form): Financial Cryptology 2017

Date: received 26 Oct 2016, last revised 1 Feb 2017

Contact author: anamaria costache at bristol ac uk,nigel@cs bris ac uk,sv venkatesh@bristol ac uk

Available format(s): PDF | BibTeX Citation

Version: 20170201:084213 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]