Paper 2023/264

Public Key Encryption with Secure Key Leasing

Shweta Agrawal, IIT Madras
Fuyuki Kitagawa, NTT Social Informatics Laboratories
Ryo Nishimaki, NTT Social Informatics Laboratories
Shota Yamada, National Institute of Advanced Industrial Science and Technology
Takashi Yamakawa, NTT Social Informatics Laboratories

We introduce the notion of public key encryption with secure key leasing (PKE-SKL). Our notion supports the leasing of decryption keys so that a leased key achieves the decryption functionality but comes with the guarantee that if the quantum decryption key returned by a user passes a validity test, then the user has lost the ability to decrypt. Our notion is similar in spirit to the notion of secure software leasing (SSL) introduced by Ananth and La Placa (Eurocrypt 2021) but captures significantly more general adversarial strategies. In more detail, our adversary is not restricted to use an honest evaluation algorithm to run pirated software. Our results can be summarized as follows: 1. Definitions: We introduce the definition of PKE with secure key leasing and formalize a security notion that we call indistinguishability against key leasing attacks (IND-KLA security). We also define a one-wayness notion for PKE-SKL that we call OW-KLA security and show that an OW-KLA secure PKE-SKL scheme can be lifted to an IND-KLA secure one by using the (quantum) Goldreich-Levin lemma. 2. Constructing IND-KLA PKE with Secure Key Leasing: We provide a construction of OW-KLA secure PKE-SKL (which implies IND-KLA secure PKE-SKL as discussed above) by leveraging a PKE scheme that satisfies a new security notion that we call consistent or inconsistent security against key leasing attacks (CoIC-KLA security). We then construct a CoIC-KLA secure PKE scheme using 1-key Ciphertext-Policy Functional Encryption (CPFE) that in turn can be based on any IND-CPA secure PKE scheme. 3. Identity Based Encryption, Attribute Based Encryption and Functional Encryption with Secure Key Leasing: We provide definitions of secure key leasing in the context of advanced encryption schemes such as identity based encryption (IBE), attribute-based encryption (ABE) and functional encryption (FE). Then we provide constructions by combining the above PKE-SKL with standard IBE, ABE and FE schemes. Notably, our definitions allow the adversary to request distinguishing keys in the security game, namely, keys that distinguish the challenge bit by simply decrypting the challenge ciphertext, so long as it returns them (and they pass the validity test) before it sees the challenge ciphertext. All our constructions satisfy this stronger definition, albeit with the restriction that only a bounded number of such keys be allowed to the adversary in the IBE and ABE (but not FE) security games. Prior to our work, the notion of single decryptor encryption (SDE) has been studied in the context of PKE (Georgiou and Zhandry, Eprint 2020) and FE (Kitigawa and Nishimaki, Asiacrypt 2022) but all their constructions rely on strong assumptions including indistinguishability obfuscation. In contrast, our constructions do not require any additional assumptions, showing that PKE/IBE/ABE/FE can be upgraded to support secure key leasing for free.

Note: Added related works and a comparison with a concurrent work (2023-04-07).

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2023
Contact author(s)
shweta a @ cse iitm ac in
fuyuki kitagawa yh @ hco ntt co jp
ryo nishimaki zk @ hco ntt co jp
yamada-shota @ aist go jp
takashi yamakawa ga @ hco ntt co jp
2023-04-06: revised
2023-02-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shweta Agrawal and Fuyuki Kitagawa and Ryo Nishimaki and Shota Yamada and Takashi Yamakawa},
      title = {Public Key Encryption with Secure Key Leasing},
      howpublished = {Cryptology ePrint Archive, Paper 2023/264},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.