Cryptology ePrint Archive: Report 2019/176
Homomorphic Encryption for Finite Automata
Nicholas Genise and Craig Gentry and Shai Halevi and Baiyu Li and Daniele Micciancio
Abstract: 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.
Category / Keywords: secret-key cryptography / Finite Automata, Inhomogeneous NTRU, Homomorphic Encryption, Regular Expressions.
Original Publication (with minor differences): IACR-ASIACRYPT-2019
Date: received 18 Feb 2019, last revised 12 Sep 2019
Contact author: nicholasgenise at gmail com
Available format(s): PDF | BibTeX Citation
Version: 20190912:192859 (All versions of this report)
Short URL: ia.cr/2019/176
[ Cryptology ePrint archive ]