License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TQC.2014.141
URN: urn:nbn:de:0030-drops-48135
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4813/
Go to the corresponding LIPIcs Volume Portal

Alagic, Gorjan ; Jeffery, Stacey ; Jordan, Stephen

Circuit Obfuscation Using Braids

pdf-format:
13.pdf (0.7 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{alagic_et_al:LIPIcs:2014:4813,
  author =	{Gorjan Alagic and Stacey Jeffery and Stephen Jordan},
  title =	{{Circuit Obfuscation Using Braids}},
  booktitle =	{9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)},
  pages =	{141--160},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-73-6},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{27},
  editor =	{Steven T. Flammia and Aram W. Harrow},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4813},
  URN =		{urn:nbn:de:0030-drops-48135},
  doi =		{10.4230/LIPIcs.TQC.2014.141},
  annote =	{Keywords: obfuscation, cryptography, universality, quantum}
}

Keywords: obfuscation, cryptography, universality, quantum
Collection: 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)
Issue Date: 2014
Date of publication: 11.12.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI