⚛️ quantum physics

Trapdoor Functions with Secure Key Leasing and Copy Protection

This paper initiates the study of trapdoor functions (TDFs) in the context of secure key leasing and copy protection by defining and constructing TDFs with these unclonable properties under standard cryptographic assumptions, and subsequently leveraging them to build robust public-key encryption and single-decryptor encryption schemes that prevent the destruction of quantum decryption keys.

Original authors: Fuyuki Kitagawa, Ryo Nishimaki, Yuki Shirakawa, Takashi Yamakawa

Published 2026-09-09

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Fuyuki Kitagawa, Ryo Nishimaki, Yuki Shirakawa, 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

In the quantum world, a fundamental rule known as the no-cloning theorem dictates that an unknown piece of information cannot be perfectly copied. Unlike a digital file on a computer, which can be duplicated endlessly without losing the original, a quantum state is fragile; the moment you try to measure or copy it, you inevitably disturb it. This unique property has inspired scientists to imagine new forms of cryptography where security relies not on mathematical difficulty, but on the laws of physics themselves. In these systems, secret keys are not just strings of numbers but delicate quantum states. If someone tries to steal a copy of such a key, the act of copying destroys the original, alerting the owner that a breach has occurred. This concept has led to the development of tools like "secure key leasing," where a user can rent a decryption key and return it, and "copy protection," where a software program is encoded in a way that prevents it from being duplicated.

However, a critical weakness has plagued these quantum tools. In many existing designs, the quantum key is so sensitive that if a user tries to decrypt a message that was not created by the legitimate sender—a "malicious" message—the key can collapse and become useless. It is as if a master key, designed to open a specific lock, shatters the moment it is forced against a fake door. This fragility limits the practical use of quantum security, as real-world systems must handle unexpected or malformed data without losing their ability to function. The question remained: could researchers build quantum tools that are not only unclonable but also robust enough to survive these accidental or malicious encounters?

A team of researchers has now answered this question by creating a new class of mathematical functions called trapdoor functions that are both secure against copying and resilient to damage. In classical cryptography, a trapdoor function is a mathematical operation that is easy to perform in one direction but extremely difficult to reverse without a special secret, known as a "trapdoor." Think of it like a combination lock that is easy to spin to a random number but impossible to crack back to the starting position without knowing the code. The researchers have successfully adapted this concept for the quantum realm, creating versions where the secret code is a quantum state that can be leased, returned, and protected from being copied.

The team first tackled the problem of "secure key leasing." They designed a system where a user can rent a quantum trapdoor to perform a specific task, such as decrypting a message. The user can then delete this key and provide a certificate proving they have done so, ensuring the key cannot be used again. Crucially, they proved that this system works even if the user attempts to decrypt messages that were not properly formed. In their construction, the quantum key remains intact and reusable after such attempts, solving the fragility issue that had plagued previous designs. They achieved this by building the system on well-established mathematical assumptions, specifically the Learning With Errors problem, which is believed to be secure even against future quantum computers.

Next, the researchers addressed "copy protection." They created a version of the trapdoor function where the ability to reverse the operation is encoded into a quantum state that cannot be duplicated. If an adversary tries to split this state into two copies to share the decryption power, the security guarantees ensure that at least one of the copies will fail to work. This prevents the unauthorized distribution of decryption capabilities. To build this, the team combined advanced cryptographic techniques, including a method called indistinguishability obfuscation, which scrambles a program's code so thoroughly that its inner workings cannot be understood, even if the code is visible.

The significance of this work extends beyond the theoretical. By creating these robust, unclonable functions, the researchers have provided the building blocks for more reliable quantum encryption systems. They demonstrated that their new trapdoor functions can be used to construct public-key encryption schemes and single-decryptor encryption systems that do not break when faced with malformed data. This means that in the future, quantum-secured communications could be more practical and reliable, capable of handling the messy reality of real-world data without losing their security or functionality. The work confirms that it is possible to have quantum cryptographic tools that are both unclonable and tough, bridging the gap between theoretical possibility and practical application.

