PIRSA:13040111

Classical and quantum circuit obfuscation with braids

Jordan, S. (2013). Classical and quantum circuit obfuscation with braids. Perimeter Institute. https://pirsa.org/13040111

Jordan, Stephen. Classical and quantum circuit obfuscation with braids. Perimeter Institute, Apr. 08, 2013, https://pirsa.org/13040111 

          @misc{ pirsa_PIRSA:13040111,
            doi = {10.48660/13040111},
            url = {https://pirsa.org/13040111},
            author = {Jordan, Stephen},
            keywords = {Quantum Foundations},
            language = {en},
            title = {Classical and quantum circuit obfuscation with braids},
            publisher = {Perimeter Institute},
            year = {2013},
            month = {apr},
            note = {PIRSA:13040111 see, \url{https://pirsa.org}}
          }

Stephen Jordan National Institute of Standards & Technology

DOI 10.48660/13040111
Collection
Talk Type Scientific Series
Subject

Abstract

A circuit obfuscator is an algorithm that translates logic circuits into functionally-equivalent similarly-sized logic circuits that are hard to understand. While ad hoc obfuscators have been implemented, theoretical progress has mainly been limited to no-go results. In this work, we propose a new notion of circuit obfuscation, which we call partial indistinguishability. We then prove that, in contrast to previous definitions of obfuscation, partial indistinguishability obfuscation can be achieved by a polynomial-time algorithm. Specifically, our algorithm re-compiles the given circuit using a gate that satisfies the relations of the braid group, and then reduces to a braid normal form. Variants of our obfuscation algorithm can be applied to both classical and quantum circuits.