E-mail senden E-Mail Adresse kopieren
2026-11-10

On Composing Oracle Separations

Zusammenfassung

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 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 P1⇏BBQ$$\mathcal {P}_1 {\mathop {\nRightarrow }\limits ^{BB}} \mathcal {Q}$$ and P2⇏BBQ$$\mathcal {P}_2 {\mathop {\nRightarrow }\limits ^{BB}} \mathcal {Q}$$ satisfy our conditions, then Q$$\mathcal {Q}$$ is also separated from black-box combinations of P1$$\mathcal {P}_1$$ and P2$$\mathcal {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$$\textsf{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).

Konferenzbeitrag

Theory of Cryptography Conference (TCC)

Veröffentlichungsdatum

2026-11-10

Letztes Änderungsdatum

2026-11-17