Revocable Cryptography in a Quantum World

Poremba, 2023

Category: Quantum Cryptography

Overall Rating

2.3/5 (16/35 pts)

This thesis introduces novel techniques for leveraging quantum information in cryptographic revocation: specifically, the use of Gaussian superpositions over lattices for building certified deletion and key revocation, and the development of a "simultaneous extraction" approach.
While some presented schemes suffer from practical limitations (e.g., semi-honest security, reliance on unproven conjectures for strongest guarantees) and parts may be superseded by follow-up work, the underlying quantum-algorithmic techniques for manipulating and extracting information from structured quantum states (like Gaussian superpositions) could serve as building blocks for future research...
...provided theoretical barriers (such as proving Conjecture 1) can be overcome.

The core technical result enabling key-revocation is the development and application of a "simultaneous search-to-decision reduction with quantum auxiliary input" tailored for the Dual-Regev scheme, leveraging properties of Gaussian superpositions over lattices (Section 5.5, Theorem 30, and Conjecture 1).
A specific, unconventional research direction this could fuel is in generalizing this "simultaneous extraction with quantum auxiliary input" technique beyond the specific context of lattice-based cryptography and Gaussian states.
Developing a more abstract or general framework for such "simultaneous quantum information processing and classical extraction/verification" could have implications for quantum complexity theory, proofs of quantum advantage for structured problems, or even new forms of quantum interactive protocols, extending beyond the cryptographic applications explored here.

The assumption of subexponential hardness for LWE/SIS, necessary for the strongest results (Theorems 24, 33, 38, 39), is stronger than the polynomial hardness often assumed in baseline PQC schemes, potentially limiting the scheme's relevance if alternative constructions emerge under weaker assumptions.
The semi-honest security model for the FHE with simultaneous deletion protocol (Protocol 1, p. 118) is a significant practical weakness; real-world servers are often malicious.
The reliance on the unproven "Simultaneous Dual-Regev Extraction (SDRE) conjecture" (Conjecture 1) for the strongest key-revocation results (Theorems 25, 39) is a major theoretical vulnerability that could lead to its neglect if the conjecture remains unproven or is shown false.
Given that subsequent work quickly improved upon some results and the strongest theorems depend on an unproven conjecture, modern researchers should likely focus on the newer, potentially more robust constructions that built upon this work rather than revisiting these specific, possibly superseded, schemes.

Watch