We propose a new, unifying framework that yields an array of cryptographic primitives with certified deletion. These primitives enable a party in possession of a quantum ciphertext to generate a classical certificate that the encrypted plaintext has been information-theoretically deleted, and cannot be recovered even given unbounded computational resources. - For X \in {public-key, attribute-based, fully-homomorphic, witness, timed-release}, our compiler converts any (post-quantum) X encryption to X encryption with certified deletion. In addition, we compile statistically-binding commitments to statistically-binding commitments with certified everlasting hiding. As a corollary, we also obtain statistically-sound zero-knowledge proofs for QMA with certified everlasting zero-knowledge assuming statistically-binding commitments. - We also obtain a strong form of everlasting security for two-party and multi-party computation in the dishonest majority setting. While simultaneously achieving everlasting security against all parties in this setting is known to be impossible, we introduce everlasting security transfer (EST). This enables any one party (or a subset of parties) to dynamically and certifiably information-theoretically delete other participants' data after protocol execution. We construct general-purpose secure computation with EST assuming statistically-binding commitments, which can be based on one-way functions or pseudorandom quantum states. We obtain our results by developing a novel proof technique to argue that a bit b has been information-theoretically deleted from an adversary's view once they output a valid deletion certificate, despite having been previously information-theoretically determined by the ciphertext they held in their view. This technique may be of independent interest.
翻译:我们提出了一个新的、统一的框架,它产生了一系列具有认证删除功能的密码学原语。这些原语使得拥有量子密文的一方能够生成一个经典证书,证明加密的明文在信息理论意义下已被删除,即使拥有无限的计算资源都不能恢复。对于X \in {公钥,属性基础,全同态,证人,定时发布},我们的编译器将任何(后量子)X加密转换为具有认证删除的X加密。此外,我们将统计绑定承诺编译为具有统计永久隐藏保证的统计绑定承诺。作为推论,我们也获得了基于统计绑定承诺的统计有声零知识证明的结果。我们还在不诚实多数情况下获得了两方和多方计算的强大的永久安全性。虽然在此设置中同时实现永久安全对所有参与方都是不可能的,但是我们引入了永久安全转移(EST)。这使得任何一方(或一组方)能够在协议执行后动态和可证实地信息理论上删除其他参与者的数据。我们使用统计绑定承诺构建了具有EST的通用安全计算,可以基于单向函数或伪随机量子状态。我们通过开发一种新的证明技术来证明比特b已在对手的视图中被信息理论地删除,一旦他们输出一个有效的删除证书,尽管先前由他们所持有的密文中已被以信息论意义确定。这项技术可能具有独立的兴趣。