#  Functional Encryption with Secure Key Leasing

Fuyuki Kitagawa 1 and Ryo Nishimaki 1

###### Abstract

Secure software leasing is a quantum cryptographic primitive that enables us
to lease software to a user by encoding it into a quantum state. Secure
software leasing has a mechanism that verifies whether a returned software is
valid or not. The security notion guarantees that once a user returns a
software in a valid form, the user no longer uses the software.

In this work, we introduce the notion of secret-key functional encryption
(SKFE) with secure key leasing, where a decryption key can be securely leased
in the sense of secure software leasing. We also instantiate it with standard
cryptographic assumptions. More specifically, our contribution is as follows.

  * •

We define the syntax and security definitions for SKFE with secure key
leasing.

  * •

We achieve a transformation from standard SKFE into SKFE with secure key
leasing _without using additional assumptions_. Especially, we obtain bounded
collusion-resistant SKFE for $\mathsf{P}/\mathsf{poly}$ with secure key
leasing based on post-quantum one-way functions since we can instantiate
bounded collusion-resistant SKFE for $\mathsf{P}/\mathsf{poly}$ with the
assumption.

Some previous secure software leasing schemes capture only pirate software
that runs on an _honest_ evaluation algorithm (on a legitimate platform).
However, our secure key leasing notion captures arbitrary attack strategies
and does not have such a limitation.

As an additional contribution, we introduce the notion of single-decryptor FE
(SDFE), where each functional decryption key is copy-protected. Since copy-
protection is a stronger primitive than secure software leasing, this notion
can be seen as a stronger cryptographic primitive than FE with secure key
leasing. More specifically, our additional contribution is as follows.

  * •

We define the syntax and security definitions for SDFE.

  * •

We achieve collusion-resistant single-decryptor PKFE for
$\mathsf{P}/\mathsf{poly}$ from post-quantum indistinguishability obfuscation
and quantum hardness of the learning with errors problem.

Keywords: Functional encryption, secure leasing, copy-protection, quantum
cryptography

1 NTT Social Informatics Laboratories, Tokyo, Japan

<EMAIL_ADDRESS>
0.50.9

1[0.5,0](0,.25)

###### Contents

  1. 1 Introduction
    1. 1.1 Background
    2. 1.2 Our Result
    3. 1.3 Technical Overview
    4. 1.4 More on Related Work
  2. 2 Preliminaries
    1. 2.1 Standard Cryptographic Tools
    2. 2.2 Advanced Tools
  3. 3 Definition of SKFE with Secure Key Leasing
    1. 3.1 SKFE with Secure Key Leasing
    2. 3.2 SKFE with Static-Bound Secure Key Leasing
    3. 3.3 Index-Based SKFE with Static-Bound Secure Key Leasing
  4. 4 Index-Base SKFE with Static-Bound Secure Key Leasing
  5. 5 SKFE with Static-Bound Secure Key Leasing
  6. 6 SKFE with Secure Key Leasing
  7. 7 Single-Decryptor Functional Encryption
    1. 7.1 Preliminaries for SDFE
    2. 7.2 Single-Decryptor Encryption
    3. 7.3 Definitions for Single-Decryptor Functional Encryption
    4. 7.4 Single-Key Secure Single-Decryptor Functional Encryption
    5. 7.5 Collusion-Resistant Single-Decryptor Functional Encryption
  8. A CPA-Style Anti-Piracy Security Notions
  9. B Adaptive and Simulation-based Security for Secure Key Leasing
    1. B.1 Adaptive Security for Secure Key Leasing
    2. B.2 Simulation-based Security for Secure Key Leasing

##  1 Introduction

###  1.1 Background

Functional encryption (FE) [BSW11] is an advanced encryption system that
enables us to compute on encrypted data. In FE, an authority generates a
master secret key and an encryption key. An encryptor uses the encryption key
to generate a ciphertext $\mathsf{ct}_{x}$ of a plaintext $x$. The authority
generates a functional decryption key $\mathsf{fsk}$ from a function $f$ and
the master secret key. When a decryptor receives $\mathsf{fsk}$ and
$\mathsf{ct}_{x}$, it can compute $f(x)$ and obtains nothing beyond $f(x)$. In
secret-key FE (SKFE), the encryption key is the same as the master secret key,
while the encryption key is public in public-key FE (PKFE).

FE offers flexible accessibility to encrypted data since multiple users can
obtain various processed data via functional decryption keys. Public-key
encryption (PKE) and attribute-based encryption (ABE) [SW05] do not have this
property since they recover an entire plaintext if decryption succeeds. This
flexible feature is suitable for analyzing sensitive data and computing new
data from personal data without compromising data privacy. For example, we can
compute medical statistics from patients’ data without directly accessing
individual data. Some works present practical applications of FE (for limited
functionalities): non-interactive protocol for hidden-weight coin flips
[CS19], biometric authentication, nearest-neighbor search on encrypted data
[KLM+18], private inference on encrypted data [RPB+19].

One issue is that once a user obtains $\mathsf{fsk}$, it can compute $f(x)$
from a ciphertext of $x$ forever. An authority may not want to provide users
with the permanent right to compute on encrypted data. A motivative example is
as follows. A research group member receives a functional decryption key
$\mathsf{fsk}$ to compute some statistics from many encrypted data for their
research. When the member leaves the group, an authority wants to prevent the
member from doing the same computation on another encrypted data due to terms
and conditions. However, the member might _keep a copy_ of their functional
decryption key and penetrate the database of the group to do the same
computation. Another motivation is that the subscription business model is
common for many services such as cloud storage services (ex. OneDrive,
Dropbox), video on demand (ex. Netflix, Hulu), software applications (ex.
Office 365, Adobe Photoshop). If we can keep a copy of functional decryption
keys, we cannot use FE in the subscription business model (for example, FE can
be used as broadcast encryption in a video on demand). We can also consider
the following subscription service. A company provides encrypted data sets for
machine learning and a functional decryption key. A researcher can perform
some tasks using the encrypted data set and the key.

Achieving a revocation mechanism [NP01] is an option to solve the issue above.
Some works propose revocation mechanisms for advanced encryption such as ABE
[SSW12] and FE [NWZ16]. However, revocation is not a perfect solution since we
need to update ciphertexts to embed information about revoked users. We want
to avoid updating ciphertexts for several reasons. One is a practical reason.
We possibly handle a vast amount of data, and updating ciphertexts incurs
significant overhead. Another one is more fundamental. Even if we update
ciphertexts, _there is no guarantee that all old ciphertexts are appropriately
deleted._ If some user keeps copies of old ciphertexts, and a data breach
happens after revocation, another functional decryption key holder whose key
was revoked still can decrypt the old ciphertexts.

This problem is rooted in classical computation since we cannot prevent
copying digital data. Ananth and La Placa introduce the notion of secure
software leasing [AL21] to solve the copy problem by using the power of
quantum computation. Secure software leasing enables us to encode software
into a leased version. The leased version has the same functionality as the
original one and must be a quantum state to prevent copying. _After a lessor
verifies that the returned software from a lessee is valid (or that the lessee
deleted the software)_ , the lessee cannot execute the software anymore.
Several works present secure software leasing for simple functionalities such
as a sub-class of evasive functions ($\mathsf{subEVS}$), PKE, signatures,
pseudorandom functions (PRFs) [AL21, ALL+21, KNY21, BJL+21, CMP20]. If we can
securely implement leasing and returning mechanisms for functional decryption
keys, we can solve the problem above. Such mechanisms help us to use FE in
real-world applications.

Thus, the main question in this work is as follows.

_Can we achieve secure a leasing mechanism for functional decryption keys of
FE?_

We can also consider copy-protection, which is stronger security than secure
leasing. Aaronson [Aar09] introduces the notion of quantum copy-protection.
Copy-protection prevents users from creating a pirate copy. _It does not have
a returning process_ , and prevents copying software. If a user returns the
original software, no copy is left behind on the user, and it cannot run the
software. Coladangelo, Liu, Liu, and Zhandry [CLLZ21] achieve copy-protected
PRFs and single-decryptor encryption (SDE)111SDE is PKE whose decryption keys
are copy-protected.. Our second question in this work is as follows.

_Can we achieve copy-protection for functional decryption keys of FE?_

We affirmatively answer those questions in this work.

###  1.2 Our Result

#### Secure key leasing.

Our main contributions are introducing the notion of SKFE with secure key
leasing and instantiating it with standard cryptographic assumptions. More
specifically,

  * •

We define the syntax and security definitions for SKFE with secure key
leasing.

  * •

We achieve a transformation from standard SKFE into SKFE with secure key
leasing _without using additional assumptions_.

In SKFE with secure key leasing, a functional decryption key is a quantum
state. More specifically, the key generation algorithm takes as input a master
secret key, a function $f$, and an availability bound $n$ (in terms of the
number of ciphertexts), and outputs a quantum decryption key $\mathpzc{fsk}$
tied to $f$. We can generate a _certificate for deleting_ the decryption key
$\mathpzc{fsk}$. If the user of this decryption key deletes $\mathpzc{fsk}$
within the declared availability bound $n$ and the generated certificate is
valid, the user cannot compute $f(x)$ from a ciphertext of $x$ anymore. We
provide a high-level overview of the security definition in Section 1.3.

We can obtain bounded collusion-resistant SKFE for $\mathsf{P}/\mathsf{poly}$
with secure key leasing from OWFs since we can instantiate bounded collusion-
resistant SKFE for $\mathsf{P}/\mathsf{poly}$ with OWFs.222If we start with
fully collusion-resistant SKFE, we can obtain fully collusion-resistant SKFE
with secure key leasing. Note that all building blocks in this work are post-
quantum secure since we use quantum computation and we omit “post-quantum”.

Our secure key leasing notion is similar to but different from secure software
leasing [AL21] for FE because adversaries in secure software leasing (for FE)
must run their pirate software by an _honest_ evaluation algorithm (on a
legitimate platform). This is a severe limitation. In our FE with secure key
leasing setting, adversaries do _not_ necessarily run their pirate software
(for functional decryption) by an honest evaluation algorithm and can take
arbitrary attack strategies.

We develop a transformation from standard SKFE into SKFE with secure key
leasing by using quantum power. In particular, we use (reusable) secret-key
encryption (SKE) with certified deletion [BI20, HMNY21], where we can securely
delete _ciphertexts_ , as a building block. We also develop a technique based
on the security bound amplification for FE [AJL+19, JKMS20] to amplify the
availability bound, that is, the number of encryption queries before
$\mathsf{ct}^{\ast}$ is given. This technique deviates from known multi-party-
computation-based techniques for achieving bounded many-ciphertext security
for SKFE [GVW12, AV19].333These techniques [GVW12, AV19] work as
transformations from single-key FE into bounded collusion-resistant FE.
However, they also work as transformations from single-ciphertext SKFE into
bounded many-ciphertext SKFE. See Section 1.4 for the detail. Many-ciphertext
means that SKFE is secure even if adversaries can send unbounded polynomially
many queries to an encryption oracle. The security bound amplification-based
technique is of independent interest since the security bound amplification is
not directly related to the amplification of the number of queries. These are
the main technical contributions of this work. See Section 1.3 and main
sections for more details.

#### Copy-protected functional decryption keys.

The other contributions are copy-protected functional decryption keys. We
introduce the notion of single-decryptor FE (SDFE), where each functional
decryption key is copy-protected. This notion can be seen as a stronger
cryptographic primitive than FE with secure key leasing, as we argued in
Section 1.1.

  * •

We define the syntax and security definitions for SDFE.

  * •

We achieve collusion-resistant public key SDFE for $\mathsf{P}/\mathsf{poly}$
from sub-exponentially secure indistinguishability obfuscation (IO) and the
sub-exponential hardness of the learning with errors problem (QLWE
assumption).

First, we transform single-key PKFE for $\mathsf{P}/\mathsf{poly}$ into
_single-key_ SDFE for $\mathsf{P}/\mathsf{poly}$ by using SDE. Then, we
transform single-key SDFE $\mathsf{P}/\mathsf{poly}$ into collusion-resistant
SDFE for $\mathsf{P}/\mathsf{poly}$ by using an IO-based key bundling
technique [KNT21, BNPW20]. We can instantiate SDE with IO and the QLWE
assumption [CLLZ21, CV21] and single-key PKFE for $\mathsf{P}/\mathsf{poly}$
with PKE [SS10, GVW12].

###  1.3 Technical Overview

We provide a high-level overview of our techniques. Below, standard math font
stands for classical algorithms and classical variables, and calligraphic font
stands for quantum algorithms and quantum states.

#### Syntax of SKFE with secure key leasing.

We first recall a standard SKFE scheme. It consists of four algorithms
$(\mathsf{Setup},\mathsf{KG},\mathsf{Enc},\mathsf{Dec})$. $\mathsf{Setup}$ is
given a security parameter $1^{\lambda}$ and a collusion bound $1^{q}$ and
generates a master secret key $\mathsf{msk}$. $\mathsf{Enc}$ is given
$\mathsf{msk}$ and a plaintext $x$ and outputs a ciphertext $\mathsf{ct}$.
$\mathsf{KG}$ is given $\mathsf{msk}$ and a function $f$ and outputs a
decryption key $\mathsf{fsk}$ tied to $f$. $\mathsf{Dec}$ is given
$\mathsf{fsk}$ and $\mathsf{ct}$ and outputs $f(x)$. Then, the
indistinguishability-security of SKFE roughly states that any QPT adversary
cannot distinguish encryptions of $x_{0}$ and $x_{1}$ under the existence of
the encryption oracle and the key generation oracle. Here, the adversary can
access the key generation oracle at most $q$ times and can query only a
function $f$ such that $f(x_{0})=f(x_{1})$.

An SKFE scheme with secure key leasing (SKFE-SKL) is a tuple of six algorithms
$(\mathsf{Setup},\mathpzc{KG},\mathsf{Enc},\mathpzc{Dec},\allowbreak\mathpzc{Cert},\mathsf{Vrfy})$,
where the first four algorithms form a standard SKFE scheme except the
following difference on $\mathpzc{KG}$. In addition to a function $f$,
$\mathpzc{KG}$ is given an availability bound $1^{n}$ in terms of the number
of ciphertexts. Also, given those inputs, $\mathpzc{KG}$ outputs a
verification key $\mathsf{vk}$ together with a decryption key $\mathpzc{fsk}$
tied to $f$ encoded in a quantum state, as
$(\mathpzc{fsk},\mathsf{vk})\leftarrow\mathpzc{KG}(\mathsf{msk},f,1^{n})$. By
using $\mathpzc{Cert}$, we can generate a (classical) certificate that a
quantum decryption key $\mathpzc{fsk}$ is deleted, as
$\mathsf{cert}\leftarrow\mathpzc{Cert}(\mathpzc{fsk})$. We check the validity
of certificates by using $\mathsf{vk}$ and $\mathsf{Vrfy}$, as
$\top/\bot\leftarrow\mathsf{Vrfy}(\mathsf{vk},\mathsf{cert})$. In addition to
the decryption correctness, an SKFE-SKL scheme is required to satisfy the
verification correctness that states that a correctly generated certificate is
accepted, that is, $\top=\mathsf{Vrfy}(\mathsf{vk},\mathsf{cert})$ for
$(\mathpzc{fsk},\mathsf{vk})\leftarrow\mathpzc{KG}(\mathsf{msk},f,1^{n})$ and
$\mathsf{cert}\leftarrow\mathpzc{Cert}(\mathpzc{fsk})$.

#### Security of SKFE-SKL.

The security notion of SKFE-SKL we call lessor security intuitively guarantees
that if an adversary given $\mathpzc{fsk}$ deletes it and the generated
certificate is accepted within the declared availability bound, the adversary
cannot use $\mathpzc{fsk}$ any more. The following indistinguishability
experiment formalizes this security notion. For simplicity, we focus on a
selective setting where the challenge plaintext pair $(x_{0}^{*},x_{1}^{*})$
and the collusion bound $q$ are fixed outside of the security experiment in
this overview.

  1. 1.

Throughout the experiment, $\mathpzc{A}$ can get access to the following
oracles, where $L_{\mathtt{\mathpzc{KG}}}$ is a list that is initially empty.

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

This is the standard encryption oracle that returns
$\mathsf{Enc}(\mathsf{msk},x)$ given $x$.

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

This oracle takes as input a function $f$ and an availability bound $1^{n}$,
generate
$(\mathpzc{fsk},\mathsf{vk})\leftarrow\mathpzc{KG}(\mathsf{msk},f,1^{n})$,
returns $\mathpzc{fsk}$ to $\mathpzc{A}$, and adds
$(f,1^{n},\mathsf{vk},\bot)$ to $L_{\mathtt{\mathpzc{KG}}}$. Differently from
the standard SKFE, $\mathpzc{A}$ can query a function $f$ such that
$f(x_{0}^{*})\neq f(x_{1}^{*})$. $\mathpzc{A}$ can get access to the key
generation oracle at most $q$ times.

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

Also, $\mathpzc{A}$ can get access to the verification oracle. Intuitively,
this oracle checks that $\mathpzc{A}$ deletes leased decryption keys correctly
within the declared availability bounds. Given $(f,\mathsf{cert})$, it finds
an entry $(f,1^{n},\mathsf{vk},M)$ from $L_{\mathtt{\mathpzc{KG}}}$. (If there
is no such entry, it returns $\bot$.) If
$\top=\mathsf{Vrfy}(\mathsf{vk},\mathsf{cert})$ and the number of queries to
$O_{\mathtt{\mathsf{Enc}}}$ at this point is less than $n$, it returns $\top$
and updates the entry into $(f,1^{n},\mathsf{vk},\top)$. Otherwise, it returns
$\bot$.

  2. 2.

When $\mathpzc{A}$ requests the challenge ciphertext, the challenger checks if
$\mathpzc{A}$ has correctly deleted all leased decryption keys for functions
$f$ such that $f(x_{0}^{*})\neq f(x_{1}^{*})$. If so, the challenger gives the
challenge ciphertext
$\mathsf{ct}^{*}\leftarrow\mathsf{Enc}(\mathsf{msk},x_{\mathsf{coin}}^{*})$
for random bit $\mathsf{coin}\leftarrow\\{0,1\\}$ to $\mathpzc{A}$, and
otherwise the challenger output $0$. Hereafter, $\mathpzc{A}$ is not allowed
to send a function $f$ such that $f(x_{0}^{*})\neq f(x_{1}^{*})$ to
$O_{\mathtt{\mathpzc{KG}}}$.

  3. 3.

$\mathpzc{A}$ outputs a guess $\mathsf{coin}^{\prime}$ of $\mathsf{coin}$.

We say that the SKFE-SKL scheme is lessor secure if no QPT adversary can guess
$\mathsf{coin}$ significantly better than random guessing. We see that if
$\mathpzc{A}$ can use a decryption key after once $\mathpzc{A}$ deletes and
the deletion certificate is accepted, $\mathpzc{A}$ can detect $\mathsf{coin}$
with high probability since $\mathpzc{A}$ can obtain a decryption key for $f$
such that $f(x_{0}^{*})\neq f(x_{1}^{*})$. Thus, this security notion captures
the above intuition. We see that _lessor security implies standard
indistinguishability-security for SKFE_.

We basically work with the above indistinguishability based selective security
for simplicity. In Appendix B, we also provide the definitions of adaptive
security and simulation based security notions and general transformations to
achieve those security notions from indistinguishability based selective
security.

#### Dynamic availability bound vs. static availability bound.

In SKFE-SKL, we can set the availability bound for each decryption key
differently. We can also consider a weaker variant where we statically set the
single availability bound applied to each decryption key at the setup
algorithm. We call this variant SKFE with static bound secure key leasing
(SKFE-sbSKL). In fact, by using a technique developed in the context of
dynamic bounded collusion FE [AMVY21, GGLW21], we can generically transform
SKFE-sbSKL into SKFE-SKL if the underlying SKFE-sbSKL satisfies some
additional security property and efficiency requirement. For the overview of
this transformation, see Section 3.2. Therefore, we below focus on how to
achieve SKFE-sbSKL. For simplicity, we ignore those additional properties
required for the transformation to SKFE-SKL.

