* [AR17] Shweta Agrawal and Alon Rosen.  Functional encryption for bounded collusions, revisited.  In Yael Kalai and Leonid Reyzin, editors, TCC 2017, Part I, volume 10677 of LNCS, pages 173–205. Springer, Heidelberg, November 2017\.
  * [AV19] Prabhanjan Ananth and Vinod Vaikuntanathan.  Optimal bounded-collusion secure functional encryption.  In Dennis Hofheinz and Alon Rosen, editors, TCC 2019, Part I, volume 11891 of LNCS, pages 174–198. Springer, Heidelberg, December 2019\.
  * [BGI+12] Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang.  On the (im)possibility of obfuscating programs.  Journal of the ACM, 59(2):6:1–6:48, 2012.
  * [BGI14] Elette Boyle, Shafi Goldwasser, and Ioana Ivan.  Functional signatures and pseudorandom functions.  In Hugo Krawczyk, editor, PKC 2014, volume 8383 of LNCS, pages 501–519. Springer, Heidelberg, March 2014.
  * [BGMZ18] James Bartusek, Jiaxin Guan, Fermi Ma, and Mark Zhandry.  Return of GGH15: Provable security against zeroizing attacks.  In Amos Beimel and Stefan Dziembowski, editors, TCC 2018, Part II, volume 11240 of LNCS, pages 544–574. Springer, Heidelberg, November 2018.
  * [BI20] Anne Broadbent and Rabib Islam.  Quantum encryption with certified deletion.  In Rafael Pass and Krzysztof Pietrzak, editors, TCC 2020, Part III, volume 12552 of LNCS, pages 92–122. Springer, Heidelberg, November 2020.
  * [BJL+21] Anne Broadbent, Stacey Jeffery, Sébastien Lord, Supartha Podder, and Aarthi Sundaram.  Secure software leasing without assumptions.  In Kobbi Nissim and Brent Waters, editors, TCC 2021, Part I, volume 13042 of LNCS, pages 90–120. Springer, Heidelberg, November 2021\.
  * [BNPW20] Nir Bitansky, Ryo Nishimaki, Alain Passelègue, and Daniel Wichs.  From cryptomania to obfustopia through secret-key functional encryption.  Journal of Cryptology, 33(2):357–405, April 2020.
  * [BS17] Shalev Ben-David and Or Sattath.  Quantum tokens for digital signatures.  Cryptology ePrint Archive, Report 2017/094, 2017.  https://eprint.iacr.org/2017/094.
  * [BS18] Zvika Brakerski and Gil Segev.  Function-private functional encryption in the private-key setting.  Journal of Cryptology, 31(1):202–225, January 2018.
  * [BSW11] Dan Boneh, Amit Sahai, and Brent Waters.  Functional encryption: Definitions and challenges.  In Yuval Ishai, editor, TCC 2011, volume 6597 of LNCS, pages 253–273. Springer, Heidelberg, March 2011.
  * [BV11] Zvika Brakerski and Vinod Vaikuntanathan.  Fully homomorphic encryption from ring-LWE and security for key dependent messages.  In Phillip Rogaway, editor, CRYPTO 2011, volume 6841 of LNCS, pages 505–524. Springer, Heidelberg, August 2011.
  * [BV18] Nir Bitansky and Vinod Vaikuntanathan.  Indistinguishability obfuscation from functional encryption.  Journal of the ACM, 65(6):39:1–39:37, 2018.
  * [BW13] Dan Boneh and Brent Waters.  Constrained pseudorandom functions and their applications.  In Kazue Sako and Palash Sarkar, editors, ASIACRYPT 2013, Part II, volume 8270 of LNCS, pages 280–300. Springer, Heidelberg, December 2013.
  * [CGO21] Michele Ciampi, Vipul Goyal, and Rafail Ostrovsky.  Threshold garbled circuits and ad hoc secure computation.  In Anne Canteaut and François-Xavier Standaert, editors, EUROCRYPT 2021, Part III, volume 12698 of LNCS, pages 64–93. Springer, Heidelberg, October 2021.
  * [CHVW19] Yilei Chen, Minki Hhan, Vinod Vaikuntanathan, and Hoeteck Wee.  Matrix PRFs: Constructions, attacks, and applications to obfuscation.  In Dennis Hofheinz and Alon Rosen, editors, TCC 2019, Part I, volume 11891 of LNCS, pages 55–80. Springer, Heidelberg, December 2019\.
  * [CLLZ21] Andrea Coladangelo, Jiahui Liu, Qipeng Liu, and Mark Zhandry.  Hidden cosets and applications to unclonable cryptography.  In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part I, volume 12825 of LNCS, pages 556–584, Virtual Event, August 2021. Springer, Heidelberg.
  * [CMP20] Andrea Coladangelo, Christian Majenz, and Alexander Poremba.  Quantum copy-protection of compute-and-compare programs in the quantum random oracle model.  Cryptology ePrint Archive, Report 2020/1194, 2020.  https://eprint.iacr.org/2020/1194.
  * [CS19] R. Joseph Connor and Max Schuchard.  Blind bernoulli trials: A noninteractive protocol for hidden-weight coin flips.  In Nadia Heninger and Patrick Traynor, editors, USENIX Security 2019, pages 1483–1500. USENIX Association, August 2019.
  * [CV21] Eric Culf and Thomas Vidick.  A monogamy-of-entanglement game for subspace coset states.  arXiv (CoRR), abs/2107.13324, 2021.
  * [DIJ+13] Angelo De Caro, Vincenzo Iovino, Abhishek Jain, Adam O’Neill, Omer Paneth, and Giuseppe Persiano.  On the achievability of simulation-based security for functional encryption.  In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part II, volume 8043 of LNCS, pages 519–535. Springer, Heidelberg, August 2013.
  * [DQV+21] Lalita Devadas, Willy Quach, Vinod Vaikuntanathan, Hoeteck Wee, and Daniel Wichs.  Succinct LWE sampling, random polynomials, and obfuscation.  In Kobbi Nissim and Brent Waters, editors, TCC 2021, Part II, volume 13043 of LNCS, pages 256–287. Springer, Heidelberg, November 2021\.
  * [GGH+16] Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters.  Candidate indistinguishability obfuscation and functional encryption for all circuits.  SIAM Journal on Computing, 45(3):882–929, 2016.
  * [GGHW17] Sanjam Garg, Craig Gentry, Shai Halevi, and Daniel Wichs.  On the implausibility of differing-inputs obfuscation and extractable witness encryption with auxiliary input.  Algorithmica, 79(4):1353–1373, 2017.
  * [GGLW21] Rachit Garg, Rishab Goyal, George Lu, and Brent Waters.  Dynamic collusion bounded functional encryption from identity-based encryption.  Cryptology ePrint Archive, Report 2021/847, 2021.  https://eprint.iacr.org/2021/847.
  * [GGM86] Oded Goldreich, Shafi Goldwasser, and Silvio Micali.  How to construct random functions.  Journal of the ACM, 33(4):792–807, 1986.
  * [GKP+13] Shafi Goldwasser, Yael Tauman Kalai, Raluca A. Popa, Vinod Vaikuntanathan, and Nickolai Zeldovich.  How to run turing machines on encrypted data.  In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part II, volume 8043 of LNCS, pages 536–553. Springer, Heidelberg, August 2013.
  * [GKW17] Rishab Goyal, Venkata Koppula, and Brent Waters.  Lockable obfuscation.  In Chris Umans, editor, 58th FOCS, pages 612–621. IEEE Computer Society Press, October 2017.
  * [GVW12] Sergey Gorbunov, Vinod Vaikuntanathan, and Hoeteck Wee.  Functional encryption with bounded collusions via multi-party computation.  In Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012, volume 7417 of LNCS, pages 162–179. Springer, Heidelberg, August 2012\.
  * [GZ20] Marios Georgiou and Mark Zhandry.  Unclonable decryption keys.  Cryptology ePrint Archive, Report 2020/877, 2020.  https://eprint.iacr.org/2020/877.
  * [HMNY21] Taiga Hiroka, Tomoyuki Morimae, Ryo Nishimaki, and Takashi Yamakawa.  Quantum encryption with certified deletion, revisited: Public key, attribute-based, and classical communication.  In Mehdi Tibouchi and Huaxiong Wang, editors, ASIACRYPT 2021, Part I, volume 13090 of LNCS, pages 606–636. Springer, Heidelberg, December 2021.
  * [JKMS20] Aayush Jain, Alexis Korb, Nathan Manohar, and Amit Sahai.  Amplifying the security of functional encryption, unconditionally.  In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part I, volume 12170 of LNCS, pages 717–746. Springer, Heidelberg, August 2020.
  * [JLS21] Aayush Jain, Huijia Lin, and Amit Sahai.  Indistinguishability obfuscation from well-founded assumptions.  In Samir Khuller and Virginia Vassilevska Williams, editors, STOC 2021, pages 60–73. ACM, 2021.
  * [JLS22] Aayush Jain, Huijia Lin, and Amit Sahai.  Indistinguishability obfuscation from LPN over $\mathbb{F}_{p}$, DLIN, and PRGs in ${NC}^{0}$.  In Orr Dunkelman and Stefan Dziembowski, editors, EUROCRYPT 2022, Part I, volume 13275 of LNCS, pages 670–699. Springer, Heidelberg, May / June 2022.
  * [KLM+18] Sam Kim, Kevin Lewi, Avradip Mandal, Hart Montgomery, Arnab Roy, and David J. Wu.  Function-hiding inner product encryption is practical.  In Dario Catalano and Roberto De Prisco, editors, SCN 18, volume 11035 of LNCS, pages 544–562. Springer, Heidelberg, September 2018\.
  * [KNT21] Fuyuki Kitagawa, Ryo Nishimaki, and Keisuke Tanaka.  Simple and generic constructions of succinct functional encryption.  Journal of Cryptology, 34(3):25, July 2021.
  * [KNT22] Fuyuki Kitagawa, Ryo Nishimaki, and Keisuke Tanaka.  Obfustopia built on secret-key functional encryption.  J. Cryptol., 35(3):19, 2022.
  * [KNY21] Fuyuki Kitagawa, Ryo Nishimaki, and Takashi Yamakawa.  Secure software leasing from standard assumptions.  In Kobbi Nissim and Brent Waters, editors, TCC 2021, Part I, volume 13042 of LNCS, pages 31–61. Springer, Heidelberg, November 2021\.
  * [KPTZ13] Aggelos Kiayias, Stavros Papadopoulos, Nikos Triandopoulos, and Thomas Zacharias.  Delegatable pseudorandom functions and applications.  In Ahmad-Reza Sadeghi, Virgil D. Gligor, and Moti Yung, editors, ACM CCS 2013, pages 669–684. ACM Press, November 2013.
  * [MW16] Pratyay Mukherjee and Daniel Wichs.  Two round multiparty computation via multi-key FHE.  In Marc Fischlin and Jean-Sébastien Coron, editors, EUROCRYPT 2016, Part II, volume 9666 of LNCS, pages 735–763. Springer, Heidelberg, May 2016.
  * [NNL01] Dalit Naor, Moni Naor, and Jeffery Lotspiech.  Revocation and tracing schemes for stateless receivers.  In Joe Kilian, editor, CRYPTO 2001, volume 2139 of LNCS, pages 41–62. Springer, Heidelberg, August 2001.
  * [NP01] Moni Naor and Benny Pinkas.  Efficient trace and revoke schemes.  In Yair Frankel, editor, FC 2000, volume 1962 of LNCS, pages 1–20. Springer, Heidelberg, February 2001.
  * [NWZ16] Ryo Nishimaki, Daniel Wichs, and Mark Zhandry.  Anonymous traitor tracing: How to embed arbitrary information in a key.  In Marc Fischlin and Jean-Sébastien Coron, editors, EUROCRYPT 2016, Part II, volume 9666 of LNCS, pages 388–419. Springer, Heidelberg, May 2016.
  * [RPB+19] Théo Ryffel, David Pointcheval, Francis R. Bach, Edouard Dufour-Sans, and Romain Gay.  Partially encrypted deep learning using functional encryption.  In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett, editors, NeurIPS 2019, pages 4519–4530, 2019.
  * [SS10] Amit Sahai and Hakan Seyalioglu.  Worry-free encryption: functional encryption with public keys.  In Ehab Al-Shaer, Angelos D. Keromytis, and Vitaly Shmatikov, editors, ACM CCS 2010, pages 463–472. ACM Press, October 2010.
  * [SSW12] Amit Sahai, Hakan Seyalioglu, and Brent Waters.  Dynamic credentials and ciphertext delegation for attribute-based encryption.  In Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012, volume 7417 of LNCS, pages 199–217. Springer, Heidelberg, August 2012\.
  * [SW05] Amit Sahai and Brent R. Waters.  Fuzzy identity-based encryption.  In Ronald Cramer, editor, EUROCRYPT 2005, volume 3494 of LNCS, pages 457–473. Springer, Heidelberg, May 2005.
  * [SW21] Amit Sahai and Brent Waters.  How to use indistinguishability obfuscation: Deniable encryption, and more.  SIAM J. Comput., 50(3):857–908, 2021.
  * [WZ17] Daniel Wichs and Giorgos Zirdelis.  Obfuscating compute-and-compare programs under LWE.  In Chris Umans, editor, 58th FOCS, pages 600–611. IEEE Computer Society Press, October 2017.
  * [Zha20] Mark Zhandry.  Schrödinger’s pirate: How to trace a quantum decoder.  In Rafael Pass and Krzysztof Pietrzak, editors, TCC 2020, Part III, volume 12552 of LNCS, pages 61–91. Springer, Heidelberg, November 2020.

