\documentclass[a4]{seminar}

\usepackage{jason}
\usepackage{color}
\usepackage{sem-a4}
\usepackage{slidesec}
\usepackage{fancybox}
\usepackage{fancyhdr}
\input{seminar.bug}
\usepackage{multirow}

\pagestyle{empty}
\newcommand{\slidetitle}[1]{\large\textbf{#1}\normalsize}
\newcommand{\red}[1]{\begin{color}{red}#1\end{color}}

\renewcommand{\makeslideheading}[1]{\raggedright \textcolor{blue}{\large\textbf{#1}}}


\newcommand{\mkK}{\ensuremath{\mathsf{makeKeys}}}
\newcommand{\mkS}{\ensuremath{\mathsf{makeSecrets}}}
\newcommand{\mkP}{\ensuremath{\mathsf{makePublicData}}}
\newcommand{\getK}{\ensuremath{\mathsf{getKey}}}

\newcommand{\vbls}{\vspace*{\baselineskip}}

\newcommand{\authors}{Jason Crampton~$\cdot$~Keith Martin~$\cdot$~Peter Wild}

\sloppy
\autoslidemarginstrue

\slideframe{none}
%\centerslidesfalse

\pagestyle{empty}


\begin{document}

\begin{slide}

\vspace*{\stretch{1}}

{\bf \large {\textcolor{blue}{On Key Assignment for\\ Hierarchical Access Control}}}

\vspace*{\stretch{.15}}

{\bf \authors}\\[-18pt]

\small{Information Security Group, Royal Holloway, University of London}

\vspace*{\stretch{1}}

\end{slide}

%---------------------------
\newpagestyle{mypagestyle}%
    {\tiny{On Key Assignment for Hierarchical Access Control/\theslideheading\hfil}}
    {\tiny{CSFW 2006}\hfil \authors}

\slidepagestyle{mypagestyle}
%---------------------------

\begin{slide}
\slideheading[Introduction]{What is hierarchical access control?}

Assume the existence of a set of users $U$ and a set of objects $O$

Assume the existence of a partially ordered set $(X,\leqslant)$ and a function $\lambda : U \cup O \rightarrow X$
  \begin{itemize}
    \item $X$ associates each entity $e$ with a security label $\lambda(e)$
    \item $u \in U$ may access $o \in O$ if $\lambda(u) \geqslant \lambda(o)$
      \begin{itemize}
        \item Sometimes known as the \emph{simple security property}
        \item Cornerstone of many military security policies
      \end{itemize}
  \end{itemize}
\end{slide}

\begin{slide}
\slideheading[Introduction]{Example}

$X = \set{{\tt unclassified},{\tt classified},{\tt secret},{\tt top\ secret}}$
  \begin{itemize}
    \item ${\tt unclassified} < {\tt classified} < {\tt secret} < {\tt top\ secret}$
    \item $\lambda(\mathit{george}) = {\tt top\ secret}$, $\lambda(\mathit{jason}) = {\tt classified}$
    \item \textit{george} can access any object
    \item \textit{jason} can access any {\tt unclassified} or {\tt classified} object
  \end{itemize}
\end{slide}

\begin{slide}
\slideheading[Introduction]{What is a key assignment scheme?}

The simple security property can be enforced by encrypting objects and supplying users with appropriate keys
  \begin{itemize}
    \item Give \textit{george} $k_u$, $k_c$, $k_s$ and $k_t$
    \item Give \textit{jason} $k_u$ and $k_c$
  \end{itemize}

\textit{george} has to maintain a number of different keys -- can we do better?
\end{slide}

\begin{slide}
\slideheading[Introduction]{A simple scheme}

Use some symmetric encryption algorithm to derive lower keys from their respective security labels
  \begin{itemize}
    \item Choose $k_t$ and define
      \begin{itemize}
        \item $k_s = E_{k_t}(``{\tt secret}")$
        \item $k_c = E_{k_s}(``{\tt classified}")$
        \item $k_u = E_{k_c}(``{\tt unclassified}")$
      \end{itemize}
    \item Give \textit{george} $k_t$ and \textit{jason} $k_c$
      \begin{itemize}
        \item \textit{george} can decrypt any key using his key
        \item \textit{jason} can decrypt $k_u$ using his key, but cannot (feasibly) compute $k_s$ or $k_t$
      \end{itemize}
   \end{itemize}
\end{slide}

\begin{comment}
\begin{slide}
\slideheading[Introduction]{Key encrypting scheme}

Choose keys $k_u$, $k_c$, $k_s$ and $k_t$ as before
  \begin{itemize}
    \item Publish $E_{k_t}(k_s)$, $E_{k_s}(k_c)$, and $E_{k_c}(k_u)$
    \item Give \textit{george} $k_t$ and \textit{jason} $k_c$
      \begin{itemize}
        \item \textit{george} can decrypt any key using his key
        \item \textit{jason} can decrypt $k_u$ using his key, but cannot (feasibly) compute $k_s$ or $k_t$
      \end{itemize}
  \end{itemize}
\end{slide}

\begin{slide}
\slideheading[Introduction]{Key encrypting scheme for trees}

Partially ordered set $(X,\leqslant)$ is defined by reflexive, anti-symmetric, transitive, binary relation on $X$
  \begin{itemize}
    \item \emph{Hasse diagram} is graph of reflexive, transitive reduction of $\leqslant$
  \end{itemize}

If (Hasse diagram of) $X$ is a tree then
  \begin{itemize}
    \item Publish $\set{E_{\kappa(x)}(\kappa(y)) : y \lessdot x}$
    \item For any $x,y \in X$ such that $y \leqslant x$, there exists a unique path $y = z_0 \lessdot z_1 \lessdot \dots \lessdot z_n = x$
    \item If user has security label $x$ she can derive $\kappa(y)$ by obtaining the keys $\kappa(z_{n-1}),\dots,\kappa(z_0)$
  \end{itemize}
\end{slide}

\begin{slide}
\slideheading[Introduction]{Example}

Publish $\set{E_{k_1}(k_2),E_{k_1}(k_3),E_{k_2}(k_4), E_{k_2}(k_5),E_{k_3}(k_6)}$

\begin{minipage}[b][.4\textheight][t]{.45\textwidth}
To derive $k_5$ from $k_1$
  \begin{itemize}
    \item decrypt $k_2$ (using $k_1$)
    \item decrypt $k_5$ (using $k_2$)
  \end{itemize}
\end{minipage}
\hfill
\begin{minipage}[t][.4\textheight][t]{.45\textwidth}\centering\setlength{\unitlength}{\textwidth/160}
  \begin{picture}(160,100)(-80,-10)
      \node{t}{-80}{0}{$x_4$}
          \drawline(-80,0)(-40,40)
      \node{t}{0}{0}{$x_5$}
          \drawline(0,0)(-40,40) %\drawline(0,0)(40,40)
      \node{t}{80}{0}{$x_6$}
          \drawline(80,0)(40,40)
      \node{b}{-40}{40}{$x_2$}
          \drawline(-40,40)(0,80)
      \node{b}{40}{40}{$x_3$}
          \drawline(40,40)(0,80)
      \node{b}{0}{80}{$x_1$}
  \end{picture}
\end{minipage}

\vspace*{\baselineskip}

\end{slide}
\end{comment}

\begin{comment}
\begin{slide}
\slideheading[Introduction]{Extending the scheme to trees}

Partially ordered set $(X,\leqslant)$ is defined by reflexive, anti-symmetric, transitive, binary relation on $X$
  \begin{itemize}
    \item \emph{Hasse diagram} is graph of reflexive, transitive reduction of $\leqslant$
  \end{itemize}

If (Hasse diagram of) $X$ is a tree then
  \begin{itemize}
    \item For all $x,y \in X$, $y \lessdot x$ define $k(y) = E_{k(x)}(y)$
    \item For any $x,y \in X$ such that $y \leqslant x$, there exists a unique path $y = z_0 \lessdot z_1 \lessdot \dots \lessdot z_n = x$
    \item If user has security label $x$ she can derive $k(y)$ by obtaining the keys $k(z_{n-1}),\dots,k(z_0)$
  \end{itemize}
\end{slide}
\end{comment}

\begin{slide}
\slideheading[Introduction]{Example}

$k_2 = E_{k_1}(x_2),k_3 = E_{k_1}(x_3), k_4 = E_{k_2}(x_4), k_5 = E_{k_2}(x_5), k_6 = E_{k_3}(x_6)$

\vbls

\begin{minipage}[b][.4\textheight][t]{.45\textwidth}
To derive $k_5$ from $k_1$
  \begin{itemize}
    \item compute $E_{k_1}(x_2)$
    \item compute $E_{k_2}(x_5)$
  \end{itemize}
\end{minipage}
\hfill
\begin{minipage}[t][.4\textheight][t]{.45\textwidth}\centering\setlength{\unitlength}{\textwidth/160}
  \begin{picture}(160,100)(-80,-10)
      \node{t}{-80}{0}{$x_4$}
          \drawline(-80,0)(-40,40)
      \node{t}{0}{0}{$x_5$}
          \drawline(0,0)(-40,40) %\drawline(0,0)(40,40)
      \node{t}{80}{0}{$x_6$}
          \drawline(80,0)(40,40)
      \node{b}{-40}{40}{$x_2$}
          \drawline(-40,40)(0,80)
      \node{b}{40}{40}{$x_3$}
          \drawline(40,40)(0,80)
      \node{b}{0}{80}{$x_1$}
  \end{picture}
\end{minipage}

\vspace*{\baselineskip}

\end{slide}
\begin{slide}
\slideheading[Introduction]{Motivation}

\vspace*{\baselineskip}

\begin{minipage}[b][.4\textheight][t]{.45\textwidth}
\begin{itemize}
  \item How do we handle arbitrary posets?
  \item There is not a unique path from $x_1$ to $x_5$
\end{itemize}
\end{minipage}
\hfill
\begin{minipage}[b][.4\textheight][t]{.45\textwidth}\centering\setlength{\unitlength}{\textwidth/160}
  \begin{picture}(160,100)(-80,-10)
      \node{t}{-80}{0}{$x_4$}
          \drawline(-80,0)(-40,40)
      \node{t}{0}{0}{$x_5$}
          \drawline(0,0)(-40,40) \drawline(0,0)(40,40)
      \node{t}{80}{0}{$x_6$}
          \drawline(80,0)(40,40)
      \node{b}{-40}{40}{$x_2$}
          \drawline(-40,40)(0,80)
      \node{b}{40}{40}{$x_3$}
          \drawline(40,40)(0,80)
      \node{b}{0}{80}{$x_1$}
  \end{picture}
\end{minipage}

\vspace*{\baselineskip}

\end{slide}

\begin{slide}
\slideheading[Introduction]{Motivation}

There are many schemes in the literature
  \begin{itemize}
    \item Rely on specific cryptographic primitives
    \item Do not consider basic requirements and features of key assignment schemes
  \end{itemize}

We want to develop an abstract approach to key assignment schemes
  \begin{itemize}
    \item Classify existing schemes
    \item Evaluate the respective merits of different types of scheme
  \end{itemize}

\end{slide}

\begin{slide}
\slideheading[Introduction]{Structure of talk}

\begin{itemize}
  \item Key assignment schemes for arbitrary posets
  \item The Akl-Taylor scheme
  \item Simplifying the Akl-Taylor scheme
  \item A hybrid key assignment scheme
\end{itemize}
\end{slide}

\begin{slide}

\slideheading{Key assignment schemes}

\end{slide}

\begin{slide}
\slideheading[Key assignment schemes]{Basic concepts}

We assume the existence of a scheme administrator (trusted centre)

A key assignment scheme comprises four algorithms
  \begin{itemize}
    \item \mkK\ returns a labelled set of encryption keys $(\kappa(x): x \in X)$
    \item \mkS\ returns a labelled set of secret values $(\sigma(x): x \in X)$
    \item \mkP\ returns a set of data $Pub$ that is made public by the trusted centre
    \item \getK\ takes $x,y \in X$, $\sigma(x)$ and $Pub$ and returns $\kappa(y)$ whenever $y \leqslant x$
  \end{itemize}

A scheme has \emph{independent keys} if the keys can be chosen independently of each other and $Pub$
\end{slide}

\begin{slide}
\slideheading[Key assignment schemes]{Benchmarks}

\begin{itemize}
  \item Amount of secret data that needs to be distributed to and stored by end users
  \item Amount of data that needs to be made public
  \item Complexity of key derivation
  \item Complexity of key update (if user leaves or key is compromised)
  \item Key independency
\end{itemize}

\end{slide}

\begin{slide}
\slideheading[Key assignment schemes]{Trivial key assignment scheme}

\vbls

\begin{minipage}[t][.75\textheight][t]{.55\textwidth}\raggedright
\begin{itemize}
  \item Independent keys $\kappa(X)$
  \item $\sigma(x) = (\kappa(y) : y \leqslant x)$
  \item $Pub = \emptyset$
  \item $\kappa(y) \in \sigma(x)$ so key derivation is trivial
\end{itemize}
\end{minipage}
\hfill
\begin{minipage}[t][.75\textheight][t]{.4\textwidth}\setlength{\unitlength}{\textwidth/160}
%
$\sigma_2 = \set{\kappa_2,\kappa_4,\kappa_5}$

\vbls

  \begin{picture}(160,100)(-80,-10)
      \node{t}{-80}{0}{$x_4$}
          \drawline(-80,0)(-40,40)
      \node{t}{0}{0}{$x_5$}
          \drawline(0,0)(-40,40) \drawline(0,0)(40,40)
      \node{t}{80}{0}{$x_6$}
          \drawline(80,0)(40,40)
      \node{b}{-40}{40}{$x_2$}
          \drawline(-40,40)(0,80)
      \node{b}{40}{40}{$x_3$}
          \drawline(40,40)(0,80)
      \node{b}{0}{80}{$x_1$}
  \end{picture}
\end{minipage}

\end{slide}

\begin{slide}
\slideheading[Key assignment schemes]{Trivial key assignment scheme}

\vbls

\begin{minipage}[t][.75\textheight]{.55\textwidth}\raggedright
\begin{itemize}
  \item Independent keys $\kappa(X)$
  \item $\sigma(x) = (\kappa(y) : y \leqslant x)$
  \item $Pub = \emptyset$
  \item $\kappa(y) \in \sigma(x)$ so key derivation is trivial
\end{itemize}
\end{minipage}
\hfill
\begin{minipage}[t][.75\textheight]{.4\textwidth}\raggedright
\begin{itemize}
  \item \textcolor{red}{High private storage costs}
  \item \textcolor{green}{No public storage}
  \item \textcolor{red}{High update costs for private data}
\end{itemize}
\end{minipage}
\end{slide}

\begin{slide}
\slideheading[Key assignment schemes]{Trivial key encrypting key assignment scheme}

\vbls

\begin{minipage}[t][.75\textheight][t]{.55\textwidth}\raggedright
\begin{itemize}
  \item Independent keys $\kappa(X)$ and set of key encrypting keys $K(X)$
  \item $\sigma(x) = (K(y) : y \leqslant x)$
  \item $Pub = (E_{K(x)}(\kappa(x)): x \in X)$
  \item $\kappa(y)$ is obtained by decrypting $E_{K(y)}(\kappa(y)) \in Pub$ using $K(y) \in \sigma(x)$
\end{itemize}
\end{minipage}
\hfill
\begin{minipage}[t][.75\textheight][t]{.4\textwidth}\setlength{\unitlength}{\textwidth/160}
%
\mbox{$\sigma_2 = \set{K_2,K_4,K_5}$}\\
\mbox{$Pub = \set{E_{K_1}(\kappa_1), E_{K_2}(\kappa_2),\dots}$}

\vbls

  \begin{picture}(160,100)(-80,-10)
      \node{t}{-80}{0}{$x_4$}
          \drawline(-80,0)(-40,40)
      \node{t}{0}{0}{$x_5$}
          \drawline(0,0)(-40,40) \drawline(0,0)(40,40)
      \node{t}{80}{0}{$x_6$}
          \drawline(80,0)(40,40)
      \node{b}{-40}{40}{$x_2$}
          \drawline(-40,40)(0,80)
      \node{b}{40}{40}{$x_3$}
          \drawline(40,40)(0,80)
      \node{b}{0}{80}{$x_1$}
  \end{picture}
\end{minipage}

\end{slide}

\begin{slide}
\slideheading[Key assignment schemes]{Trivial key encrypting key assignment scheme}

\vbls

\begin{minipage}[t][.75\textheight]{.55\textwidth}\raggedright
\begin{itemize}
  \item Independent keys $\kappa(X)$ and set of key encrypting keys $K(X)$
  \item $\sigma(x) = (K(y) : y \leqslant x)$
  \item $Pub = (E_{K(x)}(\kappa(x)): x \in X)$
  \item $\kappa(y)$ is obtained by decrypting $E_{K(y)}(\kappa(y)) \in Pub$ using $K(y) \in \sigma(x)$
\end{itemize}
\end{minipage}
\hfill
\begin{minipage}[t][.75\textheight]{.4\textwidth}\raggedright
\begin{itemize}
  \item \textcolor{red}{High private storage costs}
  \item \textcolor{red}{High public storage costs}
  \item \textcolor{green}{Very low costs for update of $\kappa(y)$}
  \item \textcolor{red}{High costs for update of $K(y)$}
\end{itemize}
\end{minipage}

\end{slide}

\begin{slide}
\slideheading[Key assignment schemes]{Direct key encrypting key assignment scheme}

\vbls

\begin{minipage}[t][.75\textheight]{.55\textwidth}\raggedright
\begin{itemize}
  \item Independent keys $\kappa(X)$
  \item $\sigma(x) = \kappa(x)$
  \item $Pub = (E_{\kappa(x)}(\kappa(y)): y < x)$
  \item $\kappa(y)$ is obtained by decrypting $E_{\kappa(x)}(\kappa(y)) \in Pub$ using $\kappa(x)$
\end{itemize}
\end{minipage}
\hfill
\begin{minipage}[t][.75\textheight]{.4\textwidth}\raggedright\setlength{\unitlength}{\textwidth/160}
\mbox{$Pub = \set{E_{\kappa_1}(\kappa_2), E_{\kappa_1}(\kappa_4),\dots}$}

\vbls

  \begin{picture}(160,100)(-80,-10)
      \node{t}{-80}{0}{$x_4$}
          \drawline(-80,0)(-40,40)
      \node{t}{0}{0}{$x_5$}
          \drawline(0,0)(-40,40) \drawline(0,0)(40,40)
      \node{t}{80}{0}{$x_6$}
          \drawline(80,0)(40,40)
      \node{b}{-40}{40}{$x_2$}
          \drawline(-40,40)(0,80)
      \node{b}{40}{40}{$x_3$}
          \drawline(40,40)(0,80)
      \node{b}{0}{80}{$x_1$}
  \end{picture}
\end{minipage}

\end{slide}

\begin{slide}
\slideheading[Key assignment schemes]{Direct key encrypting key assignment scheme}

\vbls

\begin{minipage}[t][.75\textheight]{.55\textwidth}\raggedright
\begin{itemize}
  \item Independent keys $\kappa(X)$
  \item $\sigma(x) = \kappa(x)$
  \item $Pub = (E_{\kappa(x)}(\kappa(y)): y < x)$
  \item $\kappa(y)$ is obtained by decrypting $E_{\kappa(x)}(\kappa(y)) \in Pub$ using $\kappa(x)$
\end{itemize}
\end{minipage}
\hfill
\begin{minipage}[t][.75\textheight]{.4\textwidth}\raggedright
\begin{itemize}
  \item \textcolor{green}{Minimizes private storage costs}
  \item \textcolor{red}{High public storage costs}
  \item Moderate costs for update of private and public data
\end{itemize}
\end{minipage}

\end{slide}

\begin{slide}
\slideheading[Key assignment schemes]{Iterative key encrypting key assignment scheme}

\vbls

\begin{minipage}[t][.75\textheight]{.55\textwidth}\raggedright
\begin{itemize}
  \item Independent keys $\kappa(X)$
  \item $\sigma(x) = \kappa(x)$
  \item $Pub = (E_{\kappa(x)}(\kappa(y)): y \lessdot x)$
  \item $\kappa(y)$ is obtained by decrypting $\kappa(z)$ for all $z$ on a path from $x$ to~$y$
\end{itemize}
\end{minipage}
\hfill
\begin{minipage}[t][.75\textheight]{.4\textwidth}\raggedright\setlength{\unitlength}{\textwidth/160}
\mbox{$Pub = \set{E_{\kappa_1}(\kappa_2), E_{\kappa_2}(\kappa_4),\dots}$}

\vbls

  \begin{picture}(160,100)(-80,-10)
      \node{t}{-80}{0}{$x_4$}
          \drawline(-80,0)(-40,40)
      \node{t}{0}{0}{$x_5$}
          \drawline(0,0)(-40,40) \drawline(0,0)(40,40)
      \node{t}{80}{0}{$x_6$}
          \drawline(80,0)(40,40)
      \node{b}{-40}{40}{$x_2$}
          \drawline(-40,40)(0,80)
      \node{b}{40}{40}{$x_3$}
          \drawline(40,40)(0,80)
      \node{b}{0}{80}{$x_1$}
  \end{picture}
\end{minipage}

\end{slide}

\begin{slide}
\slideheading[Key assignment schemes]{Iterative key encrypting key assignment scheme}

\vbls

\begin{minipage}[t][.75\textheight]{.55\textwidth}\raggedright
\begin{itemize}
  \item Independent keys $\kappa(X)$
  \item $\sigma(x) = \kappa(x)$
  \item $Pub = (E_{\kappa(x)}(\kappa(y)): y \lessdot x)$
  \item $\kappa(y)$ is obtained by decrypting $\kappa(z)$ for all $z$ on a path from $x$ to~$y$
\end{itemize}
\end{minipage}
\hfill
\begin{minipage}[t][.75\textheight]{.4\textwidth}\raggedright
\begin{itemize}
  \item \textcolor{green}{Minimizes private storage costs}
  \item \textcolor{green}{Minimizes public storage costs}
  \item Moderate costs for update of private and public data
  \item \textcolor{red}{Key derivation is iterative}
\end{itemize}
\end{minipage}

\end{slide}

\begin{slide}
\slideheading[Key assignment schemes]{IKEKAS example}

Atallah, Frikken and Blanton (\emph{CCS} 2005)

\begin{itemize}
  \item $Pub = \set{\kappa(y) - h(\kappa(x),y) : y \lessdot x}$, $h$ is a hash function
  \item User with security label $x$ can recover $\kappa(y)$ by computing $h(\kappa(x),y)$
\end{itemize}

All the schemes we have considered thus far make use of the order relation or the covering relation
  \begin{itemize}
    \item Collectively, we call these schemes \emph{edge-based}
  \end{itemize}

\end{slide}

\begin{slide}
\slideheading[Key assignment schemes]{Node-based key assignment scheme}

\begin{itemize}
  \item $Pub \supseteq (e(x) : x \in X)$
  \item $\kappa(x) = f(e(x))$
    \begin{itemize}
      \item $f$ is a secret function
      \item There exists a public algorithm $g$ such that
          \[
            g(f(e(x)),e(x),e(y)) = g(\kappa(x),e(x),e(y)) = \kappa(y)
          \]
           for all $y \leqslant x$
    \end{itemize}
  \item By construction $\kappa(y)$ can be derived (directly) from $\kappa(x)$ (using $g$)
  \item Dependent keys ($\kappa(x) = f(e(x))$)
\end{itemize}

\end{slide}

\begin{slide}
\slideheading[Key assignment schemes]{Summary}


\newlength{\mylength}
\newlength{\mylengtha}
\newlength{\mylengthb}
\newlength{\mylengthc}
\settowidth{\mylength}{\bf Storage requirements}
\settowidth{\mylengtha}{derivation}
\settowidth{\mylengthb}{independent}
\settowidth{\mylengthc}{\bf update}

\vbls

\begin{center}
  \begin{tabular}{|l|c|c|r|r|}
    \hline
      \multirow{2}{*}{\bf Scheme} & \multicolumn{2}{c|}{\bf Storage}  & \multicolumn{2}{c|}{\bf Update $\kappa(x)$}\\
    \cline{2-5}
                                                                & \bf Private & \bf Public & \bf Private & \bf Public \\
    \hline
      TKAS & $|\dset{x}|$ & $0$ & $|\uset{(\dset{x})}|$ & $0$\\
      TKEKAS & $|\dset{x}|$ & $m$ & $|\uset{(\dset{x})}|$ & $|\uset{(\dset{x})}|$\\
      DKEKAS & $1$ & $e$ & $|\dset{x}|$ & $|\uset{x}| + |\dset{x}|$ \\
      IKEKAS & $1$ & $c$ & $|\dset{x}|$ & $|\dset{x}|$ \\
      NBKAS & $1$ & $m$ & ? & ? \\
    \hline
  \end{tabular}
\end{center}

\begin{alignat*}{3}
  \dset{x} &= \set{y \in X: y \leqslant x} &\qquad \uset{x} &= \set{y \in X: y \geqslant x} &\qquad m &= |X|  \\
  e &= |\set{(y,x) : y \leqslant x}| & c &= |\set{(y,x) : y \lessdot x}|
\end{alignat*}

\end{slide}

\begin{slide}
\slideheading[Key assignment schemes]{Summary}

\begin{minipage}[t]{.48\textwidth}\raggedright
We surveyed about 30 papers in the literature
  \begin{itemize}
    \item 2 are TKAS
    \item 3 are TKEKAS
    \item 2 are DKEKAS
    \item 7 are IKEKAS
    \item 12 are NBKAS
    \item A couple of weird hybrids
  \end{itemize}
Often clumsy and almost always over-complicated
\end{minipage}
\hfill
\begin{minipage}[t]{.48\textwidth}\raggedright
Wide variety of cryptographic and mathematical techniques
  \begin{itemize}
    \item RSA
    \item Rabin cryptosystem
    \item Polynomial interpolation
    \item Chinese remainder theorem
    \item Discrete logs
    \item Sibling intractable function families
    \item Hash functions with collisions
  \end{itemize}
\end{minipage}

\end{slide}

\begin{slide}
\slideheading[Key assignment schemes]{An example from the literature}

\begin{itemize}
  \item Independent keys $\kappa(X)$
  \item Each $x \in X$ is also associated with a public-private key pair
    \begin{itemize}
      \item Private key is a pair of large primes $(p(x),q(x))$
      \item Public key is $(d(x),n(x))$, where $n(x) = p(x)q(x)$
    \end{itemize}
  \item $\sigma(x)= (y,p(y),q(y) : y \leqslant x)$
  \item $Pub = (d(x) : x \in X) \cup (n(x) : x \in X) \cup ((\kappa(x) \parallel x)((\kappa(x) \parallel x)  + d(x))) \mod n(x) : x \in X)$
\end{itemize}

\textcolor{white}{This is nothing more than a trivial key encrypting scheme based on the Rabin cryptosystem}

%  \begin{itemize}
%    \item A symmetric encryption algorithm is perfectly adequate
%    \item Symmetric keys are far smaller
%  \end{itemize}

\end{slide}

\begin{slide}
\slideheading[Key assignment schemes]{An example from the literature}

\begin{itemize}
  \item Independent keys $\kappa(X)$
  \item Each $x \in X$ is also associated with a public-private key pair
    \begin{itemize}
      \item Private key is a pair of large primes $(p(x),q(x))$
      \item Public key is $(d(x),n(x))$, where $n(x) = p(x)q(x)$
    \end{itemize}
  \item $\sigma(x)= (y,p(y),q(y) : y \leqslant x)$
  \item $Pub = (d(x) : x \in X) \cup (n(x) : x \in X) \cup ((\kappa(x) \parallel x)((\kappa(x) \parallel x)  + d(x))) \mod n(x) : x \in X)$
\end{itemize}

This is nothing more than a trivial key encrypting scheme based on the Rabin cryptosystem

%  \begin{itemize}
%    \item A symmetric encryption algorithm is perfectly adequate
%    \item Symmetric keys are far smaller
%  \end{itemize}

\end{slide}

\begin{slide}
\slideheading{The Akl-Taylor scheme}
\end{slide}

\begin{slide}
\slideheading[The Akl-Taylor scheme]{Introduction}

Akl and Taylor (\emph{ACM Trans. Comp. Sys.}, 1983)

\begin{itemize}
  \item $Pub = \set{n} \cup (e(x) : x \in X)$
    \begin{itemize}
      \item $n = pq$, $p$ and $q$ are large primes
      \item $e(x) \mid e(y)$ if and only if $y \leqslant x$
    \end{itemize}
  \item $\kappa(x) = s^{e(x)} \mod n$, $s \in \mathbb{Z}^*_n$
  \item Note that $(s^{e(x)})^{\frac{e(y)}{e(x)}} = s^{e(y)}$
    \begin{itemize}
      \item Hence $\kappa(y) = \left(\kappa(x)\right)^{\frac{e(y)}{e(x)}}$
      \item It is only feasible to compute $\kappa(y)$ if $y \leqslant x$
    \end{itemize}
\end{itemize}

Policy enforcement relies on the assumption that it is difficult to compute integral roots modulo $n$ (where $n$ is composite) and the choice of $e$

\end{slide}

\begin{slide}
\slideheading[The Akl-Taylor scheme]{Choosing public parameters}

It can be shown that particular choices of $e(x)$ are good
  \begin{itemize}
    \item It is not possible for any set of users to obtain a key that one of them couldn't already obtain
    \item See paper for details about resistance to collusion attacks
  \end{itemize}

\begin{Pro}[Akl and Taylor]
$\kappa(y)$ can be feasibly computed from a set of keys $\kappa(Y)$, $Y \subseteq X$, if and only if $\gcd\set{e(x) : x \in Y} \mid e(y)$
\end{Pro}

\begin{Cor}[Akl and Taylor]
A collusion secure scheme has the following property for all $y \in X$
  \[
    \gcd\set{e(x) : x \not\geqslant y} \nmid e(y)
  \]
\end{Cor}

\end{slide}

\begin{slide}
\slideheading[The Akl-Taylor scheme]{Choosing public parameters}

\vbls

\begin{minipage}{.45\textwidth} \centering\setlength{\unitlength}{\textwidth/180}
  \begin{picture}(160,100)(-80,-10)
      \node{b}{-80}{0}{\textcolor{blue}{$7$}}
      \node{t}{-80}{0}{\textcolor{red}{$2.3.5.11.13$}}
          \drawline(-80,0)(-40,40)
      \node{b}{0}{0}{\textcolor{blue}{$11$}}
      \node{t}{0}{0}{\textcolor{red}{$2.3.5.7.13$}}
          \drawline(0,0)(-40,40) \drawline(0,0)(40,40)
      \node{b}{80}{0}{\textcolor{blue}{$13$}}
      \node{t}{80}{0}{\textcolor{red}{$2.3.5.7.11$}}
          \drawline(80,0)(40,40)
      \node{r}{-40}{40}{\textcolor{blue}{$3$}}
      \node{l}{-40}{40}{\textcolor{red}{$2.5.13$}}
          \drawline(-40,40)(0,80)
      \node{r}{40}{40}{\textcolor{blue}{$5$}}
      \node{l}{40}{40}{\textcolor{red}{$2.3.7$}}
          \drawline(40,40)(0,80)
      \node{b}{0}{80}{\textcolor{blue}{$2$}}
      \node{t}{0}{80}{\textcolor{red}{$1$}}
  \end{picture}%
\end{minipage}
\hfill
\begin{minipage}{.45\textwidth}\raggedright\setlength{\unitlength}{\textwidth/180}
Associate a prime $p(x)$ with each $x \in X$ and define
  \[
    \textcolor{red}{e}(x) = \prod_{z \not\geqslant x} \textcolor{blue}{p}(z)
  \]
%$\kappa(x_2) = s^{2.5.13}$ $\kappa(x_5) = s^{2.3.5.7.13}$\\
To derive $\kappa(x_5)$ from $\kappa(x_2)$
  \begin{itemize}
    \item compute $\frac{2.3.5.7.13}{2.5.13} = 3.7$
    \item compute $(\kappa(x_2))^{3.7} \mod n$
  \end{itemize}
\end{minipage}

\vbls

It is this instantiation of the scheme that has inspired much of the subsequent research on key assignment schemes
\end{slide}

\begin{slide}
\slideheading[The Akl-Taylor scheme]{Characteristics claimed of Akl-Taylor scheme}

\begin{itemize}
  \item \textcolor{green}{Low private storage}
  \item \textcolor{red}{High public storage (product of primes is $\bigO{m \log m}$)}
  \item \textcolor{green}{Direct key derivation} \textcolor{red}{(but does require division of two products of primes and exponentiation)}
  \item \textcolor{red}{High cost for update of public data}
  \item \textcolor{red}{High costs for update of private data}
\end{itemize}

\end{slide}

\begin{slide}

\slideheading{Simplifying the Akl-Taylor scheme}

\end{slide}

\begin{slide}
\slideheading[Simplifying the Akl-Taylor scheme]{Some observations}

The Akl-Taylor scheme has the following characteristics
  \begin{itemize}
    \item the enforcement of the simple security property relies on the fact that it is difficult to compute integral roots
    \item $y \leqslant x$ implies $e(x) \mid e(y)$
  \end{itemize}

In other words, $e : X \hookrightarrow D(k)$, where
  \[
    k = \prod_{x \in X} p(x)\quad \text{and}\quad e(x) = \frac{\displaystyle\prod_{x \in X} p(x)}{\displaystyle\prod_{y \leqslant x} p(x)}
  \]

Essentially $e$ is an encoding of the structure of $X$ using order filters

\end{slide}

\begin{slide}
\slideheading[Simplifying the Akl-Taylor scheme]{A simpler embedding}

Define $p : X \rightarrow \mathbb{P}$, where $\mathbb{P}$ is the set of primes, and $e' : X \rightarrow 2^X$, where $e'(x) = X \setminus \dset{x}$

\begin{Pro}
$e = p \circ e'$
\end{Pro}

Instead of using products of primes as the public information, we encode subsets of $X$ as binary strings and publish them along with $p$
  \begin{itemize}
    \item $e'(x)$ can be represented as a string of $m$ bits
    \item $e(y)/e(x)$ can be computed by evaluating $e'(y) \oplus e'(x)$ and then multiplying the appropriate primes
%    \item That is, $\kappa(y) = \kappa(x)^{p(e'(x) \oplus e'(y))}$
  \end{itemize}

\end{slide}

\begin{slide}
\slideheading[Simplifying the Akl-Taylor scheme]{Example}

\vbls

\begin{minipage}{.45\textwidth}\centering\centering\setlength{\unitlength}{\textwidth/180}
  \begin{picture}(160,100)(-80,-10)
      \node{t}{-80}{0}{$x_4$}
          \drawline(-80,0)(-40,40)
      \node{t}{0}{0}{$x_5$}
          \drawline(0,0)(-40,40) \drawline(0,0)(40,40)
      \node{t}{80}{0}{$x_6$}
          \drawline(80,0)(40,40)
      \node{b}{-40}{40}{$x_2$}
          \drawline(-40,40)(0,80)
      \node{b}{40}{40}{$x_3$}
          \drawline(40,40)(0,80)
      \node{b}{0}{80}{$x_1$}
  \end{picture}
\end{minipage}
\hfill
\begin{minipage}{.45\textwidth} \centering\setlength{\unitlength}{\textwidth/180}
    \begin{picture}(160,100)(-80,-10)
        \node{t}{-80}{0}{${111011}$}
            \drawline(-80,0)(-40,40)
        \node{t}{0}{0}{${111101}$}
            \drawline(0,0)(-40,40) \drawline(0,0)(40,40)
        \node{t}{80}{0}{${111110}$}
            \drawline(80,0)(40,40)
        \node{r}{-40}{40}{${101001}$}
            \drawline(-40,40)(0,80)
        \node{l}{40}{40}{${110100}$}
            \drawline(40,40)(0,80)
        \node{b}{0}{80}{$000000$}
    \end{picture}%
\end{minipage}

\vbls

\begin{itemize}
  \item $e'(x_2) = 101001$, $e'(x_5) = 111101$
  \item $e'(x_2) \oplus e'(x_5) = 010100$
  \item $e(x) = p(x_2)p(x_5) = 3.7$ (which corresponds to the quotient of $2.5.13$ and $2.3.5.7.13$)
\end{itemize}
\end{slide}

\begin{slide}
\slideheading[Simplifying the Akl-Taylor scheme]{Updates in the Akl-Taylor scheme and IKEKAS}
%
%\begin{Pro}
%In order to update $\kappa(x)$ it is sufficient to update one prime $p(z)$, where $z \not\leqslant x$
%\end{Pro}

\begin{Pro}
In changing $\kappa(x)$ it is necessary to change
  \begin{itemize}
    \item $\min\set{|L \setminus \dset{z}| : z \not\leqslant x}$ keys
    \item One prime $p(z)$, where $z \not\leqslant x$
  \end{itemize}
\end{Pro}

\begin{Pro}
In changing $\kappa(x)$ in IKEKAS it is necessary to change
  \begin{itemize}
    \item $|\dset{x}|$ keys
    \item $\bigO{|\dset{x}|}$ items of public information
  \end{itemize}
\end{Pro}
\end{slide}

\begin{slide}
\slideheading[Simplifying the Akl-Taylor scheme]{Characteristics of simplified Akl-Taylor scheme}

\begin{itemize}
  \item \textcolor{green}{Time complexity of computing the quotient of $e(x)$ and $e(y)$ reduces from $\bigO{m^2 \log^2 m}$ to $\bigO{1}$}
  \item \textcolor{green}{Update of public information is trivial because only one prime needs to be changed}
    \begin{itemize}
      \item \textcolor{green}{Updating all keys requires no change to public information (since we simply choose new secret parameter $s'$)}
    \end{itemize}
  \item Public storage reduces from $\bigO{m^2 \log m}$ to $\bigO{m^2}$
  \item \textcolor{red}{Update of secret information remains the same}
\end{itemize}

\end{slide}

\begin{slide}
\slideheading[Conclusions]{Conclusions}


\end{slide}

\begin{slide}
\slideheading[Conclusions]{Contributions}

\begin{itemize}
  \item Classification of key assignment schemes
    \begin{itemize}
      \item Comparison of characteristics of such schemes
      \item Evaluation of many schemes in the literature
    \end{itemize}
  \item Improvement to implementation of Akl-Taylor
    \begin{itemize}
      \item Significant reduction in key derivation complexity
      \item Reduction in storage requirements
      \item Improved insight into key updates
    \end{itemize}
  \item Development of hybrid key assignment scheme
    \begin{itemize}
      \item Poset ``partitioned'' into domains
      \item Each domain has a NBKAS
      \item Domains linked using ideas from IKEKAS
    \end{itemize}
\end{itemize}
\end{slide}

\begin{slide}
\slideheading[Conclusions]{Future work}

\begin{itemize}
  \item Are there other trapdoor functions for node-based schemes?
  \item Are there better embeddings of $X$ for Akl-Taylor schemes?
    \begin{itemize}
      \item Is there a ``canonical'' representation and embedding for the Bell-LaPadula security lattice?
    \end{itemize}
  \item Can we extend the model to key assignment schemes where key availability is a function of time?
\end{itemize}

\end{slide}

\end{document}