#### SKFE-sbSKL with the availability bound $0$ from certified deletion.

We start with a simple construction of an SKFE-sbSKL scheme secure for the
availability bound $0$ based on an SKE scheme with certified deletion [BI20,
HMNY21]. The availability bound is $0$ means that it is secure if an adversary
deletes decryption keys without seeing any ciphertext.

SKE with certified deletion consists of five algorithms
$(\mathsf{KG},\mathpzc{Enc},\mathpzc{Dec},\mathpzc{Del},\mathsf{Vrfy})$. The
first three algorithms form a standard SKE scheme except that $\mathpzc{Enc}$
output a verification key $\mathsf{vk}$ together with a ciphertext encoded in
a quantum state $\mathpzc{ct}$. By using $\mathpzc{Del}$, we can generate a
(classical) certificate that $\mathpzc{ct}$ is deleted. The certificate is
verified using $\mathsf{vk}$ and $\mathsf{Vrfy}$. In addition to the
decryption correctness, it satisfies the verification correctness that
guarantees that a correctly generated certificate is accepted. The security
notion roughly states that once an adversary deletes a ciphertext
$\mathpzc{ct}$ and the generated certificate is accepted, the adversary cannot
obtain any plaintext information encrypted inside $\mathpzc{ct}$, even if the
adversary is given the secret key after the deletion.

We now construct an SKFE-sbSKL scheme $\mathsf{zSKFE}\textrm{-}\mathsf{sbSKL}$
that is secure for the availability bound $0$, based on a standard SKFE scheme
$\mathsf{SKFE}=(\mathsf{Setup},\mathsf{KG},\allowbreak\mathsf{Enc},\mathsf{Dec})$
and an SKE scheme with certified deletion
$\mathsf{CDSKE}=(\mathsf{CD}.\mathsf{KG},\mathsf{CD}.\mathpzc{Enc},\allowbreak\mathsf{CD}.\mathpzc{Dec},\mathsf{CD}.\mathpzc{Del},\mathsf{CD}.\mathsf{Vrfy})$.
In the setup of $\mathsf{zSKFE}\textrm{-}\mathsf{sbSKL}$, we generate
$\mathsf{msk}\leftarrow\mathsf{Setup}(1^{\lambda},1^{q})$ and
$\mathsf{cd}.\mathsf{sk}\leftarrow\mathsf{CD}.\mathsf{KG}(1^{\lambda})$, and
the master secret key of $\mathsf{zSKFE}\textrm{-}\mathsf{sbSKL}$ is set to
$\mathsf{zmsk}=(\mathsf{msk},\mathsf{cd}.\mathsf{sk})$. To generate a
decryption key for $f$, we generate a decryption key for $f$ by
$\mathsf{SKFE}$ as $\mathsf{fsk}\leftarrow\mathsf{KG}(\mathsf{msk},f)$ and
encrypt it by $\mathsf{CDSKE}$ as
$(\mathsf{cd}.\mathpzc{ct},\mathsf{vk})\leftarrow\mathsf{CD}.\mathpzc{Enc}(\mathsf{cd}.\mathsf{sk},\mathsf{fsk})$.
The resulting decryption key is
$\mathpzc{zfsk}\coloneqq\mathsf{cd}.\mathpzc{ct}$ and the corresponding
verification key is $\mathsf{vk}$. To encrypt a plaintext $x$, we just encrypt
it by $\mathsf{SKFE}$ as $\mathsf{ct}\leftarrow\mathsf{Enc}(\mathsf{msk},x)$
and append $\mathsf{cd}.\mathsf{sk}$ contained in $\mathsf{zmsk}$, as
$\mathsf{zct}\coloneqq(\mathsf{ct},\mathsf{cd}.\mathsf{sk})$. To decrypt
$\mathsf{zct}$ with $\mathpzc{zfsk}$, we first retrieve $\mathsf{fsk}$ from
$\mathsf{cd}.\mathsf{ct}$ and $\mathsf{cd}.\mathsf{sk}$, and compute
$f(x)\leftarrow\mathsf{Dec}(\mathsf{fsk},\mathsf{ct})$. The certificate
generation and verification are simply defined as those of $\mathsf{CDSKE}$
since $\mathpzc{zfsk}$ is a ciphertext of $\mathsf{CDSKE}$.

The security of $\mathsf{zSKFE}\textrm{-}\mathsf{sbSKL}$ is easily analyzed.
Let $(x_{0}^{*},x_{1}^{*})$ be the challenge plaintext pair. When an adversary
$\mathpzc{A}$ queries $f$ to $O_{\mathtt{\mathpzc{KG}}}$, $\mathpzc{A}$ is
given $\mathpzc{zfsk}\coloneqq\mathsf{cd}.\mathpzc{ct}$, where
$\mathsf{fsk}\leftarrow\mathsf{KG}(\mathsf{msk},f)$ and
$(\mathsf{cd}.\mathpzc{ct},\mathsf{vk})\leftarrow\mathsf{CD}.\mathpzc{Enc}(\mathsf{cd}.\mathsf{sk},\mathsf{fsk})$.
If $f(x_{0}^{*})\neq f(x_{1}^{*})$, $\mathpzc{A}$ is required to delete
$\mathpzc{zfsk}$ without seeing any ciphertext. This means that $\mathpzc{A}$
cannot obtain $\mathsf{cd}.\mathsf{sk}$ before $\mathpzc{zfsk}$ is deleted.
Then, from the security of $\mathsf{CDSKE}$, $\mathpzc{A}$ cannot obtain any
information of $\mathsf{fsk}$. This implies that $\mathpzc{A}$ can obtain a
decryption key of $\mathsf{SKFE}$ only for a function $f$ such that
$f(x_{0}^{*})=f(x_{1}^{*})$, and thus the lessor security of
$\mathsf{zSKFE}\textrm{-}\mathsf{sbSKL}$ follows form the security of
$\mathsf{SKFE}$.

#### How to amplify the availability bound?

We now explain how to amplify the availability bound from $0$ to any
polynomial $n$. One possible solution is to rely on the techniques for bounded
collusion FE [GVW12, AV19]. Although the bounded collusion techniques can be
used to amplify “$1$-bounded security” to “poly-bounded security”, it is not
clear how to use it starting from “$0$-bounded security”. For more detailed
discussion on this point, see Remark 3.7. Therefore, we use a different
technique from the existing bounded collusion FE. At a high level, we reduce
the task of amplifying the availability bound to the task of amplifying the
security bound, which has been studied in the context of standard FE [AJL+19,
JKMS20].

We observe that we can obtain an SKFE-sbSKL scheme with availability bound $n$
for any $n$ that is secure with only inverse polynomial probability by just
using many instances of $\mathsf{zSKFE}\textrm{-}\mathsf{sbSKL}$ in parallel.
Concretely, suppose we use $N=\alpha n$ instances of
$\mathsf{zSKFE}\textrm{-}\mathsf{sbSKL}$ to achieve a scheme with availability
bound $n$, where $\alpha\in\mathbb{N}$. To generate a decryption key for $f$,
we generate
$(\mathpzc{zfsk}_{j},\mathsf{vk}_{j})\leftarrow\mathpzc{zKG}(\mathsf{zmsk}_{j},f)$
for every $j\in[N]$, and set the resulting decryption key as
$(\mathpzc{zfsk}_{j})_{j\in[N]}$ and the corresponding verification key as
$(\mathsf{vk}_{j})_{j\in[N]}$. To encrypt $x$, we randomly choose
$j\leftarrow[N]$, generate
$\mathsf{zct}_{j}\leftarrow\mathsf{zEnc}(\mathsf{zmsk}_{j},x)$, and set the
resulting ciphertext as $(j,\mathsf{zct}_{j})$. To decrypt this ciphertext
with $(\mathpzc{zfsk}_{j})_{j\in[N]}$, we just compute
$f(x)\leftarrow\mathpzc{zDec}(\mathpzc{zfsk}_{j},\mathsf{zct}_{j})$. The
certification generation and verification are done by performing them under
all $N$ instances. The security of this construction is analyzed as follows.
The probability that the $j^{*}$ chosen when generating the challenge
ciphertext collides with some of $n$ indices $j_{1},\cdots,j_{n}$ used by the
first $n$ calls of the encryption oracle, is at most $n/N=1/\alpha$. If such a
collision does not happen, we can use the security of $j^{*}$-th instance of
$\mathsf{zSKFE}\textrm{-}\mathsf{sbSKL}$ to prove the security of this
construction. Therefore, this construction is secure with probability roughly
$1-1/\alpha$ (denoted by $1/\alpha$-secure scheme).

Thus, all we have to do is to convert an SKFE-sbSKL scheme with inverse
polynomial security into one with negligible security. As stated above, such
security amplification has been studied for standard FE. In this work, we
adopt the amplification technique using homomorphic secret sharing (HSS)
[AJL+19, JKMS20].

#### Amplification using HSS.

In this overview, we describe our construction using HSS that requires the LWE
assumption with super-polynomial modulus to give a high-level intuition.
However, our actual construction uses a primitive called set homomorphic
secret sharing (SetHSS) [JKMS20], which is a weak form of HSS and _can be
based on OWFs_. 444The definition of HSS provided below is not standard. We
modify the definition to be close to SetHSS. Note that HSS defined below can
be constructed from multi-key fully homomorphic encryption with simulatable
partial decryption property [MW16]. See Section 5 for our construction based
on OWFs.

An HSS scheme consists of three algorithms
$(\mathsf{InpEncode},\allowbreak\mathsf{FuncEncode},\allowbreak\mathsf{Decode})$.
$\mathsf{InpEncode}$ is given a security parameter $1^{\lambda}$, a number
$1^{m}$, and an input $x$, and outputs $m$ input shares $(s_{i})_{i\in[m]}$.
$\mathsf{FuncEncode}$ is given a security parameter $1^{\lambda}$, a number
$1^{m}$, and a function $f$, and outputs $m$ function shares
$(f_{i})_{i\in[m]}$. $\mathsf{Decode}$ takes a set of evaluations of function
shares on their respective input shares $(f_{i}(s_{i}))_{i\in[m]}$, and
outputs a value $f(x)$. Then, the security property of an HSS scheme roughly
guarantees that for any $(i^{*},x_{0}^{*},x_{1}^{*})$, given a set of input
shares $(s_{i})_{i\in[m]\setminus\\{i^{*}\\}}$ for some $i^{*}$, an adversary
cannot detect from which of the challenge inputs they are generated, under the
existence of function encode oracle that is given $f$ such that
$f(x_{0}^{*})=f(x_{1}^{*})$ and returns $(f_{i}(s_{i}))_{i\in[m]}$.

We describe SKFE-sbSKL scheme $\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}$ with the
availability bound $n\geq 1$ of our choice using a HSS scheme
$\mathsf{HSS}=(\mathsf{InpEncode},\allowbreak\mathsf{FuncEncode},\mathsf{Decode})$.
In the setup of $\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}$, we first set up
$1/2$-secure SKFE-sbSKL scheme
$\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}^{\prime}$ with the availability bound
$n$. This is done by parallelizing $2n$ instances of
$\mathsf{zSKFE}\textrm{-}\mathsf{sbSKL}$ as explained before. We generate $m$
master secret keys $\mathsf{msk}_{1},\cdots,\mathsf{msk}_{m}$ of
$\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}^{\prime}$. Then, to generate a
decryption key for $f$ by $\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}$, we first
generate
$(f_{i})_{i\in[m]}\leftarrow\mathsf{FuncEncode}(1^{\lambda},1^{m},f)$, and
generate a decryption key $\mathpzc{fsk}_{i}$ tied to $f_{i}$ under
$\mathsf{msk}_{i}$ for each $i\in[m]$. To encrypt $x$ by
$\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}$, we first generate
$(s_{i})_{i\in[m]}\leftarrow\mathsf{InpEncode}(1^{\lambda},1^{m},x)$ and
generate a ciphertext $\mathsf{ct}_{i}$ of $s_{i}$ under $\mathsf{msk}_{i}$
for each $i\in[m]$. The certification generation and verification are done by
performing those of $\mathsf{SKFE\textrm{-}SKL}^{\prime}$ for all of the $m$
instances. When decrypting the ciphertext $(\mathsf{ct}_{i})_{i\in[m]}$ by
$(\mathpzc{fsk}_{i})_{i\in[m]}$, we can obtain $f_{i}(s_{i})$ by decrypting
$\mathsf{ct}_{i}$ with $\mathpzc{fsk}_{i}$ for every $i\in[m]$. By combining
$(f_{i}(s_{i}))_{i\in[m]}$ using $\mathsf{Decode}$, we can obtain $f(x)$.

The lessor security of $\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}$ can be proved
as follows. Each of $m$ instances of
$\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}^{\prime}$ is secure independently with
probability $1/2$. Thus, there is at least one secure instance without
probability $1/2^{m}$, which is negligible by setting $m=\omega(\log\lambda)$.
Suppose $i^{*}$-th instance is a secure instance. Let $(x_{0}^{*},x_{1}^{*})$
be the challenge plaintext pair, and let
$(s^{*}_{i})_{i\in[m]}\leftarrow\mathsf{InpEncode}(1^{\lambda},1^{m},x^{*}_{\mathsf{coin}})$
for $\mathsf{coin}\leftarrow\\{0,1\\}$. In the security experiment, from the
security of $\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}^{\prime}$ under
$\mathsf{msk}_{i^{*}}$, an adversary cannot obtain the information of
$s_{i^{*}}$ except for its evaluation on function shares for a function $f$
queried to $O_{\mathtt{\mathpzc{KG}}}$ that satisfies that
$f(x_{0}^{*})=f(x_{1}^{*})$. Especially, from the security of
$\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}^{\prime}$ under $\mathsf{msk}_{i^{*}}$,
the adversary cannot obtain an evaluation of $s_{i^{*}}$ on function shares
for a function $f$ such that $f(x_{0}^{*})\neq f(x_{1}^{*})$, though
$\mathpzc{A}$ can query such a function to $O_{\mathtt{\mathpzc{KG}}}$. Then,
we see that the lessor security of $\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}$ can
be reduced to the security of $\mathsf{HSS}$. 555Actual construction and
security proof needs to use a technique called the trojan method [ABSV15]. We
ignore the issue here for simplicity.

In the actual construction, we use SetHSS instead of HSS, as stated before.
Also, in the main body, we abstract the parallelized
$\mathsf{zSKFE}\textrm{-}\mathsf{sbSKL}$ as index-based SKFE-sbSKL. This makes
the security proof of our construction using SetHSS simple. Moreover, in the
actual construction of an index-based SKFE-sbSKL, we bundle the parallelized
instances of $\mathsf{zSKFE}\textrm{-}\mathsf{sbSKL}$ using a PRF. This
modification is necessary to achieve the efficiency required for the above
transformation into SKFE-SKL.

Goyal et al. [CGO21] use a similar technique using HSS in a different setting
(private simultaneous message protocols). However, their technique relies on
the LWE assumption unlike ours.

#### Single decryptor PKFE.

In this work, we also define the notion of single decryptor PKFE, which is
PKFE whose functional decryption key is copy-protected. The definition is a
natural extension of SDE (PKE with copy-protected decryption keys). An
adversary $\mathpzc{A}$ tries to copy a target functional decryption key
$\mathpzc{sk}_{f^{\ast}}$. More specifically, $\mathpzc{A}$ is given
$\mathpzc{sk}_{f^{\ast}}$ and outputs two possibly entangled quantum
distinguishers $\mathpzc{D}_{1}$ and $\mathpzc{D}_{2}$ and two plaintexts
$(x_{0},x_{1})$ such that $f^{\ast}(x_{0})\neq f^{\ast}(x_{1})$. If
$\mathpzc{D}_{1}$ or $\mathpzc{D}_{2}$ cannot distinguish a given ciphertext
is encryption of $x_{0}$ or $x_{1}$, $\mathpzc{sk}_{f^{\ast}}$ is copy-
protected.666In the security definition of SDE, quantum _decryptors_ try to
recover the entire plaintext [CLLZ21]. We extend the definition because
quantum decryptors are not sufficient for using SDFE as a building block. See
Section 7 for detail. If both $\mathpzc{D}_{1}$ and $\mathpzc{D}_{2}$ have
$\mathpzc{sk}_{f^{\ast}}$, they can trivially distinguish the challenge
ciphertext. Thus, the definition guarantees copy-protection security. We
provide a collusion-resistant single-decryptor PKFE scheme, where adversaries
obtain polynomially many functional decryption keys, based on IO.

We first show that a single-key single-decryptor PKFE can be constructed from
a single-key standard PKFE scheme and SDE scheme. The construction is simple
nested encryption. Namely, when encrypting a plaintext $x$, we first encrypt
it by the standard PKFE scheme and then encrypt the ciphertext by the SDE
scheme. The secret key of the SDE scheme is included in the functional
decryption key of the resulting single-decryptor PKFE scheme. Although a PKFE
functional decryption key can be copied, the SDE decryption key cannot be
copied and adversaries cannot break the security of PKFE. This is because we
need to run the SDE decryption algorithm before we run the PKFE decryption
algorithm.

The security notion for SDE by Coladangelo et al. [CLLZ21] is not sufficient
for our purpose since SDE plaintexts are ciphertexts of the standard PKFE in
the construction. We need to extend the security notion for SDE to prove the
security of this construction because we need to handle randomized messages
(the PKFE encryption is a randomized algorithm). Roughly speaking, this new
security notion guarantees that the security of SDE holds for plaintexts of
the form $g(x;r)$, where $g$ and $x$ respectively are a function and an input
chosen by an adversary and $r$ is a random coin chosen by the experiment. We
can observe that the SDE scheme proposed by Coladangelo et al. [CLLZ21] based
on IO satisfies this security notion. Then, by setting $g$ as the encryption
circuit of the standard PKFE, the security of the single-key single-decryptor
PKFE scheme above can be immediately reduced to the security of the SDE
scheme. We also extend adversarial quantum decryptors, which try to output an
entire plaintext, to adversarial quantum distinguishers, which try to guess a
$1$-bit coin used to generate a ciphertext. We need this extension to use SDE
as a building block. It is easy to observe the SDE scheme by Coladangelo et
al. [CLLZ21] is secure even against quantum distinguishers.

Once we obtain a single-key single-decryptor PKFE scheme, we can transform it
into a collusion-resistant single-decryptor PKFE scheme by again using IO.
This transformation is based on one from a single-key standard PKFE scheme
into a collusion-resistant standard PKFE scheme [BNPW20, KNT21]. The idea is
as follows. We need to generate a fresh instance of the single-key scheme
above for _each random tag_ and bundle (unbounded) polynomially many instances
to achieve collusion-resistance. We use IO to bundle multiple instances of
single-key SDFE. More specifically, a public key is an obfuscated circuit of
the following setup circuit. The setup circuit takes a public tag $\tau$ as
input, generates a key pair $(\mathsf{pk}_{\tau},\mathsf{msk}_{\tau})$ of the
single-key SDFE scheme using PRF value $\mathsf{F}_{\mathsf{K}}(\tau)$ as
randomness, and outputs only $\mathsf{pk}_{\tau}$. The master secret key is
the PRF key $\mathsf{K}$. We can generate a functional decryption key for $f$
by choosing a random tag $\tau$ and generating a functional decryption key
$\mathpzc{sk}_{f,\tau}$ under $\mathsf{msk}_{\tau}$. A functional decryption
key of our collusion-resistant scheme consists of
$(\tau,\mathpzc{sk}_{f,\tau})$. A ciphertext is an obfuscated circuit of the
following encryption circuit, where a plaintext $x$ is hardwired. The
encryption circuit takes a public tag $\tau$, generates $\mathsf{pk}_{\tau}$
by using the public key explained above, and outputs a ciphertext of $x$ under
$\mathsf{pk}_{\tau}$. Due to this mechanism, only one functional decryption
key $\mathpzc{sk}_{f,\tau}$ under $\mathsf{msk}_{\tau}$ is issued for each
$\tau$, but we can generate polynomially many functional decryption keys by
using many tags. If we use a different tag $\tau^{\prime}$, an independent key
pair $(\mathsf{pk}_{\tau^{\prime}},\mathsf{msk}_{\tau^{\prime}})$ is generated
and it is useless for another instance under
$(\mathsf{pk}_{\tau},\mathsf{msk}_{\tau})$. The IO security guarantees that
the information about $\mathsf{K}$ (and $\mathsf{msk}_{\tau}$) is hidden.777We
use puncturable PRFs and the puncturing technique here as the standard
technique for cryptographic primitives based on IO [SW21]. Thus, we can reduce
the collusion-resistance to the single-key security of the underlying single-
decryptor PKFE. Note that we need to consider super-polynomially many hybrid
games to complete the proof since the tag space size must be super-polynomial
to treat _unbounded_ polynomially many tags. This is the reason why we need
the sub-exponential security for building blocks.