##  Appendix A CPA-Style Anti-Piracy Security Notions

We introduce the CPA-style anti-piracy security for SDE.

###### Definition A.1 (Anti-Piracy Security, CPA-Style [CLLZ21]).

We consider the CPA-style anti-piracy game
$\mathsf{Exp}_{\mathsf{SDE},\mathpzc{A}}^{\mathsf{anti}\mbox{-}\mathsf{piracy}\mbox{-}\mathsf{cpa}}(\lambda)$
between the challenger and an adversary $\mathpzc{A}$ below.

  1. 1.

The challenger generates
$(\mathsf{pk},\mathsf{sk})\leftarrow\mathsf{Setup}(1^{\lambda})$.

  2. 2.

The challenger generates $\mathpzc{sk}\leftarrow\mathpzc{QKG}(\mathsf{sk})$
and sends $(\mathsf{pk},\mathpzc{sk})$ to $\mathpzc{A}$.

  3. 3.

$\mathpzc{A}$ outputs $(m_{0},m_{1})$ and two (possibly entangled) quantum
decryptors
$\mathpzc{D}_{1}=(\mathpzc{q}[{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}{\mathsf{R}}}_{1}],\boldsymbol{U}_{1})$
and
$\mathpzc{D}_{2}=(\mathpzc{q}[{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}{\mathsf{R}}}_{2}],\boldsymbol{U}_{2})$,
where $m_{0}\neq m_{1}$, $\absolutevalue{m_{0}}=\absolutevalue{m_{1}}$,
$\mathpzc{q}$ is a quantum state over registers
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>and
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>and $\boldsymbol{U}_{1}$ and $\boldsymbol{U}_{2}$ are general quantum
circuits.

  4. 4.