Technical Summary: Trapdoor Functions with Secure Key Leasing and Copy Protection

1. Problem Statement and Motivation

This work addresses a gap in the field of unclonable cryptography: the lack of study on Trapdoor Functions (TDFs) within the contexts of Secure Key Leasing (SKL) and Copy Protection (CP). While TDFs are fundamental primitives in classical public-key cryptography (enabling constructions of IND-CPA and IND-CCA secure Public-Key Encryption), they have not been extensively explored in quantum settings where keys are quantum states and functionalities must be unclonable.

Furthermore, existing constructions of Public-Key Encryption with Secure Key Leasing (PKE-SKL) and Single-Decryptor Encryption (SDE) suffer from a critical vulnerability known as key destruction. In these schemes, a quantum decryption key is typically a quantum state. If an adversary sends a maliciously chosen ciphertext (not necessarily generated by the honest encryption algorithm) to a holder of the quantum key, the decryption process may cause the quantum state to collapse, rendering the key unusable for future decryptions. Existing schemes do not guarantee that the decryption key remains reusable after decrypting arbitrary ciphertexts.

The paper poses two central questions:

Can TDFs with secure key leasing and TDFs with copy protection be constructed from standard assumptions?
Can robust PKE-SKL and SDE schemes be constructed that remain secure against key-destruction attacks?

2. Methodology and Definitions

2.1 Trapdoor Functions with Secure Key Leasing (TDF-SKL)

The authors define TDF-SKL as a tuple of algorithms $(KG, Eval, Inv, Del, Vrfy)$ where:

KG outputs a classical evaluation key ($ek$), a quantum trapdoor ($td$), and a classical verification key ($vk$).
Eval is a deterministic algorithm mapping inputs to outputs.
Inv is a quantum algorithm that inverts the function using $td$.
Del allows the holder of $td$ to delete it and produce a classical certificate.
Vrfy verifies the certificate using $vk$.

The security notion is one-wayness: an adversary who obtains $ek$ and $td$, submits a valid deletion certificate, and then receives a challenge image $y$ (the output of $Eval$ on a random input $x$ ) cannot recover $x$ .

The paper distinguishes between two variants:

TDF-SKL (without domain sampler): One-wayness holds for inputs sampled uniformly at random.
TDF-SKL with domain sampler: Includes a sampling algorithm $Samp$. One-wayness holds for inputs sampled by $Samp$, and the adversary receives the verification key $vk$ alongside the challenge image (analogous to IND-VRA security in PKE-SKL).

2.2 Trapdoor Functions with Copy Protection (TDF-CP)

TDF-CP is defined as a tuple $(Setup, KG, Eval, Inv)$ where:

Setup generates a classical $ek$ and $td$.
KG generates a quantum trapdoor $td$ from $td$.
Eval is deterministic.
Inv is a quantum inversion algorithm.

The security notion is search anti-piracy security. In a security game, an adversary $A$ receives a quantum trapdoor, splits it into a bipartite state shared with $B$ and $C$ , and sends them challenge images $y_B$ and $y_C$ (corresponding to independent inputs $x_B$ and $x_C$ ). $B$ and $C$ must simultaneously invert their respective challenges. Security requires that the probability of both succeeding is negligible.

2.3 Robustness

A scheme is robust if the quantum decryption key remains reusable (i.e., the trace distance between the pre-decryption and post-decryption states is negligible) even after decrypting any ciphertext, including maliciously constructed ones.

3. Key Constructions and Results

3.1 Construction of TDF-SKL

The authors provide two constructions based on different assumptions:

