Efficient completely non-malleable and RKA secure public key encryptions

Motivated by tampering attacks in practice, two different but related security notions, termed complete non-malleability and relatedkey attack security, have been proposed recently. In this work, we study their relations and present the first public key encryption scheme that is secure in both notions under standard assumptions. Moreover, by exploiting the technique for achieving complete non-malleability, we give a practical scheme for the related-key attack security. Precisely, the scheme is proven secure against polynomial functions of bounded degree d under a newly introduced hardness assumption called dmodified extended decisional bilinear Diffie-Hellman assumption. Since the schemes are constructed in a direct way instead of relying on the noninteractive zero knowledge proof or signature techniques, they not only achieve the strong security notions but also have better performances.