The challenger chooses
$\mathsf{coin}_{1},\mathsf{coin}_{2}\leftarrow\\{0,1\\}$, and generates
$\mathsf{ct}_{1}\leftarrow\mathsf{Enc}(\mathsf{pk},m_{\mathsf{coin}_{1}})$ and
$\mathsf{ct}_{2}\leftarrow\mathsf{Enc}(\mathsf{pk},m_{\mathsf{coin}_{2}})$.
The challenger runs $m_{i}^{\prime}\leftarrow\mathpzc{D}_{i}(\mathsf{ct}_{i})$
for $i\in\\{1,2\\}$. If $m_{i}^{\prime}=m_{\mathsf{coin}_{i}}$ for
$i\in\\{1,2\\}$, the challenger outputs $1$, otherwise outputs $0$.

We say that $\mathsf{SDE}$ is $\gamma$-anti-piracy secure if for any QPT
adversary $\mathpzc{A}$, it satisfies that

$\Pr[\mathsf{Exp}_{\mathsf{SDE},\mathpzc{A}}^{\mathsf{anti}\mbox{-}\mathsf{piracy}\mbox{-}\mathsf{cpa}}(\lambda)=1]\leq\frac{1}{2}+\gamma(\lambda)+{\mathsf{negl}}(\lambda).$

###### Theorem A.2 ([CLLZ21]).

If an SDE scheme satisfies strong $\gamma$-anti-piracy security, it also
satisfies $\gamma$-anti-piracry security (in the CPA-style).

We can define a similar security notion for SDFE.

###### Definition A.3 (Anti-Piracy Security for FE, CPA-Style).

We consider the CPA-style anti-piracy game for FE
$\mathsf{Exp}_{\mathsf{SDFE},\mathpzc{A}}^{\mathsf{anti}\mbox{-}\mathsf{piracy}\mbox{-}\mathsf{cpa}}(\lambda)$
between the challenger and an adversary $\mathpzc{A}$ below.

  1. 1.

The challenger generates
$(\mathsf{pk},\mathsf{msk})\leftarrow\mathsf{Setup}(1^{\lambda})$ and sends
$\mathsf{pk}$ to $\mathpzc{A}$.

  2. 2.

$\mathpzc{A}$ sends key queries $f_{i}$ to the challenger and receives
$\mathpzc{sk}_{f_{i}}\leftarrow\mathpzc{QKG}(\mathsf{sk}_{f_{i}})$ where
$\mathsf{sk}_{f_{i}}\leftarrow\mathsf{KG}(\mathsf{msk},f_{i})$.

  3. 3.

At some point $\mathpzc{A}$ sends a challenge query $f^{*}$ to the challenger
and receives
$\mathpzc{sk}_{f^{*}}\leftarrow\mathpzc{QKG}(\mathsf{msk},f^{\ast})$.

  4. 4.

Again, $\mathpzc{A}$ sends $f_{i}$ to the challenger and receives
$\mathpzc{sk}_{f_{i}}\leftarrow\mathpzc{QKG}(\mathsf{sk}_{f_{i}})$ where
$\mathsf{sk}_{f_{i}}\leftarrow\mathsf{KG}(\mathsf{msk},f_{i})$.

  5. 5.

$\mathpzc{A}$ outputs $(x_{0},x_{1})$ and two (possibly entangled) quantum
decryptors
$\mathpzc{D}_{1}=(\mathpzc{q}[{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}{\mathsf{R}}}_{1}],\boldsymbol{U}_{1})$
and
$\mathpzc{D}_{2}=(\mathpzc{q}[{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}{\mathsf{R}}}_{2}],\boldsymbol{U}_{2})$,
where $\forall i\ f_{i}(x_{0})=f_{i}(x_{1})$, $f^{*}(x_{0})\neq f^{*}(x_{1})$,
$\mathpzc{q}$ is a quantum state over registers
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>and
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>and $\boldsymbol{U}_{1}$ and $\boldsymbol{U}_{2}$ are general quantum
circuits.

  6. 6.

The challenger chooses
$\mathsf{coin}_{1},\mathsf{coin}_{2}\leftarrow\\{0,1\\}$, and generates
$\mathsf{ct}_{1}\leftarrow\mathsf{Enc}(\mathsf{pk},x_{\mathsf{coin}_{1}})$ and
$\mathsf{ct}_{2}\leftarrow\mathsf{Enc}(\mathsf{pk},x_{\mathsf{coin}_{2}})$.
The challenger runs
$\mathsf{coin}_{k}^{\prime}\leftarrow\mathpzc{D}_{k}(\mathsf{ct}_{k})$ for
$k\in\\{1,2\\}$. If $\mathsf{coin}_{k}^{\prime}=\mathsf{coin}_{k}$ for
$k\in\\{1,2\\}$, the challenger outputs $1$, otherwise outputs $0$.

We say that $\mathsf{SDFE}$ is $\gamma$-anti-piracy secure if for any QPT
adversary $\mathpzc{A}$, it satisfies that

$\Pr[\mathsf{Exp}_{\mathsf{SDFE},\mathpzc{A}}^{\mathsf{anti}\mbox{-}\mathsf{piracy}\mbox{-}\mathsf{cpa}}(\lambda)=1]\leq\frac{1}{2}+\gamma(\lambda)+{\mathsf{negl}}(\lambda).$

If $\mathpzc{A}$ can send only the challenge query $f^{\ast}$ during the
experiment, we say that $\mathsf{SDFE}$ is challenge-only $\gamma$-anti-piracy
secure.

We can also define the CPA-style anti-piracy for the predictor-based quantum
decryptors as Definition A.1. That is, $\mathpzc{D}_{i}$ outputs
$f^{\ast}(x_{\mathsf{coin}_{i}})$ for $i\in\\{1,2\\}$ instead of
$\mathsf{coin}_{i}$. We omit the variation.

###### Theorem A.4.

If an SDFE scheme satisfies strong $\gamma$-anti-piracy security, it also
satisfies $\gamma$-anti-piracy security in the CPA-style.

The proof of this theorem is almost the same as that of Theorem A.2, so we
omit it to avoid replication.

##  Appendix B Adaptive and Simulation-based Security for Secure Key Leasing

This section presents how to upgrade FE with secure key leasing security.

###  B.1 Adaptive Security for Secure Key Leasing

