A study of the relationships among cryptographic primitives

Over the years, cryptographic research has proposed solutions to many security problems. The security of these solutions was proven under a growing number of (unproven) computational assumptions which imply that P ≠ NP. Therefore, for most cryptographic protocols, unconditional proofs of security seem well beyond the reach of complexity theory. Nevertheless, it might be possible that many of these assumptions are related to one another. Exploring the relationship between these assumptions, and determining those that are integral to cryptography as building blocks, would thus greatly clarify our understanding of the cryptographic world, and is considered to be one of the most fundamental goals of research in cryptography. Once the relationship between primitives is established, an equally important goal is to determine whether the protocols constructed using certain cryptographic building blocks are efficient.; We use the oracle separation model [IR89, GT00] to study the relationships among some of the most fundamental primitives and protocols in cryptography: public-key encryption, oblivious transfer (which is equivalent to general secure multi-party computation), trapdoor functions, and key agreement. We show rather surprising separations between public key encryption and oblivious transfer. This two-sided separation implies that in fact public key encryption and oblivious transfer are incomparable with respect to black-box reductions, which makes it a unique situation. Furthermore, we show that trapdoor functions are not necessary for public key encryption. Among our additional results are positive implications in special cases, corollaries separating oblivious transfer and key agreement, and separating trapdoor permutations from public key encryption and oblivious transfer.; We show that the efficiency of known encryption schemes is optimal: for public-key encryption when constructed using trapdoor permutations, and private-key encryption when constructed using one-way permutations. We also show lower bounds on the efficiency of the verification algorithm for digital signature schemes based on one-way permutations.