Quantum Key Leasing for PKE and FHE with a Classical Lessor
摘要
In this work, we consider the problem of secure key leasing, also known as revocable cryptography (Agarwal et al. Eurocrypt’ 23, Ananth et al. TCC’ 23), as a strengthened security notion to its predecessor put forward in Ananth et al. (Eurocrypt’ 21). This problem aims to leverage unclonable nature of quantum information to allow a lessor to lease a quantum key with reusability for evaluating a classical functionality. Later, the lessor can request the lessee to provably delete the key and then the lessee will be completely deprived of the capability to evaluate. In this work, we construct a secure key leasing scheme to lease a decryption key of a (classical) public-key, homomorphic encryption scheme from standard lattice assumptions. Our encryption scheme is exactly identical to the (primal) version of Gentry-Sahai-Waters homomorphic encryption scheme with a carefully chosen public key matrix. We achieve strong form of security where: Our security relies on subexponential time hardness of learning with errors assumption. Our scheme is the first scheme to be based on a standard assumption and satisfying the two properties mentioned above. The main technical novelty in our work is the design of an FHE scheme that enables us to apply elegant analyses done in the context of classical verification of quantumness from LWE (Brakerski et al. (FOCS’18, JACM’21) and its parallel amplified version in Radian et al. (AFT’21)) to the setting of secure leasing. This connection to classical verification of quantumness leads to a modular construction and arguably simpler proofs than previously known. An important technical component we prove along the way is an amplified quantum search-to-decision reduction: we design an extractor that uses a quantum distinguisher (who has an internal quantum state) for decisional LWE, to extract secrets with success probability amplified to almost one. This technique might be of independent interest.