# Verifiable Hierarchical Key Assignment Schemes

Anna Lisa Ferrara, Federica Paci, Chiara Ricciardi

► To cite this version:

Anna Lisa Ferrara, Federica Paci, Chiara Ricciardi. Verifiable Hierarchical Key Assignment Schemes. 35th IFIP Annual Conference on Data and Applications Security and Privacy (DBSec), Jul 2021, Calgary, AB, Canada. pp.357-376, 10.1007/978-3-030-81242-3_21. hal-03677042

HAL Id: hal-03677042

https://inria.hal.science/hal-03677042

Submitted on 24 May 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
# Verifiable Hierarchical Key Assignment Schemes

Anna Lisa Ferrara¹, Federica Paci², and Chiara Ricciardi¹

¹ Università degli Studi del Molise, Italy,

annalisa.ferrara@unimol.it; c.ricciardi1@studenti.unimol.it

² Università degli Studi di Verona, Italy

federicamariafrancesca.paci@univr.it

**Abstract.** A Hierarchical Key Assignment Scheme (HKAS) is a method to assign some private information and secret keys to a set of classes in a partially ordered hierarchy, so that the private information of a higher class together with some public information can be used to derive the keys of all classes lower down in the hierarchy. Historically, HKAS has been introduced to enforce multi-level access control, where it can be safely assumed that the public information is made available in some authenticated form. Subsequently, HKAS has found application in several other contexts where, instead, it would be convenient to certify the trustworthiness of public information. Such application contexts include key management for IoT and for emerging distributed data acquisition systems such as wireless sensor networks. In this paper, motivated by the need of accommodating this additional security requirement, we first introduce a new cryptographic primitive: *Verifiable Hierarchical Key Assignment Scheme* (VHKAS). A VHKAS is a key assignment scheme with a verification procedure that allows honest users to verify whether public information has been maliciously modified to induce an honest user to obtain an incorrect key. Then, we design and analyse VHKASs which are provably secure. Our solutions support key update for compromised secret keys by making a limited number of changes to public and private information.

**Keywords:** hierarchical key assignment, access control, applied cryptography

## 1 Introduction

Users of a computer system could be organized into a hierarchy consisting of a number of separate classes. These classes, called security classes, are positioned and ordered within the hierarchy according to the fact that some users have more access rights than others. For instance, in a hospital, doctors can access their patients' medical records, while researchers can only consult anonymous clinical information for studies.

A hierarchical key assignment (HKAS) scheme is a method to assign a secret key and some private information to each class in the hierarchy so that keys for descendant classes can be obtained via a key derivation procedure. This
assignment is carried out by a central authority, the Trusted Authority (TA). Following the seminal work by Akl and Taylor [2], many researchers have proposed different HKASs that either have better performances or allow dynamic updates to the hierarchy (e.g., [3, 5, 10, 14, 12, 16, 19]). Crampton et al. in [15] provided a detailed classification for HKASs, according to several parameters, including memory requirements for public and private information and the complexity of handling dynamic updates. In particular, they identified families of schemes where the public information is used to store secret keys in order to reduce the amount of private information users need to manage<fnref n="3" />. The use of HKASs belonging to such families is desirable to prevent or limit the change of private information and its redistribution when handling encryption key updates. Indeed, for these schemes, the key update procedure which is necessary to replace compromised keys, often requires changing only the public information without the need of interacting with the involved users. In the remainder of the paper, we refer to HKAS schemes belonging to such families.

Historically, HKASs have been introduced to enforce multi-level access control in scenarios where it can be safely assumed that the public information is made available to everyone via a publicly accessible repository for which only the TA has write permissions. However, key assignment schemes have recently been employed in different application context where the public information may be exposed to changes by malicious users. These application contexts include key management for IoT and distributed data acquisition systems such as wireless sensor networks [4, 10, 24] as well as sensitive data outsourcing to the cloud [9, 11, 17, 18, 23]. For instance, consider sensitive data outsourcing in cloud; the data owner encrypts the data before outsourcing them at the server and distributes the private information (i.e., secret keys used to encrypt the data and derivation material) to the users by means of an HKAS according to the access policy. Only the data owner and users who know the appropriate encryption and derivation keys will be able to decrypt the data. However, metadata which includes the public information will also be stored at the server and thus may be modified voluntarily or involuntarily by those who have access to it, including the cloud service provider which is not necessarily trusted. Unfortunately, a change in the public information will prevent an honest user to derive a correct decryption key. Similarly, in wireless sensor networks, the cluster head nodes are responsible for forwarding any public information that has been changed as a result of key updates. If a cluster head node is corrupted, this information may be maliciously modified before reaching its destination.

The scenarios outlined above introduce the need for an honest user to verify the trustworthiness of the public information. In order to accommodate this additional security requirement, we introduce a new cryptographic primitive: *Verifiable Hierarchical Key Assignment Scheme* (VHKAS). A VHKAS is a key assignment scheme with a verification procedure that allows honest users to verify whether public information has been maliciously modified. In order to capture a notion of security against an adversary who has the ability to replace or

<footnote n="3">³ Such families include IKEKAS, DKEKAS, and TKEKAS[15].</footnote>
modify the public information, we introduce the notion of strong key-consistency.
This notion models the fact that even the TA is unable to maliciously modify
the public information once distributed the private information.

More in detail, our contributions are as follows:

- We first give formal definitions for VHKAS; and the notion of security strong key-consistency;

- subsequently, we present a construction of VHKAS that uses as building
  block a Message Locked Encryption (MLE) scheme. We show that the con-
  struction is provably-secure with respect to strong key-consistency and key
  indistinguishability, which corresponds to the requirement that an adversary
  is not able to learn any information about a key that it should not have
  access to;

- afterwards, we show how to handle key replacement for compromised secret
keys by making a limited number of changes to public and private informa-
tion;

- finally, we instantiate our MLE-based construction with the deterministic
MLE scheme proposed by Abadi et al.[1].

The paper is organized as follows: in Section 2 we review the definitions of
HKAS, and MLE as well as their notions of security. In Section 3 we define
VHKAS and introduce the security notion of strong key-consistency. In Section
4 we show our MLE-based construction, prove it to be provably-secure with
respect to key-consistency and key indistinguishability and instantiate it with
the deterministic MLE scheme proposed by Abadi et al.[1]. In Section 5 we show
how to handle key replacements. In Section 6 we evaluate the performance of our
construction by comparing it with that of popular HKAS from the literature,
while Section 7 concludes the paper.

2 Preliminaries

**Notation.** We use the standard notation to describe probabilistic algorithm and experiments. If $A(\cdot, \cdot, \dots)$ is any probabilistic algorithm then $a \leftarrow A(x, y, \dots)$ denotes the experiment of running $A$ on inputs $x, y, \dots$ and letting $a$ be the outcome, the probability being over the coins of $A$. Similarly, if $X$ is a set then $x \leftarrow X$ denotes the experiment of selecting an element uniformly from $X$ and assigning $x$ this value. If $w$ is neither an algorithm nor a set then $x \leftarrow w$ is a simple assignment statement. For two bit-strings $x$ and $y$ we denote by $x||y$ their concatenation. A function $\epsilon: \mathbb{N} \to \mathbb{R}$ is negligible if for every constant $c > 0$ there exists an integer $n_c$ such that $\epsilon(n) < n^{-c}$ for all $n \ge n_c$.

## 2.1 Hierarchical Key Assignment Schemes

Consider a set of users divided into a number of disjoint classes, called *security classes*. A binary relation $\preceq$ that partially orders the set of classes $V$ is defined in accordance with authority, position, or power of each class in $V$. The poset $(V, \preceq)$
is called a *partially ordered hierarchy*. For any two classes $u$ and $v$, the notation $u \preceq v$ is used to indicate that the users in $v$ can access $u$'s data. The partially ordered hierarchy $(V, \preceq)$ can be represented by the directed graph $G = (V, E)$, where each class corresponds to a vertex and there is a path from class $v$ to class $u$ if and only if $u \preceq v$. A hierarchical key assignment scheme is a method to assign a secret key and some private information to each class in the hierarchy. The private information will be used by each class to compute the keys assigned to all classes lower down in the hierarchy. This assignment is carried out by the TA. Formally:

