⚛️ quantum physics

A Unified Approach to Quantum Key Leasing with a Classical Lessor

This paper presents a modular framework for constructing secure quantum key leasing schemes with a fully classical lessor, enabling the leasing and revocation of keys for public-key encryption, pseudorandom functions, and digital signatures via classical communication while satisfying strong verification key revealing attack security under the learning with errors assumption.

Original authors: Fuyuki Kitagawa, Jiahui Liu, Shota Yamada, Takashi Yamakawa

Published 2026-07-22

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Fuyuki Kitagawa, Jiahui Liu, Shota Yamada, Takashi Yamakawa

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where you can rent a super-powerful tool, like a magic key that opens a digital vault, but with a catch: once you return the key, you are magically forced to forget how to make a copy of it. This is the dream of secure key leasing. In the real world, if you lend someone a physical key, they can easily copy it and keep using it even after you ask for it back. But in the quantum world, the laws of physics say you cannot copy a specific type of information without destroying the original. This paper explores how to use that "no-copying" rule to create a system where a boss (the lessor) can rent out a secret key to a worker (the lessee) and, when the rental period ends, verify that the worker has truly deleted the key and can no longer use it.

The tricky part is that usually, to rent out a quantum key, the boss needs to be a quantum computer themselves, which is expensive and hard to build. This paper asks a bold question: Can a boss who is completely "classical" (just a regular computer with no quantum powers) still rent out these uncopyable quantum keys? The authors propose a new, modular framework that says "yes." They show how to upgrade standard encryption, password generators, and digital signatures into "rentable" versions where the boss stays classical, the worker does all the heavy quantum lifting, and the key can be revoked and verified with just normal, classical messages.

The "Magic Rental" Framework

Think of the problem like this: A manager wants to let an employee use a special digital stamp to sign documents while on vacation. When the manager returns, they need to make sure the employee can't keep using that stamp. In the past, solutions required the manager to be a quantum wizard, sending complex quantum signals to the employee. This new paper introduces a "Universal Adapter" that lets a regular, classical manager do the same job.

The authors built a framework that takes three common digital tools and gives them a "quantum lease" upgrade:

Public Key Encryption (PKE): The ability to send secret messages.
Pseudorandom Functions (PRF): Tools that generate numbers that look random but are actually determined by a secret key (like a password generator).
Digital Signatures (DS): The ability to sign documents to prove they are authentic.

The magic happens through a clever three-step dance involving a "Noisy Trapdoor Claw-Free" (NTCF) function, which acts like a quantum lockbox, and a "Secure Function Evaluation" (SFE), which is like a secure black box that computes things without revealing the inputs.

How the "Classical Boss" Does It

Here is the playful analogy of how the system works, using the paper's specific construction:

