  (Sender-)Deniable encryption provides a very strong privacy guarantee: a
sender who is coerced by an attacker into "opening" their ciphertext
after-the-fact is able to generate "fake" local random choices that are
consistent with any plaintext of their choice. The only known fully-efficient
constructions of public-key deniable encryption rely on indistinguishability
obfuscation (iO) (which currently can only be based on sub-exponential hardness
assumptions). In this work, we study (sender-)deniable encryption in a setting
where the encryption procedure is a quantum algorithm, but the ciphertext is
classical. First, we propose a quantum analog of the classical definition in
this setting. We give a fully efficient construction satisfying this
definition, assuming the quantum hardness of the Learning with Errors (LWE)
problem. Second, we show that quantum computation unlocks a fundamentally
stronger form of deniable encryption, which we call perfect unexplainability.
The primitive at the heart of unexplainability is a quantum computation for
which there is provably no efficient way, such as exhibiting the "history of
the computation", to establish that the output was indeed the result of the
computation. We give a construction which is secure in the random oracle model,
assuming the quantum hardness of LWE. Crucially, this notion implies a form of
protection against coercion "before-the-fact", a property that is impossible to
achieve classically.
