1. Faster Homomorphic Evaluation of Discrete Fourier Transforms 2017 FHE FinancialCryptography Privacy
    Anamaria Costache, Nigel P. Smart, Srinivas Vivek
    [View PDF on fc17.ifca.ai]
    [Show BibTex Citation]

    author = {Anamaria Costache and
    Nigel P. Smart and
    Srinivas Vivek},
    editor = {Aggelos Kiayias},
    title = {Faster Homomorphic Evaluation of Discrete Fourier Transforms},
    booktitle = {Financial Cryptography and Data Security - 21st International Conference,
    {FC} 2017, Sliema, Malta, April 3-7, 2017, Revised Selected Papers},
    series = {Lecture Notes in Computer Science},
    volume = {10322},
    pages = {517--529},
    publisher = {Springer},
    year = {2017},
    url = {https://doi.org/10.1007/978-3-319-70972-7\_29},
    doi = {10.1007/978-3-319-70972-7\_29},
    timestamp = {Tue, 14 May 2019 10:00:38 +0200},
    biburl = {https://dblp.org/rec/bib/conf/fc/CostacheSV17},
    bibsource = {dblp computer science bibliography, https://dblp.org}

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.