It is well known that proving the security of a key agreement protocol (even in a special case where the protocol transcript looks random to an outside observer) implies the existence of one-way functions and therefore is at least as difficult as proving $P \not = NP$. Another (seemingly unrelated) statement in cryptography is the existence of two or more non-adaptively secure pseudo-random functions that do not become adaptively secure under sequential or parallel composition. Pietrzak (Eurocrypt'06) showed that {\em at least one} of these two seemingly unrelated statements is true. Pietrzak's result was significant since it showed a surprising connection between the worlds of public-key (i.e., ``cryptomania") and private-key cryptography (i.e., ``minicrypt").

In this work, we further examine the relationship between the security of compositions of non-adaptively secure pseudo-random functions and other public key systems.

First, for the parallel composition case, we prove that the above duality is far stronger: {\em at least one} of these two statements must also be false. In other words, we show their {\em equivalence}. More specifically, we show that if there exists {\em any} uniform-transcript key agreement (UTKA) protocol, then parallel composition does not imply adaptive security. This implication holds based on virtually all known key agreement protocols and can also be based on general complexity assumptions such as the existence of dense trapdoor permutations.

Second, we prove the impossibility of adaptive security from sequential compositions assuming the existence of public key encryption scheme which is uniform and rerandomizable under both ciphertexts and public keys. It remains open if this stronger black-box assumption is also necessary.

This revision includes a retraction of theorems 4 and 5 and a new theorem 9. See the acknowledgments at the end of this paper for details. The original abstract appeared in CRYPTO 2010.

We prove that achieving adaptive security from composing two general non-adaptively secure pseudo-random functions is impossible if and only if a uniform-transcript key agreement protocol exists.

It is well known that proving the security of a key agreement protocol (even in a special case where the protocol transcript looks random to an outside observer) is at least as difficult as proving $P \not = NP$. Another (seemingly unrelated) statement in cryptography is the existence of two or more non-adaptively secure pseudo-random functions that do not become adaptively secure under sequential or parallel composition. In 2006, Pietrzak showed that {\em at least one} of these two seemingly unrelated statements is true. Pietrzak's result was significant since it showed a surprising connection between the worlds of public-key (i.e., ``cryptomania") and private-key cryptography (i.e., ``minicrypt"). In this paper we show that this duality is far stronger: we show that {\em at least one} of these two statements must also be false. In other words, we show their {\em equivalence}.

More specifically, Pietrzak's paper shows that if sequential composition of two non-adaptively secure pseudo-random functions is not adaptively secure, then there exists a key agreement protocol. However, Pietrzak's construction implies a slightly stronger fact: If sequential composition does not imply adaptive security (in the above sense), then a {\em uniform-transcript} key agreement protocol exists, where by uniform-transcript we mean a key agreement protocol where the transcript of the protocol execution is indistinguishable from uniform to eavesdroppers. In this paper, we complete the picture, and show the reverse direction as well as a strong equivalence between these two notions. More specifically, as our main result, we show that if there exists {\em any} uniform-transcript key agreement protocol, then composition does not imply adaptive security. Our result holds for both parallel and sequential composition. Our implication holds based on virtually all known key agreement protocols, and can also be based on general complexity assumptions of the existence of dense trapdoor permutations.

Fixed Typos, Clarified Intuitions and Proofs.

It is well known that proving the security of a key agreement protocol (even in a special case where the protocol transcript looks random to an outside observer) is at least as difficult as proving $P \not = NP$. Another (seemingly unrelated) statement in cryptography is the existence of two or more non-adaptively secure pseudo-random functions that do not become adaptively secure under sequential or parallel composition. In 2006, Pietrzak showed that {\em at least one} of these two seemingly unrelated statements is true. Pietrzak's result was significant since it showed a surprising connection between the worlds of public-key (i.e., ``cryptomania") and private-key cryptography (i.e., ``minicrypt"). In this paper we show that this duality is far stronger: we show that {\em at least one} of these two statements must also be false. In other words, we show their {\em equivalence}.

More specifically, Pietrzak's paper shows that if sequential composition of two non-adaptively secure pseudo-random functions is not adaptively secure, then there exists a key agreement protocol. However, Pietrzak's construction implies a slightly stronger fact: If sequential composition does not imply adaptive security (in the above sense), then a {\em uniform-transcript} key agreement protocol exists, where by uniform-transcript we mean a key agreement protocol where the transcript of the protocol execution is indistinguishable from uniform to eavesdroppers. In this paper, we complete the picture, and show the reverse direction as well as a strong equivalence between these two notions. More specifically, as our main result, we show that if there exists {\em any} uniform-transcript key agreement protocol, then composition does not imply adaptive security. Our result holds for both parallel and sequential composition. Our implication holds based on virtually all known key agreement protocols, and can also be based on general complexity assumptions of the existence of dense trapdoor permutations.