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
$\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$.
$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$.
$\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.
Characterization of IND-AD-CCA1 Security
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.
$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.
$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:- compute
$f \gets \tau(a)$. - choose a random
$n \stackrel{\$}{\gets} \mathcal{N}_f$. - output ciphertext
$\psi_f(m) \ast n \in \mathcal{C}_f$.
- compute
- A secret key for policy
$f \in \mathbb{F}$contains an efficient description of$\psi_f^{-1} \circ \mu_f$where$\mu_f : \hat{\mathcal{C}}_f \to \mathcal{R}_f$such that$r = \mu_f(c)$is the unique representative with$c = r \ast n$where$n \in \mathcal{N}_f$.
The next thing we want to do is to identify conditions for a GIFT scheme to satisfy IND-AD-CCA1 security. Theorem 3 in the full version of my Africacrypt paper on arXiv shows that a GIFT ABGHE scheme is IND-AD-CCA1 secure if and only if a problem called ISOAP is hard. So what is this ISOAP problem?
ISOAP (Interactive Splitting Oracle-Assisted (Subgroup Membership) Problem) is a subgroup membership problem with access to a splitting oracle, which we will define momentarily. The goal is to determine whether an element $c \in \mathcal{C}_f$ is a member of $\mathcal{N}_f \subset \mathcal{C}_f$. Queries can be made to the splitting oracle before the challenge is received. A splitting oracle for a group $\mathcal{C}_f$ with normal subgroup $\mathcal{N}_f$ answers with $(r, n)$ when queried with an element $c \in \mathcal{C}_f$ such that $c = r \ast n$. In fact, it is sufficient for the oracle to return $r$ since $n$ is trivially obtained by computing $c \ast r^{-1}$. The splitting oracle corresponds to the decryption oracle in the IND-AD-CCA1 security game where the target attribute is $a \in \mathbb{A}$ and we have that $f = \tau(a) \in \mathbb{F}$. Theorem 3 in the full version of my paper on arXiv shows that the hardness of ISOAP and IND-AD-CCA1 security are equivalent for a GIFT PE scheme, but since the proof does not rely on attribute privacy, the equivalence also holds for a GIFT ABGHE scheme. KSW [3] is an example of a GIFT ABGHE scheme with respect to several attribute semilattices and classes of policies such as those discussed above and in [1], but it has not been shown (to the best of our knowledge) to be CCA1 secure.
References
- A Note on Attribute-Based Group Homomorphic Encryption.Michael Clear and Ciaran McGoldrick. Cryptology ePrint Archive, Report 2017/752. 2017.
- Homomorphic Encryption with Access Policies: Characterization and New Constructions. Michael Clear, Arthur Hughes and Hitesh Tewari. AFRICACRYPT. 2013.
- Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products.. Jonathan Katz, Amit Sahai and Brent Waters. EUROCRYPT. 2008.
- Group homomorphic encryption: characterizations, impossibility results, and applications.. Frederik Armknecht, Stefan Katzenbeisser and Andreas Peter. Des. Codes Cryptogr.. 2013.