# home / posts

## Another Look at Attribute-Based Group Homomorphic Encryption

In this post I expand upon the notions described in my paper "A Note on Attribute-Based Group Homomorphic Encryption" [1]. This post assumes that you have read and are familar with this paper. The same notation defined therein is used here.

The first thing I want to do is to rigorously define a function $\tau : \mathbb{A} \to \mathbb{F}$ that is used in one of my papers, the full version of [2], which is on arXiv, but is regrettably not properly defined in that paper. The function $\tau$ is needed by an abstraction called GIFT on which the characterization of IND-AD-CCA1 security in that paper relies. At the end of the post, I give an overview of this characterization and explain where $\tau$ fits in, but for now, I'm going to make an attempt at its proper definition.

## The Minimal Policy Associated with an Attribute

1. We can define a partial order $\preceq$ on the set of attributes $\mathbb{A}$ which follows from the attribute semilattice $(\mathbb{A}, \odot)$. $$a \preceq b := f(a) \implies f(b) \;\;\;\;\;\; \forall f \in \mathbb{F}.$$The following is an invariant: $a \preceq b \iff a \odot b = a$.
2. The minimal policy with respect to $a \in \mathbb{A}$ is the unique predicate $f \in \mathbb{F}$ satisfying
$$f(a) \land a \preceq a' \; \forall a' \in \mathsf{supp}(f).$$ We define the map $\tau : \mathbb{A} \to \mathbb{F}$ that maps an attribute $a$ to its minimal policy $f$.
3. The set of policies $\mathbb{F}$ is said to be complete iff $\tau$ is efficiently computable and $\tau(a)$ exists in $\mathbb{F}$ for all $a \in \mathbb{A}$.

So now we are equipped with what we need for the characterization of IND-AD-CCA1 security described at the end of the post, but for now, I'm going to elaborate a bit more on attribute semilattices.

# Attribute Semilattices

We now recall the equivalence relation $\sim$ that partitions the class of access policies $\mathbb{F}$ defined in Section 3.2 in [1]. The relation is defined thus $$f \sim g := \mathsf{supp}(f) \cap \mathsf{supp}(g) \neq \emptyset.$$ This relation induces a partition also on the set of attributes $\mathbb{A}$. Let $F_1, \ldots, F_n \subset \mathbb{F}$ be the equivalence classes in $\mathbb{F} / \sim$. Then let $A_1, \ldots, A_n \subset \mathbb{A}$ be the pairwise disjoint subsets of attributes in $\mathbb{A}$ that collectively form a partition of $\mathbb{A}$ where $A_i = \bigcup_{f \in F_i} \mathsf{supp}(f)$. Each $A_i$ has its own identity element, and therefore $(A_i, \odot)$ is a bounded semilattice. The directed graph corresponding to the Hasse diagram for the partial order $(\mathbb{A}, \preceq)$ has $n$ disconnected components. The supremum of $A_i$ is the identity element in $A_i$. Now in many cases, the partial orders $(A_i, \preceq)$ may be lattices i.e. they have a dual operation to $\odot$ and hence there is both a natural meet and join semilattice. This is the case for the example of the power set of a finite universe considered in Section 4.1 in [1]. The vector matching example in Section 4.2 in [1] is a special case of the power set example by choosing an appropriate representation. For example, the vector $(1, 0, 1)$ could be represented by the set of pairs $\{(1, 1), (2, 0), (3, 1)\}$ and an access policy associated with the pattern $(1, \ast, 1)$ is represented by the set $\{(1, 1), (3, 1)\}$ i.e. the pairs associated with wildcards in the pattern are excluded and hence, the latter set is a subset of the former. Then the $\odot$ operation naturally corresponds to set intersection. However this semilattice has no natural dual that is meaningful in the context of binary vector matching. Therefore, this attribute semilattice is not a lattice.

Another well-known example of a semilattice is the set of finite words over an alphabet ordered by prefix where $\odot$ is defined as returning the prefix common to two words which may in fact be the empty word $\epsilon$. This semilattice has a natural representation via sets akin to our representation for the previous example. An issue with this representation is that it permits sets corresponding to invalid attributes. For a binary alphabet, we define the set of representative sets associated with well-formed attributes as follows. Let $U = \{(i, b) \in [n] \times \{0, 1\}\}$ and define $V := \{W \subset U : (i, b) \in W \implies ((j, 0) \in W) \neq ((j, 1) \in W)\;\;\forall j \in [i], i \in [n], b \in \{0, 1\}\}$ (what is meant by $((j, 0) \in W) \neq ((j, 1) \in W)$ is that either $(j, 0)$ or $(j, 1)$ is in $W$ but not both - i.e. exclusive OR) . Now $V$ consists of the sets representing well-formed attributes, which are finite words in $\{w \in \{0, 1\}^\ast : |w| \leq n\}$. Recall that the policies match prefixes, so an attribute associated with a certain word matches a policy if it contains the prefix associated with that policy. The structure we have is a tree rooted at the empty string $\epsilon$. Every node corresponds to a minimal policy for the prefix obtained by the path from the root to that node. Every node is also associated with an attribute. The attribute at a node matches all policies on the path from the root to the node and the policy at a node matches all attributes at itself and its children. Now this semilattice is not bounded i.e. it does not have an identity element. But this makes it not suitable for ABGHE. We therefore have to add a logical identity element. Now if $\odot$ is defined as set intersection, a natural choice is the set $U$. While this is not a valid attribute ($U \notin V$), it can be assigned a special meaning in applications. By the transitivity property of $\sim$, it is easy to see that a single-rooted tree has a single identity element. If we exclude the empty string, the corresponding tree will have two disconnected components and there will be a partition of policies $\{F_0, F_1\}$ and of attributes $\{A_0, A_1\}$ where $A_0$ will have identity element $U \setminus \{(1, 1)\}$ and $A_1$ will have identity element $U \setminus \{(1, 0)\}$.