**Definition 1 ([20]).** Let $\Gamma$ be a family of graphs corresponding to partially ordered hierarchies. A HKAS for $\Gamma$ is a pair $(\text{Gen}, \text{Der})$ of algorithms satisfying the following conditions:

1. The information generation algorithm Gen is probabilistic polynomial-time. It takes as input the security parameter $1^{\tau}$ and a graph $G = (V, E)$ in $\Gamma$, and produces as outputs

- a private information $s_u$, for any class $u \in V$;

- a key $k_u$, for any class $u \in V$;

- a public information pub.

We denote by $(s, k, \text{pub})$ the output of the algorithm Gen, where $s$ and $k$ denote the sequences of private information and of keys, respectively.

2. The key derivation algorithm Der is deterministic polynomial-time. It takes as input the security parameter $1^{\tau}$, a graph $G = (V, E)$ in $\Gamma$, two classes $u, v$ in $V$, the private information $s_u$ assigned to class $u$ and the public information pub, and produces as output the key $k_v$ assigned to class $v$ if $v \preceq u$, or a special rejection symbol $\perp$ otherwise.

We require that for each class $u \in V$, each class $v \preceq u$, each private information $s_u$, each key $k_v$, each public information pub which can be computed by Gen on inputs $1^{\tau}$ and $G$, it holds that $\text{Der}(1^{\tau}, G, u, v, s_u, \text{pub}) = k_v$.

**Security notions.** Atallah et al. [5] first introduced two different security goals for HKASs: security with respect to key indistinguishability and security against key recovery. In this paper, we only consider the stronger notion of key indistinguishability [6, 5].

$\text{STAT}_u$ is a static adversary who wants to attack a class $u \in V$ and who is able to corrupt all users not entitled to compute the key of class $u$. Algorithm $\text{Corrupt}_u$ which, on input the private information $s$ generated by the algorithm $\text{Gen}$, extracts the secret values $s_v$ associated to each class that the adversary is able to corrupt. In the indistinguishability game, the adversary must distinguish the key of class $u$ from a random value.

**Definition 2.** [IND-ST] Let $\Gamma$ be a family of graphs corresponding to partially ordered hierarchies, let $G = (V, E)$ be a graph in $\Gamma$, let $(\text{Gen}, \text{Der})$ be a HKAS for $\Gamma$ and let $\text{STAT}_u$ be a static adversary who attacks a class $u$. Consider the following two experiments:
Experiment $\mathbf{Exp}_{\text{STAT}_u}^{\text{IND-}1}(1^{\tau}, G)$
$(s, k, \text{pub}) \leftarrow \text{Gen}(1^{\tau}, G)$
$\text{corr} \leftarrow \text{Corrupt}_u(s)$
$d \leftarrow \text{STAT}_u(1^{\tau}, G, \text{pub}, \text{corr}, k_u)$
\textbf{return }$d$

Experiment $\mathbf{Exp}_{\text{STAT}_u}^{\text{IND-}0}(1^{\tau}, G)$
$(s, k, \text{pub}) \leftarrow \text{Gen}(1^{\tau}, G)$
$\text{corr} \leftarrow \text{Corrupt}_u(s)$
$\rho \leftarrow \{0, 1\}^{\text{length}(k_u)}$
$d \leftarrow \text{STAT}_u(1^{\tau}, G, \text{pub}, \text{corr}, \rho)$
\textbf{return }$d$

The advantage of $\text{STAT}_u$ is defined as $\mathbf{Adv}_{\text{STAT}_u}^{\text{IND}}(1^{\tau}, G) = |\Pr[\mathbf{Exp}_{\text{STAT}_u}^{\text{IND}-1}(1^{\tau}, G) = 1] - \Pr[\mathbf{Exp}_{\text{STAT}_u}^{\text{IND}-0}(1^{\tau}, G) = 1]|$. The scheme is secure in the sense of IND-ST if, for each graph $G = (V, E)$ in $\Gamma$ and each $u \in V$, the function $\mathbf{Adv}_{\text{STAT}_u}^{\text{IND}}(1^{\tau}, G)$ is negligible, for each adversary $\text{STAT}_u$ with time complexity polynomial in $\tau^4$.

## 2.2 Message-Locked Encryption

An Message-Locked Encryption (MLE) is a symmetric encryption scheme in which the key is itself derived from the message. Provably-secure MLE schemes have been first proposed by Bellare et al. in [8].

**Definition 3 ([1]).** A MLE scheme is a tuple $(\text{PPGen}, \text{KD}, \text{Enc}, \text{Dec}, \text{Valid})^5$ of algorithms satisfying the following conditions:

1. The parameter generation algorithm $\text{PPGen}$ on input $1^{\tau}$ returns a public parameter $\text{pp}$.

2. The key derivation function $\text{KD}$ takes as input the message $m$ in the message space $\mathcal{M}$ and $\text{pp}$ and produces as output message-derived key $k_m$.

3. The encryption algorithm $\text{Enc}$ takes as input $\text{pp}$, the key $k_m$, and the message $m$ in $\mathcal{M}$, and produces as output the ciphertext $c$.

4. The decryption algorithm $\text{Dec}$ takes as input $\text{pp}$, the key $k_m$ and the ciphertext $c$ and produces as output the message $m$ or $\perp$.

5. The validity-test $\text{Valid}$ takes as input public parameters $\text{pp}$ and a ciphertext $c$ and outputs $1$ if the ciphertext $c$ is a valid ciphertext, and $0$ otherwise.

**Security notions.** The definitions below make use of some parameters that are functions of the security parameter. Specifically, $k = k(\tau)$ denoting min-entropy requirements over message sources, and $T = T(\tau)$ representing the number of blocks in the message.

*Entropy.* The min-entropy of a random variable $X$ is defined as $H_{\infty}(X) = -\log(\max_x \Pr[X = x])$. In other words, $H_{\infty}(X) = k$, if $\max_x \Pr[X = x] = 2^{-k}$. A $k$-source is a random variable $X$ with $H_{\infty}(X) \ge k$. A $(k_1, \dots, k_T)$-source is a random variable $\mathbf{X} = (X_1, \dots, X_T)$ where each $X_i$ is a $k_i$-source. A $(T, k)$-source is a random variable $\mathbf{X} = (X_1, \dots, X_T)$ where, for each $i = 1, \dots, T$, it holds that $X_i$ is a $k$-source. Next, we recall the definitions of real-or-random encryption oracle, polynomial-size $X$-source adversary, and, for schemes that rely on random oracles, $q$-query $X$-source adversary.

<footnote n="4">⁴ In [6] it has been proven that security against adaptive adversaries is (polynomially) equivalent to security against static adversaries.</footnote>

<footnote n="5">⁵ MLE definition also includes an equality algorithm. We omit it since it is not necessary for our goals.</footnote>
**Definition 4 ([1]).** Real or Random encryption oracle. The real-or-random encryption oracle, RoR, takes as input triplets of the form (mode, pp, M), where mode ∈ {real, rand}, pp denotes public parameters, and M is a polynomial size circuit representing a joint distribution over T messages. If mode = real then the oracle samples (m₁, ..., m_T) ← M, and if mode = rand then the oracle samples uniform and independent messages (m₁, ..., m_T) ← M. Next, for each i = 1, ..., T, it samples kᵢ ← KD(pp, mᵢ), computes cᵢ ← Enc(pp, kᵢ, mᵢ) and outputs the ciphertext vector (c₁, ..., c_T).

**Definition 5 ([1]).** Poly-sampling complexity adversary. Let A be a probabilistic polynomial-time algorithm that is given as input a pair (1^τ, pp) and oracle access to (1^τ, pp) for some mode ∈ {real, rand}. Then, A is a polynomial-size (T, k)-source adversary if for each of A's RoR-queries M it holds that M is an (T, k)-source that is samplable by a circuit of (an arbitrary) polynomial size in the security parameter.

**Definition 6 ([1]).** PRV-CDA2 security<fnref n="6" />. An MLE scheme Π = (PPGen, KD, Enc, Dec, EQ, Valid) is (T, k)-source PRV-CDA2 secure, if for any probabilistic polynomial-time polynomial-size (T, k)-source adversary A, there exists a negligible function ϵ(τ) such that the advantage of A is defined as

