Classical and quantum circuit obfuscation with braids

Playing this video requires the latest flash player from Adobe.

Download link (right click and 'save-as') for playing in VLC or other f4v compatible player.

Recording Details

Scientific Areas: 
PIRSA Number: 


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.