###  1.4 More on Related Work

#### Secure software leasing.

Ananth and La Place [AL21] achieve secure software leasing for
$\mathsf{subEVS}$ from the QLWE assumption and IO. Kitagawa, Nishimaki, and
Yamakawa [KNY21] achieve secure software leasing for PRFs and
$\mathsf{subEVS}$ only from the QLWE (that is, without IO). Broadbent,
Jeffery, Lord, Podder, and Sundaram [BJL+21] achieve secure software leasing
for $\mathsf{subEVS}$ without assumptions. Coladangelo, Majenz, and Poremba
[CMP20] also achieve secure software leasing for $\mathsf{subEVS}$ in the
quantum random oracle (QROM) model (without assumptions).

In secure software leasing, we force adversaries to run pirate software by an
_honest_ evaluation algorithm denoted by $\mathpzc{Run}$ [AL21]. An honest
evaluation algorithm verifies the format of software when software is
executed, and adversaries cannot adopt arbitrary strategies for creating
pirate software. Aaronson, Liu, Liu, Zhandry, and Zhang [ALL+21] introduce
copy-detection, which is essentially the same notion as secure software
leasing. Although a check algorithm verifies returned software, there is no
honest evaluation algorithm, and adversaries can adopt arbitrary strategies in
the copy-detection setting. Aaronson et al. [ALL+21] achieve copy-detection
for PRFs, PKE, and signatures from IO and standard cryptographic assumptions.
Those cryptographic functionalities are much weaker than FE. Moreover, we need
IO to achieve security against adversaries that adopt any strategy to execute
pirate software. Secure software leasing by Coladangelo et al. [CMP20] is also
secure against such arbitrary adversaries, but their construction relies on
QROM, and its functionality is severely limited.

#### Certified deletion.

Broadbent and Islam [BI20] present the notion of quantum encryption with
certified deletion. They achieve one-time SKE with certified deletion without
assumptions. Hiroka, Morimae, Nishimaki, and Yamakawa [HMNY21] extend the
notion to reusable SKE, PKE, and ABE with certified deletion, and instantiate
them with standard SKE, PKE, and IO and OWFs, respectively. Our FE with secure
key leasing can also be seen as certified deletion for functional decryption
keys.

#### Copy-protection.

Aaronson [Aar09] achieves copy-protection for arbitrary unlearnable Boolean
functions _relative to a quantum oracle_ , and presents two _heuristic_ copy-
protection schemes for point functions. Aaronson et al. [ALL+21] achieve
quantum copy-protection for all unlearnable functions by using _classical
oracles_. Georgiou and Zhandry [GZ20] present the notion of SDE and
instantiate it with one-shot signatures [AGKZ20] and extractable witness
encryption (WE) [GKP+13]. They also introduce the notion of broadcast
encryption with unclonable decryption and splittable ABE, which can be seen as
copy-protected variants of broadcast encryption and ABE, respectively. They
instantiate splittable ABE with the same tools as those for SDE. They
instantiate broadcast encryption with unclonable decryption with tokenized
signatures [BS17], extractable WE, and collision-resistant hash functions.
Coladangelo et al. [CLLZ21] achieve quantum copy-protection for PRFs and SDE
from IO and OWFs, the QLWE assumption, and the strong monogamy-of-entanglement
conjecture. Later, Culf and Vidick prove that the strong monogamy-of-
entanglement conjecture is true without any assumption [CV21]. Those
cryptographic functionalities are weaker than FE, as in the case of secure
software leasing. Most of those works rely on magical oracles or knowledge-
type assumptions such as the existence of extractable WE, which is implausible
[GGHW17]. Only the constructions by Coladangelo et al. [CLLZ21, CV21] do not
rely on such strong tools. However, note that there is no provably secure
_post-quantum_ IO from well-founded assumptions so far.888There are some
candidates [BGMZ18, CHVW19, AP20, DQV+21]. The known IO constructions from
well-founded assumptions [JLS21, JLS22] are vulnerable against quantum
adversaries.

Ben-David and Sattath [BS17] present the notion of tokenized signatures, where
we can generate a delegated signing token from a signing key. A signing token
enables a user to sign one and only one message. They instantiate it with
virtual black-box obfuscation [BGI+12]. Amos, Georgiou, Kiayias, and Zhandry
present the notion of one-shot signatures, where adversaries cannot generate
two valid signatures for different two messages even under an adversarially
generated verification key. They instantiate it with _classical oracles_ ,
which can be seen as an idealized virtual black-box obfuscation. Those are
copy-protected variants of signatures. Relationships between (copy-protected)
FE and them are not known so far.

#### Functional encryption.

FE has been extensively studied since Boneh, Sahai, and Waters [BSW11]
formally defined its notion. Although there are many works on FE, we focus on
FE for $\mathsf{P}/\mathsf{poly}$ that are closely related to our work in this
paper.

Sahai and Seyalioglu [SS10] present the first (selectively secure) single-key
PKFE for $\mathsf{P}/\mathsf{poly}$ from PKE. Gorbunov, Vaikuntanathan, and
Wee [GVW12] present transformations from (adaptively secure) single-key PKFE
for $\mathsf{NC}^{1}$ into (adaptively secure) bounded collusion-resistant
PKFE for $\mathsf{P}/\mathsf{poly}$ by using pseudorandom generators (PRGs) in
$\mathsf{NC}^{1}$. The transformation also converts single-key and many-
ciphertext SKFE for $\mathsf{NC}^{1}$ into bounded collusion-resistant and
many-ciphertext SKFE for $\mathsf{P}/\mathsf{poly}$. They also show that we
can achieve adaptively secure single-key PKFE (resp. SKFE) for
$\mathsf{NC}^{1}$ from PKE (resp. OWFs). Ananth, Brakerski, Segev, and
Vaikuntanathan [ABSV15] observe that we can invert the roles of the functions
and plaintexts in SKFE by using the function-privacy of SKFE [BS18], and
obtain collusion-resistant and bounded many-ciphertext SKFE for
$\mathsf{P}/\mathsf{poly}$ from OWFs by using the transformations. Later,
Ananth and Vaikuntanathan [AV19] improve the assumptions (remove PRGs in
$\mathsf{NC}^{1}$) for the transformation and achieve the optimal ciphertext
size (in the asymptotic sense). These transformations [GVW12, AV19] run $N$
independent copies of a single-key FE scheme and encrypt the views of some
$N$-party multi-party computation (MPC) protocol. Agrawal and Rosen [AR17]
construct bounded collusion-resistant PKFE for $\mathsf{NC}^{1}$ by using FE
for inner-product [ABDP15, ALS16] and the homomorphic property of some
encryption scheme [BV11].999We can upgrade FE for $\mathsf{NC}^{1}$ to FE for
$\mathsf{P}/\mathsf{poly}$ by using randomized encoding [ABSV15]. Their
construction supports arithmetic circuits. Agrawal, Maitra, Vempati, and
Yamada [AMVY21] and Garg, Goyal, Lu, and Waters [GGLW21] concurrently and
independently present the notion of dynamic bounded collusion-resistant FE and
how to achieve it from identity-based encryption (IBE). In the dynamic bounded
collusion setting, the setup algorithm of FE does not depend on the number of
key queries, and only the encryption algorithm of FE depends on it.

Security amplification is transforming an $\epsilon$-secure cryptographic
scheme into a $\nu$-secure one, where $\epsilon\in(0,1)$ is a constant and
$\nu$ is a negligible function. Ananth, Jain, Lin, Matt, and Sahai [AJL+19]
propose security amplification techniques for standard FE. Their techniques
are based on multi-key homomorphic encryption, which can be instantiated with
the LWE assumption. Jain, Korb, Manohar, and Sahai [JKMS20] also propose how
to amplify the security of standard FE by using SetHSS, which can be
instantiated with OWFs.

IO for $\mathsf{P}/\mathsf{poly}$ is necessary and sufficient for collusion-
resistant FE (for $\mathsf{NC}^{1}$) up to sub-exponential security loss
[GGH+16, BV18, AJ15, AJS15, KNT22]. Jain, Lin, and Sahai [JLS21, JLS22]
achieve the first IO (and collusion-resistant FE for
$\mathsf{P}/\mathsf{poly}$) from well-founded assumptions. However, they are
not post-quantum secure since the constructions heavily rely on cryptographic
bilinear maps.

Revocation mechanisms have been extensively studied, especially in the context
of broadcast encryption [NP01, NNL01].101010We omit references since there are
too many previous works on broadcast encryption and trace-and-revoke systems.
Nishimaki et al. [NWZ16] introduce revocable FE to achieve a trace-and-revoke
system with flexible identities. They achieve the first revocable FE by using
IO and OWFs. We need to manage a revocation list and update ciphertexts to
revoke a user.

##  2 Preliminaries

#### Notations and conventions.

In this paper, standard math or sans serif font stands for classical
algorithms (e.g., $C$ or $\mathsf{Gen}$) and classical variables (e.g., $x$ or
$\mathsf{pk}$). Calligraphic font stands for quantum algorithms (e.g.,
$\mathpzc{Gen}$) and calligraphic font and/or the bracket notation for (mixed)
quantum states (e.g., $\mathpzc{q}$ or $\ket{\psi}$). For strings $x$ and $y$,
$x\|y$ denotes the concatenation of $x$ and $y$. Let $\boldsymbol{0}$ denote a
string consisting of an appropriate number of $0$. Let $[\ell]$ denote the set
of integers $\\{1,\cdots,\ell\\}$, $\lambda$ denote a security parameter, and
$y\coloneqq z$ denote that $y$ is set, defined, or substituted by $z$.

In this paper, for a finite set $X$ and a distribution $D$, $x\leftarrow X$
denotes selecting an element from $X$ uniformly at random, $x\leftarrow D$
denotes sampling an element $x$ according to $D$. Let
$y\leftarrow\mathsf{A}(x)$ and $y\leftarrow\mathpzc{A}(\mathpzc{x})$ denote
assigning to $y$ the output of a probabilistic or deterministic algorithm
$\mathsf{A}$ and a quantum algorithm $\mathpzc{A}$ on an input $x$ and
$\mathpzc{x}$, respectively. When we explicitly show that $\mathsf{A}$ uses
randomness $r$, we write $y\leftarrow\mathsf{A}(x;r)$. PPT and QPT algorithms
stand for probabilistic polynomial-time algorithms and polynomial-time quantum
algorithms, respectively. Let ${\mathsf{negl}}$ denote a negligible function.

###  2.1 Standard Cryptographic Tools

###### Definition 2.1 (Pseudorandom Function).

Let
$\\{\mathsf{F}_{K}:\\{0,1\\}^{\ell_{1}}\rightarrow\allowbreak\\{0,1\\}^{\ell_{2}}\mid
K\in\\{0,1\\}^{\lambda}\\}$ be a family of polynomially computable functions,
where $\ell_{1}$ and $\ell_{2}$ are some polynomials of $\lambda$. We say that
$\mathsf{F}$ is a pseudorandom function (PRF) family if, for any PPT
distinguisher $\mathcal{A}$, there exists ${\mathsf{negl}}(\cdot)$ such that
it holds that

$\displaystyle\absolutevalue{\Pr[\mathpzc{A}^{\mathsf{F}_{K}(\cdot)}(1^{\lambda})=1\mid
K\leftarrow\\{0,1\\}^{\lambda}]-\Pr[\mathpzc{A}^{\mathsf{R}(\cdot)}(1^{\lambda})=1\mid\mathsf{R}\leftarrow\mathcal{U}]}\leq{\mathsf{negl}}(\lambda),$
(1)

where $\mathcal{U}$ is the set of all functions from $\\{0,1\\}^{\ell_{1}}$ to
$\\{0,1\\}^{\ell_{2}}$.

###### Theorem 2.2 ([GGM86]).

If one-way functions exist, then for all efficiently computable functions
$n(\lambda)$ and $m(\lambda)$, there exists a PRF that maps $n(\lambda)$ bits
to $m(\lambda)$ bits.

###### Definition 2.3 (Secret Key Encryption).

An SKE scheme $\mathsf{SKE}$ is a two tuple $(\mathsf{E},\mathsf{D})$ of PPT
algorithms.

  * •

The encryption algorithm $\mathsf{E}$, given a key $K\in\\{0,1\\}^{\lambda}$
and a plaintext $m\in\mathcal{M}$, outputs a ciphertext $\mathsf{ct}$, where
$\mathcal{M}$ is the plaintext space of $\mathsf{SKE}$.

  * •

The decryption algorithm $\mathsf{D}$, given a key $K$ and a ciphertext
$\mathsf{ct}$, outputs a plaintext $\tilde{m}\in\\{\bot\\}\cup\mathcal{M}$.
This algorithm is deterministic.

Correctness:

We require $\mathsf{D}(K,\mathsf{E}(K,m))=m$ for every $m\in\mathcal{M}$ and
key $K\in\\{0,1\\}^{\lambda}$.

CPA Security:

We define the following experiment
$\mathsf{Expt}_{\mathpzc{A},\mathsf{SKE}}^{\mathsf{cpa}}(1^{\lambda},\mathsf{coin})$
between a challenger and an adversary $\mathpzc{A}$.

  1. 1.

The challenger generates $K\leftarrow\\{0,1\\}^{\lambda}$. Then, the
challenger sends $1^{\lambda}$ to $\mathpzc{A}$.

  2. 2.

$\mathpzc{A}$ may make polynomially many encryption queries adaptively.
$\mathpzc{A}$ sends $(m_{0},m_{1})\in\mathcal{M}\times\mathcal{M}$ to the
challenger. Then, the challenger returns
$\mathsf{ct}\leftarrow\mathsf{E}(K,m_{\mathsf{coin}})$.

  3. 3.

$\mathpzc{A}$ outputs $\mathsf{coin}^{\prime}\in\\{0,1\\}$.

We say that $\mathsf{SKE}$ is CPA secure if for any QPT adversary
$\mathpzc{A}$, we have

$\mathsf{Adv}_{\mathsf{SKE},\mathpzc{A}}^{\mathsf{cpa}}(\lambda)=\absolutevalue{\Pr[\mathsf{Expt}_{\mathpzc{A},\mathsf{SKE}}^{\mathsf{cpa}}(1^{\lambda},0)=1]-\Pr[\mathsf{Expt}_{\mathpzc{A},\mathsf{SKE}}^{\mathsf{cpa}}(1^{\lambda},1)=1]}\leq{\mathsf{negl}}(\lambda).$

###### Definition 2.4 (Ciphertext Pseudorandomness for SKE).

Let $\\{0,1\\}^{\ell}$ be the ciphertext space of $\mathsf{SKE}$. We define
the following experiment
$\mathsf{Exp}_{\mathpzc{A},\mathsf{SKE}}^{\mathsf{pr}\mbox{-}\mathsf{ct}}(1^{\lambda},\mathsf{coin})$
between a challenger and an adversary $\mathpzc{A}$.

  1. 1.

The challenger generates $K\leftarrow\\{0,1\\}^{\lambda}$. Then, the
challenger sends $1^{\lambda}$ to $\mathpzc{A}$.

  2. 2.

$\mathpzc{A}$ may make polynomially many encryption queries adaptively.
$\mathpzc{A}$ sends $m\in\mathcal{M}$ to the challenger. Then, the challenger
returns $\mathsf{ct}\leftarrow\mathsf{E}(K,m)$ if $\mathsf{coin}=0$, otherwise
$\mathsf{ct}\leftarrow\\{0,1\\}^{\ell}$.

  3. 3.

$\mathpzc{A}$ outputs $\mathsf{coin}^{\prime}\in\\{0,1\\}$.

We say that $\mathsf{SKE}$ is pseudorandom-secure if for any QPT adversary
$\mathpzc{A}$, we have

$\mathsf{Adv}_{\mathsf{SKE},\mathpzc{A}}^{\mathsf{pr}\mbox{-}\mathsf{ct}}(\lambda)=\absolutevalue{\Pr[\mathsf{Exp}_{\mathpzc{A},\mathsf{SKE}}^{\mathsf{pr}\mbox{-}\mathsf{ct}}(1^{\lambda},0)=1]-\Pr[\mathsf{Exp}_{\mathpzc{A},\mathsf{SKE}}^{\mathsf{pr}\mbox{-}\mathsf{ct}}(1^{\lambda},1)=1]}\leq{\mathsf{negl}}(\lambda).$

###### Theorem 2.5.

If OWFs exist, there exists a pseudorandom-secure SKE scheme.

###### Definition 2.6 (Secret-Key Functional Encryption).

An SKFE scheme $\mathsf{SKFE}$ is a tuple of four PPT algorithms
$(\mathsf{Setup},\mathsf{KG},\mathsf{Enc},\mathsf{Dec})$. Below, let
$\mathcal{X}$, $\mathcal{Y}$, and $\mathcal{F}$ be the plaintext, output, and
function spaces $\mathsf{SKFE}$, respectively.

$\mathsf{Setup}(1^{\lambda},1^{q})\rightarrow\mathsf{msk}$:

The setup algorithm takes a security parameter $1^{\lambda}$ and a collusion
bound $1^{q}$, and outputs a master secret key $\mathsf{msk}$.

$\mathsf{KG}(\mathsf{msk},f)\rightarrow\mathsf{sk}_{f}$:

The key generation algorithm takes a master secret key $\mathsf{msk}$ and a
function $f\in\mathcal{F}$, and outputs a functional decryption key
$\mathsf{sk}_{f}$.

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

The encryption algorithm takes a master secret key $\mathsf{msk}$ and a
plaintext $x\in\mathcal{X}$, and outputs a ciphertext $\mathsf{ct}$.

$\mathsf{Dec}(\mathsf{sk}_{f},\mathsf{ct})\rightarrow y$:

The decryption algorithm takes a functional decryption key $\mathsf{sk}_{f}$
and a ciphertext $\mathsf{ct}$, and outputs $y\in\\{\bot\\}\cup\mathcal{Y}$.

Correctness:

We require that for every $x\in\mathcal{X}$, $f\in\mathcal{F}$,
$q\in\mathbb{N}$, we have that

$\Pr\left[\mathsf{Dec}(\mathsf{sk}_{f},\mathsf{ct})=f(x)\
\middle|\begin{array}[]{rl}&\mathsf{msk}\leftarrow\mathsf{Setup}(1^{\lambda},1^{q}),\\\
&\mathsf{sk}_{f}\leftarrow\mathsf{KG}(\mathsf{msk},f),\\\
&\mathsf{ct}\leftarrow\mathsf{Enc}(\mathsf{msk},x)\end{array}\right]=1-{\mathsf{negl}}(\lambda).$

###### Definition 2.7 (Selective Indistinguishability-Security).

We say that $\mathsf{SKFE}$ is a selectively indistinguishability-secure SKFE
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}}^{\mathsf{sel}\mbox{-}\mathsf{ind}}(1^{\lambda},\mathsf{coin})$
between an adversary $\mathpzc{A}$ and a challenger:

  1. 1.

