Paper 2019/176

Homomorphic Encryption for Finite Automata

Nicholas Genise, Craig Gentry, Shai Halevi, Baiyu Li, and Daniele Micciancio


We describe a somewhat homomorphic GSW-like encryption scheme, natively encrypting matrices rather than just single elements. This scheme offers much better performance than existing homomorphic encryption schemes for evaluating encrypted (nondeterministic) finite automata (NFAs). Differently from GSW, we do not know how to reduce the security of this scheme to LWE, instead we reduce it to a stronger assumption, that can be thought of as an inhomogeneous variant of the NTRU assumption. This assumption (that we term iNTRU) may be useful and interesting in its own right, and we examine a few of its properties. We also examine methods to encode regular expressions as NFAs, and in particular explore a new optimization problem, motivated by our application to encrypted NFA evaluation. In this problem, we seek to minimize the number of states in an NFA for a given expression, subject to the constraint on the ambiguity of the NFA.

Available format(s)
Secret-key cryptography
Publication info
A minor revision of an IACR publication in Asiacrypt 2019
Finite AutomataInhomogeneous NTRUHomomorphic EncryptionRegular Expressions.
Contact author(s)
nicholasgenise @ gmail com
2020-03-16: last of 2 revisions
2019-02-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nicholas Genise and Craig Gentry and Shai Halevi and Baiyu Li and Daniele Micciancio},
      title = {Homomorphic Encryption for Finite Automata},
      howpublished = {Cryptology ePrint Archive, Paper 2019/176},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.