Research Paper Explores Certified Deletion of Quantum Information
/ 4 min read
Quick take - Vipul Goyal and Justin Raizes have authored a paper that investigates the concept of certified deletion of quantum information, proposing a framework of certified deniability that ensures once information is deleted, it cannot be convincingly evidenced as having existed, while also critiquing existing schemes that fail to align with this principle.
Fast Facts
- Vipul Goyal and Justin Raizes explore certified deletion of quantum information, focusing on erasing quantum data while retaining knowledge of its existence.
- They critique existing signature schemes that allow evidence of a signature’s existence, arguing this contradicts true deletion principles.
- The authors introduce “certified deniability,” ensuring that any retained information post-deletion could have been obtained without the original object, defined within a simulation-based security model.
- Their work constructs two non-interactive primitives—signatures and non-interactive zero-knowledge arguments (NIZKs)—that adhere to certified deniability in the quantum random oracle model.
- The paper discusses practical applications, such as deniable contracts, and emphasizes the need for non-black-box security proofs to achieve certified deniability.
Certified Deletion of Quantum Information
Overview
Vipul Goyal from NTT Research and Carnegie Mellon University, alongside Justin Raizes from Carnegie Mellon University, have authored a paper exploring the concept of certified deletion of quantum information. The paper focuses on the feasibility of completely erasing quantum information while retaining only the knowledge of its existence. This investigation builds on previous works, including a recent study by Morimae, Poremba, and Yamakawa, which examined signature schemes that incorporate certified deletion, where a user cannot recreate a deleted signature.
Critique of Existing Schemes
Goyal and Raizes critique existing schemes that allow users to hold evidence of a signature’s existence, arguing that this does not align with the true essence of deletion. To address this, they introduce the concept of certified deniability, which ensures that any information retained after deletion could have been obtained without the original object. Certified deniability is defined within a simulation-based security model, which is fundamental to their proposed solutions. The authors define and construct two non-interactive primitives adhering to certified deniability in the quantum random oracle model: signatures and non-interactive zero-knowledge arguments (NIZKs). Their findings indicate that once a signature or NIZK is deleted, the user cannot provide convincing evidence of its prior existence.
Implications and Contributions
This work builds on foundational concepts introduced by Broadbent and Islam related to encryption with certified deletion, which have since been generalized to various cryptographic primitives. The authors critique existing revocable signature schemes, asserting that these schemes fail to capture the essence of true deletion, as they allow users to prove that a message was signed at a certain point. Goyal and Raizes advocate for a philosophy of certified deletion, positing that once information is deleted, it should be as if it was never received at all.
The paper discusses the challenges of achieving non-interactive deniability in classical contexts and emphasizes the unique advantages provided by quantum mechanics. A significant aspect of the paper is the simulation-based definition for certified deniability, which stipulates that the state of an adversary, after producing a valid deletion certificate, can be simulated without having received the signature or NIZK. The authors demonstrate that their results circumvent previous impossibility results related to deniable NIZKs within the random oracle model and provide a technical overview of evidence-collection attacks, illustrating how adversarial verifiers can retain evidence of signatures even after revocation.
The discussion extends to the implications of their work for practical applications, such as deniable contracts, where parties can sign agreements that cannot be proven after deletion. The authors highlight their main contributions, including the definitional groundwork for signatures and NIZKs that incorporate certified deniability, and address the barriers encountered in achieving certified deniability within the plain model, noting that valid security proofs must be non-black-box. The paper outlines the authors’ findings and contributions and acknowledges the support received for their research, while also discussing related works in the field.
Original Source: Read the Full Article Here