At the beginning, $\mathpzc{A}$ sends $(1^{q},x_{0}^{*},x_{1}^{*})$ to the
challenger. The challenger runs
$\mathsf{msk}\leftarrow\mathsf{Setup}(1^{\lambda},1^{q})$. Also, the
challenger generates
$\mathsf{ct}^{*}\leftarrow\mathsf{Enc}(\mathsf{msk},x_{\mathsf{coin}}^{*})$
and sends $\mathsf{ct}^{*}$ to $\mathpzc{A}$. 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{\mathsf{KG}}}(f)$:

Given $f$, if $f(x_{0}^{*})\neq f(x_{1}^{*})$, it returns $\bot$. Otherwise,
it returns $\mathsf{KG}(\mathsf{msk},f)$. $\mathpzc{A}$ can access this oracle
at most $q$ times.

  2. 2.

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

We say that $\mathsf{SKFE}$ is selectively indistinguishability-secure if, for
any QPT $\mathpzc{A}$, it holds that

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

It is easy to see that we can consider the adaptively indistinguishability-
secure variant as in Definition 7.15.

###### Theorem 2.8 ([GVW12]).

If there exist OWFs, then there exists selectively indistinguishability-secure
SKFE for $\mathsf{P}/\mathsf{poly}$.

###  2.2 Advanced Tools

We present the definitions for reusable SKE with certified deletion introduced
by Hiroka et al. [HMNY21]

###### Definition 2.9 (Reusable SKE with Certified Deletion (Syntax)).

A secret key encryption scheme with certified deletion is a tuple of quantum
algorithms
$(\mathsf{KG},\mathpzc{Enc},\mathpzc{Dec},\mathpzc{Del},\mathsf{Vrfy})$ with
plaintext space $\mathcal{M}$ and key space $\mathcal{K}$.

$\mathsf{KG}(1^{\lambda})\rightarrow\mathsf{sk}$:

The key generation algorithm takes as input the security parameter
$1^{\lambda}$ and outputs a secret key $\mathsf{sk}\in\mathcal{K}$.

$\mathpzc{Enc}(\mathsf{sk},m)\rightarrow(\mathsf{vk},\mathpzc{ct})$:

The encryption algorithm takes as input $\mathsf{sk}$ and a plaintext
$m\in\mathcal{M}$ and outputs a verification key $\mathsf{vk}$ and a
ciphertext $\mathpzc{ct}$.

$\mathpzc{Dec}(\mathsf{sk},\mathpzc{ct})\rightarrow m^{\prime}$:

The decryption algorithm takes as input $\mathsf{sk}$ and $\mathpzc{ct}$ and
outputs a plaintext $m^{\prime}\in\mathcal{M}$ or $\bot$.

$\mathpzc{Del}(\mathpzc{ct})\rightarrow\mathsf{cert}$:

The deletion algorithm takes as input $\mathpzc{ct}$ and outputs a
certification $\mathsf{cert}$.

$\mathsf{Vrfy}(\mathsf{vk},\mathsf{cert})\rightarrow\top\mbox{ or }\bot$:

The verification algorithm takes $\mathsf{vk}$ and $\mathsf{cert}$ and outputs
$\top$ or $\bot$.

Decryption correctness:

There exists a negligible function ${\mathsf{negl}}$ such that for any
$m\in\mathcal{M}$,

$\displaystyle\Pr\left[\mathpzc{Dec}(\mathsf{sk},\mathpzc{ct})=m\
\middle|\begin{array}[]{ll}\mathsf{sk}\leftarrow\mathsf{KG}(1^{\lambda})\\\
(\mathsf{vk},\mathpzc{ct})\leftarrow\mathpzc{Enc}(\mathsf{sk},m)\end{array}\right]=1-{\mathsf{negl}}(\lambda).$
(5)

Verification correctness:

There exists a negligible function ${\mathsf{negl}}$ such that for any
$m\in\mathcal{M}$,

$\displaystyle\Pr\left[\mathsf{Vrfy}(\mathsf{vk},\mathsf{cert})=\top\
\middle|\begin{array}[]{ll}\mathsf{sk}\leftarrow\mathsf{KG}(1^{\lambda})\\\
(\mathsf{vk},\mathpzc{ct})\leftarrow\mathpzc{Enc}(\mathsf{sk},m)\\\
\mathsf{cert}\leftarrow\mathpzc{Del}(\mathpzc{ct})\end{array}\right]=1-{\mathsf{negl}}(\lambda).$
(9)

###### Definition 2.10 (IND-CPA-CD Security for Reusable SKE with Certified
Deletion).

Let
$\Sigma=(\mathsf{KG},\mathpzc{Enc},\mathpzc{Dec},\mathpzc{Del},\mathsf{Vrfy})$
be a secret key encryption with certified deletion. We consider the following
security experiment
$\mathsf{Exp}_{\Sigma,\mathpzc{A}}^{\mathsf{sk}\mbox{-}\mathsf{cert}\mbox{-}\mathsf{del}}(\lambda,b)$.

  1. 1.

The challenger computes $\mathsf{sk}\leftarrow\mathsf{KG}(1^{\lambda})$.

  2. 2.

$\mathpzc{A}$ sends an encryption query $m$ to the challenger. The challenger
computes $(\mathsf{vk},\mathpzc{ct})\leftarrow\mathpzc{Enc}(\mathsf{sk},m)$ to
$\mathpzc{A}$ and returns $(\mathsf{vk},\mathpzc{ct})$ to $\mathpzc{A}$. This
process can be repeated polynomially many times.

  3. 3.

$\mathpzc{A}$ sends $(m_{0},m_{1})\in\mathcal{M}^{2}$ to the challenger.

  4. 4.

The challenger computes
$(\mathsf{vk}_{b},\mathpzc{ct}_{b})\leftarrow\mathpzc{Enc}(\mathsf{sk},m_{b})$
and sends $\mathpzc{ct}_{b}$ to $\mathpzc{A}$.

  5. 5.

Again, $\mathpzc{A}$ can send encryption queries.

  6. 6.

At some point, $\mathpzc{A}$ sends $\mathsf{cert}$ to the challenger.

  7. 7.

The challenger computes $\mathsf{Vrfy}(\mathsf{vk}_{b},\mathsf{cert})$. If the
output is $\bot$, the challenger sends $\bot$ to $\mathpzc{A}$. If the output
is $\top$, the challenger sends $\mathsf{sk}$ to $\mathpzc{A}$.

  8. 8.

If the challenger sends $\bot$ in the previous item, $\mathpzc{A}$ can send
encryption queries again.

  9. 9.

$\mathpzc{A}$ outputs $b^{\prime}\in\\{0,1\\}$.

We say that $\Sigma$ is IND-CPA-CD secure if for any QPT $\mathpzc{A}$, it
holds that

$\displaystyle\mathsf{Adv}_{\Sigma,\mathpzc{A}}^{\mathsf{sk}\mbox{-}\mathsf{cert}\mbox{-}\mathsf{del}}(\lambda)\coloneqq\absolutevalue{\Pr[\mathsf{Exp}_{\Sigma,\mathpzc{A}}^{\mathsf{sk}\mbox{-}\mathsf{cert}\mbox{-}\mathsf{del}}(\lambda,0)=1]-\Pr[\mathsf{Exp}_{\Sigma,\mathpzc{A}}^{\mathsf{sk}\mbox{-}\mathsf{cert}\mbox{-}\mathsf{del}}(\lambda,1)=1]}\leq{\mathsf{negl}}(\lambda).$
(10)

We introduce an additional property for certificates.

###### Definition 2.11 (Unique Certificate).

We say that an SKE scheme with certified deletion has the unique certificate
property if there is at most one certification $\mathsf{cert}$ for each
$\mathsf{vk}$ output by $\mathsf{Enc}$ such that
$\top=\mathsf{Vrfy}(\mathsf{vk},\mathsf{cert})$.

Known constructions of SKE (and PKE) with certified deletion based on BB84
states has the unique certificate property.

###### Theorem 2.12 ([HMNY21]).

If there exist OWFs, there exists an IND-CPA-CD secure SKE scheme that has the
unique certificate property.

We introduce a variant of IND-CPA-CD security where the adversary can send
many verification queries, called indistinguishability against Chosen
Verification Attacks (CVA). We use this security notion to achieve SKFE with
secure key leasing in Section 4.

###### Definition 2.13 (IND-CVA-CD Security for Reusable SKE with Certified
Deletion).

Let
$\Sigma=(\mathsf{KG},\mathpzc{Enc},\mathpzc{Dec},\mathpzc{Del},\mathsf{Vrfy})$
be a secret key encryption with certified deletion. We consider the following
security experiment
$\mathsf{Exp}_{\Sigma,\mathpzc{A}}^{\mathsf{sk}\mbox{-}\mathsf{cert}\mbox{-}\mathsf{vo}}(\lambda,b)$.

  1. 1.

The challenger computes $\mathsf{sk}\leftarrow\mathsf{KG}(1^{\lambda})$.

  2. 2.

$\mathpzc{A}$ sends an encryption query $m$ to the challenger. The challenger
computes $(\mathsf{vk},\mathsf{ct})\leftarrow\mathpzc{Enc}(\mathsf{sk},m)$ to
$\mathpzc{A}$ and returns $(\mathsf{vk},\mathsf{ct})$ to $\mathpzc{A}$. This
process can be repeated polynomially many times.

  3. 3.

$\mathpzc{A}$ sends $(m_{0},m_{1})\in\mathcal{M}^{2}$ to the challenger.

  4. 4.

The challenger computes
$(\mathsf{vk}_{b},\mathpzc{ct}_{b})\leftarrow\mathpzc{Enc}(\mathsf{sk},m_{b})$
and sends $\mathpzc{ct}_{b}$ to $\mathpzc{A}$.

  5. 5.

Again, $\mathpzc{A}$ can send encryption queries. $\mathpzc{A}$ can also send
a verification query $\mathsf{cert}$ to the challenger. The challenger returns
$\mathsf{sk}$ if $\top=\mathsf{Vrfy}(\mathsf{vk}_{b},\mathsf{cert})$, $\bot$
otherwise. This process can be repeated polynomially many times.

  6. 6.

$\mathpzc{A}$ outputs $b^{\prime}\in\\{0,1\\}$.

We say that $\Sigma$ is IND-CVA-CD secure if for any QPT $\mathpzc{A}$, it
holds that

$\displaystyle\mathsf{Adv}_{\Sigma,\mathpzc{A}}^{\mathsf{sk}\mbox{-}\mathsf{cert}\mbox{-}\mathsf{vo}}(\lambda)\coloneqq\absolutevalue{\Pr[\mathsf{Exp}_{\Sigma,\mathpzc{A}}^{\mathsf{sk}\mbox{-}\mathsf{cert}\mbox{-}\mathsf{vo}}(\lambda,0)=1]-\Pr[\mathsf{Exp}_{\Sigma,\mathpzc{A}}^{\mathsf{sk}\mbox{-}\mathsf{cert}\mbox{-}\mathsf{vo}}(\lambda,1)=1]}\leq{\mathsf{negl}}(\lambda).$
(11)

Known IND-CPA-CD secure SKE schemes satisfy IND-CVA-CD security thanks to the
following theorem since they satisfy Definition 2.11.

###### Theorem 2.14.

If an SKE scheme is IND-CPA-CD secure and has the unique certificate property,
then it also satisfies IND-CVA-CD security.

###### Proof.

We construct an adversary $\mathpzc{B}$ for IND-CPA-CD by using an adversary
$\mathpzc{A}$ for IND-CVA-CD as follows.

  1. 1.

At the beginning, the adversary $\mathpzc{A}$ is fixed, so the number of the
verification query by $\mathpzc{A}$ is also fixed. We denote the number by
$q$.

  2. 2.

When $\mathpzc{A}$ sends an encryption query $m$, $\mathpzc{B}$ sends $m$ to
its challenger, receives
$(\mathsf{vk},\mathpzc{ct})\leftarrow\mathpzc{Enc}(\mathsf{sk},m)$, and passes
$(\mathsf{vk},\mathpzc{ct})$ to $\mathpzc{A}$.

  3. 3.

When $\mathpzc{A}$ sends $(m_{0},m_{1})$, $\mathpzc{B}$ sends $(m_{0},m_{1})$
to its challenger, receives $\mathpzc{ct}_{b}$, passes $\mathpzc{ct}_{b}$ to
$\mathpzc{A}$.

  4. 4.

Then, $\mathpzc{B}$ guesses an index $i^{\ast}\leftarrow[q+1]$.

  5. 5.

When $\mathpzc{A}$ sends $\mathsf{cert}_{i}$ as the $i$-th verification query,
if $i<i^{\ast}$, $\mathpzc{B}$ returns $\bot$. When $\mathpzc{A}$ sends
$\mathsf{cert}_{i^{\ast}}$ as the $i^{\ast}$-th verification query, if there
exits $i$ such that $\mathsf{cert}_{i}=\mathsf{cert}_{i^{\ast}}$,
$\mathpzc{B}$ aborts. Otherwise, $\mathpzc{B}$ forwards
$\mathsf{cert}_{i^{\ast}}$ to its challenger. If $\mathpzc{B}$ receives
$\bot$, $\mathpzc{B}$ aborts. If $\mathpzc{B}$ receives $\mathsf{sk}$, then
$\mathpzc{B}$ passes $\mathsf{sk}$ to $\mathpzc{A}$. After $\mathpzc{B}$
receives $\mathsf{sk}$, if a query
$\mathsf{cert}_{i}=\mathsf{cert}_{i^{\ast}}$, $\mathpzc{B}$ answers
$\mathsf{sk}$, otherwise $\bot$.

  6. 6.

$\mathpzc{B}$ outputs what $\mathpzc{A}$ outputs.

Since we consider unique certificate SKE with certified deletion, if
$\mathcal{B}$ receives $\mathsf{sk}$ from its challenger, it is the only one
correct certificate under $\mathsf{vk}_{b}$. Hence, $\mathpzc{B}$ can
correctly simulate the IND-CVA-CD game with probability $1/(q+1)$ (Note that
$i^{\ast}=q+1$ means $\mathpzc{A}$ did not output a correct certificate).
Therefore, we obtain
$\mathsf{Adv}_{\Sigma,\mathpzc{A}}^{\mathsf{sk}\mbox{-}\mathsf{cert}\mbox{-}\mathsf{del}}(\lambda)=\frac{1}{q+1}\mathsf{Adv}_{\Sigma,\mathpzc{A}}^{\mathsf{sk}\mbox{-}\mathsf{cert}\mbox{-}\mathsf{vo}}(\lambda)$,
and the proof completes.

###### Definition 2.15 (Set Homomorphic Secret Sharing).

A set homomorphic secret sharing scheme $\mathsf{SetHSS}$ consists of three
algorithms $(\mathsf{InpEncode},\mathsf{FuncEncode},\mathsf{Decode})$. Below,
we let $\mathcal{X}$, $\mathcal{Y}$, and $\mathcal{F}$ be the input, output,
and function spaces of $\mathsf{SetHSS}$, respectively.

$\mathsf{SetGen}(1^{\lambda})\rightarrow\mathsf{params}\coloneqq(p,\ell,(T_{i})_{i\in[m]})$:

The set generation algorithm takes as input a security parameter, and outputs
parameters $p$ and $\ell$, and a collection of $m$ sets $(T_{i})_{i\in[m]}$,
where each set $T_{i}\subseteq[\ell]$.

$\mathsf{InpEncode}(\mathsf{params},x)\rightarrow(s_{i})_{i\in[m]}$:

The input encoding algorithm takes as input $\mathsf{params}$ output by
$\mathsf{SetGen}$ and an input $x\in\mathcal{X}$, and outputs a set of input
shares $(s_{i})_{i\in[m]}$.

$\mathsf{FuncEncode}(\mathsf{params},f)\rightarrow(f_{i})_{i\in[m]}$:

The function encoding algorithm takes as input $\mathsf{params}$ output by
$\mathsf{SetGen}$ and a function $f\in\mathcal{F}$, and outputs a set of
function shares $(f_{i})_{i\in[m]}$.

$\mathsf{Decode}((f_{i}(s_{i}))_{i\in[m]})\rightarrow y$:

The decoding algorithm takes as input a set of evaluations of function shares
on their respective input shares $(f_{i}(s_{i}))_{i\in[m]}$ and outputs a
value $y\in\mathcal{Y}$.

Correctness:

We require that for every $x\in\mathcal{X}$, $f\in\mathcal{F}$, we have that

$\Pr\left[\mathsf{Decode}((f_{i}(s_{i}))_{i\in[m]})\neq f(x)\
\middle|\begin{array}[]{rl}&\mathsf{params}=(p,\ell,(T_{i})_{i\in[m]})\leftarrow\mathsf{SetGen}(1^{\lambda}),\\\
&(s_{i})_{i\in[m]}\leftarrow\mathsf{InpEncode}(\mathsf{params},x),\\\
&(f_{i})_{i\in[m]}\leftarrow\mathsf{FuncEncode}(\mathsf{params},f)\end{array}\right]={\mathsf{negl}}(\lambda).$

Existence of Unmarked Element:

Let
$\mathsf{params}=(p,\ell,(T_{i})_{i\in[m]})\leftarrow\mathsf{SetGen}(1^{\lambda})$.
Suppose we randomly generate a set $S\subseteq[m]$ so that each $i\in[m]$ is
independently included in $S$ with probability at most $p$. Then, without
negligible probability, there exists $e\in[\ell]$ such that
$e\notin\bigcup_{i\in S}T_{i}$.

Selective Indistinguishability-Security:

Consider the following experiment
$\mathsf{Exp}_{\mathpzc{A},\mathsf{SetHSS}}^{\mathsf{sel}\mbox{-}\mathsf{ind}}(1^{\lambda},\mathsf{coin})$
between an adversary $\mathpzc{A}$ and a challenger:

  1. 1.

The challenger generates
$\mathsf{params}=(p,\ell,(T_{i})_{i\in[m]})\leftarrow\mathsf{SetGen}(1^{\lambda})$
and sends $\mathsf{params}$ to $\mathpzc{A}$. $\mathpzc{A}$ sends
$(e^{*},x_{0}^{*},x_{1}^{*})$ to the challenger, where $e^{*}\in[\ell]$. The
challenger runs
$(s_{i})_{i\in[m]}\leftarrow\mathsf{InpEncode}(\mathsf{params},x_{\mathsf{coin}})$
and sends $(s_{i})_{i\in[m]_{e^{*}\notin}}$ to $\mathpzc{A}$, where
$[m]_{e^{*}\notin}$ denotes the subset of $[m]$ consisting of $i$ such that
$e^{*}\notin T_{i}$. $\mathpzc{A}$ can access the following oracle.

$O_{\mathtt{\mathsf{FuncEncode}}}(f)$:

Given $f$, if $f(x_{0}^{*})\neq f(x_{1}^{*})$, it returns $\bot$. Otherwise,
it generates
$(f_{i})_{i\in[m]}\leftarrow\mathsf{FuncEncode}(\mathsf{params},f)$ and
returns $(f_{i},f_{i}(s_{i}))_{i\in[m]}$.

  2. 2.

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

We say that $\mathsf{SetHSS}$ is selectively indistinguishability-secure if,
for any QPT $\mathpzc{A}$, it holds that

$\displaystyle\mathsf{Adv}_{\mathsf{SetHSS},\mathpzc{A}}^{\mathsf{sel}\mbox{-}\mathsf{ind}}(\lambda)\coloneqq\absolutevalue{\Pr[\mathsf{Exp}_{\mathsf{SetHSS},\mathpzc{A}}^{\mathsf{sel}\mbox{-}\mathsf{ind}}(1^{\lambda},0)=1]-\Pr[\mathsf{Exp}_{\mathsf{SetHSS},\mathpzc{A}}^{\mathsf{sel}\mbox{-}\mathsf{ind}}(1^{\lambda},0)=1]}\leq{\mathsf{negl}}(\lambda).$
(12)

