Equivalence of Uniform Key Agreement and Composition Insecurity
Chongwon Cho, Chen-Kuei Lee, and Rafail Ostrovsky
Abstract:
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 equal to 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 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., "ryptomania") 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.
comment: Crypto 2010: 447-464
Fetch PDF file of the paper
| Back to Publications List |