Paper 2008/184

On the Secure Obfuscation of Deterministic Finite Automata

W. Erik Anderson

Abstract

In this paper, we show how to construct secure obfuscation for Deterministic Finite Automata, assuming non-uniformly strong one-way functions exist. We revisit the software protection approaches originally proposed by [B79,G87,GO96,K80] and revise them to the current obfuscation setting of Barak et al. [BGI+01]. Under this model, we introduce an efficient oracle that retains some ``small" secret about the original program. Using this secret, we can construct an obfuscator and two-party protocol that securely obfuscates Deterministic Finite Automata against malicious adversaries. The security of this model retains the strong ``virtual black box" property originally proposed in [BGI+01] while incorporating the stronger condition of dependent auxiliary inputs in [GTK05]. Additionally, we further show that our techniques remain secure under concurrent self-composition with adaptive inputs and that Turing machines are obfuscatable under this model.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
Obfuscationdeterministic finite automatastate machinesTuring machinesauthenticated encryptionoracle machinesprovable securitygame-playing.
Contact author(s)
weander @ sandia gov
History
2008-06-02: last of 3 revisions
2008-04-24: received
See all versions
Short URL
https://ia.cr/2008/184
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/184,
      author = {W.  Erik Anderson},
      title = {On the Secure Obfuscation of Deterministic Finite Automata},
      howpublished = {Cryptology {ePrint} Archive, Paper 2008/184},
      year = {2008},
      url = {https://eprint.iacr.org/2008/184}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.