###### Theorem 2.16 ([JKMS20]).

If there exist OWFs, there exists a set homomorphic secret sharing.

The above definition of SetHSS is different from the original one by Jain et
al. [JKMS20] in that the original definition does not have the set generation
algorithm and does not require the existence of unmarked element property.
Jain et al. defined SetHSS so that it works for any collection of sets. Then,
Jain et al. separately introduced the set generation algorithm and properties
of it, which perfectly match the security bound amplification for FE. We can
obtain Theorem 2.16 from [JKMS20, Theorem 5.3, Lemma 6.1 and 6.2, in eprint
ver.] and the parmeter setting provided in the proof of [JKMS20, Theorem 8.1
in eprint ver.]. In their parameter setting, $p=1/{\mathrm{poly}}(\lambda)$,
$\ell=\lambda$, and $m={\mathrm{polylog}}(\lambda)$.

##  3 Definition of SKFE with Secure Key Leasing

We introduce the definition of SKFE with secure key leasing and its variants.

###  3.1 SKFE with Secure Key Leasing

We first define SKFE with secure key leasing (SKFE-SKL).

###### Definition 3.1 (SKFE with Secure Key Leasing).

An SKFE-SKL scheme $\mathsf{SKFE\textrm{-}SKL}$ is a tuple of six algorithms
$(\mathsf{Setup},\mathpzc{KG},\mathsf{Enc},\mathpzc{Dec},\mathpzc{Cert},\mathsf{Vrfy})$.
Below, let $\mathcal{X}$, $\mathcal{Y}$, and $\mathcal{F}$ be the plaintext,
output, and function spaces of $\mathsf{SKFE\textrm{-}SKL}$, respectively.

$\mathsf{Setup}(1^{\lambda},1^{q})\rightarrow\mathsf{msk}$:

The setup algorithm takes a security parameter $1^{\lambda}$ and a collusion
bound $1^{q}$, and outputs a master secret key $\mathsf{msk}$.

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

The key generation algorithm takes a master secret key $\mathsf{msk}$, a
function $f\in\mathcal{F}$, and an availability bound $1^{n}$, and outputs a
functional decryption key $\mathpzc{fsk}$ and a verification key
$\mathsf{vk}$.

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

The encryption algorithm takes a master secret key $\mathsf{msk}$ and a
plaintext $x\in\mathcal{X}$, and outputs a ciphertext $\mathsf{ct}$.

$\mathpzc{Dec}(\mathpzc{fsk},\mathsf{ct})\rightarrow\widetilde{x}$:

The decryption algorithm takes a functional decryption key $\mathpzc{fsk}$ and
a ciphertext $\mathsf{ct}$, and outputs a value $\tilde{x}$.

$\mathpzc{Cert}(\mathpzc{fsk})\rightarrow\mathsf{cert}$:

The certification algorithm takes a function decryption key $\mathpzc{fsk}$,
and outputs a classical string $\mathsf{cert}$.

$\mathsf{Vrfy}(\mathsf{vk},\mathsf{cert})\rightarrow\top/\bot$:

The certification-verification algorithm takes a verification key
$\mathsf{vk}$ and a string $\mathsf{cert}$, and outputs $\top$ or $\bot$.

Decryption correctness:

For every $x\in\mathcal{X}$, $f\in\mathcal{F}$, and $q,n\in\mathbb{N}$, we
have

$\displaystyle\Pr\left[\mathpzc{Dec}(\mathpzc{fsk},\mathsf{ct})\allowbreak=f(x)\
\middle|\begin{array}[]{ll}\mathsf{msk}\leftarrow\mathsf{Setup}(1^{\lambda},1^{q})\\\
(\mathpzc{fsk},\mathsf{vk})\leftarrow\mathpzc{KG}(\mathsf{msk},f,1^{n})\\\
\mathsf{ct}\leftarrow\mathsf{Enc}(\mathsf{msk},x)\end{array}\right]=1-{\mathsf{negl}}(\lambda).$
(16)

Verification correctness:

For every $f\in\mathcal{F}$ and $q,n\in\mathbb{N}$, we have

$\displaystyle\Pr\left[\mathsf{Vrfy}(\mathsf{vk},\mathsf{cert})=\top\
\middle|\begin{array}[]{ll}\mathsf{msk}\leftarrow\mathsf{Setup}(1^{\lambda},1^{q})\\\
(\mathpzc{fsk},\mathsf{vk})\leftarrow\mathpzc{KG}(\mathsf{msk},f,1^{n})\\\
\mathsf{cert}\leftarrow\mathpzc{Cert}(\mathpzc{fsk})\end{array}\right]=1-{\mathsf{negl}}(\lambda).$
(20)

###### Definition 3.2 (Selective Lessor Security).

We say that $\mathsf{SKFE\textrm{-}SKL}$ is a selectively 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{sel}\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},x_{0}^{*},x_{1}^{*})$ to the
challenger. The challenger runs
$\mathsf{msk}\leftarrow\mathsf{Setup}(1^{\lambda},1^{q})$. 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})$,
sends $\mathpzc{fsk}$ to $\mathpzc{A}$, and adds $(f,1^{n},\mathsf{vk},\bot)$
to $L_{\mathtt{\mathpzc{KG}}}$. $\mathpzc{A}$ can access this oracle at most
$q$ times.

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

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

  2. 2.

When $\mathpzc{A}$ requests the challenge ciphertext, the challenger checks if
for any entry $(f,1^{n},\mathsf{vk},M)$ in $L_{\mathtt{\mathpzc{KG}}}$ such
that $f(x_{0}^{*})\neq f(x_{1}^{*})$, it holds that $M=\top$. If so, the
challenger generates
$\mathsf{ct}^{*}\leftarrow\mathsf{Enc}(\mathsf{msk},x_{\mathsf{coin}}^{*})$
and sends $\mathsf{ct}^{*}$ to $\mathpzc{A}$. Otherwise, the challenger
outputs $0$. Hereafter, $\mathpzc{A}$ is not allowed to sends a function $f$
such that $f(x_{0}^{*})\neq f(x_{1}^{*})$ to $O_{\mathtt{\mathpzc{KG}}}$.

  3. 3.

$\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{sel}\mbox{-}\mathsf{lessor}}(\lambda)\coloneqq\absolutevalue{\Pr[\mathsf{Exp}_{\mathsf{SKFE\textrm{-}SKL},\mathpzc{A}}^{\mathsf{sel}\mbox{-}\mathsf{lessor}}(1^{\lambda},0)=1]-\Pr[\mathsf{Exp}_{\mathsf{SKFE\textrm{-}SKL},\mathpzc{A}}^{\mathsf{sel}\mbox{-}\mathsf{lessor}}(1^{\lambda},1)=1]}\leq{\mathsf{negl}}(\lambda).$
(21)

######  Remark 3.3 (On the adaptive security).

We can similarly define adaptive lessor security where we allow $\mathpzc{A}$
to adaptively choose the challenge plaintext pair $(x_{0}^{*},x_{1}^{*})$. For
standard FE, we can generically convert a selectively secure one into an
adaptively secure one without any additional assumption [ABSV15]. We observe
that a similar transformation works for SKFE with secure key leasing. Thus,
for simplicity, we focus on selective lessor security in this work. See
Section B.1 for the definition and transformation.

######  Remark 3.4 (On the simulation-based security).

We can also define a simulation-based variant of selective/adaptive lessor
security where a simulator simulates a challenge ciphertext without the
challenge plaintext $x^{\ast}$ as the simulation-based security for standard
FE [BSW11, GVW12]. We can generically convert indistinguishability-based
lessor secure SKFE with secure key leasing into a simulation-based lessor
secure one without any additional assumptions as standard FE [DIJ+13]. See
Section B.2 for the simulation-based definition and the transformation.

###  3.2 SKFE with Static-Bound Secure Key Leasing

In this section, we define SKFE with static-bound secure key leasing (SKFE-
sbSKL). It is a weaker variant of SKFE-SKL in which a single availability
bound $n$ applied to every decryption key is fixed at the setup time. We
design SKFE-sbSKL so that it can be transformed into SKFE-SKL in a generic
way. For this reason, we require an SKFE-sbSKL scheme to satisfy an efficiency
requirement called weak optimal efficiency and slightly stronger variant of
the lessor security notion. 111111We borrow the term weak optimal efficiency
from the paper by Garg, Goyal, Lu, and Waters [GGLW21], which studies dynamic
bounded collusion security for standard FE.

Below, we first introduce the syntax of SKFE-sbSKL. Then, before introducing
the definition of (selective) lessor security for it, we provide the overview
of the transformation to SKFE-SKL since we think the overview makes it easy to
understand the security notion.

###### Definition 3.5 (SKFE with Static-Bound Secure Key Leasing).

An SKFE-sbSKL scheme $\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}$ is a tuple of six
algorithms
$(\mathsf{Setup},\mathpzc{KG},\mathsf{Enc},\mathpzc{Dec},\mathpzc{Cert},\mathsf{Vrfy})$.
The only difference from a normal SKFE scheme with secure key leasing is that
$\mathpzc{KG}$ does not take as input the availability bound $n$, and instead,
$\mathsf{Setup}$ takes it as an input. Moreover, $\mathsf{Setup}$ takes it in
binary as $\mathsf{Setup}(1^{\lambda},1^{q},n)$, and we require the following
weak optimal efficiency.

Weak Optimal Efficiency:

We require that the running time of $\mathsf{Setup}$ and $\mathsf{Enc}$ is
bounded by a fixed polynomial of $\lambda$, $q$, and $\log n$.

#### Overview of the transformation to SKFE-SKL.

As seen above, $\mathsf{Setup}$ and $\mathsf{Enc}$ of an SKFE-sbSKL scheme
$\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}$ is required to run in time $\log n$.
This is because, in the transformation to SKFE-SKL, we use $\lambda$ instances
of $\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}$ where the $k$-th instance is set up
with the availability bound $2^{k}$ for every $k\in[\lambda]$. The weak
optimal efficiency ensures that $\mathsf{Setup}$ and $\mathsf{Enc}$ of all
$\lambda$ instances run in polynomial time. The details of the transformation
are as follows.

We construct an SKFE-SKL scheme $\mathsf{SKFE\textrm{-}SKL}$ from an SKFE-
sbSKL scheme
$\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}=(\mathsf{Setup},\mathpzc{KG},\mathsf{Enc},\mathpzc{Dec},\mathpzc{Cert},\mathsf{Vrfy})$.
When generating a master secret key $\mathsf{skl}.\mathsf{msk}$ of
$\mathsf{SKFE\textrm{-}SKL}$, we generate
$\mathsf{msk}_{k}\leftarrow\mathsf{Setup}(1^{\lambda},1^{q},2^{k})$ for every
$k\in[\lambda]$, and set
$\mathsf{skl}.\mathsf{msk}\coloneqq(\mathsf{msk}_{k})_{k\in[\lambda]}$. To
encrypt $x$ by $\mathsf{SKFE\textrm{-}SKL}$, we encrypt it by all $\lambda$
instances, that is, generate
$\mathsf{ct}_{k}\leftarrow\mathsf{Enc}(\mathsf{msk}_{k},x)$ for every
$k\in[\lambda]$. The resulting ciphertext is
$\mathsf{skl}.\mathsf{ct}\coloneqq(\mathsf{ct}_{k})_{k\in[\lambda]}$. To
generate a decryption key of $\mathsf{SKFE\textrm{-}SKL}$ for a function $f$
and an availability bound $n$, we first compute $k^{\prime}\in[\lambda]$ such
that $2^{k^{\prime}-1}\leq n\leq 2^{k^{\prime}}$. Then, we generate
$(\mathpzc{fsk}_{k^{\prime}},\mathsf{vk}_{k^{\prime}})\leftarrow\mathpzc{KG}(\mathsf{msk}_{k^{\prime}},f)$.
The resulting decryption key is
$\mathsf{skl}.\mathpzc{fsk}\coloneqq(k^{\prime},\mathpzc{fsk}_{k^{\prime}})$
and the corresponding verification key is
$\mathsf{vk}\coloneqq\mathsf{vk}_{k^{\prime}}$. Decryption is performed by
decrypting $\mathsf{ct}_{k^{\prime}}$ included in
$\mathsf{skl}.\mathsf{ct}\coloneqq(\mathsf{ct}_{k})_{k\in[\lambda]}$ by
$\mathpzc{fsk}_{k^{\prime}}$. The certification generation and verification of
$\mathsf{SKFE\textrm{-}SKL}$ are simply those of $\mathsf{SKFE\textrm{-}SKL}$.

We now consider the security proof of $\mathsf{SKFE\textrm{-}SKL}$. In the
experiment
$\mathsf{Exp}_{\mathpzc{A},\mathsf{SKFE\textrm{-}SKL}}^{\mathsf{sel}\mbox{-}\mathsf{lessor}}(1^{\lambda},0)$,
an adversary $\mathpzc{A}$ is given the challenge ciphertext
$\mathsf{skl}.\mathsf{ct}^{*}\coloneqq(\mathsf{ct}^{*}_{k})_{k\in[\lambda]}$,
where $\mathsf{ct}^{*}_{k}\leftarrow\mathsf{Enc}(\mathsf{msk}_{k},x_{0}^{*})$
for every $k\in[\lambda]$. The proof is done if we can switch all of
$\mathsf{ct}^{*}_{k}$ into $\mathsf{Enc}(\mathsf{msk}_{k},x_{1}^{*})$ without
being detected by $\mathpzc{A}$. To this end, the underlying
$\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}$ needs to satisfy a stronger variant of
lessor security notion where an adversary is allowed to declare the
availability bound such that $\mathpzc{KG}$ does not run in polynomial time,
if the adversary does not make any query to the key generation oracle. For
example, to switch $\mathsf{ct}^{*}_{\lambda}$, the reduction algorithm
attacking $\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}$ needs to declare the
availability bound $2^{\lambda}$, under which $\mathpzc{KG}$ might not run in
polynomial time. Note that $\mathsf{Setup}$ and $\mathsf{Enc}$ run in
polynomial time even for such an availability bound due to the weak optimal
efficiency. Thus, we formalize the security notion of SKFE-sbSKL as follows.

###### Definition 3.6 (Selective Strtong Lessor Security).

We define selective strong lessor security for SKFE-sbSKL in the same way as
that for SKFE-SKL defined in Definition 3.2 , except the following changes for
the security experiment.

  * •

$\mathpzc{A}$ outputs $n$ at the beginning, and the challenger generates
$\mathsf{msk}\leftarrow\mathsf{Setup}(1^{\lambda},1^{q},n)$. If $\mathpzc{A}$
makes a query to $O_{\mathtt{\mathpzc{KG}}}$ or $O_{\mathtt{\mathsf{Vrfy}}}$,
$\mathpzc{A}$ is required to output $n$ such that $\mathpzc{KG}$ and
$\mathsf{Vrfy}$ run in polynomial time.

  * •

$O_{\mathtt{\mathpzc{KG}}}$ does not take $1^{n}$ as an input.

######  Remark 3.7 (Insufficiency of existing bounded collusion techniques).

In Section 1.3, we stated that it is not clear how to use the existing bounded
collusion techniques [GVW12, AV19] for constructing SKFE-sbSKL. We provide a
more detailed discussion on this point.

The bounded collusion technique essentially enables us to increase the number
of decryption keys that an adversary can obtain. Thus, to try to use the
bounded collusion technique in our context, imagine the following naive
construction using standard SKFE $\mathsf{SKFE}$ and SKE with certified
deletion $\mathsf{CDSKE}$. This construction is a flipped version of the naive
construction provided in Section 1.3. In the construction, we encrypt a
ciphertext of $\mathsf{SKFE}$ by $\mathsf{CDSKE}$, and we include the key of
$\mathsf{CDSKE}$ into the decryption key of the resulting scheme. The
construction can be seen as an SKFE scheme with certified deletion (for
ciphertexts) that is secure if an adversary deletes the challenge ciphertext
before seeing any decryption key. The roles of ciphertexts and decryption keys
are almost symmetric in SKFE [BS18]. Thus, if we can amplify the security of
this construction so that it is secure if an adversary sees some decryption
keys before deleting the challenge ciphertext, it would lead to SKFE-sbSKL.
The question is whether we can perform such an amplification using the
existing bounded collusion techniques [GVW12, AV19]. We observe that it is
highly non-trivial to adapt the existing bounded collusion technique starting
from “$0$-bounded” security. Especially, it seems difficult to design such a
transformation so that the resulting SKFE-sbSKL obtained by flipping the roles
of ciphertexts and decryption keys satisfies weak optimal efficiency and
security against unbounded number of encryption queries such as Definition
3.6.

We develop a different technique due to the above reason. Namely, we reduce
the task of amplifying the availability bound of SKFE-sbSKL into the task of
amplifying the security bound of it. In fact, our work implicitly shows that
security bound amplification for FE can be used to achieve bounded collusion-
resistance. We see that we can construct bounded collusion secure FE from
single-key FE by our parallelizing then security bound amplification
technique.

###  3.3 Index-Based SKFE with Static-Bound Secure Key Leasing

We define index-based SKFE-sbSKL. Similarly to SKFE-sbSKL, it needs to satisfy
weak optimal efficiency and (selective) strong lessor security.

###### Definition 3.8 (Index-Base SKFE with Static-Bound Secure Key Leasing).

An index-base SKFE-sbSKL scheme $\mathsf{iSKFE\textrm{-}sbSKL}$ is a tuple of
six algorithms
$(\mathsf{Setup},\mathpzc{KG},\mathsf{iEnc},\allowbreak\mathpzc{Dec},\mathpzc{Cert},\mathsf{Vrfy})$.
The only difference from an SKFE-sbSKL scheme is that the encryption algorithm
$\mathsf{iEnc}$ additionally takes as input an index $j\in[n]$.

Decryption correctness:

For every $x\in\mathcal{X}$, $f\in\mathcal{F}$, $q,n\in\mathbb{N}$, and
$j\in[n]$, we have

$\displaystyle\Pr\left[\mathpzc{Dec}(\mathpzc{fsk},\mathsf{ct})\allowbreak=f(x)\
\middle|\begin{array}[]{ll}\mathsf{msk}\leftarrow\mathsf{Setup}(1^{\lambda},1^{q},n)\\\
(\mathpzc{fsk},\mathsf{vk})\leftarrow\mathpzc{KG}(\mathsf{msk},f)\\\
\mathsf{ct}\leftarrow\mathsf{Enc}(\mathsf{msk},j,x)\end{array}\right]=1-{\mathsf{negl}}(\lambda).$
(25)

Verification correctness:

For every $f\in\mathcal{F}$ and $q,n\in\mathbb{N}$, we have

$\displaystyle\Pr\left[\mathsf{Vrfy}(\mathsf{vk},\mathsf{cert})=\top\
\middle|\begin{array}[]{ll}\mathsf{msk}\leftarrow\mathsf{Setup}(1^{\lambda},1^{q},n)\\\
(\mathpzc{fsk},\mathsf{vk})\leftarrow\mathpzc{KG}(\mathsf{msk},f)\\\
\mathsf{cert}\leftarrow\mathpzc{Cert}(\mathpzc{fsk})\end{array}\right]=1-{\mathsf{negl}}(\lambda).$
(29)

Weak Optimal Efficiency:

We require that the running time of $\mathsf{Setup}$ and $\mathsf{Enc}$ is
bounded by a fixed polynomial of $\lambda$, $q$, and $\log n$.

###### Definition 3.9 (Selective Strong Lessor Security).