$$ \mathbf{Adv}_{\mathcal{A}}^{\text{PRV-CDA2}}(1^{\tau}) = |\Pr[\mathbf{Exp}_{\mathcal{A}}^{\text{real}}(1^{\tau}) = 1] - \Pr[\mathbf{Exp}_{\mathcal{A}}^{\text{rand}}(1^{\tau}) = 1]| \le \epsilon(\tau) $$

where for each mode ∈ {real, rand} the experiment Exp<sub>A</sub><sup>mode</sup>(τ) is defined in the following game:

$$ \begin{array}{l} \text{Experiment } \mathbf{Exp}_{\mathcal{A}}^{\text{PRV-CDA2}} \\ \quad pp \leftarrow \text{PPGen}(1^{\tau}) \\ \quad \text{return } \mathcal{A}^{\text{RoR}(\text{mode}, pp, \cdot)}(1^{\tau}, pp) \end{array} $$

## 3 Verifiable Hierarchical Key Assignment Schemes

In this section, we introduce a novel cryptographic primitive that we call Verifiable Hierarchical Key Assignment Scheme (VHKAS). A HKAS is a hierarchical key assignment scheme equipped with a verification procedure that allows honest users to check whether the public information has been maliciously changed.

A HKAS for a family Γ of graphs, corresponding to partially ordered hierarchies, is defined as follows:

**Definition 7.** A HKAS is a triple (Gen, Der, Ver) of algorithms satisfying the following conditions:

1. The information generation algorithm Gen is probabilistic polynomial-time defined as in Definition 1.

2. The key derivation algorithm Der is deterministic polynomial-time defined as in Definition 1.

<footnote n="6">⁶ Notice that PRV-CDA2 notion enables adversaries to query the oracle with message distributions that depend on the public parameters pp.</footnote>
3. The verification algorithm Ver is deterministic polynomial-time. It takes as input the security parameter $1^{\tau}$, a graph $G = (V, E)$ in $\Gamma$, a class $u$ in $V$, the private information $s_u$, a public information pub and it outputs 1 if for each class $v \in V$ such that $v \preceq u$, $Der(1^{\tau}, G, u, v, s_u, pub)$ return a valid key for the class $v$, 0 otherwise.

**Security Notions.** In order to capture a notion of security against an adversary who has the ability to replace or modify the public information so as to mislead an honest user into deriving an incorrect key, we introduce the notion of *Strong Key-Consistency* (Strong-KC). Specifically, an adversary SSTAT is able to generate the secret information $s$, the set of keys $k$, and two different public values pub and pub' in such a way that, given a class $u$, the key of some class $v \preceq u$ derived by a user in class $u$ according to pub differs from that derived according to pub' while the verification procedure succeeds in both cases. This notion models the fact that even the TA is not able to maliciously modify public information once private information has been distributed.

Now, we formally define the notion of Strong-KC:

**Definition 8.** [Strong-KC] Let $\Gamma$ be a family of graphs corresponding to partially ordered hierarchies, let $G = (V, E)$ be a graph in $\Gamma$, let $(Gen, Der, Ver)$ be a VHKAS for $\Gamma$ and let SSTAT be an adversary. Consider the following experiment:

