Efficient completely non-malleable and RKA secure public key encryptions

Abstract

© Springer International Publishing Switzerland 2016.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 bil..