We say that $\mathsf{iSKFE\textrm{-}sbSKL}$ is a selectively strong lessor
secure index-based SKFE-sbSKL scheme for $\mathcal{X},\mathcal{Y}$, and
$\mathcal{F}$, if it satisfies the following requirement, formalized from the
experiment
$\mathsf{Exp}_{\mathpzc{A},\mathsf{iSKFE\textrm{-}sbSKL}}^{\mathsf{sel}\mbox{-}\mathsf{s}\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},n,j^{*},x_{0}^{*},x_{1}^{*})$ to
the challenger. If $\mathpzc{A}$ makes a query to $O_{\mathtt{\mathpzc{KG}}}$
or $O_{\mathtt{\mathsf{Vrfy}}}$, $\mathpzc{A}$ is required to output $n$ such
that $\mathpzc{KG}$ and $\mathsf{Vrfy}$ run in polynomial time. The challenger
runs $\mathsf{msk}\leftarrow\mathsf{Setup}(1^{\lambda},1^{q},n)$. Throughout
the experiment, $\mathpzc{A}$ can access the following oracles.

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

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

$O_{\mathtt{\mathpzc{KG}}}(f)$:

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

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

Given $(f,\mathsf{cert})$, it finds an entry $(f,\mathsf{vk},M)$ from
$L_{\mathtt{\mathpzc{KG}}}$. (If there is no such entry, it returns $\bot$.)
If $\top=\mathsf{Vrfy}(\mathsf{vk},\mathsf{cert})$, it returns $\top$ and
updates the entry into $(f,\mathsf{vk},\top)$. Otherwise, it returns $\bot$.

  2. 2.

When $\mathpzc{A}$ requests the challenge ciphertext, the challenger checks if
for any entry $(f,\mathsf{vk},M)$ in $L_{\mathtt{\mathpzc{KG}}}$ such that
$f(x_{0}^{*})\neq f(x_{1}^{*})$, it holds that $M=\top$, and $\mathpzc{A}$
does not make a query with $j^{*}$ to $O_{\mathtt{\mathsf{Enc}}}$ at this
point. If so, the challenger generates
$\mathsf{ct}^{*}\leftarrow\mathsf{Enc}(\mathsf{msk},j^{*},x_{\mathsf{coin}}^{*})$
and sends $\mathsf{ct}^{*}$ to $\mathpzc{A}$. Otherwise, the challenger
outputs $0$. Hereafter, $\mathpzc{A}$ is not allowed to sends a function $f$
such that $f(x_{0}^{*})\neq f(x_{1}^{*})$ to $O_{\mathtt{\mathpzc{KG}}}$.

  3. 3.

$\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{iSKFE\textrm{-}sbSKL},\mathpzc{A}}^{\mathsf{sel}\mbox{-}\mathsf{s}\mbox{-}\mathsf{lessor}}(\lambda)\coloneqq\absolutevalue{\Pr[\mathsf{Exp}_{\mathsf{iSKFE\textrm{-}sbSKL},\mathpzc{A}}^{\mathsf{sel}\mbox{-}\mathsf{s}\mbox{-}\mathsf{lessor}}(1^{\lambda},0)=1]-\Pr[\mathsf{Exp}_{\mathsf{iSKFE\textrm{-}sbSKL},\mathpzc{A}}^{\mathsf{sel}\mbox{-}\mathsf{s}\mbox{-}\mathsf{lessor}}(1^{\lambda},0)=1]}\leq{\mathsf{negl}}(\lambda).$
(30)

##  4 Index-Base SKFE with Static-Bound Secure Key Leasing

We construct an index-based SKFE-sbSKL scheme
$\mathsf{iSKFE\textrm{-}sbSKL}=(\mathsf{iSetup},\mathpzc{iKG},\allowbreak\mathsf{iEnc},\mathpzc{iDec},\mathpzc{iCert},\mathsf{iVrfy})$
using the following tools:

  * •

An SKFE scheme
$\mathsf{SKFE}=(\mathsf{Setup},\mathsf{KG},\mathsf{Enc},\mathsf{Dec})$.

  * •

An SKE scheme with Certified Deletion
$\mathsf{CDSKE}=(\mathsf{CD}.\mathsf{KG},\mathsf{CD}.\mathpzc{Enc},\mathsf{CD}.\mathpzc{Dec},\allowbreak\mathsf{CD}.\mathpzc{Del},\mathsf{CD}.\mathsf{Vrfy})$.

  * •

A PRF $\mathsf{F}$.

The description of $\mathsf{iSKFE\textrm{-}sbSKL}$ is as follows.

$\mathsf{iSetup}(1^{\lambda},1^{q},n)$:

  * •

Generate $K\leftarrow\\{0,1\\}^{\lambda}$.

  * •

Output $\mathsf{skl}.\mathsf{msk}:=(q,n,K)$.

$\mathpzc{iKG}(\mathsf{msk},f)$:

  * •

Parse $(q,n,K)\leftarrow\mathsf{skl}.\mathsf{msk}$.

  * •

Compute $r_{j}\|w_{j}\leftarrow\mathsf{F}_{K}(j)$,
$\mathsf{msk}_{j}\leftarrow\mathsf{Setup}(1^{\lambda},1^{q};r_{j})$, and
$\mathsf{cd}.\mathsf{sk}_{j}\leftarrow\mathsf{CD}.\mathsf{KG}(1^{\lambda};w_{j})$
for every $j\in[n]$.

  * •

Generate $\mathsf{fsk}_{j}\leftarrow\mathsf{KG}(\mathsf{msk}_{j},f)$ for every
$j\in[n]$.

  * •

Generate
$(\mathsf{cd}.\mathpzc{ct}_{j},\mathsf{vk}_{j})\leftarrow\mathsf{CD}.\mathpzc{Enc}(\mathsf{cd}.\mathsf{sk}_{j},\mathsf{fsk}_{j})$
for every $j\in[n]$.

  * •

Output $\mathsf{skl}.\mathpzc{fsk}:=(\mathsf{cd}.\mathpzc{ct}_{j})_{j\in[n]}$
and $\mathsf{vk}:=(\mathsf{vk}_{j})_{j\in[n]}$.

$\mathsf{iEnc}(\mathsf{skl}.\mathsf{msk},j,x)$:

  * •

Parse $(q,n,K)\leftarrow\mathsf{skl}.\mathsf{msk}$.

  * •

Compute $r_{j}\|w_{j}\leftarrow\mathsf{F}_{K}(j)$,
$\mathsf{msk}_{j}\leftarrow\mathsf{Setup}(1^{\lambda},1^{q};r_{j})$, and
$\mathsf{cd}.\mathsf{sk}_{j}\leftarrow\mathsf{CD}.\mathsf{KG}(1^{\lambda};w_{j})$.

  * •

Generate $\mathsf{ct}_{j}\leftarrow\mathsf{Enc}(\mathsf{msk}_{j},x)$.

  * •

Output
$\mathsf{skl}.\mathsf{ct}:=(j,\mathsf{ct}_{j},\mathsf{cd}.\mathsf{sk}_{j})$.

$\mathpzc{iDec}(\mathsf{skl}.\mathpzc{fsk},\mathsf{skl}.\mathsf{ct})$:

  * •

Parse
$(\mathsf{cd}.\mathpzc{ct}_{j})_{j\in[n]}\leftarrow\mathsf{skl}.\mathpzc{fsk}$
and
$(j,\mathsf{ct}_{j},\mathsf{cd}.\mathsf{sk}_{j})\leftarrow\mathsf{skl}.\mathsf{ct}$.

  * •

Compute
$\mathsf{fsk}_{j}\leftarrow\mathsf{CD}.\mathpzc{Dec}(\mathsf{cd}.\mathsf{sk}_{j},\mathsf{skl}.\mathpzc{fsk}_{j})$.

  * •

Output $y\leftarrow\mathsf{Dec}(\mathsf{fsk}_{j},\mathsf{ct}_{j})$.

$\mathpzc{iCert}(\mathsf{skl}.\mathpzc{fsk})$:

  * •

Parse
$(\mathsf{cd}.\mathpzc{ct}_{j})_{j\in[n]}\leftarrow\mathsf{skl}.\mathpzc{fsk}$.

  * •

Compute
$\mathsf{cert}_{j}\leftarrow\mathsf{CD}.\mathpzc{Del}(\mathsf{cd}.\mathsf{ct}_{j})$
for every $j\in[n]$.

  * •

Output $\mathsf{cert}:=(\mathsf{cert}_{j})_{j\in[n]}$.

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

  * •

Parse $(\mathsf{vk}_{j})_{j\in[n]}\leftarrow\mathsf{vk}$ and
$(\mathsf{cert}_{j})_{j\in[n]}\leftarrow\mathsf{cert}$.

  * •

Output $\top$ if
$\top=\mathsf{CD}.\mathsf{Vrfy}(\mathsf{vk}_{j},\mathsf{cert}_{j})$ for every
$j\in[n]$, and otherwise $\bot$.

It is clear that $\mathsf{iSKFE\textrm{-}sbSKL}$ satisfies correctness and
weak optimal efficiency. For security, we have the following theorem.

###### Theorem 4.1.

If $\mathsf{SKFE}$ is selective indistinguishability-secure, $\mathsf{CDSKE}$
is IND-CVA-CD secure,121212See Definition 2.13 for the defition of IND-CVA-CD.
and $\mathsf{F}$ is a secure PRF, then $\mathsf{iSKFE\textrm{-}sbSKL}$
satisfies selective strong lessor security.

###### Proof of Theorem 4.1.

We define a sequence of hybrid games to prove the theorem.

$\mathsf{Hyb}_{0}$:

This is the same as
$\mathsf{Exp}_{\mathpzc{A},\mathsf{iSKFE\textrm{-}sbSKL}}^{\mathsf{sel}\mbox{-}\mathsf{s}\mbox{-}\mathsf{lessor}}(1^{\lambda},0)$.

  1. 1.

At the beginning, $\mathpzc{A}$ sends $(1^{q},n,j^{*},x_{0}^{*},x_{1}^{*})$ to
the challenger. The challenger generates $K\leftarrow\\{0,1\\}^{\lambda}$.
Below, we let $r_{j}\|w_{j}\leftarrow\mathsf{F}_{K}(j)$,
$\mathsf{msk}_{j}\leftarrow\mathsf{Setup}(1^{\lambda},1^{q};r_{j})$, and
$\mathsf{cd}.\mathsf{sk}_{j}\leftarrow\mathsf{CD}.\mathsf{KG}(1^{\lambda};w_{j})$
for every $j\in[n]$. Throughout the experiment, $\mathpzc{A}$ can access the
following oracles.

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

Given $j$ and $x$, it generates
$\mathsf{ct}_{j}\leftarrow\mathsf{Enc}(\mathsf{msk}_{j},x)$ and returns
$\mathsf{skl}.\mathsf{ct}\coloneqq(j,\mathsf{ct}_{j},\mathsf{cd}.\mathsf{sk}_{j})$.

$O_{\mathtt{\mathpzc{KG}}}(f)$:

Given $f$, it does the following.

     * •

Compute $\mathsf{fsk}_{j}\leftarrow\mathsf{KG}(\mathsf{msk}_{j},f)$ for every
$j\in[n]$.

     * •

Compute
$(\mathsf{cd}.\mathpzc{ct}_{j},\mathsf{vk}_{j})\leftarrow\mathsf{CD}.\mathpzc{Enc}(\mathsf{cd}.\mathsf{sk}_{j},\mathsf{fsk}_{j})$
for every $j\in[n]$.

     * •

Sets
$\mathsf{skl}.\mathpzc{fsk}\coloneqq(\mathsf{cd}.\mathpzc{ct}_{j})_{j\in[n]}$
and $\mathsf{skl}.\mathsf{vk}\coloneqq(\mathsf{vk}_{j})_{j\in[n]}$.

It sends $\mathsf{skl}.\mathpzc{fsk}$ to $\mathpzc{A}$ and adds
$(f,\mathsf{skl}.\mathsf{vk},\bot)$ to $L_{\mathtt{\mathpzc{KG}}}$.
$\mathpzc{A}$ is allowed to make at most $q$ queries to this oracle.

$O_{\mathtt{\mathsf{Vrfy}}}(f,\mathsf{cert}\coloneqq(\mathsf{cert}_{j})_{j\in[n]})$:

Given $(f,\mathsf{cert}\coloneqq(\mathsf{cert}_{j})_{j\in[n]})$, it finds an
entry $(f,\mathsf{vk},M)$ from $L_{\mathtt{\mathpzc{KG}}}$. (If there is no
such entry, it returns $\bot$.) If
$\top=\mathsf{Vrfy}(\mathsf{vk}_{j},\mathsf{cert}_{j})$ for every $j\in[n]$,
it returns $\top$ and updates the entry into $(f,\mathsf{vk},\top)$.
Otherwise, it returns $\bot$.

  2. 2.

When $\mathpzc{A}$ requests the challenge ciphertext, the challenger checks if
for any entry $(f,\mathsf{vk},M)$ in $L_{\mathtt{\mathpzc{KG}}}$ such that
$f(x_{0}^{*})\neq f(x_{1}^{*})$, it holds that $M=\top$, and $\mathpzc{A}$
does not make a query with $j^{*}$ to $O_{\mathtt{\mathsf{Enc}}}$ at this
point. If so, the challenger generates
$\mathsf{ct}^{*}_{j^{*}}\leftarrow\mathsf{Enc}(\mathsf{msk}_{j^{*}},x_{0}^{*})$
and sends
$\mathsf{skl}.\mathsf{ct}^{*}\coloneqq(j^{*},\mathsf{ct}^{*}_{j^{*}},\mathsf{cd}.\mathsf{sk}_{j^{*}})$
to $\mathpzc{A}$. Otherwise, the challenger outputs $0$. Hereafter,
$\mathpzc{A}$ is not allowed to sends a function $f$ such that
$f(x_{0}^{*})\neq f(x_{1}^{*})$ to $O_{\mathtt{\mathpzc{KG}}}$.

  3. 3.

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

$\mathsf{Hyb}_{1}$:

This is the same as $\mathsf{Hyb}_{0}$ except that $r_{j}\|w_{j}$ is generated
as a uniformly random string for every $j\in[n]$.

We have
$\absolutevalue{\Pr[\mathsf{Hyb}_{0}=1]-\Pr[\mathsf{Hyb}_{1}=1]}={\mathsf{negl}}(\lambda)$
from the security of $\mathsf{F}$.

$\mathsf{Hyb}_{2}$:

This hybrid is the same as $\mathsf{Hyb}_{1}$ except that when $\mathpzc{A}$
sends $f$ to $O_{\mathtt{\mathpzc{KG}}}$, if $f(x_{0}^{*})\neq f(x_{1}^{*})$,
the challenger generates $\mathsf{cd}.\mathpzc{ct}_{j^{*}}$ included in
$\mathsf{skl}.\mathpzc{fsk}\coloneqq(\mathsf{cd}.\mathpzc{ct}_{j})_{j\in[n]}$
as
$(\mathsf{cd}.\mathpzc{ct}_{j^{*}},\mathsf{vk}_{j^{*}})\leftarrow\mathsf{CD}.\mathpzc{Enc}(\mathsf{cd}.\mathsf{sk}_{j^{*}},\boldsymbol{0})$.

We can show that
$\absolutevalue{\Pr[\mathsf{Hyb}_{1}=1]-\Pr[\mathsf{Hyb}_{2}=1]}={\mathsf{negl}}(\lambda)$
from the security of $\mathsf{CDSKE}$ as follows. We say $\mathpzc{A}$ is
valid if when $\mathpzc{A}$ requests the challenge ciphertext, for any entry
$(f,\mathsf{vk},M)$ in $L_{\mathtt{\mathpzc{KG}}}$ such that $f(x_{0}^{*})\neq
f(x_{1}^{*})$, it holds that $M=\top$, and $\mathpzc{A}$ does not make a query
with $j^{*}$ to $O_{\mathtt{\mathsf{Enc}}}$ at this point. In the estimation
of $\absolutevalue{\Pr[\mathsf{Hyb}_{1}=1]-\Pr[\mathsf{Hyb}_{2}=1]}$, we have
to consider the case where $\mathpzc{A}$ is valid since if $\mathpzc{A}$ is
not valid, the output of the experiment is $0$. In this transition of
experiments, we change a plaintext encrypted under
$\mathsf{cd}.\mathsf{sk}_{j^{*}}$. If $\mathpzc{A}$ is valid, $\mathpzc{A}$
cannot obtain $\mathsf{cd}.\mathsf{sk}_{j^{*}}$ before $\mathpzc{A}$ is given
$\mathsf{skl}.\mathsf{ct}^{*}$, and $\mathpzc{A}$ returns all ciphertexts
under $\mathsf{cd}.\mathsf{sk}_{j^{*}}$ before it gets
$\mathsf{cd}.\mathsf{sk}_{j^{*}}$. Although the reduction does not have
$\mathsf{vk}_{j^{\ast}}$ here, it can simulate $O_{\mathtt{\mathsf{Vrfy}}}$ by
using the verification oracle in IND-CVA-CD game. Then, we see that
$\absolutevalue{\Pr[\mathsf{Hyb}_{1}=1]-\Pr[\mathsf{Hyb}_{2}=1]}={\mathsf{negl}}(\lambda)$
follows from the security of $\mathsf{CDSKE}$ under the key
$\mathsf{cd}.\mathsf{sk}_{j^{*}}$.

$\mathsf{Hyb}_{3}$:

This hybrid is the same as $\mathsf{Hyb}_{2}$ except that the challenger
generates $\mathsf{ct}^{*}_{j^{*}}$ included in $\mathsf{skl}.\mathsf{ct}^{*}$
as
$\mathsf{ct}^{*}_{j^{*}}\leftarrow\mathsf{Enc}(\mathsf{msk}_{j^{*}},x_{1}^{*})$.

By the previous transition, in $\mathsf{Hyb}_{2}$ and $\mathsf{Hyb}_{3}$,
$\mathpzc{A}$ can obtain a decryption key under $\mathsf{msk}_{j^{*}}$ for a
function $f$ such that $f(x_{0}^{*})=f(x_{1}^{*})$. Thus,
$\absolutevalue{\Pr[\mathsf{Hyb}_{2}=1]-\Pr[\mathsf{Hyb}_{3}=1]}={\mathsf{negl}}(\lambda)$
holds from the security of $\mathsf{SKFE}$.

$\mathsf{Hyb}_{4}$:

This hybrid is the same as $\mathsf{Hyb}_{3}$ except that we undo the changes
from $\mathsf{Hyb}_{0}$ to $\mathsf{Hyb}_{2}$. $\mathsf{Hyb}_{4}$ is the same
as
$\mathsf{Exp}_{\mathpzc{A},\mathsf{iSKFE\textrm{-}sbSKL}}^{\mathsf{sel}\mbox{-}\mathsf{s}\mbox{-}\mathsf{lessor}}(1^{\lambda},1)$.

$\absolutevalue{\Pr[\mathsf{Hyb}_{3}=1]-\Pr[\mathsf{Hyb}_{4}=1]}={\mathsf{negl}}(\lambda)$
holds from the security of $\mathsf{F}$ and $\mathsf{CDSKE}$.

From the above discussions, $\mathsf{iSKFE\textrm{-}sbSKL}$ satisfies
selective lessor security.

##  5 SKFE with Static-Bound Secure Key Leasing

We construct an SKFE-sbSKL scheme
$\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}=(\mathsf{sbSKL}.\mathsf{Setup},\mathsf{sbSKL}.\mathpzc{KG},\allowbreak\mathsf{sbSKL}.\mathsf{Enc},\mathsf{sbSKL}.\mathpzc{Dec},\allowbreak\mathsf{sbSKL}.\mathpzc{Cert},\mathsf{sbSKL}.\mathsf{Vrfy})$
from the following tools:

  * •

An index-based SKFE-sbSKL scheme
$\mathsf{iSKFE\textrm{-}sbSKL}=(\mathsf{iSetup},\mathpzc{iKG},\mathsf{iEnc},\allowbreak\mathpzc{iDec},\allowbreak\mathpzc{iCert},\mathsf{iVrfy})$.

  * •