Ananth et al. [ABSV15] present transformations from selectively secure FE into
adaptively secure FE. Almost the same transformation works for FE with secure
key leasing. The adaptive lessor security for SKFE with SKL is almost the same
as Definition 3.2 except that $\mathpzc{A}$ declares
$(x_{0}^{\ast},x_{1}^{\ast})$ when $\mathpzc{A}$ sends $\mathsf{cert}$ to the
challenger and we separate the key oracle into two types. The formal
definition is as follows.

###### Definition B.1 (Adaptive Lessor Security).

We say that $\mathsf{SKFE\textrm{-}SKL}$ is an adaptively lessor secure SKFE-
SKL scheme for $\mathcal{X},\mathcal{Y}$, and $\mathcal{F}$, if it satisfies
the following requirement, formalized from the experiment
$\mathsf{Exp}_{\mathpzc{A},\mathsf{SKFE\textrm{-}SKL}}^{\mathsf{ada}\mbox{-}\mathsf{lessor}}(1^{\lambda},\mathsf{coin})$
between an adversary $\mathpzc{A}$ and a challenger:

  1. 1.

At the beginning, $\mathpzc{A}$ sends $1^{q+q^{\ast}}$ to the challenger. The
challenger runs
$\mathsf{msk}\leftarrow\mathsf{Setup}(1^{\lambda},1^{q+q^{\ast}})$. Throughout
the experiment, $\mathpzc{A}$ can access the following oracles.

$O_{\mathtt{\mathsf{Enc}}}(x)$:

Given $x$, it returns $\mathsf{Enc}(\mathsf{msk},x)$.

$O_{\mathtt{\mathpzc{KG}}}(f,1^{n})$:

Given $(f,1^{n})$, it generates
$(\mathpzc{fsk},\mathsf{vk})\leftarrow\mathpzc{KG}(\mathsf{msk},f,1^{n})$, and
sends $\mathpzc{fsk}$ to $\mathpzc{A}$. $\mathpzc{A}$ can access this oracle
at most $q$ times.

  2. 2.

$\mathpzc{A}$ can access the following oracles before $\mathpzc{A}$ declares
the challenge plaintexts.

$O_{\mathtt{\mathpzc{KG}}}^{\ast}(f^{\ast},1^{n^{\ast}})$:

Given $(f^{\ast},1^{n^{\ast}})$, it generates
$(\mathpzc{fsk}^{\ast},\mathsf{vk}^{\ast})\leftarrow\mathpzc{KG}(\mathsf{msk},f^{\ast},1^{n^{\ast}})$,
adds $(f^{\ast},1^{n^{\ast}},\mathsf{vk}^{\ast},\bot)$ to
$L_{\mathtt{\mathpzc{KG}}}$, and sends $\mathpzc{fsk}^{\ast}$ to
$\mathpzc{A}$. $\mathpzc{A}$ can access this oracle at most $q^{\ast}$ times.

$O_{\mathtt{\mathsf{Vrfy}}}(f^{\ast},\mathsf{cert}^{\ast})$:

Given $(f^{\ast},\mathsf{cert}^{\ast})$, it finds an entry
$(f^{\ast},1^{n^{\ast}},\mathsf{vk}^{\ast},M)$ from
$L_{\mathtt{\mathpzc{KG}}}$. (If there is no such entry, it returns $\bot$.)
If $\top=\mathsf{Vrfy}(\mathsf{vk}^{\ast},\mathsf{cert}^{\ast})$ and the
number of queries to $O_{\mathtt{\mathsf{Enc}}}$ at this point is less than
$n^{\ast}$, it returns $\top$ and updates the entry into
$(f^{\ast},1^{n^{\ast}},\mathsf{vk}^{\ast},\top)$. Otherwise, it returns
$\bot$.

  3. 3.

When $\mathpzc{A}$ sends $(x_{0}^{\ast},x_{1}^{\ast})$ to receive the
challenge ciphertext, if there exists
$(f^{\ast},1^{n^{\ast}},\mathsf{vk}^{\ast},\bot)$ in
$L_{\mathtt{\mathpzc{KG}}}$, or $O_{\mathtt{\mathpzc{KG}}}$ received
$(f,1^{n})$ such that $f(x_{0}^{\ast})\neq f(x_{1}^{\ast})$, the challenger
outputs $0$ as the final output of this experiment. Otherwise, the challenger
generates
$\mathsf{ct}^{*}\leftarrow\mathsf{Enc}(\mathsf{msk},x_{\mathsf{coin}}^{*})$
and sends $\mathsf{ct}^{*}$ to $\mathpzc{A}$. Hereafter,
$O_{\mathtt{\mathpzc{KG}}}$ rejects a query $(f,1^{n})$ such that
$f(x_{0}^{\ast})\neq f(x_{1}^{\ast})$ and $\mathpzc{A}$ cannot access
$O_{\mathtt{\mathpzc{KG}}}^{\ast}$ and $O_{\mathtt{\mathsf{Vrfy}}}$.

  4. 4.

$\mathpzc{A}$ outputs a guess $\mathsf{coin}^{\prime}$ for $\mathsf{coin}$.
The challenger outputs $\mathsf{coin}^{\prime}$ as the final output of the
experiment.

For any QPT $\mathpzc{A}$, it holds that

$\displaystyle\mathsf{Adv}_{\mathsf{SKFE\textrm{-}SKL},\mathpzc{A}}^{\mathsf{ada}\mbox{-}\mathsf{lessor}}(\lambda)\coloneqq\absolutevalue{\Pr[\mathsf{Exp}_{\mathsf{SKFE\textrm{-}SKL},\mathpzc{A}}^{\mathsf{ada}\mbox{-}\mathsf{lessor}}(1^{\lambda},0)=1]-\Pr[\mathsf{Exp}_{\mathsf{SKFE\textrm{-}SKL},\mathpzc{A}}^{\mathsf{ada}\mbox{-}\mathsf{lessor}}(1^{\lambda},1)=1]}\leq{\mathsf{negl}}(\lambda).$
(49)

######  Remark B.2.

The definition above considers two key oracles $O_{\mathtt{\mathpzc{KG}}}$ and
$O_{\mathtt{\mathpzc{KG}}}^{\ast}$ unlike Definition 3.2 to distinguish a
functional decryption key which is deleted from one which is not deleted. The
oracle $O_{\mathtt{\mathpzc{KG}}}^{\ast}$ accepts a query
$(f^{\ast},1^{n^{\ast}})$ such that $f^{\ast}(x_{0}^{\ast})\neq
f^{\ast}(x_{1}^{\ast})$. We need to distinguish these two types of queries
since we need to know whether $f(x_{0}^{\ast})=f(x_{1}^{\ast})$ or not when an
adversary sends a query in the security proof of the construction below. It is
not clear whether we can achieve a stronger adaptive security where
adversaries access a single key generation oracle as Definition 3.2. We leave
it as an open question.

We construct an adaptively secure SKFE scheme with secure key leasing
$\mathsf{SKFE\textrm{-}SKL}=(\mathsf{Setup},\mathpzc{KG},\mathsf{Enc},\allowbreak\mathpzc{Dec},\mathpzc{Cert},\mathsf{Vrfy})$
using the following tools:

  * •

A selectively secure SKFE scheme with secure key leasing
$\mathsf{Sel}.\mathsf{SKFE}=\mathsf{Sel}.(\mathsf{Setup},\allowbreak\mathpzc{KG},\mathsf{Enc},\mathpzc{Dec},\allowbreak\mathpzc{Cert},\mathsf{Vrfy})$.

  * •

