The Quantum Decoherence Model: Everlasting Composable Secure Computation and More

Quantum cryptography allows to achieve security goals which are unobtainable using classical cryptography alone: it offers the promise of everlasting privacy. That is, an adversary trying to attack a protocol must succeed during the run of the protocol. After the protocol has terminated, security holds unconditionally.

In this work, we initiate the study of a new model which we call the quantum decoherence model (QDM). In a nutshell, this model captures adversaries that are computationally bounded during the run of a protocol (and some time after), but become computationally unbounded long after the protocol terminates. Importantly, once the adversary becomes computationally unbounded, he can only remember a bounded number of qubits from before the computational bound was lifted.

We provide a variant of the Universal Composability framework which captures the new notion of quantum decoherence and augment it with quantum random oracles. As our main contribution, we construct a non-interactive commitment scheme achieving unconditional and statistical security against malicious senders and everlasting security against malicious receivers under our new security notion. ... mehrSuch commitments imply general secure multiparty computation with everlasting security.

Finally, we show that our core technique can be applied to a broader spectrum of problems. We show that it gives rise to everlasting public key encryption and OT in the QDM. Finally, we also consider the weaker notion of incompressible encryption in the setting of quantum decoherence, and show that post-quantum IND-CPA secure public key encryption is sufficient to realize this notion without resorting to random oracles.

At the technical core of our constructions is a new, conceptually simple yet powerful reverse entropic uncertainty relation.