Experiment $\mathbf{Exp}_{\text{SSTAT}}^{\text{Strong-KC}}(1^{\tau}, G)$
(s, k, pub, pub', u) $\leftarrow$ SSTAT(1^{\tau}, G)
    if ($Ver(1^{\tau}, G, u, s_u, pub) = 0 \lor Ver(1^{\tau}, G, u, s_u, pub') = 0$) return 0
    for each $v \preceq u$
        if ($Der(1^{\tau}, G, u, v, s_u, pub) \neq Der(1^{\tau}, G, u, v, s_u, pub')$)
            return 1
        return 0

The advantage of SSTAT is defined as $Adv_{\text{SSTAT}}^{\text{Strong-KC}}(1^{\tau}) = |Pr[\mathbf{Exp}_{\text{SSTAT}}^{\text{Strong-KC}}(1^{\tau}) = 1]|$. The scheme is Strong-KC secure if, the function $Adv_{\text{SSTAT}}^{\text{Strong-KC}}(1^{\tau})$ is negligible, for each adversary SSTAT whose time complexity is polynomial in $\tau$.

**Remark 1.** To help understand the extra feature provided by a VHKAS over an HKAS, in the following we consider the Encryption-Based Construction (EBC) proposed in [20] and show an example of how an attacker who manages to modify the public values is able to induce honest users to derive an incorrect key. In the EBC every class $u$ is assigned a private information $s_u$, a secret key $k_u$, and a public information $\pi(u, u)$, which is the encryption of the key $k_u$ with the private information $s_u$; furthermore, for each edge $(u, v)$, there is a public value $p(u, v)$, which allows class $u$ to compute the private information $s_v$ held by class $v$. Indeed, $p(u, v)$ consists of encrypting the private information $s_v$ with the private information $s_u$. This allows any user of a class $u$ to compute the key $k_v$ held by any class $v$ lower down in the hierarchy.

The public value $\pi(u, u)$ can be considered as being associated with an additional edge connecting the class $u$ to a dummy class $u'$. The figure 1 illustrates
<figure><img src="image_3.png" /><figcaption>Fig. 1: A chain of length 3 along with the public information generated by the EBC.</figcaption></figure>

a chain of length $t = 3$ together with the public information associated by the EBC with the edges of the chain, as well as that associated with the additional edges, which are represented by dashed lines.

A malicious user belonging to the class $u_2$ who manages to modify the public value $\pi(u_2, u_3)$ is able to induce honest users of $u_2$ and $u_1$ to derive a secret key $k$ of his choice instead of the real key $k_{u_2}$ associated with the class $u_2$. Indeed, such a malicious user, as part of the class $u_2$, holds the private information $s_{u_2}$ and can use it to compute the value $Enc_{s_{u_2}}(k)$ which can then be substituted for the public value $\pi(u_2, u_3)$ associated with the edge $(u_2, u'_2)$.

Note that even if the TA digitally signs the public values, the EBC construction does not achieve the notion of Strong-KC. Indeed, the adversary could reuse old public values and induce honest users to derive old keys. Furthermore, digitally signing public values does not prevent scenarios where the TA is involved in maliciously modifying public information.

A VHKAS will be able to withstand such attacks because public and private information will be crafted in such a way that any malicious changes to public values will be identified through the verification procedure.

## 4 An MLE-based Construction

In this section, we present a VHKAS which uses as a building block an MLE scheme. The scheme assumes that the partially ordered hierarchy has been partitioned into chains (i.e. totally ordered sets) [13, 22]. This gives a method of constructing a HKAS, represented by a directed acyclic graph $G = (V, E)$, from a HKAS for a simple chain by partitioning the poset into chains. This approach
Let $\Gamma$ be a family of graphs corresponding to chains. Let $G = (V, E) \in \Gamma$ and let $\Pi = (PPGen, KD, Enc, Dec, Valid)$ be an MLE scheme whose key derivation function KD is collision-resistant and let $\mathcal{F}: \{0, 1\}^\tau \times \{0, 1\}^\tau \to \{0, 1\}^\tau$ be a PRF.

**Algorithm Gen(1<sup>τ</sup>, G)**

1. Let $u_1, \dots, u_t$ be the classes in the chain.

2. Let $pp \leftarrow PPGen(1^\tau)$;

3. Let $\pi_{u_{t+1}} \leftarrow \{0, 1\}^\tau$;

4. For each class $u_i$, for $i = t, \dots, 1$, let

(a) $r_{u_i} \leftarrow \{0, 1\}^\tau$;

(b) $\pi_{u_i} \leftarrow KD(pp, \pi_{u_{i+1}} || r_{u_i})$;

(c) $k_{u_i} \leftarrow \mathcal{F}(\pi_{u_i}, r_{u_i})$;

(d) $s_{u_i} = (pp, r_{u_i}, \pi_{u_i}, k_{u_i})$;

5. Let $s$ and $k$ be the sequences of private information $s_{u_1}, s_{u_2}, \dots, s_{u_t}$ and keys $k_{u_1}, k_{u_2}, \dots, k_{u_t}$, respectively, computed in the previous steps;

6. For each $i = 1, \dots, t$, compute the public information

$$p_{(u_i, u_{i+1})} \leftarrow \text{Enc}(pp, \pi_{u_i}, \pi_{u_{i+1}} || r_{u_i});$$

7. Let $pub$ be the sequence of public information $p_{(u_1, u_2)}, p_{(u_2, u_3)}, \dots, p_{(u_t, u_{t+1})}$ computed in the previous step;

8. Output $(s, k, pub)$.

**Algorithm Der(1<sup>τ</sup>, G, u, v, s<sub>u</sub>, pub)**

1. Let $u = u_i$ and $v = u_j$, for some $j \ge i$, $j = 1, \dots, t$.

2. Parse $s_u$ as $(pp, r_{u_i}, \pi_{u_i}, k_{u_i})$;

3. For any $z = i, \dots, j$, extract the public value $p_{(u_z, u_{z+1})}$ from $pub$

(a) if $Valid(pp, p_{(u_z, u_{z+1})}) = 0$, return $\perp$;

(b) compute

$$(\pi_{u_{z+1}} || r_{u_z}) \leftarrow \text{Dec}(pp, \pi_{u_z}, p_{(u_z, u_{z+1})});$$

4. Output $k_v \leftarrow \mathcal{F}(\pi_{u_j}, r_{u_j})$.

**Algorithm Ver(1<sup>τ</sup>, G, u, s<sub>u</sub>, pub)**

1. Let $u = u_i$, for some $i = 1, \dots, t$.

2. Parse $s_u$ as $(pp, r_{u_i}, \pi_{u_i}, k_{u_i})$;

3. For each $j = i, \dots, t$,

(a) extract the public value $p_{(u_j, u_{j+1})}$ from $pub$;

(b) if $Valid(pp, p_{(u_j, u_{j+1})}) = 0$, return 0;

(c) let $\alpha_i = \pi_{u_i}$, compute

$$(\alpha_{j+1} || \beta_j) \leftarrow \text{Dec}(pp, \alpha_j, p_{(u_j, u_{j+1})});$$

(d) if $KD(pp, \alpha_{j+1} || \beta_j)$ is different from $\alpha_j$, return 0;

4. return 1.

<caption>Fig. 2: The MLE-based Construction.</caption>
has the nice property that the amount of private storage needed per class, is bounded by the width of the poset$^7$. Thus, in the following we will only consider a family $\Gamma$ of graphs corresponding to chains. Figure 2 shows the MLE-based construction for a chain of $t$ classes $u_1, \dots, u_t$. In order to simplify the presentation, we consider a dummy class $u_{t+1}$. This will enable us to consider all public information as values associated to the edges of a chain.

The public information, associated to the edges of the chain, is used to store the secret keys in an encrypted form. Indeed, for each $i = 1, \dots, t$, $k_{u_i} \leftarrow \mathcal{F}(\pi_{u_i}, r_{u_i})$ can be obtained by retrieving $\pi_{u_i}$ and $r_{u_i}$, respectively from $p_{(u_{i-1}, u_i)}$ and $p_{(u_i, u_{i+1})}$. Figure 3 illustrates the public information computed by the scheme for a chain of length $t = 3$. The verification procedure allows to check whether a

<figure><img src="image_4.png" /><figcaption>Fig. 3: Public information generated by the MLE-based construction for a chain of length $t = 3$.</figcaption></figure>

honest user is able to derive valid keys. Specifically, in the MLE-based construction a honest user in some class $u_i$ will derive valid keys $k_{u_j} = \text{Der}(1^\tau, G, u_i, u_j, s_{u_i}, \text{pub})$, if for each $j = i, \dots, t$, the public information $p_{(u_j, u_{j+1})}$ stores a value $x$ such that $\pi_{u_j} = \text{KD}(pp, x)$. Intuitively, any changes to public values will be detected since $\text{KD}$ is collision resistant. For example, if a malicious user belonging to class $u_1$ (see figure 3) changes $p(u_1, u_2)$ in such a way that honest users in $u_1$

<footnote>$^7$ The width is the cardinality of the largest antichain in $V$. $A \subseteq V$ is an antichain in $V$ if for all $u, v \in A$, where $u \neq v$, we have $v \preceq u$ and $u \preceq v$.</footnote>
derive a value $\pi'_{u_2} \neq \pi_{u_2}$, the verification procedure fails since $KD(pp, \pi'_{u_2} || r_{u_1})$ is different from $\pi_{u_1}$.

## 4.1 Analysis of the Scheme

In this section we show that the security of the MLE-based construction depends upon the security properties of the underlying MLE scheme.

We first show that the MLE-based construction is secure in the sense of IND-ST.

**Theorem 1.** Let $\Pi = (PPGen, KD, Enc, Dec, Valid)$ be a $(T, \mu)$-source PRV-CDA2 secure MLE scheme where $\mu = \omega(\log \tau)$ and let $\mathcal{F} : \{0, 1\}^\tau \times \{0, 1\}^\tau \to \{0, 1\}^\tau$ be a PRF. The MLE-based VHKAS of Figure 2 is secure in the sense of IND-ST.

**Proof.** Let $\text{STAT}_u$ be a static adversary attacking class $u$. Let $V = \{u_1, \dots, u_t\}$ and $(u_i, u_{i+1}) \in E$, for $i = 1, \dots, t-1$, and, w.l.o.g., let $u = u_j$ for some $1 \le j < t$. In order to prove the theorem, we need to show that the adversary's views in experiments $\text{Exp}_{\text{STAT}_u}^{\text{IND}-1}$ and $\text{Exp}_{\text{STAT}_u}^{\text{IND}-0}$ are indistinguishable. Notice that the only difference between $\text{Exp}_{\text{STAT}_u}^{\text{IND}-1}$ and $\text{Exp}_{\text{STAT}_u}^{\text{IND}-0}$ is the last input of $\text{STAT}_u$, which corresponds to the key $k_u$ in the former experiment and to a random value in the latter. Thus, while in $\text{Exp}_{\text{STAT}_u}^{\text{IND}-1}$ the public information is related to the last input of $\text{STAT}_u$, in $\text{Exp}_{\text{STAT}_u}^{\text{IND}-0}$ it is completely independent on such a value.

We construct a sequence of 4 experiments $\text{Exp}_u^1, \dots, \text{Exp}_u^4$, all defined over the same probability space, where the first and the last experiments of the sequence correspond to $\text{Exp}_{\text{STAT}_u}^{\text{IND}-1}$ and $\text{Exp}_{\text{STAT}_u}^{\text{IND}-0}$, respectively. In each experiment we modify the way the view of $\text{STAT}_u$ is computed, while maintaining the view's distributions indistinguishable among any two consecutive experiments. For any $q \in \{2, 3\}$, experiment $\text{Exp}_u^q$ is defined as follows:

Experiment $\text{Exp}_u^q(1^\tau, G)$
$(s, k, \text{pub}^q) \leftarrow \text{Gen}^q(1^\tau, G)$
$\text{corr} \leftarrow \text{Corrupt}_u(s)$
return $\text{STAT}_u(1^\tau, G, \text{pub}^q, \text{corr}, \alpha_u)$

The algorithm $\text{Gen}^q$ used in $\text{Exp}_u^q(1^\tau, G)$ differs from $\text{Gen}$ for the way part of the public information $\text{pub}^q$ is computed. Indeed, for any $i = 1, \dots, j$, the public values associated to the edge $(u_i, u_{i+1})$ is computed as the encryption $\text{Enc}(pp, \pi_i, \gamma_{u_{i+1}} || r_{u_i})$ where $\gamma_{u_{i+1}}$ and $r_{u_i}$ are random values in $\{0, 1\}^\tau$ and $\pi_i \leftarrow \text{KD}(pp, \gamma_{u_{i+1}} || r_{u_i})$. Moreover, $\text{Exp}_u^2(1^\tau, G)$ differs from $\text{Exp}_u^3(1^\tau, G)$ for the way $\alpha_{u_j}$ is constructed. Specifically, $\alpha_{u_j} \leftarrow \mathcal{F}(\gamma_{u_j}, r_{u_j})$ in $\text{Exp}_u^2$ while $\alpha_{u_j} \leftarrow \{0, 1\}^\tau$ in $\text{Exp}_u^3$.

Now we show that, the adversary's view in $\text{Exp}_u^1$ is indistinguishable from the adversary's view in $\text{Exp}_u^2$. Assume by contradiction that there exists a polynomial-time adversary $A$ which is able to distinguish between the adversary $\text{STAT}_u$'s views in experiments $\text{Exp}_u^1$ and $\text{Exp}_u^2$ with non-negligible advantage. We show how to construct a polynomial-time distinguisher $D$ which uses $A$ to break the security of the $(T, \mu)$-source PRV-CDA2 MLE scheme.
Let $\Pi = (PPGen, KD, Enc, Dec, Valid)$ be an MLE scheme.

**Algorithm for M**

On input the public parameter $pp$ output by $PPGen$, and a $\tau$-length value $\pi$, produces $T$ messages $m_1, \dots, m_T$ as follows:

- choose $r_T \in \{0, 1\}^\tau$;

- compute $m_T \leftarrow \pi \| r_T$;

- compute $\pi_T \leftarrow KD(pp, \pi \| r_T)$;

- for $i = 1, \dots, T-1$, choose $r_i \in \{0, 1\}^\tau$;

- for $i = 1, \dots, T-1$, compute $\pi_i \leftarrow KD(pp, \pi_{i+1} \| r_i)$;

- for $i = 1, \dots, T-1$, compute $m_i \leftarrow \pi_{i+1} \| r_i$.

<caption>Fig. 4: Polynomial size circuit M representing a joint distribution over $T$ messages.</caption>

In particular, the distinguisher $D$ constructs the public values associated to the edges $(u_i, u_{i+1})$, for $i = 1, \dots, j$, calling the $\text{RoR}$ oracle where $M$ implements the circuit of Figure 4 with $\pi = \pi_{u_{j+1}}$ and $T = j$. Notice that $M$ is $(T, \mu)$-source. Indeed, since $r_{u_i}$ is chosen at random by $M$, it is easy to see that the min-entropy of $m_i$ is at least $\tau$, for each $i = 1, \dots, T$. Distinguisher $D$ is defined in Figure 5.

Notice that if $\text{mode} = \text{real}$, then $\text{STAT}_u$'s view is that of $\text{Exp}_u^1(1^\tau, G)$ while when $\text{mode} = \text{rand}$, $\text{STAT}_u$'s view is that of $\text{Exp}_u^2(1^\tau, G)$. Therefore, if the algorithm $A$ is able to distinguish between such views with non negligible advantage, it follows that $D$ is able to break the PRV-CDA2 security of the MLE scheme.

**Algorithm $D^{\mathcal{ROR}(mode, pp, \cdot)}(1^\tau)$**
$\pi_{u_{t+1}} \leftarrow \{0, 1\}^\tau$
$corr \leftarrow \emptyset$
**for** each $i = t, \dots, j+1$
$\quad r_{u_i} \leftarrow \{0, 1\}^\tau$
$\quad \pi_{u_i} \leftarrow KD(pp, \pi_{u_{i+1}} \| r_{u_i})$
$\quad k_{u_i} \leftarrow \mathcal{F}(\pi_{u_i}, r_{u_i})$
$\quad p_{(u_i, u_{i+1})} \leftarrow \text{Enc}(pp, \pi_{u_i}, \pi_{u_{i+1}} \| r_{u_i})$
$\quad corr \leftarrow corr \cup (\pi_{u_i}, k_{u_i}, r_{u_i})$
Let $c_i = p_{(u_i, u_{i+1})}$, for $i = 1, \dots, j$
(c$_1, \dots, c_j) \leftarrow \text{RoR}(\text{mode}, pp, M(\pi_{u_{j+1}}, j))$
$b \leftarrow A(1^\tau, G, \text{pub}, corr, k_{u_j})$

**Algorithm $D^{f(\cdot)}(1^\tau)$**
$\pi_{u_{t+1}} \leftarrow \{0, 1\}^\tau$
**for** each $i = t, \dots, j+1$
$\quad r_{u_i} \leftarrow \{0, 1\}^\tau$
$\quad \pi_{u_i} \leftarrow KD(pp, \pi_{u_{i+1}} \| r_{u_i})$
$\quad k_{u_i} \leftarrow \mathcal{F}(\pi_{u_i}, r_{u_i})$
$\quad p_{(u_i, u_{i+1})} \leftarrow \text{Enc}(pp, \pi_{u_i}, \pi_{u_{i+1}} \| r_{u_i})$
$\quad corr \leftarrow (\pi_{u_{j+1}}, k_{u_{j+1}}, r_{u_{j+1}})$
**for** each $i = j, \dots, 1$
$\quad r_{u_i} \leftarrow \{0, 1\}^\tau$
$\quad \pi_{u_i} \leftarrow \{0, 1\}^\tau$
$\quad p_{(u_i, u_{i+1})} \leftarrow \text{Enc}(pp, \pi_{u_i}, \pi_{u_{i+1}} \| r_{u_i})$
$\quad \alpha_{u_j} \leftarrow f(r_{u_j})$
$\quad b \leftarrow B(1^\tau, G, \text{pub}, corr, \alpha_{u_j})$

<caption>Fig. 5: Distinguishers $D$ and $D'$.</caption>
Now we show that, the adversary's view in $\mathbf{Exp}_u^2$ is indistinguishable from the adversary's view in $\mathbf{Exp}_u^3$. Assume by contradiction that there exists a polynomial-time algorithm $B$ which is able to distinguish between the adversary $\text{STAT}_u$'s views in experiments $\mathbf{Exp}_u^2$ and $\mathbf{Exp}_u^3$ with non-negligible advantage. We show how to construct a polynomial-time distinguisher $D'$ which uses $B$ to distinguish whether its oracle $f(\cdot)$ corresponds to the pseudorandom function $\mathcal{F}(k, \cdot)$ or to a random function $\mathcal{F}(\cdot)$.

Notice that if $\alpha_{u_j}$ corresponds to the evaluation of the pseudorandom function $\mathcal{F}(k, \cdot)$ on $r_{u_j}$ then $\text{STAT}_u$'s view is that of $\mathbf{Exp}_u^2(1^\tau, G)$ while when it is the output of a random value, $\text{STAT}_u$'s view is that of $\mathbf{Exp}_u^3(1^\tau, G)$. Therefore, if the algorithm $B$ is able to distinguish between such views with non negligible advantage, it follows that the distinguisher $D'$ is able to break the pseudorandomness of $\mathcal{F}$. Figure 5 defines distinguisher $D'$.

**Algorithm D''ORR (mode, pp, \cdot) (1^\tau)**
$$ \pi_{u_{t+1}} \leftarrow \{0, 1\}^\tau $$
$$ \text{corr} \leftarrow \emptyset $$
**for** each $i = t, \dots, j + 1$
$$ r_{u_i} \leftarrow \{0, 1\}^\tau $$
$$ \pi_{u_i} \leftarrow \text{KD}(\text{pp}, \pi_{u_{i+1}} || r_{u_i}) $$
$$ k_{u_i} \leftarrow \mathcal{F}(\pi_{u_i}, r_{u_i}) $$
$$ p_{(u_i, u_{i+1})} \leftarrow \text{Enc}(\text{pp}, \pi_{u_i}, \pi_{u_{i+1}} || r_{u_i}) $$
$$ \text{corr} \leftarrow \text{corr} \cup (\pi_{u_i}, k_{u_i}, r_{u_i}) $$
Let $c_i = p_{(u_i, u_{i+1})}$, for $i = 1, \dots, j$
$$ (c_1, \dots, c_j) \leftarrow \text{RoR}(\text{mode}, \text{pp}, \text{M}(\pi_{u_{j+1}}, j)) $$
$$ \rho \leftarrow \{0, 1\}^\tau $$
$$ b \leftarrow C(1^\tau, G, \text{pub}, \text{corr}, \rho) $$

<caption>Fig. 6: Distinguisher $D''$.</caption>

We finally show that, the adversary's view in $\mathbf{Exp}_u^4$ is indistinguishable from the adversary's view in $\mathbf{Exp}_u^3$.

Assume by contradiction that there exists a polynomial-time algorithm $C$ which is able to distinguish between the adversary $\text{STAT}_u$'s views in experiments $\mathbf{Exp}_u^4$ and $\mathbf{Exp}_u^3$ with non-negligible advantage.

Notice that such views differ only for the public values associated to the edges $(u_i, u_{i+1})$ for $i = 1, \dots, j$. We show how to construct a polynomial-time distinguisher $D''$ which uses $C$ to break the PRV-CDA2 security of the MLE scheme. In particular, the algorithm $D''$, on input $1^\tau$, constructs the public values associated to the edges $(u_i, u_{i+1})$, for $i = 1, \dots, j$, calling the RoR oracle where $M$ implements the circuit of Figure 4 with $\pi = \pi_{u_{j+1}}$ and $T = j$.

Formally, distinguisher $D''$ is defined in Figure 6. Notice that if $\text{mode} = \text{real}$, then $\text{STAT}_u$'s view is that of $\mathbf{Exp}_u^4$ while when $\text{mode} = \text{rand}$, $\text{STAT}_u$'s view is that of $\mathbf{Exp}_u^3$.
Thus, if C distinguishes such views with non negligible advantage, it follows that algorithm $D''$ breaks the PRV-CDA2 security of the MLE scheme. □

We now show that the MLE-based construction is secure in the sense of Strong-KC.

**Theorem 2.** Let $\Pi = (PPGen, KD, Enc, Dec, Valid)$ be an MLE scheme whose key derivation function KD is collision-resistant. The MLE-based VHKAS of Figure 2 is secure in the sense of Strong-KC.

**Sketch of the Proof.** Let $V = \{u_1, \dots, u_t\}$ and $(u_i, u_{i+1}) \in E$, for $i = 1, \dots, t-1$. We show by contradiction that if there exists a static adversary SSTAT whose advantage $Adv_{SSTAT}^{\text{Strong-KC}}$ is non-negligible, then there exists a PPT adversary $\mathcal{A}$ such that $\Pr[(x_0, x_1) \leftarrow \mathcal{A}(1^{\tau}, KD(pp, \cdot)) : x_0 \neq x_1 \land KD(pp, x_0) = KD(pp, x_1)]$ is non-negligible.

The adversary SSTAT first produces two public values pub and pub' along with the private information. Then, it chooses a class $u \in V$ such that $Ver(1^{\tau}, G, u, s_u, pub) = Ver(1^{\tau}, G, u, s_u, pub') = 1$ while there exists a class $v \prec u$ where $Der(1^{\tau}, G, u, v, s_u, pub) = k_v$, $Der(1^{\tau}, G, u, v, s_u, pub') = k'_v$ and $k_v \neq k'_v$.

W.l.o.g., let $u = u_i$ and $v = u_j$, for some $1 \le i < j \le t$ where $j$ is the smallest index such that $k_{u_j} = \mathcal{F}(\pi_{u_j}, r_{u_j})$ is different from $k'_{u_j} = \mathcal{F}(\pi'_{u_j}, r'_{u_j})$.

We distinguish the following two cases:

1. $\pi_{u_j} = \pi'_{u_j}$ and $r_{u_j} \neq r'_{u_j}$;

2. $\pi_{u_j} \neq \pi'_{u_j}$.

In the following, for each class $u_s$ we will denote by $s_{u_s} = (pp, r_{u_s}, \pi_{u_s}, k_{u_s})$ and $s_{u'_s} = (pp, r'_{u_s}, \pi'_{u_s}, k'_{u_s})$, the private information computed by using the derivation procedure with respect to pub and pub'. Consider the first case. In order for the verification procedure to succeed on both pub and pub' it must be $\pi_{u_j} = KD(pp, \pi_{u_{j+1}}||r_{u_j}) = KD(pp, \pi'_{u_{j+1}}||r'_{u_j})$ where $\pi_{u_{j+1}}$ may or may not be equal to $\pi'_{u_{j+1}}$. Thus, the adversary $\mathcal{A}$ wins his game by exhibiting $x_0 = \pi_{u_{j+1}}||r_{u_j}$ and $x_1 = \pi'_{u_{j+1}}||r'_{u_j}$.

Now, consider the second case. In order for the verification procedure to succeed on both pub and pub' it must be

$$ 
\begin{aligned}
\pi_{u_i} &= KD(pp, \pi_{u_{i+1}}||r_{u_i}) \\
&= KD(pp, KD(pp, \pi_{u_{i+2}}||r_{u_{i+1}})||r_{u_i}) \\
&= KD(pp, KD(\dots(KD(pp, \pi_{u_j}||r_{u_{j-1}})||r_{u_{j-2}})\dots)||r_{u_i})
\end{aligned}
$$

and

$$ 
\begin{aligned}
\pi_{u_i} &= KD(pp, \pi'_{u_{i+1}}||r'_{u_i}) \\
&= KD(pp, KD(pp, \pi'_{u_{i+2}}||r'_{u_{i+1}})||r'_{u_i}) \\
&= KD(pp, KD(\dots(KD(pp, \pi'_{u_j}||r'_{u_{j-1}})||r'_{u_{j-2}})\dots)||r'_{u_i}).
\end{aligned}
$$
Since $\pi_{u_j}$ is different from $\pi'_{u_j}$ and $\pi_{u_i} = KD(pp, \pi_{u_{i+1}}||r_{u_i}) = KD(pp, \pi'_{u_{i+1}}||r'_{u_i})$ it holds that $KD$ is not collision resistant, thus if SSTAT wins his game with non-negligible probability also $\mathcal{A}$ succeeds with overwhelming probability. $\square$

## 4.2 A Concrete Instance

In Figure 7 we instantiate the scheme of Figure 8 with the deterministic MLE scheme $\Pi_{det}^{(q)}$ proposed in [1].

Let $G = (V, E) \in \Gamma$ (family of graphs corresponding to chains.) Let (PPGen, KD, Enc, Dec, Valid) be the $\Pi_{det}^{(q)}$ scheme and let $\mathcal{F} : \{0, 1\}^{\tau} \times \{0, 1\}^{\tau} \to \{0, 1\}^{\tau}$ be a PRF.

**Algorithm Gen(1<sup>τ</sup>, G)**

1. Let $u_1, \dots, u_t$ be the classes in the chain.

2. Let $pp = (H_1, H_2, q) \leftarrow PPGen(1^\tau)$. Let $\pi_{u_{t+1}} \leftarrow \{0, 1\}^\tau$;

3. For each class $u_i$, for $i = t, \dots, 1$, let

(a) $r_{u_i} \leftarrow \{0, 1\}^\tau$;

(b) $\pi_{u_i} \leftarrow KD(pp, \pi_{u_{i+1}}||r_{u_i}) = H_1(\pi_{u_{i+1}}||r_{u_i}||1) \oplus \dots \oplus H_1(\pi_{u_{i+1}}||r_{u_i}||t+1)$

(c) $k_{u_i} \leftarrow \mathcal{F}(\pi_{u_i}, r_{u_i})$; $s_{u_i} = (pp, r_{u_i}, \pi_{u_i}, k_{u_i})$;

4. Let $s$ and $k$ be the sequences of private information $s_{u_1}, s_{u_2}, \dots, s_{u_t}$ and keys $k_{u_1}, k_{u_2}, \dots, k_{u_t}$, respectively, computed in the previous step;

5. For each $i = 1, \dots, t$, let $w_{u_{i+1}} = H_2(\pi_{u_{i+1}}||r_{u_i}||1) \oplus \dots \oplus H_2(\pi_{u_{i+1}}||r_{u_i}||t+1)$, compute the public information $p_{(u_i, u_{i+1})} \leftarrow Enc(pp, \pi_{u_i}, \pi_{u_{i+1}}||r_{u_i}||w_{u_{i+1}})$.

**Algorithm Der(1<sup>τ</sup>, G, u, v, s<sub>u</sub>, pub)**

1. Let $u = u_i$ and $v = u_j$, for some $j \ge i$, $j = 1, \dots, t$;

2. For any $z = i, \dots, j$, extract the public value $p_{(u_z, u_{z+1})}$ from pub

(a) if Valid(pp, p_{(u_z, u_{z+1})}) = 0, return $\perp$;

(b) otherwise, compute $(\pi_{u_{z+1}}||r_{u_z}||w_{u_{z+1}}) \leftarrow Dec(pp, \pi_{u_z}, p_{(u_z, u_{z+1})})$

3. Output $k_v \leftarrow \mathcal{F}(\pi_{u_j}, r_{u_j})$.

**Algorithm Ver(1<sup>τ</sup>, G, u, v, s<sub>u</sub>, pub)**

1. Let $u = u_i$, for $i = 1, \dots, t$;

2. For any $j = i, \dots, t$,

(a) extract the public value $p_{(u_j, u_{j+1})}$ from pub

(b) if Valid(pp, p_{(u_j, u_{j+1})}) = 0, return 0;

(c) let $\alpha_i = \pi_{u_i}$, compute $(\alpha_{j+1}||\beta_j||\gamma_{j+1}) \leftarrow Dec(pp, \alpha_j, p_{(u_j, u_{j+1})})$;

(d) if $KD(pp, \alpha_{j+1}||\beta_j)$ is different from $\alpha_j$, return 0;

3. return 1.

<caption>Fig. 7: An instance of the MLE-based Construction.</caption>
$\Pi_{det}^{(q)}$ uses as a building block a symmetric-key encryption scheme $\mathcal{SE} = (\mathcal{K}, \mathcal{E}, \mathcal{D})$ and two hash functions $H_1 : \{0, 1\}^* \to \{0, 1\}^\tau$ and $H_2 : \{0, 1\}^* \to \{0, 1\}^\rho$ with randomness length $\rho$. If $\mathcal{SE}$ is an IND-CPA secure scheme and $H_1$ and $H_2$ are modeled as random oracles, then, for any $T = \text{poly}(\tau)$ and any $k = \omega(\log\tau)$, $\Pi_{det}^{(q)}$ is q-query $(T, k)$-source PRV-CDA2-secure.

The scheme $\Pi_{det}^{(q)} = (\text{PPGen}, \text{KD}, \text{Enc}, \text{Dec}, \text{EQ}, \text{Valid})$ is defined as follows:

- **Parameter-generation algorithm:** On input $1^\lambda$, the algorithm PPGen chooses two hash functions $H_1 : \{0, 1\}^* \to \mathcal{K}$ and $H_2 : \{0, 1\}^* \to \{0, 1\}^\rho$. It outputs the public parameters $pp = (H_1, H_2, q)$.

- **Key-derivation function:** The algorithm KD takes as input public parameters $pp$, the message $m$ and outputs the message-derived key $k_m = H_1(m||1) \oplus H_1(m||2) \oplus \dots \oplus H_1(m||q+1) \in \mathcal{K}$.

- **Encryption algorithm:** The algorithm Enc takes as input public parameters $pp$, a message $m$, and a message-derived key $k_m$. It computes $w_m = H_2(m||1) \oplus H_2(m||2) \oplus \dots \oplus H_2(m||q+1)$ and outputs $E_{k_m}(m||w_m) \in \mathcal{C}$.

- **Validity test:** The algorithm Valid outputs 1 on any input $c \in \mathcal{C}$.

- **Decryption algorithm:** Dec takes as input public parameters $pp$, a ciphertext $c$, and a message-derived key $k_m$ and outputs $m \leftarrow D_{k_m}(c)$.

- **Equality algorithm:** Algorithm EQ on input public parameters $pp$ and ciphertexts $c_1$ and $c_2$ outputs 1 if and only if $c_1 = c_2$.

From the PRV-CDA2 security of $\Pi_{det}^{(q)}$ the instance of Figure 7 is secure in the random oracle model.

# 5 Handling Key Replacement

Cryptographic keys need to be periodically changed. Thus, a key assignment scheme should feature an efficient procedure for the TA to handle key replacements.

A VHKAS which handles key replacement is a tuple $(\text{Gen}, \text{Der}, \text{Ver}, \text{KReplace})$, where $(\text{Gen}, \text{Der}, \text{Ver})$ is defined in Definition 7 and algorithm KReplace satisfies the following conditions:

- The key replacement algorithm KReplace is probabilistic polynomial-time. It takes as input $1^\tau$ and a graph $G = (V, E)$ in $\Gamma$, a class $u$, the secret information $s$, the public information pub and produces as output $(s, k, \text{pub})$.

A key replacement procedure may require both public information and private values to be changed. Ideally, such a procedure will only change public information so that private values are not redistributed. In general, it is desirable to design the key replacement algorithm to modify as few private values as possible.
Figure 8 shows how the TA can handle the replacement of a key $k_u$ for a class $u$ in the MLE-based construction of Figure 2. In such a procedure only the classes higher than $u$ in the chain are affected by the change.

Let (Gen, Der, Ver) be the scheme of Figure 2. The MLE-based scheme with key replacement is the tuple (Gen, Der, Ver, KReplace) where KReplace is as follows:
**Algorithm KReplace(1^τ, G, u, s, pub)**

1. Let $u_1, \dots, u_t$ be the classes in the chain.

2. Let $u = u_j$, for some $1 \le j \le t$;

3. For $i = j, \dots, 1$, let

(a) choose a new $r_{u_i} \leftarrow \{0, 1\}^\tau$;

(b) $\pi_{u_i} \leftarrow KD(pp, \pi_{u_{i+1}} || r_{u_i})$;

(c) $p_{(u_i, u_{i+1})} \leftarrow Enc(pp, \pi_{u_i}, \pi_{u_{i+1}} || r_{u_i})$;

(d) $k_{u_i} \leftarrow \mathcal{F}(\pi_{u_i}, r_{u_i})$.

4. Let $s, k$, and $pub$ be the new sequences of private information, keys and public values, respectively;

5. Output($s, k, pub$).

<caption>Fig. 8: MLE-based construction with key replacement.</caption>

In Figure 9 we describe the key replacement procedure when the MLE-based construction is instantiated with the deterministic MLE scheme $\Pi_{det}^{(q)}$ proposed in [1].

**Algorithm KReplace(1^τ, G, u, s, pub)**

1. Let $u_1, \dots, u_t$ be the classes in the chain.

2. Let $u = u_j$, for some $1 \le j \le t$;

3. Choose a new $r_{u_j} \leftarrow \{0, 1\}^\tau$;

4. For $i = j, \dots, 1$, let $w_{u_{i+1}} = H_2(\pi_{u_{i+1}} || r_{u_i} || 1) \oplus \dots \oplus H_2(\pi_{u_{i+1}} || r_{u_i} || t + 1)$

(a) $\pi_{u_i} \leftarrow KD(pp, \pi_{u_{i+1}} || r_{u_i})$;

(b) $p_{(u_i, u_{i+1})} \leftarrow Enc(pp, \pi_{u_i}, \pi_{u_{i+1}} || r_{u_i} || w_{u_{i+1}})$;

(c) $k_{u_i} \leftarrow \mathcal{F}(\pi_{u_i}, r_{u_i})$.

5. Let $s, k$, and $pub$ be the new sequences of private information, keys and public values, respectively;

6. Output($s, k, pub$).

<caption>Fig. 9: The key replacement procedure for the instance of Figure 7.</caption>
## 6 Comparisons with Hierarchical Key Assignment Schemes

We evaluate the performance of our construction by comparing it with that of popular IND-ST HKAS from the literature having the feature that the public information is used to store encryption keys. The comparison shows that the performance of our construction is similar to that of such schemes despite the fact that it also achieves the notion of Strong-KC.

Figure 10 shows the comparison. The summary takes into account several parameters, such as the size of the public and private information, the number and the type of operations required by a class $u \in V$ to compute the key of a class $v$ lower down in the hierarchy. Moreover, it specifies the notions of security achieved. In Figure 10, $\tau$ and $\tau_1$ correspond respectively to the size of the secret key in symmetric encryption based constructions and in schemes obtained from factoring$^8$. The value $c$ is a constant depending on the underlying encryption scheme. For instance $c$ is equal to 2 for the so called XOR construction in [7]. Notice that, to describe the parameters of the MLE-based construction we refer to the concrete instance described in Section 4.2 where the MLE considered uses as a building block a symmetric encryption scheme. Finally, $w$ represents the width of the poset which corresponds to the number of chains in the partition.

<table><caption>Fig. 10: Comparisons with Hierarchical Key Assignment Schemes.</caption><thead><tr><th>Scheme</th><th>Public info.</th><th>Private info.</th><th>Key derivation</th><th>Security Notions</th></tr></thead><tbody><tr><td>MLE-based §4</td><td>|E|<i>c</i><i>τ</i></td><td><i>τ</i>O(w)</td><td>Path(u, v) MLE decryptions +1 PRF eval.</td><td>IND-ST<br>Strong-KC.</td></tr><tr><td>EBC [20]</td><td>(|E| + |V|)<i>c</i><i>τ</i></td><td><i>τ</i></td><td>Path(u, v) + 1 decryptions</td><td>IND-ST.</td></tr><tr><td>Freire et al. [21]</td><td><i>τ</i><sub>1</sub></td><td><i>τ</i><sub>1</sub>O(w)</td><td>Path(u, v) + 1 Modular squaring operations</td><td>IND-ST.</td></tr><tr><td>Atallah et al. [5]</td><td>2|E|<i>c</i><i>τ</i> + |V|<i>τ</i></td><td><i>τ</i></td><td>2 &middot; Path(u, v) + 1 operations: -Path(u, v) decryptions -Path(u, v) + 1 PRF eval</td><td>IND-ST.</td></tr></tbody></table>

In [18], De Capitani di Vimercati et al. proposed a data-outsourcing architecture which employs the HKAS in [5] for representing an authorization policy through an equivalent encryption policy. The positive results provided by the experimental analysis performed in [18], are encouraging in order to evaluate the feasibility of our approach. Indeed, as shown above the performance of our MLE-based construction in terms of space required to store public information and key derivation operations are similar to that exhibited by the HKAS in [5].

<footnote n="8">⁸ 1024-bit, 2048-bit, 3072-bit RSA keys are equivalent in strength to respectively, 80-bit, 112-bit, 128-bit symmetric keys.</footnote>
Only, the users need to manage a bigger number of secrets. Also, the verification procedure should not add significant overhead, indeed, it consists of computing the value of a collision resistant function (step 3(c) of the Ver Algorithm of Figure 2) at each step of derivation beside the decryption operation (step 3(b) of Der Algorithm of Figure 2).

# 7 Conclusions

In this paper we have introduced Verifiable HKAS and have designed it using an MLE scheme as a building block. The security properties of our construction depends on those of the underlying MLE scheme. The concrete instance described in Section 4.2 achieves the notions IND-ST and Strong-KC in the random oracle model. Our proposal also manages with the replacement of compromised encryption keys by making a limited number of changes to public and private information. We leave as an interesting open problem that of building VHKAS secure in the standard model. Our solution produces a scheme which belongs to the family of IKEKAS, it would also be interesting to consider other HKAS families identified in [15] to construct VHKAS and study their performance.

# Acknowledgements

The work of Ferrara and Ricciardi is partially supported by the project PON-ARS01 00860 titled *Ambient-intelligent Tele-monitoring and Telemetry for In-cepting and Catering over hUman Sustainability - ATTICUS* funded by the Italian Ministry of Education and Research - RNA/COR 576347.

# References

1. Abadi, M., Boneh, D., Mironov, I., Raghunathan, A., Segev, G.: Message-locked encryption for lock-dependent messages. In: Advances in Cryptology - CRYPTO 2013. Lecture Notes in Computer Science, vol. 8042, pp. 374–391. Springer (2013)

2. Akl, S.G., Taylor, P.D.: Cryptographic solution to a multilevel security problem. In: Advances in Cryptology: Proceedings of CRYPTO '82. pp. 237–249. Plenum Press, New York (1982)

3. Alderman, J., Farley, N., Crampton, J.: Tree-based cryptographic access control. In: ESORICS 2017 - 22nd European Symposium on Research in Computer Security. Lecture Notes in Computer Science, vol. 10492, pp. 47–64. Springer (2017)

4. Altaha, M., Muhajjar, R.: Lightweight key management scheme for hierarchical wireless sensor networks. pp. 139–147 (09 2017)

5. Atallah, M.J., Blanton, M., Fazio, N., Frikken, K.B.: Dynamic and efficient key management for access hierarchies. ACM Trans. Inf. Syst. Secur. 12(3), 18:1–18:43 (2009)

6. Ateniese, G., De Santis, A., Ferrara, A.L., Masucci, B.: Provably-secure time-bound hierarchical key assignment schemes. J. Cryptology 25(2), 243–270 (2012)

7. Bellare, M., Desai, A., Jokipii, E., Rogaway, P.: A concrete security treatment of symmetric encryption. In: FOCS 1997. pp. 394–403 (1997)
8. Bellare, M., Keelveedhi, S., Ristenpart, T.: Message-locked encryption and secure deduplication. In: EUROCRYPT 2013, Lecture Notes in Computer Science, vol. 7881, pp. 296–312. Springer (2013)

9. Berlato Stefano, Carbone Roberto, L.A.J., Silvio, R.: Exploring architectures for cryptographic access control enforcement in the cloud for fun and optimization. (ASIA CCS ’20) (2020)

10. Castiglione, A., De Santis, A., Masucci, B., Palmieri, F., Castiglione, A., Huang, X.: Cryptographic hierarchical access control for dynamic structures. IEEE Trans. Information Forensics and Security 11(10), 2349–2364 (2016)

11. Castiglione, A., De Santis, A., Masucci, B., Palmieri, F., Huang, X., Castiglione, A.: Supporting dynamic updates in storage clouds with the akl-taylor scheme. Inf. Sci. 387, 56–74 (2017)

12. Chang, C.C., Hwang, R.J., Wu, T.C.: Cryptographic key assignment scheme for access control in a hierarchy. Information Systems 17(3), 243 – 247 (1992)

13. Crampton, J., Daud, R., Martin, K.M.: Constructing key assignment schemes from chain partitions. In: Data and Applications Security and Privacy (IFIP). Lecture Notes in Computer Science, vol. 6166, pp. 130–145. Springer (2010)

14. Crampton, J., Farley, N., Gutin, G.Z., Jones, M., Poettering, B.: Cryptographic enforcement of information flow policies without public information. In: ACNS 2015. Lecture Notes in Computer Science, vol. 9092, pp. 389–408. Springer (2015)

15. Crampton, J., Martin, K.M., Wild, P.R.: On key assignment for hierarchical access control. In: 19th IEEE Computer Security Foundations Workshop, (CSFW-19 2006). pp. 98–111. IEEE Computer Society (2006)

16. D'Arco, P., De Santis, A., Ferrara, A.L., Masucci, B.: Variations on a theme by akl and taylor: Security and tradeoffs. Theor. Comput. Sci. 411(1), 213–227 (2010)

17. De Capitani di Vimercati, S., Foresti, S., Jajodia, S., Paraboschi, S., Samarati, P.: A data outsourcing architecture combining cryptography and access control. In: CSAW 2007. pp. 63–69. ACM (2007)

18. De Capitani di Vimercati, S., Foresti, S., Jajodia, S., Paraboschi, S., Samarati, P.: Encryption policies for regulating access to outsourced data. ACM Trans. Database Syst. 35(2), 12:1–12:46 (2010)

19. De Santis, A., Ferrara, A.L., Masucci, B.: New constructions for provably-secure time-bound hierarchical key assignment schemes. Theor. Comput. Sci. 407(1-3), 213–230 (2008)

20. De Santis, A., Ferrara, A.L., Masucci, B.: Efficient provably-secure hierarchical key assignment schemes. Theor. Comput. Sci. 412(41), 5684–5699 (2011)

21. Freire, E.S.V., Paterson, K.G.: Provably secure key assignment schemes from factoring. In: Parampalli, U., Hawkes, P. (eds.) ACISP 2011. Lecture Notes in Computer Science, vol. 6812, pp. 292–309. Springer (2011)

22. Freire, E.S.V., Paterson, K.G., Poettering, B.: Simple, efficient and strongly k-secure hierarchical key assignment schemes. In: Topics in Cryptology - CT-RSA 2013. vol. 7779, pp. 101–114. Springer (2013)

23. Zarandioon, S., Yao, D.D., Ganapathy, V.: K2C: cryptographic cloud storage with lazy revocation and anonymous access. In: 7th International ICST Conference, SecureComm 2011. g, vol. 96, pp. 59–76 (2011)

24. Zhu, W.T., Deng, R.H., Zhou, J., Bao, F.: Applying time-bound hierarchical key assignment in wireless sensor networks. In: 13th International Conference, ICICS 2011. vol. 7043, pp. 306–318 (2011)