Paper 2016/1019

Faster Homomorphic Evaluation of Discrete Fourier Transforms

Anamaria Costache, 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Financial Cryptology 2017
Keywords
FHE
Contact author(s)
anamaria costache @ bristol ac uk
nigel @ cs bris ac uk
sv venkatesh @ bristol ac uk
History
2017-02-01: revised
2016-10-27: received
See all versions
Short URL
https://ia.cr/2016/1019
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1019,
      author = {Anamaria Costache and Nigel P.  Smart and Srinivas Vivek},
      title = {Faster Homomorphic Evaluation of Discrete Fourier Transforms},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1019},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1019}},
      url = {https://eprint.iacr.org/2016/1019}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.