Public-Key Encryption (PKE) and Message Authentication (PKMA, aka as digital signatures) are fundamental cryptographic primitives. Traditionally, both notions are defined as non-interactive (i.e., single-message). In this paper, the authors initiate rigorous study of (possibly) interactive PKE and PKMA schemes. They obtain the following results demonstrating the power of interaction to resolve questions which are either open or impossible in the non-interactive setting. One of the most well known open questions in the area of PKE is to build, in a \"Black-box way\", so called Chosen Ciphertext Attack (CCA-) secure PKE from Chosen Plaintext Attack (CPA-) secure PKE.