An adaptively single-ciphertext secure SKFE scheme
$\mathsf{1CT}.\mathsf{SKFE}=\mathsf{1CT}.(\mathsf{Setup},\allowbreak\mathsf{KG},\mathsf{Enc},\mathsf{Dec})$.

  * •

A pseudorandom-secure SKE scheme
$\mathsf{SKE}=\mathsf{SKE}.(\mathsf{E},\mathsf{D})$.

  * •

A PRF $\mathsf{F}$.

Let $\ell_{1}$ and $\ell_{2}$ be the length of $\mathsf{SKE}$ ciphertexts and
the length of random tags, respectively. The definition of adaptive lessor
security is a natural adaptive variant of Definition 3.2. The description of
$\mathsf{SKFE\textrm{-}SKL}$ is as follows.

$\mathsf{Setup}(1^{\lambda})$:

  * •

Generate
$\mathsf{sel}.\mathsf{msk}\leftarrow\mathsf{Sel}.\mathsf{Setup}(1^{\lambda})$.

  * •

Output $\mathsf{msk}\coloneqq\mathsf{sel}.\mathsf{msk}$.

$\mathpzc{KG}(\mathsf{msk},f,1^{n})$:

  * •

Parse $\mathsf{sel}.\mathsf{msk}\leftarrow\mathsf{msk}$.

  * •

Generate $\mathsf{ct}_{\mathsf{ske}}\leftarrow\\{0,1\\}^{\ell_{1}}$ and choose
$\tau\leftarrow\\{0,1\\}^{\ell_{2}}$.

  * •

Compute
$(\mathsf{sel}.\mathpzc{sk}_{G},\mathsf{sel}.\mathsf{vk})\leftarrow\mathsf{Sel}.\mathpzc{KG}(\mathsf{sel}.\mathsf{msk},G[f,\mathsf{ct}_{\mathsf{ske}},\tau],1^{n})$,
where the circuit $G$ is described in Figure 9.

  * •

Output $\mathpzc{sk}_{f}\coloneqq\mathsf{sel}.\mathpzc{sk}_{G}$ and
$\mathsf{vk}\coloneqq\mathsf{sel}.\mathsf{vk}$.

$\mathsf{Enc}(\mathsf{msk},x)$:

  * •

Parse $\mathsf{sel}.\mathsf{msk}\leftarrow\mathsf{msk}$.

  * •

Generate
$\mathsf{1ct}.\mathsf{msk}\leftarrow\mathsf{1CT}.\mathsf{Setup}(1^{\lambda})$
and choose $\mathsf{K}\leftarrow\\{0,1\\}^{\lambda}$.

  * •

Generate
$\mathsf{1ct}.\mathsf{ct}\leftarrow\mathsf{1CT}.\mathsf{Enc}(\mathsf{1ct}.\mathsf{msk},x)$.

  * •

Generate
$\mathsf{sel}.\mathsf{ct}\leftarrow\mathsf{Sel}.\mathsf{Enc}(\mathsf{sel}.\mathsf{msk},(\mathsf{1ct}.\mathsf{msk},\mathsf{K},0^{\lambda},0))$.

  * •

Output
$\mathsf{ct}_{x}\coloneqq(\mathsf{1ct}.\mathsf{ct},\mathsf{sel}.\mathsf{ct})$.

$\mathpzc{Dec}(\mathpzc{sk}_{f},\mathsf{ct}_{x})$:

  * •

Parse $\mathsf{sel}.\mathpzc{sk}_{G}\leftarrow\mathpzc{sk}_{f}$ and
$(\mathsf{1ct}.\mathsf{ct},\mathsf{sel}.\mathsf{ct})\leftarrow\mathsf{ct}_{x}$.

  * •

Compute
$\mathsf{1ct}.\mathsf{sk}_{f}\leftarrow\mathsf{Sel}.\mathpzc{Dec}(\mathsf{sel}.\mathpzc{sk}_{G},\mathsf{sel}.\mathsf{ct})$.

  * •

Output
$y\leftarrow\mathsf{1CT}.\mathsf{Dec}(\mathsf{1ct}.\mathsf{sk}_{f},\mathsf{1ct}.\mathsf{ct})$.

$\mathpzc{Cert}(\mathpzc{sk}_{f})$:

  * •

Parse $\mathsf{sel}.\mathpzc{sk}_{f}\leftarrow\mathpzc{sk}_{f}$.

  * •

Output
$\mathsf{cert}\coloneqq\mathsf{sel}.\mathsf{cert}\leftarrow\mathsf{Sel}.\mathpzc{Cert}(\mathsf{sel}.\mathpzc{sk}_{f})$.

$\mathsf{Vrfy}(\mathsf{vk},\mathsf{cert})$:

  * •

Parse $\mathsf{sel}.\mathsf{vk}=\mathsf{vk}$ and
$\mathsf{sel}.\mathsf{cert}=\mathsf{cert}$.

  * •

Output
$\top/\bot\leftarrow\mathsf{Sel}.\mathsf{Vrfy}(\mathsf{sel}.\mathsf{vk},\mathsf{sel}.\mathsf{cert})$.

Key Generation Circuit
$G[f,\mathsf{ct}_{\mathsf{ske}},\tau](\mathsf{1ct}.\mathsf{msk},\mathsf{K},K_{\mathsf{ske}},\beta)$
Hardwired: function $f$, SKE ciphertext $\mathsf{ct}_{\mathsf{ske}}$, tag
$\tau$. Input: master secret key $\mathsf{1ct}.\mathsf{msk}$, PRF key
$\mathsf{K}$, SKE secret key $K_{\mathsf{ske}}$, bit $\beta$. 1. If $\beta=0$,
output
$\mathsf{1ct}.\mathsf{sk}_{f}\leftarrow\mathsf{1CT}.\mathsf{KG}(\mathsf{1ct}.\mathsf{msk},f;\mathsf{F}_{\mathsf{K}}(\tau))$.
2. Else, output
$\mathsf{SKE}.\mathsf{D}(K_{\mathsf{ske}},\mathsf{ct}_{\mathsf{ske}})$.

Figure 9: Description of $G[f,\mathsf{ct}_{\mathsf{ske}},\tau]$.

We emphasize that $\mathsf{1CT}.\mathsf{SKFE}$ is a classical standard SKFE
scheme, and $\mathsf{1CT}.\mathsf{KG}$ is a classical algorithm. This does not
spoil the lessor security of $\mathsf{Sel}.\mathsf{SKFE}$ because
$\mathsf{1ct}.\mathsf{sk}_{f}$ generated by the circuit $G$ depends on
$\mathsf{1ct}.\mathsf{msk}$ and $\mathsf{K}$ from the encryption algorithm and
$\tau$ from the key generation algorithm. At the decryption phase, we can
obtain $\mathsf{1ct}.\mathsf{sk}_{f}$ under $\mathsf{1ct}.\mathsf{msk}$ from
$\mathsf{Sel}.\mathpzc{KG}(\mathsf{sel}.\mathsf{msk},G,1^{n})$ and

$(\mathsf{1CT}.\mathsf{Enc}(\mathsf{1ct}.\mathsf{msk},x),\mathsf{Sel}.\mathsf{Enc}(\mathsf{sel}.\mathsf{msk},(\mathsf{1ct}.\mathsf{msk},\mathsf{K},0^{\lambda},0))).$