A set homomorphic secret sharing
$\mathsf{SetHSS}=(\mathsf{SetGen},\mathsf{InpEncode},\mathsf{FuncEncode},\allowbreak\mathsf{Decode})$.

  * •

An SKE scheme $\mathsf{SKE}=(\mathsf{E},\mathsf{D})$.

The description of $\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}$ is as follows.

$\mathsf{sbSKL}.\mathsf{Setup}(1^{\lambda},1^{q},n)$:

  * •

Generate
$\mathsf{params}\coloneqq(p,\ell,(T_{i})_{i\in[m]})\leftarrow\mathsf{SetGen}(1^{\lambda})$.

  * •

Generate $\mathsf{msk}_{i}\leftarrow\mathsf{iSetup}(1^{\lambda},1^{q},N)$ for
every $i\in[m]$, where $N=n/p$.

  * •

Generate $K\leftarrow\\{0,1\\}^{\lambda}$.

  * •

Output
$\mathsf{sbskl}.\mathsf{msk}\coloneqq(\mathsf{params},N,(\mathsf{msk})_{i\in[m]},K)$.

$\mathsf{sbSKL}.\mathpzc{KG}(\mathsf{sbskl}.\mathsf{msk},f)$:

  * •

Parse
$(\mathsf{params},N,(\mathsf{msk})_{i\in[m]},K)\leftarrow\mathsf{sbskl}.\mathsf{msk}$.

  * •

Generate $\mathsf{sct}_{i}\leftarrow\mathsf{E}(K,\boldsymbol{0})$ for every
$i\in[m]$.

  * •

Generate $(f_{i})_{i\in[m]}\leftarrow\mathsf{FuncEncode}(\mathsf{params},f)$.

  * •

Generate
$(\mathpzc{fsk}_{i},\mathsf{vk}_{i})\leftarrow\mathpzc{iKG}(\mathsf{msk}_{i},F[f_{i},\mathsf{sct}_{i}])$
for every $i\in[m]$, where the circuit $F$ is described in Figure 1.

  * •

Output $\mathsf{sbskl}.\mathpzc{fsk}\coloneqq(\mathpzc{fsk}_{i})_{i\in[m]}$
and $\mathsf{sbskl}.\mathsf{vk}\coloneqq(\mathsf{vk}_{i})_{i\in[m]}$.

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

  * •

Parse
$(\mathsf{params},N,(\mathsf{msk})_{i\in[m]},K)\leftarrow\mathsf{sbskl}.\mathsf{msk}$.

  * •

Generate $(s_{i})_{i\in[m]}\leftarrow\mathsf{InpEncode}(\mathsf{params},x)$.

  * •

Generate $j_{i}\leftarrow[N]$ for every $i\in[m]$.

  * •

Generate
$\mathsf{ct}_{i}\leftarrow\mathsf{iEnc}(\mathsf{msk}_{i},j_{i},(s_{i},\boldsymbol{0},0))$
for every $i\in[m]$.

  * •

Output $\mathsf{sbskl}.\mathsf{ct}\coloneqq(\mathsf{ct}_{i})_{i\in[m]}$.

$\mathsf{sbSKL}.\mathpzc{Dec}(\mathsf{sbskl}.\mathpzc{fsk},\mathsf{sbskl}.\mathsf{ct})$:

  * •

Parse $(\mathpzc{fsk}_{i})_{i\in[m]}\leftarrow\mathsf{sbskl}.\mathpzc{fsk}$
and $(\mathsf{ct}_{i})_{i\in[m]}\leftarrow\mathsf{sbskl}.\mathsf{ct}$.

  * •

Compute
$y_{{\boldsymbol{I}}}\leftarrow\mathpzc{iDec}(\mathpzc{fsk}_{i},\mathsf{ct}_{i})$
for every $i\in[m]$.

  * •

Output $y\leftarrow\mathsf{Decode}((y_{i})_{i\in[m]})$.

$\mathsf{sbSKL}.\mathpzc{Cert}(\mathsf{sbskl}.\mathpzc{fsk})$:

  * •

Parse $(\mathpzc{fsk}_{i})_{i\in[m]}\leftarrow\mathsf{sbskl}.\mathpzc{fsk}$.

  * •

Compute $\mathsf{cert}_{i}\leftarrow\mathpzc{iCert}(\mathpzc{fsk}_{i})$ for
every $i\in[m]$.

  * •

Output $\mathsf{sbskl}.\mathsf{cert}\coloneqq(\mathsf{cert}_{i})_{i\in[m]}$.

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

  * •

Parse $(\mathsf{vk}_{i})_{i\in[m]}\leftarrow\mathsf{sbskl}.\mathsf{vk}$ and
$(\mathsf{cert}_{i})_{i\in[m]}\leftarrow\mathsf{sbskl}.\mathsf{cert}$.

  * •

Output $\top$ if $\top=\mathsf{iVrfy}(\mathsf{vk}_{i},\mathsf{cert}_{i})$ for
every $i\in[m]$, and otherwise $\bot$.

Circuit $F[f_{i},\mathsf{sct}_{i}](s_{i},K,b)$ Hardwired: A function share
$f_{i}$ and an $\mathsf{SKE}$’s ciphertext $\mathsf{sct}_{i}$. Input: an input
share $s_{i}$, an $\mathsf{SKE}$’s secret key $K$, and a bit $b$. 1. If $b=1$,
output $\mathsf{D}(K,\mathsf{sct}_{i})$. 2. Otherwise, output $f_{i}(s_{i})$.

Figure 1: Description of $F[f_{i},\mathsf{sct}_{i}](s_{i},K,b)$.

We show the correctness of $\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}$. Let
$\mathsf{sbskl}.\mathpzc{fsk}\coloneqq(\mathpzc{fsk}_{i})_{i\in[m]}$ be a
decryption key for $f$ and let
$\mathsf{sbskl}.\mathsf{ct}\coloneqq(\mathsf{ct}_{i})_{i\in[m]}$ be a
ciphertext of $x$. From the correctness of $\mathsf{iSKFE\textrm{-}sbSKL}$, we
obtain $f_{i}(s_{i})$ by decrypting $\mathsf{ct}_{i}$ with $\mathpzc{fsk}_{i}$
for every $i\in[m]$, where
$(f_{i})_{i\in[m]}\leftarrow\mathsf{FuncEncode}(\mathsf{params},f)$ and
$(s_{i})_{i\in[m]}\leftarrow\mathsf{InpEncode}(\mathsf{params},x)$. Thus, we
obtains $f(x)\leftarrow\mathsf{Decode}((f_{i}(s_{i}))_{i\in[m]})$ from the
correctness of $\mathsf{SetHSS}$. It is clear that
$\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}$ also satisfies verification
correctness.

Also, the weak optimal efficiency of $\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}$
easily follows from that of $\mathsf{iSKFE\textrm{-}sbSKL}$ since the running
time of algorithms of $\mathsf{SetHSS}$ is independent of $n$. Note that
$\mathsf{sbSKL}.\mathsf{Enc}$ samples indices from $[N]=[n/p]$, but it can be
done in time $\log n$.

For security, we have the following theorems.

###### Theorem 5.1.

If $\mathsf{iSKFE\textrm{-}sbSKL}$ is a selectively strong lessor secure
index-based SKFE-sbSKL scheme and $\mathsf{SetHSS}$ is a set homomorphic
secret sharing scheme, and $\mathsf{SKE}$ is a CPA secure SKE scheme, then
$\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}$ is selectively strong lessor secure.

###### Proof of Theorem 5.1.

We define a sequence of hybrid games to prove the theorem.

$\mathsf{Hyb}_{0}$:

This is the same as
$\mathsf{Exp}_{\mathpzc{A},\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}}^{\mathsf{sel}\mbox{-}\mathsf{s}\mbox{-}\mathsf{lessor}}(1^{\lambda},0)$.

  1. 1.

At the beginning, $\mathpzc{A}$ sends $(1^{q},n,x_{0}^{*},x_{1}^{*})$ to the
challenger. The challenger generates
$\mathsf{params}\coloneqq(p,\ell,(T_{i})_{i\in[m]})\leftarrow\mathsf{SetGen}(1^{\lambda})$,
$\mathsf{msk}_{i}\leftarrow\mathsf{iSetup}(1^{\lambda},1^{q},N)$ for every
$i\in[m]$, and $K\leftarrow\\{0,1\\}^{\lambda}$, where $N=n/p$. Throughout the
experiment, $\mathpzc{A}$ can access the following oracles.

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

Given the $k$-th query $x^{k}$, it returns $\mathsf{sbskl}.\mathsf{ct}^{k}$
generated as follows.

     * •

Generate
$(s^{k}_{i})_{i\in[m]}\leftarrow\mathsf{InpEncode}(\mathsf{params},x^{k})$.

     * •

Generate $j^{k}_{i}\leftarrow[N]$ for every $i\in[m]$.

     * •

Generate
$\mathsf{ct}^{k}_{i}\leftarrow\mathsf{iEnc}(\mathsf{msk},i,j^{k}_{i},(s^{k}_{i},\boldsymbol{0},0))$
for every $i\in[m]$.

     * •

Set $\mathsf{sbskl}.\mathsf{ct}^{k}\coloneqq(\mathsf{ct}^{k}_{i})_{i\in[m]}$.

$O_{\mathtt{\mathpzc{KG}}}(f)$:

Given $f$, it generates $\mathsf{sbskl}.\mathpzc{fsk}$ and
$\mathsf{sbskl}.\mathsf{vk}$ as follows.

     * •

Generate $(f_{i})_{i\in[m]}\leftarrow\mathsf{FuncEncode}(\mathsf{params},f)$.

     * •

Generate $\mathsf{sct}_{i}\leftarrow\mathsf{E}(K,\boldsymbol{0})$ for every
$i\in[m]$.

     * •

Generate
$(\mathpzc{fsk}_{i},\mathsf{vk}_{i})\leftarrow\mathpzc{iKG}(\mathsf{msk}_{i},F[f_{i},\mathsf{sct}_{i}])$
for every $i\in[m]$.

     * •

Set $\mathsf{sbskl}.\mathpzc{fsk}\coloneqq(\mathpzc{fsk}_{i})_{i\in[m]}$ and
$\mathsf{sbskl}.\mathsf{vk}\coloneqq(\mathsf{vk}_{i})_{i\in[m]}$.

It sends $\mathsf{sbskl}.\mathpzc{fsk}$ to $\mathpzc{A}$ and adds
$(f,\mathsf{sbskl}.\mathsf{vk},\bot)$ to $L_{\mathtt{\mathpzc{KG}}}$.

$O_{\mathtt{\mathsf{Vrfy}}}(f,\mathsf{cert}\coloneqq(\mathsf{cert}_{i})_{i\in[m]})$:

Given $(f,\mathsf{cert}\coloneqq(\mathsf{cert}_{i})_{i\in[m]})$, it finds an
entry $(f,\mathsf{vk},M)$ from $L_{\mathtt{\mathpzc{KG}}}$. (If there is no
such entry, it returns $\bot$.) If
$\top=\mathsf{Vrfy}(\mathsf{vk}_{i},\mathsf{cert}_{i})$ for every $i\in[m]$,
it returns $\top$ and updates the entry into $(f,\mathsf{vk},\top)$.
Otherwise, it returns $\bot$.

  2. 2.

When $\mathpzc{A}$ requests the challenge ciphertext, the challenger checks if
for any entry $(f,\mathsf{vk},M)$ in $L_{\mathtt{\mathpzc{KG}}}$ such that
$f(x_{0}^{*})\neq f(x_{1}^{*})$, it holds that $M=\top$, and the number of
queries to $O_{\mathtt{\mathsf{Enc}}}$ at this point is less than $n$. If so,
the challenger sends $\mathsf{sbskl}.\mathsf{ct}^{*}$ computed as follows to
$\mathpzc{A}$.

     * •

Generate
$(s^{*}_{i})_{i\in[m]}\leftarrow\mathsf{InpEncode}(\mathsf{params},x_{0}^{*})$.

     * •

Generate $j^{*}_{i}\leftarrow[N]$ for every $i\in[m]$.

     * •

Generate
$\mathsf{ct}^{*}_{i}\leftarrow\mathsf{iEnc}(\mathsf{msk}_{i},(s^{*}_{i},\boldsymbol{0},0))$
for every $i\in[m]$.

     * •

Set $\mathsf{sbskl}.\mathsf{ct}^{*}\coloneqq(\mathsf{ct}^{*}_{i})_{i\in[m]}$.

Otherwise, the challenger outputs $0$. Hereafter, $\mathpzc{A}$ is not allowed
to sends a function $f$ such that $f(x_{0}^{*})\neq f(x_{1}^{*})$ to
$O_{\mathtt{\mathpzc{KG}}}$.

  3. 3.

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

Below, we call $i\in[m]$ _a secure instance index_ if $j_{i}^{*}\neq
j_{i}^{k}$ holds for every $k\in[n]$. We also call $i\in[m]$ _an insecure
instance index_ if it is not a secure instance index. Let
$S_{\mathtt{secure}}\subseteq[m]$ be the set of secure instance indices, and
$S_{\mathtt{insecure}}=S\setminus S_{\mathtt{secure}}$. Since each $j_{i}^{k}$
is sampled from $[N]=[n/p]$, for each $i\in[m]$, $i$ is independently included
in $S_{\mathtt{insecure}}$ with probability at most $n/N=p$. Then, from the
existence of unmarked element property of $\mathsf{SetHSS}$, without
negligible probability, there exists $e\in[\ell]$ such that
$e\notin\bigcup_{i\in S_{\mathtt{insecure}}}T_{i}$. Below, for simplicity, we
assume that there always exists at least one such instance index, and we
denote it as $e^{*}$.

$\mathsf{Hyb}_{1}$:

This is the same as $\mathsf{Hyb}_{0}$ except that we generate $j_{i}^{k}$ for
every $i\in[m]$ and $k\in[n]$ and $j_{i}^{*}$ for every $i\in[m]$ at the
beginning of the experiment. Note that by this change, secure instance indices
and $i^{*}$ are determined at the beginning of the experiment.

$\absolutevalue{\Pr[\mathsf{Hyb}_{0}=1]-\Pr[\mathsf{Hyb}_{1}=1]}=0$ holds
since the change at this step is only conceptual.

$\mathsf{Hyb}_{2}$:

This is the same as $\mathsf{Hyb}_{1}$ except that when $\mathpzc{A}$ makes a
query $f$ to $O_{\mathtt{\mathpzc{KG}}}$, if $f(x_{0}^{*})=f(x_{1}^{*})$, it
generates $\mathsf{sct}_{i}$ as
$\mathsf{sct}_{i}\leftarrow\mathsf{E}(K,f_{i}(s^{*}_{i}))$ for every $i\in
S_{\mathtt{secure}}$.

$\absolutevalue{\Pr[\mathsf{Hyb}_{1}=1]-\Pr[\mathsf{Hyb}_{2}=1]}={\mathsf{negl}}(\lambda)$
holds from the security of $\mathsf{SKE}$.

$\mathsf{Hyb}_{3}$:

This is the same as $\mathsf{Hyb}_{2}$ except that the challenger generates
$\mathsf{ct}^{*}_{i}$ as
$\mathsf{ct}^{*}_{i}\leftarrow\mathsf{iEnc}(\mathsf{msk}_{i},j^{*}_{i},(\boldsymbol{0},K,1))$
for every $i\in S_{\mathtt{secure}}$.

$\absolutevalue{\Pr[\mathsf{Hyb}_{2}=1]-\Pr[\mathsf{Hyb}_{3}=1]}={\mathsf{negl}}(\lambda)$
holds from the selective lessor security of $\mathsf{iSKFE\textrm{-}sbSKL}$.
We provide the proof of it in Proposition 5.2.

$\mathsf{Hyb}_{4}$:

This is the same as $\mathsf{Hyb}_{3}$ except that the challenger generates
$(s^{*}_{i})_{i\in[m]}$ as
$(s^{*}_{i})_{i\in[m]}\leftarrow\mathsf{InpEncode}(\mathsf{params},x_{1}^{*})$.

$\absolutevalue{\Pr[\mathsf{Hyb}_{3}=1]-\Pr[\mathsf{Hyb}_{4}=1]}={\mathsf{negl}}(\lambda)$
holds from the selective indistinguishability-security of $\mathsf{SetHSS}$.
We provide the proof of it in Proposition 5.3.

$\mathsf{Hyb}_{5}$:

This is the same as $\mathsf{Hyb}_{4}$ except that we undo the changes from
$\mathsf{Hyb}_{0}$ to $\mathsf{Hyb}_{3}$. This is the same experiment as
$\mathsf{Exp}_{\mathpzc{A},\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}}^{\mathsf{sel}\mbox{-}\mathsf{s}\mbox{-}\mathsf{lessor}}(1^{\lambda},1)$.

$\absolutevalue{\Pr[\mathsf{Hyb}_{4}=1]-\Pr[\mathsf{Hyb}_{5}=1]}={\mathsf{negl}}(\lambda)$
holds from the security of $\mathsf{SKE}$ and $\mathsf{iSKFE\textrm{-}sbSKL}$.

###### Proposition 5.2.

$\absolutevalue{\Pr[\mathsf{Hyb}_{2}=1]-\Pr[\mathsf{Hyb}_{3}=1]}={\mathsf{negl}}(\lambda)$
holds if $\mathsf{iSKFE\textrm{-}sbSKL}$ is selectively lessor secure.

###### Proof of Proposition 5.2.

We define intermediate experiments $\mathsf{Hyb}_{2,i^{\prime}}$ between
$\mathsf{Hyb}_{2}$ and $\mathsf{Hyb}_{3}$ for $i^{\prime}\in[m]$.

$\mathsf{Hyb}_{2,i^{\prime}}$:

This is the same as $\mathsf{Hyb}_{2}$ except that the challenger generates
$\mathsf{ct}^{*}_{i}$ as
$\mathsf{ct}^{*}_{i}\leftarrow\mathsf{iEnc}(\mathsf{msk}_{i},j^{*}_{i},(\boldsymbol{0},K,1))$
for every $i$ such that $i\in S_{\mathtt{secure}}$ and $i\leq i^{\prime}$.

Then, we have

$\displaystyle\absolutevalue{\Pr[\mathsf{Hyb}_{2}=1]-\Pr[\mathsf{Hyb}_{3}=1]}\leq\sum_{i^{\prime}\in
m}\absolutevalue{\Pr[\mathsf{Hyb}_{2,i^{\prime}-1}=1\land i^{\prime}\in
S_{\mathtt{secure}}]-\Pr[\mathsf{Hyb}_{2,i}=1\land i^{\prime}\in
S_{\mathtt{secure}}]},$ (31)

where we define $\mathsf{Hyb}_{2,0}=\mathsf{Hyb}_{2}$ and
$\mathsf{Hyb}_{2,m}=\mathsf{Hyb}_{3}$. To estimate each term of Equation 31,
we construct the following adversary $\mathpzc{B}$ that attacks selective
lessor security of $\mathsf{iSKFE\textrm{-}sbSKL}$.

  1. 1.

$\mathpzc{B}$ executes $\mathpzc{A}$ and obtains
$(1^{q},n,x_{0}^{*},x_{1}^{*})$. $\mathpzc{B}$ generates
$\mathsf{params}\coloneqq(p,\ell,(T_{i})_{i\in[m]})\leftarrow\mathsf{SetGen}(1^{\lambda})$.
$\mathpzc{B}$ generates $j_{i}^{k}\leftarrow[N]$ for every $i\in[m]$ and
$k\in[n]$ and $j_{i}^{*}\leftarrow[N]$ for every $i\in[m]$, and identifies
$S_{\mathtt{secure}}$ and $S_{\mathtt{insecure}}$, where $N=n/p$. If
$i^{\prime}\notin S_{\mathtt{secure}}$, $\mathpzc{B}$ aborts with output $0$.
Otherwise, $\mathpzc{B}$ behaves as follows. Below, we let
$S_{\mathtt{secure},<i^{\prime}}=S_{\mathtt{secure}}\cap[i^{\prime}-1]$.
$\mathpzc{B}$ computes
$(s_{i}^{*})_{i\in[m]}\leftarrow\mathsf{InpEncode}(\mathsf{params},x_{0}^{*})$.
$\mathpzc{B}$ also generates $K\leftarrow\\{0,1\\}^{\lambda}$. $\mathpzc{B}$
sends
$(1^{q},N,j_{i^{\prime}}^{*},\allowbreak(s^{*}_{i^{\prime}},\boldsymbol{0},0),(\boldsymbol{0},K,1))$.
$\mathpzc{B}$ also generates
$\mathsf{msk}_{i}\leftarrow\mathsf{iSetup}(1^{\lambda},1^{q},N)$ for every
$i\in[m]\setminus\\{i^{\prime}\\}$. $\mathpzc{B}$ simulates oracles for
$\mathpzc{A}$ as follows.

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

