On Composing Oracle Separations

Willy Quach; Felix Rohrbach

Paper 2026/2845

On Composing Oracle Separations

Willy Quach

, Helmholtz Center for Information Security

Felix Rohrbach

, Helmholtz Center for Information Security

Abstract

Black-box separations constitute very powerful technical barriers against constructing primitives from specific building blocks. However, they give surprisingly little indication on the usefulness of \emph{combining} several such building blocks in a single construction. We propose a set of technical conditions, under which (fully) black-box separations compose with each other. That is, if two black-box separations $P_1 \stackrel{BB}{\nRightarrow} Q$ and $P_2 \stackrel{BB}{\nRightarrow} Q$ satisfy our conditions, then $Q$ is also separated from black-box combinations of $P_1$ and $P_2$. When applicable, these conditions can be established without unpacking the full technical details of the base separations. As our main application, we show that combining indistinguishability obfuscation (iO) with collision resistant hash functions is unlikely to yield hard problems in the complexity class $SZK$, and thus unlikely to suffice for primitives such as lossy functions or fully homomorphic encryption. Previous lower bounds on iO only applied to combinations of iO with one-way permutations (Asharov-Segev, FOCS '15 and Bitansky-Degwekar-Vaikuntanathan, SIAM Journal on Computing '21).

Metadata

Available format(s): PDF
Category: Foundations
Publication info: A minor revision of an IACR publication in TCC 2026
DOI: https://doi.org/10.1007/978-3-032-43617-7_13
Keywords: oracle separations black-box separations composability
Contact author(s): willy quach @ cispa de
felix rohrbach @ cispa de
History: 2026-11-11: approved; 2026-11-09: received; See all versions
Short URL: https://ia.cr/2026/2845
License: CC BY

BibTeX

@misc{cryptoeprint:2026/2845,
      author = {Willy Quach and Felix Rohrbach},
      title = {On Composing Oracle Separations},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2845},
      year = {2026},
      doi = {https://doi.org/10.1007/978-3-032-43617-7_13},
      url = {https://eprint.iacr.org/2026/2845}
}