New Counterexamples to Sequential Composition Adaptive Insecurity
Liqing Yu · IEEE Access · 2025
At CRYPTO 2005, Pietrzak demonstrated an intriguing result: the sequential composition of two non-adaptively secure pseudorandom functions does not necessarily imply adaptive security, assuming the decisional Diffie-Hellman (DDH) assumption holds. To support this claim, they constructed a cleverly designed counterexample consisting of two functions,$\textsf {F}$and$\textsf {G}$. While both$\textsf {F}$and$\textsf {G}$are non-adaptively secure, their sequential composition$\textsf {G} \circ \textsf {F}$fails to achieve adaptive security. Such a counterexample is highly non-trivial, requiring sophisticated designs and a deep understanding of the distinctions between non-adaptive and adaptive security. In this work, we show that such well-crafted counterexample is not unique by presenting two novel counterexamples derived from entirely different intuitions. These new constructions imply that there may be potential systematic approaches to designing such counterexamples, providing new insights into the relationship between non-adaptive and adaptive security.