Skip to content

Faster Homomorphic Evaluation of Discrete Fourier Transforms

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Original languageEnglish
Title of host publicationFinancial Cryptography and Data Security
Subtitle of host publication21st International Conference, FC 2017, Sliema, Malta, April 3-7, 2017, Revised Selected Papers
Publisher or commissioning bodySpringer, Cham
Pages517-529
Number of pages13
ISBN (Electronic)9783319709727
ISBN (Print)9783319709710
DOIs
DateAccepted/In press - 31 Jan 2017
DatePublished (current) - 23 Dec 2017

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume10322
ISSN (Print)0302-9743

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.

Documents

Links

DOI

View research connections

Related faculties, schools or groups