It is worth pointing out that we can define $a \odot a'$ as the attribute associated with the lowest common ancestor of the node associated with $a$ and the node associated with $a'$. For any node in the tree, the semilattice operation returns that node if the two operands are a node from its left subtree and a node from its right subtree (in any order). This is straightforward to define when we have such a tree structure.

This got me thinking about the general case; that is, for arbitrary semilattices, and wondering: is there a simple, equivalent graph-theoretic definition of the semilattice operation? Here is a simple definition that equivalently describes the semilattice operation from a graph theory viewpoint. Let $G$ be the directed graph corresponding to the Hasse diagram for the partial order induced by the semilattice operation. Now let $G'$ be the undirected version of $G$ obtained by replacing every directed edge with an undirected edge. Suppose we wish to compute $a \odot a'$ for attribute $a$ represented by vertex $v$ and attribute $a'$ represented by vertex $v'$. Then we can define $a \odot a'$ as the attribute associated with the vertex that intersects both a shortest path in $G'$ from $v$ to the inimum vertex and a shortest path in $G'$ from $v'$ to the infimum vertex and whose distance is greatest from the infimum vertex. Note that there may be more than one "shortest" path (hence, the slightly ambiguous wording) i.e. there may be several equal-length paths whose length is minimal, which we refer to as "shortest".

Initially I was going to, at this point, talk a bit about vector encodings for inner product predicates (which could realize the above semilattice in a scheme such as KSW [3] for example) but I have decided to defer a discussion on these encodings to a later post.

With the definition of $\tau$ above under our belt, we can proceed to an overview of the characterization of IND-AD-CCA1 security from my paper on arXiv.

Before we proceed, we first recall some concepts from abstract algebra that the reader may or may not be familiar with.

4. A normal subgroup $N \subseteq G$ of a group $G$ satisfies the property that for all $n \in N$, it holds that $$g n g^{-1} \in N\;\;\;\forall g \in G.$$ In other words, $N$ remains invariant under conjugation.

It is precisely the normal subgroups (and no other subgroups) that can be used to construct quotient groups. All subgroups of an abelian group are normal. THe ABGHE schemes we mostly make reference to associate an ableian group of ciphertexts with every policy and all subgroups thereof are therefore normal.

5. Let $f \in \mathbb{F}$ be policy and $\mathcal{C}_f \subset \hat{\mathcal{C}}$ be a subgroup of the ciphertext space associated with $f$. Furthermore, let $\mathcal{N}_f \subset \mathcal{C}_f$ be a normal subgroup of $\mathcal{C}_f$. Then a set of representatives $\mathcal{R}_f \subset \mathcal{C}_f$ is a set of ciphertexts where each one is a unique representative of an equivalence class in the quotient group $\mathcal{C}_f / \mathcal{N}_f$. For every $r \in \mathcal{R}_f$, the corresponding equivalence class is $\{rn \in \mathcal{C}_f : n \in \mathcal{N}_f\}$.

I'm now going to discuss an abstraction that is defined in [4] for the public-key setting and an informal description is provided in the full version on arXiv of [2] in the context of predicate encryption, but that treatment is relevent for the attribute-based setting since no use is made of attribute privacy. The abstraction is called GIFT (Generic shIFT-Type) from Defintion 3 in [4]. I'm going to repeat the informal description from the full version of my Africacrypt 2013 paper, specifically generalizing to the attribute-based setting and correcting for any small variations in notation. As an aside, I'm not too happy with Appendix A of my paper on arXiv - the writing is densely-packed and no space is afforded to intuitions and gentle discussion. So now let us discuss the properties of a GIFT scheme in the context of ABGHE. We list each of the requirements as follows:

• The set of policies $\mathbb{F}$ is complete as per Definition 3.
• The public parameters $\mathsf{PP}$ contains information to determine a non-trivial, proper normal subgroup $\mathcal{N}_f$ of every group $\mathcal{C}_f$. Intuitively, $\mathcal{N}_f$ consists of the honest encryptions of the identity element of the message space $\mathcal{M}$ (say zero) under attribute $a$, the unique attribute such that $\tau(a) = f$.
• It holds that for every $f, g \in \mathbb{F}$, the systems of representatives $\mathcal{R}_f = \mathcal{C}_f / \mathcal{N}_f$ and $\mathcal{R}_g = \mathcal{C}_g / \mathcal{N}_g$ have the same cardinality; that is, $|\mathcal{R}_f| = |\mathcal{R}_g|$.
• $\mathsf{PP}$ contains an efficient function $\psi : \mathbb{F} \times \mathcal{M} \to \hat{\mathcal{C}}$ with the property that $\psi_f = \psi(f, \cdot)$ for any $f \in \mathbb{F}$ is an isomorphism between $\mathcal{M}$ and $\mathcal{R}_f$.
• To encrypt a message $m \in \mathcal{M}$ under attribute $a \in \mathbb{A}$, perform the following steps:
1. compute $f \gets \tau(a)$.