Efficient AGCD-based homomorphic encryption for matrix and vector arithmetic

Hilder Vitor Lima Pereira

Paper 2020/491

Efficient AGCD-based homomorphic encryption for matrix and vector arithmetic

Hilder Vitor Lima Pereira

Abstract

We propose a leveled homomorphic encryption scheme based on the Approximate Greatest Common Divisor (AGCD) problem that operates natively on vectors and matrices. To overcome the limitation of large ciphertext expansion that is typical in AGCD-based schemes, we randomize the ciphertexts with a hidden matrix, which allows us to choose smaller parameters. To be able to efficiently evaluate circuits with large multiplicative depth, we use a decomposition technique à la GSW. The running times and ciphertext sizes are practical: for instance, for 100 bits of security, we can perform a sequence of 128 homomorphic products between 128-dimensional vectors and matrices in less than one second. We show how to use our scheme to homomorphically evaluate nondeterministic finite automata and also a Naïve Bayes Classifier. We also present a generalization of the GCD attacks against the some variants of the AGCD problem.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Major revision. 18th International Conference on Applied Cryptography and Network Security (ACNS 2020)
Keywords: Homomorphic Encryption AGCD Naïve Bayes Classifier Nondeterministic finite automata.
Contact author(s): hilder vitor @ gmail com
History: 2020-04-28: received
Short URL: https://ia.cr/2020/491
License: CC BY

BibTeX

@misc{cryptoeprint:2020/491,
      author = {Hilder Vitor Lima Pereira},
      title = {Efficient {AGCD}-based homomorphic encryption for matrix and vector arithmetic},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/491},
      year = {2020},
      url = {https://eprint.iacr.org/2020/491}
}