Paper 2013/500

Obfuscating Branching Programs Using Black-Box Pseudo-Free Groups

Ran Canetti and Vinod Vaikuntanathan

Abstract

We show that the class of polynomial-size branching programs can be obfuscated according to a virtual black-box notion akin to that of Barak et al. [Crypto 01], in an idealized black-box group model over pseudo-free groups. This class is known to lie between $NC^1$ and $P$ and includes most interesting cryptographic algorithms. The construction is rather simple and is based on Kilian's randomization technique for Barrington's branching programs. The black-box group model over pseudo-free groups is a strong idealization. In particular, in a pseudo-free group, the group operation can be efficiently performed, while finding surprising relations between group elements is intractable. %inverses or linking between different representations of the same group element are infeasible. A black-box representation of the group provides an ideal interface which permits prescribed group operations, and nothing else. Still, the algebraic structure and security requirements appear natural and potentially realizable. They are also unrelated to the specific function to be obfuscated. Our modeling should be compared with the recent breakthrough obfuscation scheme of Garg et al. [FOCS 2013]: While the high level structure is similar, some important details differ. It should be stressed however that, unlike Garg et al., we do not provide a candidate concrete instantiation of our abstract structure.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. Minor revision.
Keywords
Obfuscationgeneric group modelpseudo-free groups
Contact author(s)
canetti @ bu edu
History
2013-08-15: received
Short URL
https://ia.cr/2013/500
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/500,
      author = {Ran Canetti and Vinod Vaikuntanathan},
      title = {Obfuscating Branching Programs Using Black-Box Pseudo-Free Groups},
      howpublished = {Cryptology ePrint Archive, Paper 2013/500},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/500}},
      url = {https://eprint.iacr.org/2013/500}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.