Tuesday, January 8, 2013
3:00 pm
Annenberg 107

Institute for Quantum Information Seminar

Partial-indistinguishability obfuscation using braids
Stephen Jordan, NIST

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 exist, 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. A variant of our obfuscation algorithm can also be applied to quantum circuits.

Contact Ann Harvey aharvey@caltech.edu at 626-395-4964
Add this event to my calendar