Computational Certified Deletion Property of Magic Square Game and its Application to Classical Secure Key Leasing

arXiv:2510.04529 · cs.CR, quant-ph · Submitted 2025-10-06 · Read on arXiv

cs.CR, quant-ph

Submitted: 2025-10-06

Updated: 2026-09-14

Comments: Fixed a few typos and added concurrent works

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Magic Square Game — 49× in this paper
• Verifier — 46× in this paper · explained in 2 episodes
• Certified Deletion Property — 41× in this paper
• Verification — 30× in this paper · explained in 2 episodes
• Classical Blind Quantum Computing — 5× in this paper
• Trace — 3× in this paper · explained in 2 episodes
• Trace Distance — 3× in this paper · explained in 3 episodes
• BQP — 2× in this paper · explained in 2 episodes
• Quantum Fully Homomorphic Encryption — 2× in this paper
• Core — 1× in this paper · explained in 2 episodes
• Entanglement — 1× in this paper · explained in 3 episodes
• NPA Hierarchy — 1× in this paper · explained in 2 episodes
• Robustness — 1× in this paper · explained in 5 episodes

Sources

• Quantum bounds for compiled XOR games and $d$-outcome CHSH games
• A Computational Tsirelson's Theorem for the Value of Compiled XOR Games
• Quantitative Quantum Soundness for Bipartite Compiled Bell Games via the Sequential NPA Hierarchy
• Self-testing in the compiled setting via tilted-CHSH inequalities
• Revocable Quantum Digital Signatures

Related papers

• SoK: AI-Augmented Binary Reversing
• Relaxed Sender Anonymity for CBDC Interbank Settlement: A Zero-Knowledge Approach on Permissioned EVM
• Calibration-Family Overfit: Why Trusted Sabotage Monitors Don't Transfer Across Lineages
• Efficient Fuzzy PSI under One-Sided Assumptions
• Sealing the Audit-Runtime Gap for LLM Skills
• Token Composition: A Graph Based on EVM Logs