Obfuscating Finite Automata

Steven D.  Galbraith; Lukas Zobernig

Paper 2020/1009 Original: eprint.iacr.org/2020/1009 ↗

Obfuscating Finite Automata

Steven D. Galbraith

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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
History: 2020-10-04: last updated; 2020-08-22: published
Short URL: https://ia.cr/2020/1009
License: https://creativecommons.org/licenses/by/4.0/

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},
      url = {https://eprint.iacr.org/2020/1009}
}