Inspired by the no-cloning theorem in quantum theory, a variety of quantum cryptographic primitives with unclonable functionalities, such as secure key leasing and copy protection, have been proposed and attracted significant attention. However, trapdoor functions (TDFs), fundamental primitives in public-key cryptography, have not been extensively studied in these areas. In this work, we initiate a study of TDFs in both secure key leasing and copy protection settings. We first introduce the definition of TDFs with secure key leasing (TDF-SKL), which enables leasing and deleting of quantum trapdoors. We formalize TDF-SKL both with and without domain sampler, and give a construction of TDF-SKL without domain sampler based on the LWE assumption and a construction of TDF-SKL with domain sampler based on any standard PKE schemes combined with hinting pseudorandom generators [Koppula and Waters, CRYPTO 2019]. Next, we define TDFs with copy protection (TDF-CP), where the inversion functionality is copy protected by a quantum trapdoor. We establish a construction of TDF-CP assuming indistinguishability obfuscation and the LWE assumption, following a modular framework of copy protection proposed by Ananth and Behera [CRYPTO 2024]. We also present applications of TDF-SKL and TDF-CP. Existing constructions of public-key encryption with secure key leasing (PKE-SKL) and single-decryptor encryption (SDE) suffer from a critical vulnerability: quantum decryption keys may be destroyed after decrypting maliciously chosen ciphertexts. We construct PKE-SKL schemes and SDE schemes with robust quantum decryption keys that remain reusable after decrypting arbitrary ciphertexts from TDF-SKL and TDF-CP, respectively.
Inspired by the no-cloning theorem in quantum theory, a variety of quantum cryptographic primitives with unclonable functionalities, such as secure key leasing and copy protection, have been proposed and attracted significant attention. However, trapdoor functions (TDFs), fundamental primitives in public-key cryptography, have not been extensively studied in these areas. In this work, we initiate a study of TDFs in both secure key leasing and copy protection settings. We first introduce the definition of TDFs with secure key leasing (TDF-SKL), which enables leasing and deleting of quantum trapdoors. We formalize TDF-SKL both with and without domain sampler, and give a construction of TDF-SKL without domain sampler based on the LWE assumption and a construction of TDF-SKL with domain sampler based on any standard PKE schemes combined with hinting pseudorandom generators [Koppula and Waters, CRYPTO 2019]. Next, we define TDFs with copy protection (TDF-CP), where the inversion functionality is copy protected by a quantum trapdoor. We establish a construction of TDF-CP assuming indistinguishability obfuscation and the LWE assumption, following a modular framework of copy protection proposed by Ananth and Behera [CRYPTO 2024]. We also present applications of TDF-SKL and TDF-CP. Existing constructions of public-key encryption with secure key leasing (PKE-SKL) and single-decryptor encryption (SDE) suffer from a critical vulnerability: quantum decryption keys may be destroyed after decrypting maliciously chosen ciphertexts. We construct PKE-SKL schemes and SDE schemes with robust quantum decryption keys that remain reusable after decrypting arbitrary ciphertexts from TDF-SKL and TDF-CP, respectively.
It is well known that quantum computers, when fully realized, pose a threat to most cryptosystems deployed today. On the other hand, quantum information is also known to enhance classical cryptography, in terms of improved security and efficiency. Surprisingly, quantum information can also provide guarantees that are completely impossible to attain classically. The class of quantum cryptographic primitives called unclonable primitives fall into this category, with quantum money being a canonical example. Intuitively, quantum money allows a bank to distribute currency in the form of quantum states that provably resist counterfeiting due to the no-cloning theorem of quantum mechanics. This is in sharp contrast to classical information, for which there is no fundamental barrier that prevents its duplication. This work focusses on another up-and-coming unclonable primitive referred to as secure key leasing (SKL). This is a notion that allows to encode secret keys into a quantum state that can be temporarily leased. For example, it allows decryption keys of a public-key encryption scheme to be leased, enabling the recipient to decrypt ciphertexts while it possesses the quantum state. Later, the recipient can provide a proof of deletion which ensures that they have effectively ``lost'' access to the leased key. SKL is especially useful for software distributors that wish to provide trial period access. It allows them to provide access to their service via leased quantum keys, where they can incentivize timely deletion using a refund. In more detail, this dissertation studies SKL schemes in the setting of collusion, where multiple users can be leased independently generated quantum keys that provide access to the same underlying secret-key. It involves the study of meaningful notions of collusion-resistant security in this context, which are more realistic for real world applications than schemes secure in the standalone (single-key/single-user) setting. Then, new constructions are provided to realize these notions, with an emphasis on utilizing standard/well-understood cryptographic assumptions. Another major focus of the work is on providing modular approaches to constructing collusion-resistant SKL. In this light, novel compilers for different variants of the primitive are motivated and explored in detail.
We propose a general cryptographic primitive called lossy trapdoor functions (lossy TDFs), and we use it to develop new approaches for constructing several important cryptographic tools, including (injective) trapdoor functions, collision-resistant hash functions, oblivious transfer, and chosen ciphertext-secure cryptosystems (in the standard model). All of these constructions are simple, efficient, and black-box. We realize lossy TDFs based on a variety of cryptographic assumptions, including the hardness of the decisional Diffie–Hellman (DDH) problem and the hardness of the “learning with errors” problem (which is implied by the worst-case hardness of various lattice problems). Taken together, our results resolve some long-standing open problems in cryptography. They give the first injective TDFs based on problems not directly related to integer factorization and provide the first chosen ciphertext-secure cryptosystem based solely on worst-case complexity assumptions.
We propose the first error-tolerant secure key leasing (SKL) for public-key encryption. As with SKL in prior works, our protocol consists of a lessor and lessee. In the protocol, the lessor encodes its secret key into quantum states and leases the key to the lessee. Then, the lessor can ask the lessee to return the secret key at a later point. The lessor is able to check whether the lessee has returned its key honestly. However, our protocol works even when the leased secret key is subject to noise. The lessee decrypts the ciphertext correctly, and the lessor verifies the return of the secret key correctly when the amount of error is below a certain threshold. Our improved protocol does not change the encoding of the secret key, and thus adds no overhead to the quantum information processing. Our most significant result is a framework to analyze the trade-off between robustness against error and security. We bridge the security of the error-tolerant SKL and that of the error-tolerant certified deletion with shortened codes, which is a relatively less explored concept in coding theory.
Uncloneable decryptors are encryption schemes (with classical plaintexts and ciphertexts) with the added functionality of deriving uncloneable quantum states, called decryptors, which could be used to decrypt ciphers without knowledge of the secret key (Georgiou and Zhandry, IACR'20). We study uncloneable decryptors in the computational setting and provide increasingly strong security notions which extend the various indistinguishable security notions of symmetric encryption. We show that CPA secure uncloneable bit decryptors could be instantiated from a copy protection scheme (Aaronson, CCC'09) for any balanced binary function. We introduce a new notion of flip detection security for copy protection schemes inspired by the notions of left or right security for encryption schemes, and show that it could be used to instantiate CPA secure uncloneable decryptors for messages of unrestricted length. We then show how to strengthen the CPA security of uncloneable decryptors to CCA2 security using strong EUF-CMA secure digital signatures. We show that our constructions could be instantiated relative to either the quantum oracle used in [Aar09] or the classical oracle used in (Aaronson et al., CRYPTO'21) to instantiate copy protection schemes. Our constructions are the first to achieve CPA or CCA2 security in the symmetric setting.
Lossy trapdoor functions (LTFs) were first introduced by Peikert and Waters (STOC’08). Since their introduction, lossy trapdoor functions have found numerous applications. They can be used as tools to construct important cryptographic primitives such as injective one-way trapdoor functions, chosen-ciphertext-secure public key encryptions, deterministic encryptions, et al. In this paper, we focus on the lossy trapdoor functions in the presence of continuous leakage. We introduce the new notion of updatable lossy trapdoor functions (ULTFs) and give their formal definition and security properties. Based on these, we extend the security model to the LTFs against continuous leakage when the evaluation algorithm is leakage resilient. Under the standard DDH assumption and DCR assumption, respectively, we show two explicit lossy trapdoor functions against continuous leakage in the standard model. In these schemes, using the technology of matrix kernel, the trapdoor can be refreshed at regular intervals and the adversaries can learn unbounded leakage information on the trapdoor along the whole system life. At the same time, we also show the performance of the proposed schemes compared with the known existing continuous leakage resilient lossy trapdoor functions.
In security proofs of cryptographic schemes, various kinds of assumptions have been used.Among those assumptions, the hardness of the factoring problem, called the factoring assumption, is one of the most reliable assumptions.In this dissertation, we study constructions of factoring-based cryptographic schemes.First we study a cryptographic primitive called a self-bilinear map.We define a relaxed version of a self-bilinear map, which we call a self-bilinear maps with auxiliary information (AI-SBM).We construct an AI-SBM based on the factoring assumption and the existence of indistinguishability obfuscation (iO).We also show that AI-SBM can be used for constructing cryptographic schemes including multiparty key exchange, broadcast encryption, attribute-based encryption and homomorphic signatures.As a side result, we construct a somewhat homomorphic encryption for NC 1 circuits based on the Φ-hiding assumption and the existence of iO.Second we study a cryptographic primitive called lossy trapdoor function (LTDF).We define a relaxed version of an LTDF which we call an adversary-dependent lossy trapdoor functions (ad-LTDF).Then we show that in many applications of LTDFs, we can replace LTDFs with ad-LTDFs.Moreover, we give a construction of ad-LTDFs based on the factoring assumption w.r.t.semi-smooth RSA subgroup moduli (SS moduli), which is a special type of RSA moduli introduced by Groth.As a result, we almost automatically obtain new constructions of a collision resistant hash function, CPA secure PKE scheme and DPKE scheme based on the same assumption.Especially, our DPKE scheme is the first scheme that satisfies the security notion called the PRIV security for block sources proposed by Boldyreva et al. solely based on the factoring assumption.Besides direct applications of ad-LTDFs, we construct a CCA secure PKE scheme based on the factoring assumption w.r.t.SS moduli whose ciphertext overhead is the shortest among schemes based on the same assumption.