Paper 2015/793

Algorithmic Information Theory for Obfuscation Security

Rabih Mohsen and Alexandre Miranda Pinto

Abstract

The main problem in designing effective code obfuscation is to guarantee security. State of the art obfuscation techniques rely on an unproven concept of security, and therefore are not regarded as provably secure. In this paper, we undertake a theoretical investigation of code obfuscation security based on Kolmogorov complexity and algorithmic mutual information. We introduce a new definition of code obfuscation that requires the algorithmic mutual information between a code and its obfuscated version to be minimal, allowing for controlled amount of information to be leaked to an adversary. We argue that our definition avoids the impossibility results of Barak et al. and is more advantageous then obfuscation indistinguishability definition in the sense it is more intuitive, and is algorithmic rather than probabilistic.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. International Conference on Security and Cryptography (SECRYPT 2015)
DOI
10.5220/0005548200760087
Keywords
Code ObfuscationKolmogorov ComplexityIntellectual Property Protection
Contact author(s)
r mohsen11 @ imperial ac uk
History
2015-08-10: received
Short URL
https://ia.cr/2015/793
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/793,
      author = {Rabih Mohsen and Alexandre Miranda Pinto},
      title = {Algorithmic Information Theory for Obfuscation Security},
      howpublished = {Cryptology ePrint Archive, Paper 2015/793},
      year = {2015},
      doi = {10.5220/0005548200760087},
      note = {\url{https://eprint.iacr.org/2015/793}},
      url = {https://eprint.iacr.org/2015/793}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.