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