Cryptology ePrint Archive: Report 2020/1009

Obfuscating Finite Automata

Steven D. Galbraith and Lukas Zobernig

Abstract: We construct a VBB and perfect circuit-hiding obfuscator for evasive deterministic finite automata using a matrix encoding scheme with a limited zero-testing algorithm. We construct the matrix encoding scheme by extending an existing matrix FHE scheme. Using obfuscated DFAs we can for example evaluate secret regular expressions or disjunctive normal forms on public inputs. In particular, the possibility of evaluating regular expressions solves the open problem of obfuscated substring matching.

Category / Keywords: public-key cryptography / Obfuscation, DFA, VBB, Circuit-Hiding

Original Publication (in the same form): Selected Areas in Cryptography 2020

Date: received 20 Aug 2020, last revised 4 Oct 2020

Contact author: s galbraith at auckland ac nz, lukas zobernig@auckland ac nz

Available format(s): PDF | BibTeX Citation

Note: Updated paper.

Version: 20201004:211234 (All versions of this report)

Short URL: ia.cr/2020/1009


[ Cryptology ePrint archive ]