During the last two decades, there has been intensive and fast development in Multivariate Public Key Cryptography (MPKC), which is considered to be an important candidate for post-quantum cryptography. However, it is universally regarded as a difficult task, as in the Knapsack cryptosystems, to design a secure MPKC scheme (especially an encryption scheme) employing the existing trapdoor construction. In this paper, we propose a new key-exchange scheme and an MPKC scheme based on the Morphism of Polynomials (MP) problem. The security of the proposed schemes is provably reducible to the conjectured intractability of a new difficult problem, namely the Decisional Multivariate Diffie-Hellman (DMDH) problem derived from the MP problem. The proposed key agreement is one of several non-number-theory-based protocols, and is a candidate for use in the post-quantum era. More importantly, by slightly modifying the protocol, we offer an original approach to designing a secure MPKC scheme. Furthermore, the proposed encryption scheme achieves a good tradeoff between security and efficiency, and seems competitive with traditional MPKC schemes.