On the equivalence of uniform key agreement and sequential composition insecurity

This work revisits the relationship between the existence of uniform transcript key agreements (UTKA) and the statement that the sequential composition of two general non-adaptively secure pseudorandom functions (na PRFs) must be a pseudorandom function (PRF).Pietrzak (Crypto'06) showed that if the statement is false (i.e., there exists two na PRFs whose sequential composition is not a PRF), then a key agreement (KA) exists. This result is significant, since it reveals a surprising connection between a security property in symmetric-key cryptography and the existence of a public-key primitive. Later, Cho, Lee and Ostrovsky (Crypto'10) pointed out that the KA constructed by Pietrzak was in fact a UTKA, and established the equivalence between the existence of UTKAs and the falsification of the above statement. In particular, they proved the reverse direction of Pietrzak's result: if UTKAs exist, then a counterexample to sequential composition exists. Furthermore, Cho et al. also proved a similar equivalence of UTKA and parallel composition insecurity.Unfortunately, we found that Cho et al.'s counterexample to sequential composition from UTKAs was not correct, since the primitive functions in it were not actually na PRFs (more specifically, part of their output only depends on part of their input). Our view is that the failure may be inherent. In particular, we provide strong evidence that it is impossible to construct a counterexample to sequential composition from UTKAs.