01518nas a2200133 4500008004100000245005800041210005700099260001500156520111500171100001901286700002001305700002401325856003501349 2014 eng d00aPartial-indistinguishability obfuscation using braids0 aPartialindistinguishability obfuscation using braids c2014/08/213 a
An obfuscator is an algorithm that translates circuits into functionally-equivalent similarly-sized circuits that are hard to understand. Efficient obfuscators would have many applications in cryptography. Until recently, theoretical progress has mainly been limited to no-go results. Recent works have proposed the first efficient obfuscation algorithms for classical logic circuits, based on a notion of indistinguishability against polynomial-time adversaries. In this work, we propose a new notion of obfuscation, which we call partial-indistinguishability. This notion is based on computationally universal groups with efficiently computable normal forms, and appears to be incomparable with existing definitions. We describe universal gate sets for both classical and quantum computation, in which our definition of obfuscation can be met by polynomial-time algorithms. We also discuss some potential applications to testing quantum computers. We stress that the cryptographic security of these obfuscators, especially when composed with translation from other gate sets, remains an open question.
1 aAlagic, Gorjan1 aJeffery, Stacey1 aJordan, Stephen, P. uhttp://arxiv.org/abs/1212.6358