We can keep a copy of $\mathsf{1ct}.\mathsf{sk}_{f}$. However, it does not
help us to decrypt another ciphertext

$(\mathsf{1CT}.\mathsf{Enc}(\mathsf{1ct}.\mathsf{msk}^{\prime},x^{\prime}),\mathsf{Sel}.\mathsf{Enc}(\mathsf{sel}.\mathsf{msk},(\mathsf{1ct}.\mathsf{msk}^{\prime},\mathsf{K}^{\prime},0^{\lambda},0))).$

Note that $\mathsf{1ct}.\mathsf{msk}$ is freshly generated at the encryption
phase. That is, a functional decryption key $\mathsf{1ct}.\mathsf{sk}_{f}$ is
specific to only one pair of $\mathpzc{sk}_{f}$ and $\mathsf{ct}_{x}$

Thus, after we securely delete $\mathpzc{sk}_{f}$ by using the deletion
algorithm $\mathsf{Sel}.\mathpzc{Cert}$ of $\mathsf{Sel}.\mathsf{SKFE}$, we
can no longer decrypt a fresh ciphertext generated after the deletion. Since
the deletion power is preserved, we can upgrade the selective security of
$\mathsf{Sel}.\mathsf{SKFE}$ to adaptive security by leveraging the adaptive
security of $\mathsf{1CT}.\mathsf{SKFE}$ as the transformation by Ananth et
al. [ABSV15].

###### Theorem B.3.

If $\mathsf{Sel}.\mathsf{SKFE}$ is selectively lessor secure,
$\mathsf{1CT}.\mathsf{SKFE}$ is adaptively single-ciphertext secure and
collusion-resistant, $\mathsf{SKE}$ is pseudorandom-secure, and $\mathsf{F}$
is a pseudorandom function, $\mathsf{SKFE\textrm{-}SKL}$ above is adaptively
lessor secure.

Since the proof is almost the same as that by Ananth et al. [ABSV15, Theorem 4
in the eprint ver.], we omit it to avoid the replication. Note that the
reduction needs to embed
$\mathsf{1ct}.\mathsf{sk}_{f}\leftarrow\mathsf{1CT}.\mathsf{KG}(\mathsf{1ct}.\mathsf{msk},f;\mathsf{F}_{\mathsf{K}}(\tau))$
into $\mathsf{ct}_{\mathsf{ske}}$ for a key query such that
$f(x_{0}^{\ast})=f(x_{1}^{\ast})$, but $\mathsf{ct}_{\mathsf{ske}}$ should be
a junk ciphertext for a key query such that $f(x_{0}^{\ast})\neq
f(x_{1}^{\ast})$. The reduction knows which simulation-way is correct since
Definition B.1 distinguishes two types of queries.

###  B.2 Simulation-based Security for Secure Key Leasing

Although we present indistinguishability-based security definitions for SKFE
with secure key leasing in Section 3, we can also consider simulation-based
security definitions for SKFE with secure key leasing. We present the
definition of adaptive lessor simulation-security.

###### Definition B.4 (Adaptive Lessor Simulation-security).

Let $\mathsf{SKFE\textrm{-}SKL}$ be an SKFE scheme with secure key leasing.
For a stateful QPT adversary
$\mathpzc{A}=(\mathpzc{A}_{1},\mathpzc{A}_{2},\mathpzc{A}_{3})$ and a stateful
QPT Simulator $\mathpzc{S}=(\mathpzc{SEnc},\mathpzc{SKG})$, we consider the
two experiments described in Figure 10, where

  * •

$\mathpzc{A}$ is allowed to make total at most $q$ queries to
$\mathpzc{KG}(\mathsf{msk},\cdot,\cdot)$ (resp.
$\mathpzc{KG}(\mathsf{msk},\cdot,\cdot)$ and
$O_{\mathtt{\mathpzc{SKG}}}(\cdot,\cdot)$) in
$\mathsf{Real}^{\mathsf{ad}\textrm{-}\mathsf{sim}}_{\mathsf{SKFE\textrm{-}SKL},\mathpzc{A}}(\lambda)$
(resp.
$\mathsf{Sim}^{\mathsf{ad}\textrm{-}\mathsf{sim}}_{\mathsf{SKFE\textrm{-}SKL},\mathpzc{A},\mathpzc{S}}(\lambda)$),

  * •

$\mathpzc{A}$ is allowed to make total at most $q^{\ast}$ queries to
$O_{\mathtt{\mathpzc{KG}}}^{\ast}(\cdot,\cdot)$, which is the same as
$\mathpzc{KG}(\mathsf{msk},\cdot,\cdot)$ except that it also adds
$(f^{\ast},1^{n^{\ast}},\mathsf{vk}^{\ast},\bot)$ to
$L_{\mathtt{\mathpzc{KG}}}$ when it is invoked,

  * •

$\mathpzc{A}$ is allowed to make queries to
$O_{\mathtt{\mathsf{Vrfy}}}(\cdot,\cdot)$, which is given
$(f^{\ast},\mathsf{cert}^{\ast})$, it finds an entry
$(f^{\ast},1^{n^{\ast}},\mathsf{vk}^{\ast},M)$ from
$L_{\mathtt{\mathpzc{KG}}}$, and does the following: If there is no such
entry, it returns $\bot$. If
$\top=\mathsf{Vrfy}(\mathsf{vk}^{\ast},\mathsf{cert}^{\ast})$ and the number
of queries to $O_{\mathtt{\mathsf{Enc}}}$ at this point is less than
$n^{\ast}$, it returns $\top$ and updates the entry into
$(f^{\ast},1^{n^{\ast}},\mathsf{vk}^{\ast},\top)$. Otherwise, it returns
$\bot$,

  * •

$O_{\mathtt{\mathpzc{SKG}}}(f,1^{n})=\mathpzc{SKG}(\mathsf{st},f,1^{n},f(x^{*}))$.