Given the $k$-th query $x^{k}$, $\mathpzc{B}$ returns
$\mathsf{sbskl}.\mathsf{ct}^{k}$ generated as follows.

     * •

Generate
$(s^{k}_{i})_{i\in[m]}\leftarrow\mathsf{InpEncode}(\mathsf{params},x^{k})$.

     * •

If $k\leq n$, use $(j_{i}^{k})_{i\in[m]}$ generated at the beginning.
Otherwise, Generate $j^{k}_{i}\leftarrow[N]$ for every $i\in[m]$.

     * •

Query $(j^{k}_{i^{\prime}},(s^{k}_{i^{\prime}},\boldsymbol{0},0))$ to its
encryption oracle and obtain $\mathsf{ct}^{k}_{i^{\prime}}$.

     * •

Generate
$\mathsf{ct}^{k}_{i}\leftarrow\mathsf{iEnc}(\mathsf{msk}_{i},j_{i}^{k},(s^{k}_{i},\boldsymbol{0},0))$
for every $i\in[m]\setminus\\{i^{\prime}\\}$.

     * •

Set $\mathsf{sbskl}.\mathsf{ct}^{k}\coloneqq(\mathsf{ct}^{k}_{i})_{i\in[m]}$.

$O_{\mathtt{\mathpzc{KG}}}(f)$:

Given $f$, $\mathpzc{B}$ returns $\mathsf{sbskl}.\mathpzc{fsk}$ computed as
follows.

     * •

Generate $(f_{i})_{i\in[m]}\leftarrow\mathsf{FuncEncode}(\mathsf{params},f)$.

     * •

Generate $\mathsf{sct}_{i}\leftarrow\mathsf{E}(K,\boldsymbol{0})$ for every
$i\in S_{\mathtt{insecure}}$. Generate also
$\mathsf{sct}_{i}\leftarrow\mathsf{E}(K,f_{i}(s_{i}^{*}))$ for every $i\in
S_{\mathtt{secure}}$ if $f(x_{0}^{*})=f(x_{1}^{*})$, and otherwise generate
$\mathsf{sct}_{i}\leftarrow\mathsf{E}(K,\boldsymbol{0})$ for every $i\in
S_{\mathtt{secure}}$.

     * •

Query $F[f_{i^{\prime}},\mathsf{sct}_{i^{\prime}}]$ to its key generation
oracle and obtain $(\mathpzc{fsk}_{i^{\prime}},\mathsf{vk}_{i^{\prime}})$.

     * •

Generate
$(\mathpzc{fsk}_{i},\mathsf{vk}_{i})\leftarrow\mathpzc{iKG}(\mathsf{msk}_{i},F[f_{i},\mathsf{sct}_{i}])$
for every $i\in[m]\setminus\\{i^{\prime}\\}$.

     * •

Set $\mathsf{sbskl}.\mathpzc{fsk}\coloneqq(\mathpzc{fsk}_{i})_{i\in[m]}$.

Also, $\mathpzc{B}$ adds
$(f,(\mathsf{vk}_{i})_{i\in[m]\setminus\\{i^{\prime}\\}},\bot)$ to
$L_{\mathtt{\mathpzc{KG}}}$.

$O_{\mathtt{\mathsf{Vrfy}}}(f,\mathsf{cert}\coloneqq(\mathsf{cert}_{i})_{i\in[m]})$:

Given $(f,\mathsf{cert}\coloneqq(\mathsf{cert}_{i})_{i\in[m]})$, it finds an
entry $(f,(\mathsf{vk}_{i})_{i\in[m]\setminus\\{i^{\prime}\\}},\bot)$ from
$L_{\mathtt{\mathpzc{KG}}}$. (If there is no such entry, it returns $\bot$.)
$\mathpzc{B}$ sends $(f,\mathsf{cert}_{i^{\prime}})$ to its verification
oracle and obtains $M_{i^{\prime}}$. If $M=\top$ and
$\top=\mathsf{Vrfy}(\mathsf{vk}_{i},\mathsf{cert}_{i})$ for every
$i\in[m]\setminus\\{i^{\prime}\\}$, $\mathpzc{B}$ returns $\top$ and updates
the entry into
$(f,(\mathsf{vk}_{i})_{i\in[m]\setminus\\{i^{\prime}\\}},\top)$. Otherwise,
$\mathpzc{B}$ returns $\bot$.

  2. 2.

When $\mathpzc{A}$ requests the challenge ciphertext, $\mathpzc{B}$ checks if
for any entry $(f,(\mathsf{vk}_{i})_{i\in[m]\setminus\\{i^{\prime}\\}},M)$ in
$L_{\mathtt{\mathpzc{KG}}}$ such that $f(x_{0}^{*})\neq f(x_{1}^{*})$, it
holds that $M=\top$. If so, $\mathpzc{B}$ requests the challenge ciphertext to
its challenger and obtains $\mathsf{ct}_{i^{\prime}}^{*}$. $\mathpzc{B}$ also
generates
$\mathsf{ct}^{*}_{i}\leftarrow\mathsf{iEnc}(\mathsf{msk}_{i},j_{i}^{*},(\boldsymbol{0},K,1))$
for every $i\in S_{\mathtt{secure},<i^{\prime}}$ and
$\mathsf{ct}^{*}_{i}\leftarrow\mathsf{iEnc}(\mathsf{msk}_{i},j_{i}^{*},(s^{*}_{i},\boldsymbol{0},0))$
for every
$i\in[m]\setminus(S_{\mathtt{secure},<i^{\prime}}\cup\\{i^{\prime}\\})$.
$\mathpzc{B}$ sends
$\mathsf{sbskl}.\mathsf{ct}\coloneqq(\mathsf{ct}^{*}_{i})_{i\in[m]}$ to
$\mathpzc{A}$. Hereafter, $\mathpzc{B}$ rejects $\mathpzc{A}$’s query $f$ to
$O_{\mathtt{\mathpzc{KG}}}$ such that $f(x_{0}^{*})\neq f(x_{1}^{*})$.

  3. 3.

When $\mathpzc{A}$ outputs $\mathsf{coin}^{\prime}$, $\mathpzc{B}$ outputs
$\mathsf{coin}^{\prime}$.

$\mathpzc{B}$ simulates $\mathsf{Hyb}_{2,i^{\prime}-1}$ (resp.
$\mathsf{Hyb}_{2,i^{\prime}}$) if $\mathpzc{B}$ runs in
$\mathsf{Exp}_{\mathpzc{B},\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}}^{\mathsf{sel}\mbox{-}\mathsf{s}\mbox{-}\mathsf{lessor}}(1^{\lambda},0)$
(resp.
$\mathsf{Exp}_{\mathpzc{B},\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}}^{\mathsf{sel}\mbox{-}\mathsf{s}\mbox{-}\mathsf{lessor}}(1^{\lambda},1)$)
and $i^{\prime}\in S_{\mathtt{secure}}$. This completes the proof.

###### Proposition 5.3.

$\absolutevalue{\Pr[\mathsf{Hyb}_{3}=1]-\Pr[\mathsf{Hyb}_{4}=1]}={\mathsf{negl}}(\lambda)$
holds if $\mathsf{SetHSS}$ is a set homomorphic secret sharing.

###### Proof of Proposition 5.3.

We construct the following adversary $\mathpzc{B}$ that attacks the selective
indistinguishability-security of $\mathsf{SetHSS}$.

  1. 1.

Given $\mathsf{params}\coloneqq(p,\ell,(T_{i})_{i\in[m]})$, $\mathpzc{B}$
executes $\mathpzc{A}$ and obtains $(1^{q},n,x_{0}^{*},x_{1}^{*})$.
$\mathpzc{B}$ generates $j_{i}^{k}\leftarrow[N]$ for every $i\in[m]$ and
$k\in[n]$ and $j_{i}^{*}\leftarrow[N]$ for every $i\in[m]$, and identifies
$S_{\mathtt{secure}}$, $S_{\mathtt{insecure}}$, and the unmarked element
$e^{*}$, where $N=n/p$. $\mathpzc{B}$ sends $(e^{*},x_{0}^{*},x_{1}^{*})$ to
the challenger and obtains $(s^{*}_{i})_{i\in[m]_{e^{*}\notin}}$, where
$[m]_{e^{*}\notin}$ denotes the subset of $[m]$ consisting of $i$ such that
$e^{*}\notin T_{i}$. $\mathpzc{B}$ also generates
$\mathsf{msk}_{i}\leftarrow\mathsf{iSetup}(1^{\lambda},1^{q},N)$ for every
$i\in[m]$ and $K\leftarrow\\{0,1\\}^{\lambda}$. $\mathpzc{B}$ simulates
oracles for $\mathpzc{A}$ as follows.

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

Given the $k$-th query $x^{k}$, $\mathpzc{B}$ returns
$\mathsf{sbskl}.\mathsf{ct}^{k}$ generated as follows.

     * •

Generate
$(s^{k}_{i})_{i\in[m]}\leftarrow\mathsf{InpEncode}(\mathsf{params},x^{k})$.

     * •

If $k\leq n$, use $(j_{i}^{k})_{i\in[m]}$ generated at the beginning.
Otherwise, Generate $j^{k}_{i}\leftarrow[N]$ for every $i\in[m]$.

     * •

Generate
$\mathsf{ct}^{k}_{i}\leftarrow\mathsf{iEnc}(\mathsf{msk}_{i},j^{k}_{i},(s^{k}_{i},\boldsymbol{0},0))$
for every $i\in[m]$.

     * •

Set $\mathsf{sbskl}.\mathsf{ct}^{k}\coloneqq(\mathsf{ct}^{k}_{i})_{i\in[m]}$.

$O_{\mathtt{\mathpzc{KG}}}(f)$:

Given $f$, $\mathpzc{B}$ returns $\mathsf{sbskl}.\mathpzc{fsk}$ computed as
follows.

     * •

Queries $f$ to its function encode oracle and obtain $(f_{i},y_{i}\coloneqq
f_{i}(s^{*}_{i}))_{i\in[m]})$ if $f(x_{0}^{*})=f(x_{1}^{*})$. Otherwise,
compute $(f_{i})_{i\in[m]}\leftarrow\mathsf{FuncEncode}(\mathsf{params},f)$.

     * •

Generate $\mathsf{sct}_{i}\leftarrow\mathsf{E}(K,\boldsymbol{0})$ for every
$i\in S_{\mathtt{insecure}}$. Generate also
$\mathsf{sct}_{i}\leftarrow\mathsf{E}(K,f_{i}(s_{i}^{*}))$ for every $i\in
S_{\mathtt{secure}}$ if $f(x_{0}^{*})=f(x_{1}^{*})$, and otherwise generate
$\mathsf{sct}_{i}\leftarrow\mathsf{E}(K,\boldsymbol{0})$ for every $i\in
S_{\mathtt{secure}}$.

     * •

Generate
$(\mathpzc{fsk}_{i},\mathsf{vk}_{i})\leftarrow\mathpzc{iKG}(\mathsf{msk}_{i},F[f_{i},\mathsf{sct}_{i}])$
for every $i\in[m]$.

     * •

Set $\mathsf{sbskl}.\mathpzc{fsk}\coloneqq(\mathpzc{fsk}_{i})_{i\in[m]}$.

Also, $\mathpzc{B}$ adds $(f,(\mathsf{vk}_{i})_{i\in[m]},\bot)$ to
$L_{\mathtt{\mathpzc{KG}}}$.

$O_{\mathtt{\mathsf{Vrfy}}}(f,\mathsf{cert}\coloneqq(\mathsf{cert}_{i})_{i\in[m]})$:

Given $(f,\mathsf{cert}\coloneqq(\mathsf{cert}_{i})_{i\in[m]})$, it finds an
entry $(f,(\mathsf{vk}_{i})_{i\in[m]},\bot)$ from $L_{\mathtt{\mathpzc{KG}}}$.
(If there is no such entry, it returns $\bot$.) If
$\top=\mathsf{Vrfy}(\mathsf{vk}_{i},\mathsf{cert}_{i})$ for every $i\in[m]$
and the number of queries to $O_{\mathtt{\mathsf{Enc}}}$ at this point is less
than $n$, $\mathpzc{B}$ returns $\top$ and updates the entry into
$(f,(\mathsf{vk}_{i})_{i\in[m]},\top)$. Otherwise, $\mathpzc{B}$ returns
$\bot$.

  2. 2.

When $\mathpzc{A}$ requests the challenge ciphertext, $\mathpzc{B}$ checks if
for any entry $(f,(\mathsf{vk}_{i})_{i\in[m]\setminus\\{i^{\prime}\\}},M)$ in
$L_{\mathtt{\mathpzc{KG}}}$ such that $f(x_{0}^{*})\neq f(x_{1}^{*})$, it
holds that $M=\top$. If so, $\mathpzc{B}$ generates
$\mathsf{ct}^{*}_{i}\leftarrow\mathsf{iEnc}(\mathsf{msk}_{i},j^{*}_{i},(\boldsymbol{0},K,1))$
for every $i\in S_{\mathtt{secure}}$ and
$\mathsf{ct}^{*}_{i}\leftarrow\mathsf{iEnc}(\mathsf{msk}_{i},j^{*}_{i},(s^{*}_{i},\boldsymbol{0},0))$
for every $i\in S_{\mathtt{insecure}}$, and $\mathpzc{B}$ sends
$\mathsf{sbskl}.\mathsf{ct}\coloneqq(\mathsf{ct}^{*}_{i})_{i\in[m]}$ to
$\mathpzc{A}$. Otherwise, $\mathpzc{B}$ outputs $0$ and terminates. Hereafter,
$\mathpzc{B}$ rejects $\mathpzc{A}$’s query $f$ to $O_{\mathtt{\mathpzc{KG}}}$
such that $f(x_{0}^{*})\neq f(x_{1}^{*})$.

  3. 3.

When $\mathpzc{A}$ outputs $\mathsf{coin}^{\prime}$, $\mathpzc{B}$ outputs
$\mathsf{coin}^{\prime}$.

$\mathpzc{B}$ simulates $\mathsf{Hyb}_{3}$ (resp. $\mathsf{Hyb}_{4}$) if
$\mathpzc{B}$ runs in
$\mathsf{Exp}_{\mathsf{SetHSS},\mathpzc{B}}^{\mathsf{sel}\mbox{-}\mathsf{ind}}(1^{\lambda},0)$
(resp.
$\mathsf{Exp}_{\mathsf{SetHSS},\mathpzc{B}}^{\mathsf{sel}\mbox{-}\mathsf{ind}}(1^{\lambda},1)$).
This completes the proof.

From the above discussions, $\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}$ satisfies
selective strong lessor security.

######  Remark 5.4 (Difference from FE security amplification).

A savvy reader notices that although we use the technique used in the FE
security amplification by Jain et al. [JKMS20], we do not use their
probabilistic replacement theorem [JKMS20, Theorem 7.1 in eprint ver.] and the
nested construction [JKMS20, Section 9 in eprint ver.] in the proofs of
Theorem 5.1. We do not need them for our purpose due to the following reason.

Jain et al. need the nested construction to achieve a secure FE scheme whose
adversary’s advantage is less than $1/6$ from one whose adversary’s advantage
is any constant $\epsilon\in(0,1)$. We do not need the nested construction
since we can start with a secure construction whose adversary’s advantage is
less than $1/6$ by setting a large index space in the index-based
construction.

Jain et al. need the probabilistic replacement theorem due to the following
reason. We do not know which FE instance is secure at the beginning of the FE
security game in the security amplification context, while the adversary in
set homomorphic secret sharing must declare the index of a secure instance at
the beginning. In our case, whether each index-based FE instance is secure or
not depends on whether randomly sampled indices collide or not. In addition,
we can sample all indices used in the security game at the beginning of the
game, and a secure FE instance is fixed at the beginning. Thus, we can apply
the security of set homomorphic secret sharing without the probabilistic
replacement theorem.

##  6 SKFE with Secure Key Leasing

We construct an SKFE-SKL scheme
$\mathsf{SKFE\textrm{-}SKL}=(\mathsf{SKL}.\mathsf{Setup},\mathsf{SKL}.\mathpzc{KG},\mathsf{SKL}.\mathsf{Enc},\allowbreak\mathsf{SKL}.\mathpzc{Dec},\allowbreak\mathsf{SKL}.\mathpzc{Cert},\allowbreak\mathsf{SKL}.\mathsf{Vrfy})$
from an SKFE-sbSKL scheme
$\mathsf{SKFE}\textrm{-}\mathsf{sbSKL}\allowbreak=(\mathsf{sbSKL}.\mathsf{Setup},\allowbreak\mathsf{sbSKL}.\mathpzc{KG},\mathsf{sbSKL}.\mathsf{Enc},\allowbreak\mathsf{sbSKL}.\mathpzc{Dec},\allowbreak\mathsf{sbSKL}.\mathpzc{Cert},\mathsf{sbSKL}.\mathsf{Vrfy})$.
The description of $\mathsf{SKFE}\textrm{-}\mathsf{SKL}$ is as follows.

$\mathsf{SKL}.\mathsf{Setup}(1^{\lambda},1^{q})$:

  * •

Generate
$\mathsf{msk}_{k}\leftarrow\mathsf{sbSKL}.\mathsf{Setup}(1^{\lambda},1^{q},2^{k})$
for every $k\in[\lambda]$.

  * •

Output $\mathsf{skl}.\mathsf{msk}\coloneqq(\mathsf{msk}_{k})_{k\in[\lambda]}$.

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

  * •

Parse $(\mathsf{msk}_{k})_{k\in[\lambda]}\leftarrow\mathsf{skl}.\mathsf{msk}$.

  * •

Compute $k^{\prime}$ such that $2^{k^{\prime}-1}\leq n\leq 2^{k^{\prime}}$.

  * •

Generate
$(\mathpzc{fsk}_{k^{\prime}},\mathsf{vk}_{k^{\prime}})\leftarrow\mathsf{sbSKL}.\mathpzc{KG}(\mathsf{msk}_{k^{\prime}},f)$.

  * •

Output
$\mathsf{skl}.\mathpzc{fsk}\coloneqq(k^{\prime},\mathpzc{fsk}_{k^{\prime}})$
and $\mathsf{vk}_{k^{\prime}}$.

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

  * •

Parse $(\mathsf{msk}_{k})_{k\in[\lambda]}\leftarrow\mathsf{skl}.\mathsf{msk}$.

  * •

Generate
$\mathsf{ct}_{k}\leftarrow\mathsf{sbSKL}.\mathsf{Enc}(\mathsf{msk}_{k},x)$ for
every $k\in[\lambda]$.

  * •

Output $\mathsf{skl}.\mathsf{ct}\coloneqq(\mathsf{ct}_{k})_{k\in[\lambda]}$.

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

  * •

Parse
$(k^{\prime},\mathpzc{fsk}_{k^{\prime}})\leftarrow\mathsf{skl}.\mathpzc{fsk}$
and $(\mathsf{ct}_{k})_{k\in[\lambda]}\leftarrow\mathsf{skl}.\mathsf{ct}$.

  * •

Output