CISPA
Browse
- No file added yet -

NTRU-ν-um: Secure Fully Homomorphic Encryption from NTRU with Small Modulus

Download (853.53 kB)
conference contribution
posted on 2023-11-29, 18:23 authored by Kamil Kluczniak
NTRUEncrypt is one of the first lattice-based encryption schemes. Furthermore, the earliest fully homomorphic encryption (FHE) schemes rely on the NTRU problem. Currently, NTRU is one of the leading candidates in the NIST post-quantum standardization competition. What makes NTRU appealing is the age of the cryptosystem and relatively good performance. Unfortunately, FHE based on NTRU became impractical due to efficient attacks on NTRU instantiations with ``overstretched'' modulus. In particular, currently, NTRU-based FHE schemes to support a reasonable circuit depth require instantiating NTRU with a very large modulus. Breaking the NTRU problem for such large moduli turns out to be easy. Due to these attacks, any serious work on practical NTRU-based FHE essentially stopped. In this paper, we reactivate research on practical FHE that can be based on NTRU. We design an efficient bootstrapping scheme in which the noise growth is small enough to keep the modulus to dimension ratio relatively small, thus avoiding the negative consequences of ``overstretching'' the modulus. Our bootstrapping algorithm is an accumulator-type bootstrapping scheme analogous to AP/FHEW/TFHE. Finally, we show that we can use the bootstrapping procedure to compute any function over $\mathbb{Z}_t$. Consequently, we obtain one of the fastest FHE bootstrapping schemes able to compute any function over elements of a finite field alongside reducing the error.

History

Preferred Citation

Kamil Kluczniak. NTRU-ν-um: Secure Fully Homomorphic Encryption from NTRU with Small Modulus. In: ACM Conference on Computer and Communications Security (CCS). 2022.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

ACM Conference on Computer and Communications Security (CCS)

Legacy Posted Date

2022-10-13

Open Access Type

  • Unknown

BibTeX

@inproceedings{cispa_all_3841, title = "NTRU-ν-um: Secure Fully Homomorphic Encryption from NTRU with Small Modulus", author = "Kluczniak, Kamil", booktitle="{ACM Conference on Computer and Communications Security (CCS)}", year="2022", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC