Obfuscating Finite Automata

Steven D.  Galbraith; Lukas Zobernig

Paper 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.

Note: Updated paper.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Selected Areas in Cryptography 2020
Keywords: Obfuscation DFA VBB Circuit-Hiding
Contact author(s): s galbraith @ auckland ac nz
lukas zobernig @ auckland ac nz
History: 2020-10-04: revised; 2020-08-22: received; See all versions
Short URL: https://ia.cr/2020/1009
License: CC BY

BibTeX

@misc{cryptoeprint:2020/1009,
      author = {Steven D.  Galbraith and Lukas Zobernig},
      title = {Obfuscating Finite Automata},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1009},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1009}},
      url = {https://eprint.iacr.org/2020/1009}
}