$\mathsf{Real}^{\mathsf{ad}\textrm{-}\mathsf{sim}}_{\mathsf{SKFE\textrm{-}SKL},\mathpzc{A}}(\lambda)$ | $\mathsf{Sim}^{\mathsf{ad}\textrm{-}\mathsf{sim}}_{\mathsf{SKFE\textrm{-}SKL},\mathpzc{A},\mathpzc{S}}(\lambda)$
---|---
1. |  $1^{q+q^{\ast}}\leftarrow\mathpzc{A}_{1}(1^{\lambda})$ | 1. |  $1^{q+q^{\ast}}\leftarrow\mathpzc{A}_{1}(1^{\lambda})$
2. |  $\mathsf{msk}\leftarrow\mathsf{Setup}(1^{\lambda},1^{q+q^{\ast}})$ | 2. |  $\mathsf{msk}\leftarrow\mathsf{Setup}(1^{\lambda},1^{q+q^{\ast}})$
3. |  $x^{\ast}\leftarrow\mathpzc{A}_{2}^{\mathsf{Enc}(\mathsf{msk},\cdot),\mathpzc{KG}(\mathsf{msk},\cdot,\cdot),O_{\mathtt{\mathpzc{KG}}}^{\ast}(\cdot,\cdot),O_{\mathtt{\mathsf{Vrfy}}}(\cdot,\cdot)}$ | 3. |  $x^{\ast}\leftarrow\mathpzc{A}_{2}^{\mathsf{Enc}(\mathsf{msk},\cdot),\mathpzc{KG}(\mathsf{msk},\cdot,\cdot),O_{\mathtt{\mathpzc{KG}}}^{\ast}(\cdot,\cdot),O_{\mathtt{\mathsf{Vrfy}}}(\cdot,\cdot)}$
4. |  Output $0$ if there exists $(f^{\ast},1^{n^{\ast}},\mathsf{vk}^{\ast},\bot)$ in $L_{\mathtt{\mathpzc{KG}}}$. Otherwise, go to the next step. | 4. |  Output $0$ if there exists $(f^{\ast},1^{n^{\ast}},\mathsf{vk}^{\ast},\bot)$ in $L_{\mathtt{\mathpzc{KG}}}$. Otherwise, go to the next step.
5. |  | 5. |  Let $\mathcal{Q}$ be the query/answer list for $\mathsf{Enc}(\mathsf{msk},\cdot)$
6. |  | 6. |  Let $(f_{i},1^{n_{i}})_{i\in[q]}$ be the queries for $\mathsf{KG}(\mathsf{msk},\cdot,\cdot)$
7. |  | 7. |  $y_{i}:=f_{i}(x^{*})$ for every $i\in[q]$
8. |  $\mathsf{ct}^{*}\leftarrow\mathsf{Enc}(\mathsf{msk},x^{*})$ | 8. |  $(\mathsf{ct}^{*},\mathsf{st})\leftarrow\mathpzc{SEnc}(\mathsf{msk},\mathcal{Q},(f_{i},1^{n_{i}},y_{i})_{i\in[q]})$
9. |  Output $b\leftarrow\mathpzc{A}_{3}(\mathsf{ct}^{*})^{\mathsf{Enc}(\mathsf{msk},\cdot),\mathpzc{KG}(\mathsf{msk},\cdot,\cdot)}$ | 9. |  Output $b\leftarrow\mathpzc{A}_{3}(\mathsf{ct}^{*})^{\mathsf{Enc}(\mathsf{msk},\cdot),O_{\mathtt{\mathpzc{SKG}}}(\cdot,\cdot)}$
Figure 10: Security experiments for adaptively lessor simulation-secure SKFE-
SKL

We say that $\mathsf{SKFE\textrm{-}SKL}$ is adaptively lessor simulation-
secure if there exists a QPT simulator $\mathpzc{S}$ such that for any QPT
adversary $\mathpzc{A}$, it satisfies that

$\absolutevalue{\Pr[\mathsf{Real}^{\mathsf{ad}\textrm{-}\mathsf{sim}}_{\mathsf{SKFE\textrm{-}SKL},\mathpzc{A}}(\lambda)=1]-\Pr[\mathsf{Sim}^{\mathsf{ad}\textrm{-}\mathsf{sim}}_{\mathsf{SKFE\textrm{-}SKL},\mathpzc{A},\mathpzc{S}}(\lambda)=1]}\leq{\mathsf{negl}}(\lambda).$

This is a natural simulation-based variant of adaptive lessor
(indistinguishability-)security. The simulator
$\mathpzc{S}=(\mathpzc{SEnc},\mathpzc{SKG})$ does not have
$f^{\ast}_{j}(x^{\ast})$, and the simulated ciphertext does not reveal
information about $f^{\ast}_{j}(x^{\ast})$.

######  Remark B.5.

We consider two key oracles $\mathpzc{KG}$ and
$O_{\mathtt{\mathpzc{KG}}}^{\ast}$ as Definition B.1 to distinguish two types
of queries. We can achieve this simulation-based security since we use
adaptively lessor secure SKFE-SKL in the sense of Definition B.1 as a building
block below. It is also an open question to achieve a stronger adaptive
simulation-based security where adversaries access a single key generation
oracle as Definition 3.2.

De Caro, Iovino, Jani, O’Neil, Paneth, and Persiano [DIJ+13] present a
transformation from indistinguishability-based secure FE to simulation-based
secure FE. The transformation works if the number of key queries before a
challenge ciphertext is given is a-priori bounded. We can apply almost the
same transformation to SKFE with secure leasing since we modify a plaintext in
the ciphertext and a function embedded in a functional decryption key.

We construct an adaptively lessor simulation-secure SKFE scheme with secure
key leasing
$\mathsf{adaSKL}=\mathsf{adaSKL}.(\mathsf{Setup},\mathpzc{KG},\mathsf{Enc},\mathpzc{Dec},\mathpzc{Cert},\mathsf{Vrfy})$
using the following tools:

  * •

An adaptively lessor (indistinguishability-)secure SKFE scheme with secure key
leasing
$\mathsf{indSKL}=\mathsf{indSKL}.(\mathsf{Setup},\mathpzc{KG},\mathsf{Enc},\allowbreak\mathpzc{Dec},\mathpzc{Cert},\mathsf{Vrfy})$.

  * •

A pseudorandom-secure SKE scheme
$\mathsf{SKE}=\mathsf{SKE}.(\mathsf{E},\mathsf{D})$.

Let $\ell_{1}$, $\ell_{2}$, and $m$ be the length of $\mathsf{SKE}$
ciphertexts, the length of random tags, and the output length, respectively.
The description of $\mathsf{adaSKL}$ is as follows.

$\mathsf{adaSKL}.\mathsf{Setup}(1^{\lambda})$:

  * •

Generate
$\mathsf{ind}.\mathsf{msk}\leftarrow\mathsf{indSKL}.\mathsf{Setup}(1^{\lambda})$.

  * •

Output $\mathsf{msk}\coloneqq\mathsf{ind}.\mathsf{msk}$.

$\mathsf{adaSKL}.\mathpzc{KG}(\mathsf{msk},f,1^{n})$:

  * •

Parse $\mathsf{ind}.\mathsf{msk}\leftarrow\mathsf{msk}$.

  * •

Generate $\mathsf{ct}_{\mathsf{ske}}\leftarrow\\{0,1\\}^{\ell_{1}}$ and choose
$\tau\leftarrow\\{0,1\\}^{\ell_{2}}$.

  * •

Compute
$(\mathsf{ind}.\mathpzc{sk}_{T},\mathsf{ind}.\mathsf{vk})\leftarrow\mathsf{indSKL}.\mathpzc{KG}(\mathsf{sel}.\mathsf{msk},T[f,\mathsf{ct}_{\mathsf{ske}},\tau],1^{n})$,
where the circuit $T$ is described in Figure 11.

  * •

Output $\mathpzc{sk}_{f}\coloneqq\mathsf{ind}.\mathpzc{sk}_{T}$ and
$\mathsf{vk}\coloneqq\mathsf{ind}.\mathsf{vk}$.

$\mathsf{adaSKL}.\mathsf{Enc}(\mathsf{msk},x)$:

  * •

Parse $(\mathsf{ind}.\mathsf{msk},K_{\mathsf{ske}})\leftarrow\mathsf{msk}$.

  * •

Set
$x^{\prime}\coloneqq(x,0^{\lambda},(0^{\ell_{2}},0^{m}),\ldots,(0^{\ell_{2}},0^{m}),0)$,
where $m$ is the output length of functions.

  * •

Generate
$\mathsf{ind}.\mathsf{ct}\leftarrow\mathsf{indSKL}.\mathsf{Enc}(\mathsf{ind}.\mathsf{msk},x^{\prime})$.

  * •