Step 1: The Setup (The Boss stays Classical)
The boss (the lessor) generates a set of "claw-free" locks. Imagine these locks are special puzzles where there are two different keys (let's call them Key A and Key B) that open the same door. The boss knows the secret "trapdoor" that reveals both keys, but the employee (the lessee) only sees the locked door. The boss sends these puzzle descriptions to the employee.

Step 2: The Employee's Quantum Work
The employee, who has a quantum computer, tries to solve the puzzles. Because of quantum rules, the employee can create a "superposition" state—a magical state where they hold both Key A and Key B at the same time, but in a way that is uncopyable. This is the "quantum secret key." The employee sends a classical confirmation back to the boss, proving they have the key, but without revealing which specific keys they are holding.

Step 3: The "Watermark" Trick
This is where the paper gets really clever. The boss doesn't just give the employee a raw key; they embed a "watermark" into the key. Think of this like a hidden serial number inside the quantum state. If the employee tries to use the key to decrypt a message or sign a document, the watermark is there. If the employee tries to cheat and keep a copy, the watermark helps the boss prove it later. The authors show that if an employee tries to keep the key after returning it, they will inevitably leave behind a trace that allows the boss to extract the "serial number" (the watermark) and prove the employee is still holding the key.

Step 4: The Revocation (The "Delete" Button)
When the rental period is over, the boss asks the employee to "delete" the key. The employee measures their quantum state in a specific way and sends the result back. Because of the quantum "no-cloning" rule, if the employee successfully sends the deletion proof, they are mathematically forced to lose the information needed to use the key again. The boss checks the proof using their trapdoor. If it passes, the boss is virtually certain (with a probability so close to 100% that the chance of failure is negligible) that the employee can no longer use the key.

What This Paper Actually Achieves

The paper proves that this framework works under the assumption that "Learning With Errors" (LWE) is hard to solve. LWE is a standard mathematical problem that is believed to be difficult even for quantum computers, making it a solid foundation for future security.

The authors demonstrate that:

They achieved the first schemes for Pseudorandom Functions and Digital Signatures that allow for secure key leasing with a fully classical lessor (alongside concurrent work by Takeuchi and Xu who achieved similar results independently).
They improved existing schemes for Public Key Encryption, making the process more modular and less dependent on specific, complex math structures.
They proved "VRA Security": This stands for "Verification Key Revealing Attack" security. It means that even if a hacker steals the boss's verification key after the employee has returned the key, the hacker still cannot figure out how to use the key. This is a very strong security guarantee.

What They Did Not Do (and What They Ruled Out)

It is important to note what this paper does not claim. The authors explicitly state that their method relies on the LWE assumption; they do not claim to have solved the problem using only the encryption scheme itself without extra tools like NTCF or SFE. They also clarify that while they made the key generation process "non-interactive" (meaning the boss doesn't need to chat back and forth with the employee for encryption keys), the initial setup still requires a few rounds of communication. They did not claim to have built a physical device; this is a theoretical mathematical proof that such a system can exist.

Why It Matters

This work is a significant step toward practical quantum cryptography. By showing that a "classical" boss can manage "quantum" keys, the authors remove a huge barrier to entry. In the real world, companies and individuals won't need to buy expensive, fragile quantum computers just to rent out digital services securely. They can use their regular computers to manage the process, while the heavy quantum lifting is done by the server or the user. This modular approach suggests that we can build a future where digital rights management, software licensing, and secure data access are not only possible but also verifiable and revocable, all while keeping the "boss" simple and classical.

Technical Summary: A Unified Approach to Quantum Key Leasing with a Classical Lessor

Problem Statement

Secure Key Leasing (SKL) is a cryptographic primitive that allows a lessor to lease a quantum secret key to a lessee, enabling the lessee to perform a specific cryptographic functionality (e.g., decryption, signing, or PRF evaluation). Crucially, the lessor must be able to verifiably revoke this capability later. The lessee must return a deletion certificate proving they have destroyed the key, after which they should be unable to perform the functionality.

While previous works have realized SKL for various primitives (PKE, FHE, PRF, signatures), they suffer from two main limitations:

Lack of Modularity: Constructions are often ad-hoc and tailored to specific primitives rather than arising from a unified framework.
Quantum Lessor Requirement: Existing schemes generally require the lessor (client) to be fully quantum, capable of preparing and sending quantum states. In practical cloud computing scenarios, minimizing the quantum resources required of the client is essential. The only known scheme with a classical lessor (Chardouvelis et al., Eurocrypt 2025) is limited to Public-Key Encryption (PKE) and Fully Homomorphic Encryption (FHE) and relies heavily on specific LWE structures, making generalization to other primitives difficult.

The central question addressed is: Can we develop a modular SKL framework that supports a fully classical lessor and spans a broad range of widely used cryptographic functionalities?

Methodology

The authors propose a modular framework that "upgrades" generic cryptographic primitives into SKL schemes with a classical lessor. The construction relies on three core components:

Noisy Trapdoor Claw-Free (NTCF) Generators: Based on the work of Broadbent et al. and Mahadev, NTCFs allow a classical client to verify that a quantum server has prepared a specific "claw state" (a superposition of two pre-images $|0\rangle|a_0\rangle + |1\rangle|a_1\rangle$ such that $f(a_0)=f(a_1)=y$ ). The security relies on the adaptive hardcore bit property, which ensures that once the server measures the state in the Hadamard basis (to prove deletion), it loses the ability to recover the pre-images in the computational basis.
Special Dual-Mode Secure Function Evaluation (SFE): The authors construct a novel SFE scheme based on the Learning With Errors (LWE) assumption. This SFE possesses specific properties required for the framework:
- Dual-Mode: It operates in either an extractable mode (allowing the extraction of the input message from the ciphertext) or a hiding mode (statistically hiding the input).
- State Recoverability: In hiding mode, the state information held by the receiver can be recovered from the ciphertext and input using a trapdoor.
- Efficient Superposition Generation: The receiver can generate the SFE state in superposition without leaving entanglement with the randomness used.
- Decomposability: The receiver's state can be decomposed into blocks dependent on individual bits of the input, a property crucial for the security reduction.
Watermarking with Parallel Extraction: The framework utilizes watermarkable versions of the target primitives (PKE, PRF, Signatures). A watermarkable scheme allows a "mark" (a secret string) to be embedded into a key. The security notion requires that if an adversary produces a functional program (e.g., a decryptor or signer) that works correctly, a "parallel extractor" can recover the embedded marks from the adversary's quantum state.

The Core Mechanism:
The framework transforms a standard key into a quantum state by entangling it with NTCF claw states.

The lessor (classical) sends NTCF public parameters and SFE Common Reference Strings (CRS) to the lessee.
The lessee prepares claw states and runs the first round of SFE.
The lessor defines a circuit $C$ that maps the NTCF pre-images to the actual secret keys of the underlying primitive (e.g., a watermarkable PKE key). This circuit is executed homomorphically via the SFE.
The lessee receives the result, effectively obtaining a quantum state where the secret key is embedded in superposition: $|0\rangle|sk_0\rangle + |1\rangle|sk_1\rangle$ .
Deletion: To revoke the key, the lessor asks the lessee to measure the state in the Hadamard basis. Due to the properties of NTCF and the SFE, a valid measurement certificate proves the lessee has lost the computational basis information (the pre-images and thus the secret keys).
Security Reduction: If an adversary passes the deletion verification but still retains the ability to perform the cryptographic task (e.g., decrypt a message), the reduction uses the parallel mark extraction property of the watermarking scheme to extract the NTCF pre-images. Combined with the deletion certificate (which provides Hadamard basis measurements), this breaks the cut-and-choose adaptive hardcore bit property of the NTCF.

Key Contributions and Results

1. A Unified Classical-Lessor SKL Framework

The paper presents a general compiler that converts any post-quantum secure primitive equipped with parallel-extractable watermarking into a classical-lessor SKL scheme. This framework is modular and relies on standard assumptions (LWE) rather than ad-hoc constructions.

2. Specific Schemes

Based on this framework, the authors construct:

PKE-SKL with Classical Lessor: Improves upon previous LWE-based constructions (Chardouvelis et al., Eurocrypt 2025) by removing the reliance on specific LWE structures for the PKE scheme itself. The underlying PKE can be any IND-CPA secure post-quantum scheme.
PRF-SKL with Classical Lessor: The first construction of a PRF with secure key leasing and a classical lessor. It is based on LWE and utilizes watermarkable Unpredictable Functions (UPFs).
DS-SKL with Classical Lessor: The first construction of a Digital Signature with secure key leasing and a classical lessor. This requires the underlying signature scheme to possess coherent signability (the ability to sign using a superposition of keys without collapsing the state), which the authors construct from LWE/SIS.

3. Security Notions

All schemes satisfy VRA Security (Security against Verification Key Revealing Attacks). This is a strong security notion where the scheme remains secure even if the adversary is given the deletion verification key after submitting a valid deletion certificate. This prevents the adversary from using the verification key to cheat or learn information about the key after the fact.

4. Non-Interactive Key Generation

The authors refine their construction to achieve non-interactive key generation for PKE-SKL (and constant-round for PRF/DS). In the standard protocol, the lessor and lessee interact to generate the key. The improved version allows the lessor to publish public parameters once, after which the lessee can generate the key non-interactively. The full key generation is deferred to the encryption/signing phase, where the lessee uses auxiliary information from the ciphertext to complete the key preparation.

5. Auxiliary Constructions

Along the way, the paper constructs:

A Watermarking Scheme for PKE, UPFs, and Digital Signatures with parallel extraction properties.
A Special Dual-Mode SFE scheme based on LWE, which satisfies unique state recoverability and decomposability properties not found in standard SFE definitions.

Significance and Claims

The paper claims to provide the first modular framework for secure key leasing that supports a fully classical lessor across a broad spectrum of cryptographic functionalities (PKE, PRF, Signatures).

Modularity: Unlike previous works that were tailored to specific primitives, this approach abstracts the problem into a compiler that works for any primitive with parallel-extractable watermarking.
Practicality: By enabling a classical lessor, the framework aligns with real-world cloud computing scenarios where clients lack quantum capabilities.
Security Strength: The schemes achieve VRA security, a stronger guarantee than many existing SKL definitions, ensuring robustness even if verification keys are leaked post-deletion.
Foundational Improvements: The construction of the special dual-mode SFE and the watermarking schemes with parallel extraction are presented as contributions of independent interest.

The authors note that while their PKE-SKL construction relies on LWE, the underlying PKE scheme itself need not be LWE-based, offering greater flexibility than previous LWE-structured PKE-SKL schemes. They also acknowledge that their approach for signatures requires the specific property of coherent signability, which they construct from LWE/SIS, whereas previous quantum-lessor approaches relied on different assumptions or specific signature structures.

In summary, the work bridges the gap between theoretical quantum key leasing and practical deployment by removing the quantum burden from the lessor while maintaining strong security guarantees through a unified, modular approach.