2015 | OriginalPaper | Buchkapitel
Obfuscation of Probabilistic Circuits and Applications
verfasst von : Ran Canetti, Huijia Lin, Stefano Tessaro, Vinod Vaikuntanathan
Erschienen in: Theory of Cryptography
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
This paper studies the question of how to define, construct, and use obfuscators for
probabilistic programs
. Such obfuscators compile a possibly randomized program into a
deterministic
one, which achieves computationally indistinguishable behavior from the original program as long as it is run on each input at most once. For obfuscation, we propose a notion that extends
indistinguishability obfuscation
to probabilistic circuits: It should be hard to distinguish between the obfuscations of any two circuits whose output distributions at each input are computationally indistinguishable, possibly in presence of some auxiliary input. We call the resulting notion
probabilistic indistinguishability obfuscation (
pIO
).
We define several variants of
pIO
, and study relations among them. Moreover, we give a construction of one of our variants, called
X
-
pIO
, from sub-exponentially hard indistinguishability obfuscation (for deterministic circuits) and one-way functions.
We then move on to show a number of applications of
pIO
. In particular, we first give a general and natural methodology to achieve fully homomorphic encryption (FHE) from variants of
pIO
and of semantically secure encryption schemes. In particular, one instantiation leads to FHE from any
X
-
pIO
obfuscator and any re-randomizable encryption scheme that’s slightly super-polynomially secure.
We note that this constitutes the first construction of full-fledged FHE that does not rely on encryption with circular security.
Moreover, assuming sub-exponentially secure puncturable PRFs computable in
NC
1
, sub-exponentially-secure indistinguishability obfuscation for (deterministic)
NC
1
circuits can be bootstrapped to obtain indistinguishability obfuscation for arbitrary (deterministic) poly-size circuits (previously such bootstrapping was known only assuming FHE with
NC
1
decryption algorithm).