Output $\mathsf{ct}_{x}\coloneqq\mathsf{ind}.\mathsf{ct}$.

$\mathsf{adaSKL}.\mathpzc{Dec}(\mathpzc{sk}_{f},\mathsf{ct}_{x})$:

  * •

Parse $\mathsf{ind}.\mathpzc{sk}_{T}\leftarrow\mathpzc{sk}_{f}$ and
$\mathsf{ind}.\mathsf{ct}\leftarrow\mathsf{ct}_{x}$.

  * •

Output
$y\leftarrow\mathsf{indSKL}.\mathpzc{Dec}(\mathsf{ind}.\mathpzc{sk}_{T},\mathsf{ind}.\mathsf{ct})$.

$\mathsf{adaSKL}.\mathpzc{Cert}(\mathpzc{sk}_{f})$:

  * •

Parse $\mathsf{ind}.\mathpzc{sk}_{f}\leftarrow\mathpzc{sk}_{f}$.

  * •

Output
$\mathsf{cert}\coloneqq\mathsf{ind}.\mathsf{cert}\leftarrow\mathsf{indSKL}.\mathpzc{Cert}(\mathsf{ind}.\mathpzc{sk}_{f})$.

$\mathsf{adaSKL}.\mathsf{Vrfy}(\mathsf{vk},\mathsf{cert})$:

  * •

Parse $\mathsf{ind}.\mathsf{vk}=\mathsf{vk}$ and
$\mathsf{ind}.\mathsf{cert}=\mathsf{cert}$.

  * •

Output
$\top/\bot\leftarrow\mathsf{indSKL}.\mathsf{Vrfy}(\mathsf{ind}.\mathsf{vk},\mathsf{ind}.\mathsf{cert})$.

Trapdoor Circuit
$T[f,\mathsf{ct}_{\mathsf{ske}},\tau](x,K_{\mathsf{ske}},(\tau_{1},y_{1}),\ldots,(\tau_{q},y_{q}),\beta)$
Hardwired: function $f$, SKE ciphertext $\mathsf{ct}_{\mathsf{ske}}$, tag
$\tau$. Input: plaintext $x$, SKE secret key $K_{\mathsf{ske}}$, $q$ pairs of
tag and output $(\tau_{1},y_{1}),\ldots,(\tau_{q},y_{q})$, bit $\beta$. 1. If
$\beta=1$, do the following • If there exists $i$ such that $\tau=\tau_{i}$,
output $y_{i}$. • Else output
$y^{\prime}\leftarrow\mathsf{SKE}.\mathsf{D}(K_{\mathsf{ske}},\mathsf{ct}_{\mathsf{ske}})$.
2. Else, output $f(x)$.

Figure 11: Description of $T[f,\mathsf{ct}_{\mathsf{ske}},\tau]$.

As we see above, we expand the plaintext space and use the trapdoor circuit
$T$ as De Caro et al. [DIJ+13]. We can construct a QPT simulator as follows.

  1. 1.

Generates
$\mathsf{ind}.\mathsf{msk}\leftarrow\mathsf{indSKL}.\mathsf{Setup}(1^{\lambda})$
and $K_{\mathsf{ske}}\leftarrow\\{0,1\\}^{\lambda}$.

  2. 2.

Receives
$\mathpzc{sk}_{f_{i}}=(\mathsf{ind}.\mathpzc{sk}_{f_{i}},\mathsf{ct}_{\mathsf{ske},i},\tau_{i})$
for $i\in[q_{\mathsf{pre}}]$ and outputs for pre-challenge key queries, that
is, $f_{1}(x^{\ast}),\ldots,f_{q_{\mathsf{pre}}}(x^{\ast})$.

  3. 3.

Generates a challenge ciphertext
$\mathsf{indSKL}.\mathsf{Enc}(\mathsf{ind}.\mathsf{msk},(0,K_{\mathsf{ske}},(\tau_{1},f_{1}(x^{\ast})),\ldots,\allowbreak(\tau_{q_{\mathsf{pre}}},f_{q_{\mathsf{pre}}}(x^{\ast})),1))$.

  4. 4.

Simulates functional decryption keys for post-challenge key queries as
follows. When an output value $f^{\prime}_{i}(x^{\ast})$ for a key query
$f^{\prime}_{i}$ is given, generates
$(\mathsf{ind}.\mathpzc{sk}_{T},\mathsf{ind}.\mathsf{vk})\leftarrow\mathsf{Sel}.\mathpzc{KG}(\mathsf{sel}.\mathsf{msk},T[f^{\prime}_{i},\mathsf{ct}^{\prime}_{\mathsf{ske},i},\tau^{\prime}_{i}],1^{n})$
where
$\mathsf{ct}^{\prime}_{\mathsf{ske},i}\leftarrow\mathsf{SKE}.\mathsf{E}(K_{\mathsf{ske}},f^{\prime}_{i}(x^{\ast}))$
and $\tau^{\prime}_{i}\leftarrow\\{0,1\\}^{\ell_{2}}$.

Note that the simulator should not have $f^{\ast}_{j}(x^{\ast})$ for any
$j\in[q^{\ast}]$ since $\\{\mathpzc{sk}_{f^{\ast}_{j}}\\}_{j\in[q^{\ast}]}$
are deleted and the challenge ciphertext should not reveal information about
$\\{f^{\ast}_{j}(x^{\ast})\\}_{j\in[q^{\ast}]}$, where
$\\{f^{\ast}_{j}\\}_{j\in[q^{\ast}]}$ are the challenge functions, and the
simulation-security is satisfied.

Since the flag $\beta=1$ in the simulated challenge ciphertext, the trapdoor
circuit $T$ works at the trapdoor branch. For functional decryption keys
before the challenge ciphertext, $T$ works at the first item in the $\beta=1$
branch since $\tau_{i}$ is a tag embedded in the functional decryption keys
for pre-challenge key queries. So, the output of $T$ is an embedded
$f_{i}(x^{\ast})$. This is consistent. For functional decryption keys after
the challenge ciphertext, $T$ works at the second item in the $\beta=1$ branch
since $\tau^{\prime}_{i}$ is uniformly random and must be different from
$\tau_{i}$ except negligible probability. In addition,
$y^{\prime}=f^{\prime}_{i}(x^{\ast})$ since
$\mathsf{ct}^{\prime}_{\mathsf{ske}}\leftarrow\mathsf{SKE}.\mathsf{E}(K_{\mathsf{ske}},f^{\prime}_{i}(x^{\ast}))$.
This is consistent. Thus, the simulated ciphertext does not include
information about $\\{f^{\ast}_{j}(x^{\ast})\\}_{j\in[q^{\ast}]}$.

In reducing to the adaptive lessor (indistinguishability)-security, the
simulator can simulate the key generation and encryption oracles in the
simulation-based game by using the oracles in the indistinguishability-based
game.

###### Theorem B.6.

If $\mathsf{indSKL}$ is adaptively lessor (indistinguishability-)secure and
$\mathsf{SKE}$ is pseuodrandom-secure, $\mathsf{adaSKL}$ is adaptively lessor
simulation-secure.

Since the proof is almost the same as that by De Caro et al. [DIJ+13, Theorem
14 in the eprint ver.], we omit it to avoid the replication.