1 Search Results for "Meyer, Pierre"

Document
DOI: 10.4230/LIPIcs.ITCS.2023.23
On Low-End Obfuscation and Learning

Authors: Elette Boyle, Yuval Ishai, Pierre Meyer, Robert Robere, and Gal Yehuda

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
Most recent works on cryptographic obfuscation focus on the high-end regime of obfuscating general circuits while guaranteeing computational indistinguishability between functionally equivalent circuits. Motivated by the goals of simplicity and efficiency, we initiate a systematic study of "low-end" obfuscation, focusing on simpler representation models and information-theoretic notions of security. We obtain the following results. - Positive results via "white-box" learning. We present a general technique for obtaining perfect indistinguishability obfuscation from exact learning algorithms that are given restricted access to the representation of the input function. We demonstrate the usefulness of this approach by obtaining simple obfuscation for decision trees and multilinear read-k arithmetic formulas. - Negative results via PAC learning. A proper obfuscation scheme obfuscates programs from a class C by programs from the same class. Assuming the existence of one-way functions, we show that there is no proper indistinguishability obfuscation scheme for k-CNF formulas for any constant k ≥ 3; in fact, even obfuscating 3-CNF by k-CNF is impossible. This result applies even to computationally secure obfuscation, and makes an unexpected use of PAC learning in the context of negative results for obfuscation. - Separations. We study the relations between different information-theoretic notions of indistinguishability obfuscation, giving cryptographic evidence for separations between them.
Cite as

Elette Boyle, Yuval Ishai, Pierre Meyer, Robert Robere, and Gal Yehuda. On Low-End Obfuscation and Learning. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 23:1-23:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{boyle_et_al:LIPIcs.ITCS.2023.23,
  author =	{Boyle, Elette and Ishai, Yuval and Meyer, Pierre and Robere, Robert and Yehuda, Gal},
  title =	{{On Low-End Obfuscation and Learning}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{23:1--23:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.23},
  URN =		{urn:nbn:de:0030-drops-175265},
  doi =		{10.4230/LIPIcs.ITCS.2023.23},
  annote =	{Keywords: Indistinguishability obfuscation, cryptography, learning}
}
  • Refine by Author
  • 1 Boyle, Elette
  • 1 Ishai, Yuval
  • 1 Meyer, Pierre
  • 1 Robere, Robert
  • 1 Yehuda, Gal

  • Refine by Classification
  • 1 Theory of computation → Cryptographic primitives

  • Refine by Keyword
  • 1 Indistinguishability obfuscation
  • 1 cryptography
  • 1 learning

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact