Non-malleability is an important security property for public-key encryption (PKE). Its significance is due to the fundamental unachievability of integrity and authenticity guarantees in this setting, rendering it the strongest integrity-like property achievable using PKE only, without digital signatures. In this talk, we demonstrate how to generalize non-malleability to the setting of public-key cryptography. We do this by starting from a well-known classical definition, comparison-based non-malleability, and replacing components of this definition with their natural quantum counterparts.
This generalization comes with difficulties also seen in other integrity-like security notions, mainly the “recording barrier” that prevents a challenger from providing an input state for an adversary and later comparing her output to this input. We will show how to overcome these difficulties and present an argument for the correctness of our definition as well as a hybrid quantum-classical scheme that satisfies it.