Jordan, S. (2013). Classical and quantum circuit obfuscation with braids. Perimeter Institute for Theoretical Physics. https://pirsa.org/13040111
MLA
Jordan, Stephen. Classical and quantum circuit obfuscation with braids. Perimeter Institute for Theoretical Physics, Apr. 08, 2013, https://pirsa.org/13040111
BibTex
@misc{ scivideos_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 for Theoretical Physics},
year = {2013},
month = {apr},
note = {PIRSA:13040111 see, \url{https://scivideos.org/pirsa/13040111}}
}
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.