TDF-SKL (without domain sampler):
- Assumptions: Learning With Errors (LWE) and Hinting Pseudorandom Generators (PRGs).
- Methodology: The construction adapts the approach of Garg et al. [GHMO21] but modifies it to avoid the "mirroring technique" which fails in the SKL setting due to the order of certificate submission and challenge receipt. Instead, it uses Naor's commitment scheme and a hinting PRG to achieve "almost-all-keys" correctness.
- Mechanism: The evaluation key includes random strings $r_i$ . The output $y_i$ is constructed using a PKE ciphertext and a PRG output. The inversion algorithm coherently attempts to decrypt two potential ciphertexts based on a check involving the PRG and the random strings $r_i$ .
TDF-SKL with domain sampler:
- Assumptions: IND-CPA secure PKE and Hinting PRGs.
- Methodology: This variant relies on IND-VRA secure PKE-SKL (which can be constructed from IND-CPA PKE). The construction is similar to the first but incorporates a domain sampler and ensures the adversary receives the verification key during the challenge phase.

3.2 Construction of TDF-CP

Assumptions: Indistinguishability Obfuscation (iO) and LWE.
Methodology: The construction follows the modular framework proposed by Ananth and Behera [AB24].
1. Puncturable TDFs: The authors first construct puncturable TDFs (secure against inversion even with a trapdoor punctured at two points) using iO, puncturable PRFs, and injective OWFs.
2. Unclonable Puncturable Obfuscation (UPO): They utilize UPO (constructed from iO and LWE) to obfuscate the inversion algorithm of the puncturable TDF.
3. Composition: The final TDF-CP is formed by obfuscating the puncturable TDF's inversion algorithm using UPO.

3.3 Applications: Robust PKE-SKL and Robust SDE

The primary application of these new TDF primitives is the construction of robust encryption schemes.

Robust PKE-SKL:
- Construction: Built from TDF-SKL with a domain sampler.
- Mechanism: The encryption uses the Goldreich-Levin theorem. The decryption algorithm performs a coherent inversion of the TDF-SKL. If the input is a valid image, the inversion succeeds with high probability; if not, it outputs $\perp$ .
- Robustness Proof: By the Gentle Measurement Lemma, if the measurement outcome (success or failure) is almost deterministic, the post-measurement state remains close to the original. Since the TDF-SKL inversion is almost always correct for valid inputs and always rejects invalid inputs, the decryption key remains reusable.
- Security: The resulting scheme is IND-VRA secure.
Robust SDE:
- Construction: Built from TDF-CP.
- Mechanism: Similar to the robust PKE-SKL, utilizing the Goldreich-Levin theorem and the TDF-CP inversion.
- Security: The resulting scheme is CPA+ anti-piracy secure and robust.

4. Significance and Claims

The paper claims to be the first to initiate the study of TDFs in secure key leasing and copy protection settings. Its significance lies in:

Foundational Expansion: It extends the utility of TDFs, a cornerstone of classical cryptography, into the realm of unclonable quantum cryptography.
Solving Key Destruction: It resolves the vulnerability of key destruction in existing PKE-SKL and SDE schemes. The constructed schemes are robust, meaning the quantum decryption key survives the decryption of arbitrary (potentially malicious) ciphertexts.
Black-Box Construction: The authors highlight that their construction of robust PKE-SKL relies only on the black-box use of cryptographic primitives. This contrasts with alternative approaches using Non-Interactive Zero-Knowledge (NIZK) proofs, which are inherently non-black-box.
Broader Instantiations: The approach allows for instantiations under group-action-based assumptions (via Hinting PRGs and PKE), whereas NIZK-based robustness is not currently known to exist under these assumptions.
Modular Frameworks: The work demonstrates the power of modular frameworks (like UPO for copy protection) in constructing complex quantum cryptographic primitives from standard assumptions (iO, LWE).

The authors maintain a modest tone, noting that while they provide constructions based on standard assumptions (LWE, iO), the field of unclonable cryptography is still evolving, and their work lays the groundwork for further exploration of TDFs in these quantum settings.