main.tex

\documentclass[xcolor={dvipsnames},aspectratio=169,10pt]{beamer}

\input{preamble.tex}
\addbibresource{ref.bib}

\title{Authenticated Query Processing in the Cloud}
\author{XU Cheng}
\institute{Supervisor: Prof.~XU Jianliang}
\date{January 31, 2019}
\titlegraphic{\hfill\resizebox{!}{0.7cm}{\input{figs/group-logo.tex}}}

\begin{document}

\maketitle%

\begin{frame}{Contents}
  \setbeamertemplate{section in toc}[sections numbered]
  \tableofcontents[hideallsubsections]
\end{frame}

\section{Introduction}

\begin{frame}{Background}
  \begin{itemize}[<+->]
    \item \alert{\emph{Data-as-a-Service} (DaaS)} and \alert{cloud computing} are gaining popularity for big data analytics
      \begin{figure}
        \input{figs/model.tex}
        \caption{System Model}
      \end{figure}
    \item \textcolor{Red}{Security Threats}: SP cannot be fully trusted $\Rightarrow$ Query result integrity not guaranteed
    \item \textcolor{Green}{Solution}:
      \begin{itemize}[<1->]
        \item DO signs a well-designed \alert{\emph{authenticated data structure} (ADS)}
        \item SP constructs a cryptographic proof a.k.a.\ \alert{\emph{verification object} (VO)}
        \item Clients verify the correctness of the results based on VO
      \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}{Related Works}
  \begin{columns}
    \begin{column}{0.8\linewidth}
      \begin{itemize}[<+->]
        \item There are two approaches to support authenticated query processing
        \item \alert{ADS-based Solutions}
          \begin{itemize}[<1->]
            \item Designed specifically based on the computation task
            \item \makebox[.35\linewidth][l]{\textcolor{Green}{Pros}: efficient}
              \textcolor{Red}{Cons}: only work for the specific queries
            \item \textcolor{Violet}{Examples}:
              \parbox[t]{\linewidth}{%
                \strut%
                signature chaining~\cite{10.1109/ICDE.2004.1320027}, Merkle hash tree~\cite{10.1007/0-387-34805-0_21}, \\ set accumulator~\cite{10.1145/2660267.2660373}, etc.%
                \strut%
              }%
          \end{itemize}
        \item \alert{General-Purpose Solutions}
          \begin{itemize}[<1->]
            \item Modeling computation task as boolean or arithmetic circuit
            \item \makebox[.35\linewidth][l]{\textcolor{Green}{Pros}: expressive}
              \textcolor{Red}{Cons}: high setup \& proving cost
            \item \textcolor{Violet}{Examples}: zkSNARKs~\cite{10.1109/sp.2013.47}, RAM-based VC~\cite{10.1145/2517349.2522733}, etc.
          \end{itemize}
        \item We focus on \alert{ADS-based solutions} in this dissertation
      \end{itemize}
    \end{column}%
    \begin{column}{0.2\linewidth}
      \begin{figure}
        \onslide<2->{%
          \resizebox{\linewidth}{!}{\input{figs/sig-chain.tex}}
          \caption{Signature Chaining}
          \resizebox{\linewidth}{!}{\input{figs/mht.tex}}
          \caption{Merkle Hash Tree}
          \onslide<3->{%
            \resizebox{\linewidth}{!}{\input{figs/zksnarks.tex}}
            \caption{zkSNARKs}
          }
        }
      \end{figure}%
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}{Limitations of the Existing Works}
  \begin{itemize}[<+->]
    \item However, the prior works have only considered \alert{limited query types}
    \item They fail to consider:
      \begin{itemize}[<+- | alert@+>]
        \item Aggregate queries over set-valued data for data analytics
        \item Enforcing fine-grained access control
        \item Query processing in distributed settings
      \end{itemize}
  \end{itemize}

  \begin{columns}[b,onlytextwidth]
    \begin{column}{0.33\linewidth}
      \begin{figure}
        \onslide<3->{%
          \resizebox{\linewidth}{!}{\input{figs/analytics.tex}}
          \caption{Analytical Queries}
        }
      \end{figure}
    \end{column}
    \begin{column}{0.33\linewidth}
      \begin{figure}
        \onslide<4->{%
          \resizebox{\linewidth}{!}{\input{figs/access-control.tex}}
          \caption{Access Control}
        }
      \end{figure}
    \end{column}
    \begin{column}{0.33\linewidth}
      \begin{figure}
        \onslide<5->{%
          \resizebox{\linewidth}{!}{\input{figs/distributed.tex}}
          \caption{Distributed Query Processing}
        }
      \end{figure}
    \end{column}
  \end{columns}
\end{frame}

\section{Authenticating Aggregate Queries over Set-Valued Data}

\subsection{Problem Formulation}

\begin{frame}[fragile]{Example of Aggregate Queries over Set-Valued Data}
  \begin{columns}[onlytextwidth]
    \begin{column}{.5\linewidth}
      \setbeamercovered{transparent}
      \begin{table}
        \resizebox{\linewidth}{!}{%
          \begin{tabular}{ccl}
            \toprule
            \textbf{PID} & \textbf{ZIP} & \multicolumn{1}{c}{\textbf{Mut-Genes}}\\
            \midrule
            \onslide<1,2,3>{P1&95014&\alert<2>{A-C130R}, P-I696M} \\
            \onslide<1,3,4>{P2&20482&H-C282Y, \alert<4>{P-P12A}, \alert<3,4>{R-G1886S}} \\
            \onslide<1,2,3>{P3&95014&\alert<2>{A-C130R}, U-G71R, W-R611H} \\
            \onslide<1,3>{P4&01720&A-V2050L, H-C282Y, M-R52C, U-G71R} \\
            \onslide<1,3,4>{P5&20134&A-C130R, \alert<4>{P-P12A}, \alert<3,4>{R-G1886S}, S-E366K} \\
            \onslide<1,3>{P6&17868& C-R102G, \alert<3>{R-G1886S}} \\
            \onslide<1,3>{P7&55410&C-R102G, C-Q1334H, S-E288V} \\
            \onslide<1,3,4>{P8&20852&C-R102G, \alert<4>{P-P12A}, \alert<3,4>{R-G1886S}, K-T220M} \\
            \bottomrule
          \end{tabular}
        }
        \caption{Set-Valued Genome Dataset~\cite{pgp}}
      \end{table}
    \end{column}%
    \begin{column}{.5\linewidth}
      \begin{itemize}[<+(1)->]% chktex 36
        \item \textbf{Q1}: Find the most common gene in the district of Cupertino, CA (ZIP\@: 95014) \\
          \textcolor{Violet}{\emph{Answer:} \{`A-C130R'\}}
        \item \textbf{Q2}: Count the number of participants who carry the gene `R-G1886S' \\
          \textcolor{Violet}{\emph{Answer:} 4}
        \item \textbf{Q3}: Find the most frequent genes with supports $\ge$ 3 in ZIPs 20*** \\
          \textcolor{Violet}{\emph{Answer:} \{`P-P12A', `R-G1886S'\}}
      \end{itemize}
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}{Problem Definition}
  \begin{itemize}[<+->]
    \item \textbf{Dataset} $\mathbb{D} = \{o_1, o_2, \dotsc, o_n\}$
      \begin{itemize}[<.->]
        \item $o_i = \langle A_i, X_i \rangle$.
        \item $A_i$ is a set of \textcolor{Green}{non-sensitive} attributes
        \item $X_i$ is a \textcolor{Red}{sensitive} multiset of \emph{features}
      \end{itemize}
    \item \textbf{Aggregate Query} $Q = (q, \{x_i\}, [\alpha, \beta])$
      \begin{itemize}[<.->]
        \item $q$ is an aggregate operator, i.e., \emph{max/min}, \emph{count}, \emph{sum}, \emph{top-$k$}, and \emph{frequent feature query (FFQ)}
        \item $\{x_i\}$ is the queried feature specified for \emph{count} and \emph{sum}
        \item $[\alpha, \beta]$ specifies the selection range over the \textcolor{Green}{non-sensitive} attributes
      \end{itemize}
    \item \textbf{Threat Model}
      \begin{itemize}[<.->]
        \item \alert{Integrity}: SP should prove the \emph{soundness} and \emph{completeness} of the results
        \item \alert{Confidentiality}: Clients should not infer any \emph{sensitive source data}
      \end{itemize}
  \end{itemize}
\end{frame}

\subsection{Preliminaries}

\begin{frame}{Preliminaries}
  \begin{definition}<+->[Bilinear-Map (BM) Accumulator~\cite{10.1007/978-3-540-30574-3_19}]
    Let $g$ be the group generator of a cyclic multiplicative group $\mathbb{G}$ and $s$ be a \textcolor{Red}{private value of DO}. The accumulator maps a multiset $X = \{ x_1, x_2, \dotsc, x_m \}$ to a single value in $\mathbb{G}$:
    \begin{align*}
      acc(X) = g^{P(X)} = g^{\prod_{x_i \in X}(x_i + s)}
    \end{align*}
    Without knowing $s$, one can still compute an $acc(\cdot)$ value by giving $g^s, g^{s^2}, \dotsc$
  \end{definition}
  \begin{example}<.->
    $X = \{ 1, 1, 2 \}$, $acc(X) = g^{{(1+s)}^2(2+s)} = g^{s^3+4 s^2+5 s+2} = g^{s^3} \cdot {(g^{s^2})}^4 \cdot {(g^s)}^5 \cdot g^2$
  \end{example}
  \begin{definition}<+->[Randomized BM Accumulator]
    BM accumulator is \alert{deterministic} for \emph{a fixed multiset}. As such, an adversary can tell in high confidence that two multisets are the same. We can randomize BM accumulator as following:
    \begin{align*}
      acc(X) = g^{P(X) \cdot r_X} = g^{r_X\prod_{x_i \in X}(x_i + s)}
    \end{align*}
    $r_X$ is a random value \textcolor{Red}{hidden from Clients} but \textcolor{Green}{disclosed to SP}.
  \end{definition}
\end{frame}

\begin{frame}{Preliminaries}
  \begin{definition}[Cryptographic Hash Function]
    A cryptographic hash function $H(\cdot)$ accepts an arbitrary-length string as its input and returns a fixed-length bit string such that it is computationally infeasible to find $m_1 \neq m_2$ and $H(m_1) = H(m_2)$.
  \end{definition}
  \begin{definition}[Bilinear Pairing]
    Let $\mathbb{G}, \mathbb{G}_T$ be two cyclic multiplicative groups of order $p$.
    A pairing is a map $e: \mathbb{G} \times \mathbb{G} \to \mathbb{G}_T$, which satisfies:
    \begin{itemize}
      \item \textbf{Bilinearity}: $e(u^a,v^b) = {e(u,v)}^{ab}$, $\forall u, v \in \mathbb{G}$
      \item \textbf{Non-degeneracy}: $e(g,g) \ne 1$
      \item \textbf{Computability}: Given $u, v \in \mathbb{G}$, it is easy to compute $e(u, v)$
    \end{itemize}
  \end{definition}
\end{frame}

\subsection{PA$^2$ Authentication Framework}

\begin{frame}[fragile]{PA$^2$ Authentication Framework Overview}
  \begin{figure}
    \onslide<+->{%
      \resizebox{.8\linewidth}{!}{%
        \begin{tikzpicture}
          \node[anchor=south west,inner sep=0] (A) at (0,0)
            {\includegraphics[width=\linewidth]{figs/aggregate-queries/overview.pdf}};
          \coordinate (multiset1) at (8.6,2.2);
          \coordinate (multiset2) at (11.9,3.45);
          \coordinate (aggregate1) at (9,0.1);
          \coordinate (aggregate2) at (11.7,1.55);
          \coordinate (select1) at (4.8,0.1);
          \coordinate (select2) at (7.57,3.45);
          \draw<2>[Red,ultra thick] (multiset1) rectangle (multiset2);
          \fill<2>[draw=none,fill=black,fill opacity=0.3,even odd rule]
            (A.south west) rectangle (A.north east)
            (multiset1) rectangle (multiset2);
          \draw<3>[Red,ultra thick] (aggregate1) rectangle (aggregate2);
          \fill<3>[draw=none,fill=black,fill opacity=0.3,even odd rule]
            (A.south west) rectangle (A.north east)
            (aggregate1) rectangle (aggregate2);
          \draw<4>[Red,ultra thick] (select1) rectangle (select2);
          \fill<4>[draw=none,fill=black,fill opacity=0.3,even odd rule]
            (A.south west) rectangle (A.north east)
            (select1) rectangle (select2);
        \end{tikzpicture}
      }
      \caption{Privacy-Preserving Authentication Framework for Aggregate Queries}
    }
  \end{figure}
  \begin{itemize}[<+- | alert@+>]
    \item PA$^2$ Protocols on Multiset Operations
    \item PA$^2$ Algorithms on Aggregate Queries
    \item PA$^2$ on Candidate Object Selection
  \end{itemize}
\end{frame}

\subsubsection{PA$^2$ Protocols on Multiset Operations}

\begin{frame}{PA$^2$ Protocols on Multiset Operations --- Subset}
  \begin{block}{$sub(X_1, X_2)$: returns $acc$ value of $X_1 - X_2$ iff $X_2 \subseteq X_1$}
    \begin{itemize}
      \item DO prepares $acc(X_1)$, $acc(X_2)$
      \item SP computes ${acc(X_1 - X_2)}^* = g^{r_{X_1}/r_{X_2} \prod_{x \in (X_1 - X_2)} (x+s)}$
      \item Client verifies $e(acc(X_2), {acc(X_1 - X_2)}^*) \stackrel{?}{=} e(acc(X_1), g)$
    \end{itemize}
  \end{block}
  \begin{example}
    \begin{itemize}
      \item $X_1 = \{ 1, 1, 2 \}$, $X_2 = \{ 1, 2 \}$
      \item $acc(X_1) = g^{r_{X_1}{(1+s)}^2(2+s)}$, $acc(X_2) = g^{r_{X_2}(1+s)(2+s)}$, ${acc(X_1 - X_2)}^* = g^{r_{X_1}/r_{X_2}(1+s)}$
      \item \(
        \begin{aligned}[t]
          e(acc(X_2), {acc(X_1 - X_2)}^*) &= e(g^{r_{X_2}(1+s)(2+s)},g^{r_{X_1}/r_{X_2}(1+s)}) = {e(g, g)}^{r_{X_1}{(1+s)}^2(2+s)} \\
          e(acc(X_1), g) &=  e(g^{r_{X_1}{(1+s)}^2(2+s)}, g) = {e(g, g)}^{r_{X_1}{(1+s)}^2(2+s)}
        \end{aligned}
        \)
    \end{itemize}
  \end{example}
\end{frame}

\begin{frame}{PA$^2$ Protocols on Multiset Operations --- Sum}
  \begin{block}{$sum(\{X_1, \dotsc, X_n\})$: returns $acc$ value of $S = \uplus_{i=1}^n X_i$}
    \begin{itemize}
      \item DO prepares $acc(X_1), \dotsc, acc(X_n)$
      \item SP computes ${acc(\uplus_{j = 1}^i X_j)}^*$, for $i \in [2, n]$
      \item Client verifies
        \begin{adjustbox}{valign=t}
          \(
          \begin{aligned}
            \left \{
              \begin{array}{l}
                e(acc(X_1), acc(X_2)) \stackrel{?}{=} e({acc(X_1 \uplus X_2)}^*, g)\\
                e({acc(X_1\uplus X_2)}^*, acc(X_3)) \stackrel{?}{=} e({acc(X_1\uplus X_2\uplus X_3)}^*, g) \\
                \vdots\\
                e({acc(\uplus_{i=1}^{n-1} X_i)}^*, acc(X_n)) \stackrel{?}{=} e({acc(S)}^*, g)
              \end{array}
            \right.
          \end{aligned}
          \)
        \end{adjustbox}
    \end{itemize}
  \end{block}
  \begin{example}
    \begin{itemize}
      \item $X_1 = \{ 1 \}$, $X_2 = \{ 1 \}$, $X_3 = \{ 2 \}$
      \item SP returns ${acc(X_1 \uplus X_2)}^* = acc(\{1, 1\})$ and ${acc(S)}^* = {acc(X_1 \uplus X_2 \uplus X_3)}^* = acc(\{1, 1, 2\})$
    \end{itemize}
  \end{example}
\end{frame}

\begin{frame}{PA$^2$ Protocols on Multiset Operations --- Empty}
  \begin{block}{$empty(\{X_1, \dotsc, X_n\})$: returns whether $\cap_{i=1}^n X_i = \emptyset$}
    \begin{itemize}
      \item DO prepares $acc(X_1), \dotsc, acc(X_n)$
      \item Based on \alert{extended Euclidean algorithm}
        \begin{align*}
          \textstyle%
          \cap \{ X_i \} = \emptyset \Rightarrow \exists Q_i \text{ s.t. } \sum_{i=1}^n Q_i \cdot P(X_i) = 1
        \end{align*}
      \item SP computes $F_i^* = g^{Q_i}$, for $i \in [1, n]$
      \item Client verifies $\prod_{i=1}^n e(acc(X_i), F_i^*) \stackrel{?}{=} e(g, g)$
    \end{itemize}
  \end{block}
  \begin{example}
    \begin{itemize}
      \item $X_1 = \{ 1 \}$, $X_2 = \{ 2 \}$
      \item SP returns $F_1^* = g^{-1/r_{X_1}}$, $F_2^* = g^{1/r_{X_2}}$
      \item \(
        \begin{aligned}[t]
          e(acc(X_1), F_1^*)e(acc(X_2), F_2^*) &= e(g^{r_{X_1}(1+s)}, g^{-1/r_{X_1}})e(g^{r_{X_2}(2+s)}, g^{1/r_{X_2}}) \\
                                               &= {e(g,g)}^{-1-s}{e(g,g)}^{2+s} = {e(g,g)}^{-1-s+2+s} = e(g,g)
        \end{aligned}
        \)
    \end{itemize}
  \end{example}
\end{frame}

\begin{frame}{PA$^2$ Protocols on Multiset Operations --- Union}
  \begin{block}{$union(\{X_1, \dotsc, X_2\})$: returns $acc$ value of $U = \cup_{i=1}^n X_i$}
    \begin{itemize}
      \item Denote $\widehat{X}_i$ as the \alert{set version} of a multiset $X_i$.
      \item Client verifies two conditions:
        \begin{enumerate}
          \item \alert{Deflation checking} (no object is missing):
            \begin{align*}
              \widehat{X}_1 \subseteq U \wedge \widehat{X}_2 \subseteq U \wedge \cdots \widehat{X}_n \subseteq U
            \end{align*}
          \item \alert{Inflation checking} (no non-result object is added):
            \begin{align*}
              (U - \widehat{X}_1) \cap (U - \widehat{X}_2) \cap \cdots (U - \widehat{X}_n) = \emptyset
            \end{align*}
        \end{enumerate}
    \end{itemize}
  \end{block}
  \begin{example}
    \begin{itemize}
      \item $X_1 = \{ 1 \}$, $X_2 = \{ 2 \}$, $U = \{ 1, 2 \}$
      \item \alert{Deflation checking}: $\{1\} \subseteq \{1,2\}, \{2\} \subseteq \{1,2\}$ \\
        \alert{Inflation checking}: $\{2\} \cap \{1\} = \emptyset$
    \end{itemize}
  \end{example}
\end{frame}

\begin{frame}{PA$^2$ Protocols on Multiset Operations --- Times}
  \begin{block}{$times(X, t)$: returns $acc$ value of $t \cdot X$}
    \begin{itemize}
      \item Let $d = \lfloor \log_2(t) \rfloor$ and $t = {(b_0b_1\cdots b_d)}_2$, the \alert{binary form} of $t$.
      \item $times(X, t) = sum(\{b_0 \cdot X, \dotsc, b_i \cdot 2^i \cdot X, \dotsc, b_d \cdot 2^d \cdot X\})$
      \item SP computes ${acc(2\cdot X)}^*, \dotsc, {acc({2^d} \cdot X)}^*, {acc(t \cdot X)}^*$
      \item Client verifies:
        \begin{itemize}
          \item $e({acc(2^{i-1} \cdot X)}^*, {acc(2^{i-1} \cdot X)}^*) = e({acc(2^{i} \cdot X)}^*, g)$, for $i \in [1, d]$
          \item Apply $sum(\{b_0 \cdot X, \dotsc, b_i \cdot 2^i \cdot X, \dotsc, b_d \cdot 2^d \cdot X\})$
        \end{itemize}
    \end{itemize}
  \end{block}
  \begin{example}
    \begin{itemize}
      \item When $t = 5$, SP computes $acc(2\cdot X), acc(4\cdot X)$
      \item $acc(5 \cdot X) = sum(\{X, 4\cdot X\})$
    \end{itemize}
  \end{example}
\end{frame}

\subsubsection{PA$^2$ Algorithms on Aggregate Queries}

\begin{frame}{PA$^2$ Algorithms on Aggregate Queries --- Sum Query}
  \begin{block}{Sum Query $sum(x_q)$: returns feature $x_q$'s multiplicity sum $\eta_q$}
    \begin{itemize}
      \item Denote $X_1, \dotsc, X_n$ as input multisets and $R = \{ (x_q, \eta_q) \}$ as the result.
      \item Execute $sum(\{X_1, \dotsc, X_n\})$ to get verified $acc(S)$, where $S = \uplus \{X_i\}$
      \item Client verifies two conditions:
        \begin{enumerate}
          \item \alert{Inflation checking} (no non-result object is added):
            \begin{align*}
              R \subseteq S
            \end{align*}
          \item \alert{Deflation checking} (no object is missing):
            \begin{align*}
              (S - R) \cap R = \emptyset
            \end{align*}
        \end{enumerate}
    \end{itemize}
  \end{block}
  \begin{example}
    \begin{itemize}
      \item $S = \{(a,6), (b, 1), (c, 5), (d, 3), (e, 2)\}$, $x_q = a$. The result is $R = \{(a, 6)\}$.
      \item \alert{Inflation checking}: $\{(a, 6)\} \subseteq \{(a,6)$, $(b, 1)$, $(c, 5)$, $(d, 3)$, $(e, 2)\}$ \\
        \alert{Deflation checking}: $\{(b, 1), (c,5), (d, 3), (e, 2)\} \cap \{(a, 6)\} = \emptyset$
    \end{itemize}
  \end{example}
\end{frame}

\begin{frame}{PA$^2$ Algorithms on Aggregate Queries --- Max Query}
  \begin{block}{Max Query: returns the feature with the highest (i.e., top-1) multiplicity}
    \begin{itemize}
      \item Denote $X_1, \dotsc, X_n$ as input multisets and $R = \{ (x, \tau) \}$ as the result.
      \item Execute $sum(\{X_1, \dotsc, X_n\})$ to get verified $acc(S)$, where $S = \uplus \{X_i\}$
      \item Execute $union(\{X_1, \dotsc, X_n\})$ to get verified $acc(U)$, where $U = \cup \{\widehat{X}_i\}$
      \item Client verifies three conditions:
        \begin{enumerate}
          \item \alert{Inflation checking}: $R \subseteq S$
          \item \alert{Deflation checking}: $(S - R) \cap R = \emptyset$
          \item \alert{Completeness checking} (all other features have multiplicity less than $\tau$):
            \begin{align*}
              (S - R) \subseteq \tau \cdot (U -\widehat{R})
            \end{align*}
        \end{enumerate}
    \end{itemize}
  \end{block}
  \begin{example}
    \begin{itemize}
      \item $S = \{(a,6), (b, 1), (c, 5), (d, 3), (e, 2)\}$, $U = \{(a, 1), (b, 1), (c, 1), (d, 1), (e, 1)\}$.
      \item The result is $R = \{(a, 6)\}$.
      \item \alert{Completeness checking}: $\{(b, 1), (c, 5), (d, 3), (e, 2)\} \subseteq $ $\{(b,$ $6), (c, 6), (d, 6), (e, 6)\}$
    \end{itemize}
  \end{example}
\end{frame}

\begin{frame}{PA$^2$ Algorithms on Aggregate Queries --- Other Queries}
  \begin{itemize}
    \item \textbf{Count Query}
      \begin{itemize}
        \item Returns the count of candidate objects that have the queried feature.
        \item Equivalent to \alert{Sum Query} with multiplicity of each feature enforced as 1.
      \end{itemize}
    \item \textbf{Average Query}
      \begin{itemize}
        \item Returns the average multiplicity of queried feature in the candidate objects.
        \item Equivalent to \alert{Sum Query} divided by \alert{Count Query}.
      \end{itemize}
    \item \textbf{Min Query}
      \begin{itemize}
        \item Returns the feature with the lowest (i.e. bottom-$1$) multiplicity.
        \item Similar to \alert{Max Query}, except $(S - R) \supseteq {\tau} \cdot (U - \widehat{R})$.
      \end{itemize}
    \item \textbf{Frequent Features Query}
      \begin{itemize}
        \item Returns the feature with multiplicity larger than threshold $\tau$.
        \item Sub module of \alert{Max Query}.
      \end{itemize}
    \item \textbf{Top-$k$ Query}
      \begin{itemize}
        \item Returns the features with the top-$k$ multiplicity.
        \item Similar to \alert{Max Query}, except $\tau$ is the $k$-th feature's multiplicity.
      \end{itemize}
  \end{itemize}
\end{frame}

\subsubsection{PA$^2$ on Candidate Object Selection}

\begin{frame}{PA$^2$ on Candidate Object Selection}
  \begin{figure}
    \begin{subfigure}[b]{.4\linewidth}
      \centering
      \includegraphics[width=\linewidth]{figs/aggregate-queries/pyramid.eps}
      \caption{Structure}
    \end{subfigure}\quad%
    \begin{subfigure}[b]{.4\linewidth}
      \centering
      \includegraphics[width=\linewidth]{figs/aggregate-queries/grid_tree.eps}
      \caption{Index}
    \end{subfigure}
    \caption{Merkle Grid Tree (MG-tree)}
  \end{figure}
  \begin{itemize}
    \item \alert{Leaf Node}: $dig_i = H(H(acc(X_{c_1})) | \dotsb | H(acc(X_{c_C})) )$
    \item \alert{Non-Leaf Node}: $dig_i = H(gb_{c_1} | dig_{c_1} | \dotsb | gb_{c_C} | dig_{c_C} )$
    \item Apply \alert{Bucket Indistinguishability} to \emph{preserve privacy}
  \end{itemize}
\end{frame}

\subsection{Performance Evaluation}

\begin{frame}{Performance Evaluation}
  \begin{table}
    \footnotesize
    \begin{tabular}{cccc}
      \toprule
      Dataset & \tabincell{c}{Dataset\\ Size (MB)} & {Setup Time (s)} & \tabincell{c}{MG-tree Index\\Size (MB)} \\
      \midrule
      PGP  & 0.08 & 9.7 & 0.42 \\
      FoodMarket & 0.9 & 136 & 7.1 \\
      TPC-H & 13 & 1,365 & 116 \\
      \bottomrule
    \end{tabular}
    \caption{DO Setup Overhead}
  \end{table}

  \begin{itemize}
    \item Datasets:
      \begin{description}
        \item[PGP] $600$ participants, totally $395$ unique mutation genes (avg. $35$ per person)
        \item[FoodMarket] $\fnum{164558}$ shopping transaction records from $\fnum{8842}$ users and $\fnum{1560}$ products
        \item[TPC-H] $\fnum{1020116}$ transaction records from $\fnum{255000}$ orders and $\fnum{1700}$ suppliers
      \end{description}
  \end{itemize}
\end{frame}

\begin{frame}{Performance Evaluation}
  \savebox{\figbox}{%
    \includegraphics[height=.3\textheight]{exp-figs/aggregate-queries/pgp_vo.eps}%
  }
  \begin{figure}
    \setlength{\tabcolsep}{0pt}
    \renewcommand{\arraystretch}{0}
    \begin{tabular}{c@{\quad}lll}
      PGP &
      \includegraphics[valign=m,totalheight=\ht\figbox]{exp-figs/aggregate-queries/pgp_sp.eps} &
      \includegraphics[valign=m,totalheight=\ht\figbox]{exp-figs/aggregate-queries/pgp_client.eps} &
      \includegraphics[valign=m,totalheight=\ht\figbox]{exp-figs/aggregate-queries/pgp_vo.eps}
      \\
      FoodMarket &
      \includegraphics[valign=m,totalheight=\ht\figbox]{exp-figs/aggregate-queries/foodmarket_sp.eps} &
      \includegraphics[valign=m,totalheight=\ht\figbox]{exp-figs/aggregate-queries/foodmarket_client.eps} &
      \includegraphics[valign=m,totalheight=\ht\figbox]{exp-figs/aggregate-queries/foodmarket_vo.eps}
      \\
      TPC-H &
      \includegraphics[valign=m,totalheight=\ht\figbox]{exp-figs/aggregate-queries/tpch_sp.eps} &
      \includegraphics[valign=m,totalheight=\ht\figbox]{exp-figs/aggregate-queries/tpch_client.eps} &
      \includegraphics[valign=m,totalheight=\ht\figbox]{exp-figs/aggregate-queries/tpch_vo.eps}
    \end{tabular}
    \caption{Query Performance vs. Selectivity}
  \end{figure}
\end{frame}

\section{Authenticating Relational Queries with Fine-Grained Access Control}

\subsection{Problem Formulation}

\begin{frame}{Problem Model}
  \begin{figure}
    \centering
    \resizebox{.75\linewidth}{!}{\input{figs/access-control/model.tex}}
    \caption{Query Authentication with Access Control}
  \end{figure}

  \begin{itemize}[<+->]
    \item \textbf{Problem}
      \begin{itemize}[<1->]
        \item Enforcing \alert{fine-grained access control} to enable big data sharing
        \item Support \alert{equality query}, \alert{range query}, and \alert{join query}
      \end{itemize}
    \item \textbf{Threat Model}
      \begin{itemize}[<1->]
        \item \alert{Integrity}: SP should prove the \emph{soundess} and \emph{completeness} of the results
        \item \alert{Zero-Knowledge Confidentiality}: VO should leak no information beyond query results
      \end{itemize}
  \end{itemize}
\end{frame}

\subsection{Solutions}

\begin{frame}{Equality Query}
  \begin{figure}
    \resizebox{.9\linewidth}{!}{\input{figs/access-control/handle-non-existent.tex}}
    \caption{Equality Query}
  \end{figure}
  \begin{itemize}
    \item<1-> Client submits a query key $o_q$ and a role set $\mathcal{A}$
    \item<4-> \myst<5>{\alert{Non-existent record will leak information}}
    \item<5-> Treat non-existent records as \alert{inaccessible by anyone} i.e.\ $\Upsilon' = {Role}_{\emptyset}$
  \end{itemize}
\end{frame}

\begin{frame}{ABS with Predicate Relaxation}
  \begin{itemize}
    \item<+-> \textbf{Attribute Based Signature (ABS)}~\cite{10.1007/978-3-642-19074-2_24} \\
      \small{It signs a message with a monotone boolean function predicate that is satisfied by the attributes obtained from the authority}
      \begin{figure}
        \resizebox{.85\linewidth}{!}{\input{figs/access-control/abs-basic.tex}}
      \end{figure}
    \item<+-> \textbf{Predicate Relaxation} \\
      \small{Derive a \alert{weaker} ABS signature without knowing secret key}
      \begin{figure}
        \resizebox{.85\linewidth}{!}{\input{figs/access-control/abs-relax.tex}}
      \end{figure}
  \end{itemize}
\end{frame}

\begin{frame}{Authenticated Data Structures}
  \setbeamerfont{block title example}{size=\small}
  \setbeamerfont{block body example}{size=\small}
  \begin{itemize}
    \item<+-> \emph{Access-Policy-Preserving} (APP) signature
      \begin{itemize}
        \item Signed by DO and used as \alert{ADS}
        \item It captures three parts of information: \alert{query attribute $o_i$}, \alert{data content $v_i$}, \alert{access policy $\Upsilon_i$}
      \end{itemize}
      \begin{example}
        \begin{align*}
         & \text{Record}_2 \gets \langle o_2, v_2, \Upsilon_2 = {Role}_A \land {Role}_B \rangle                  \\
         & \sigma_2 \gets \textsf{ABS.Sign}({sk}_{\textrm{DO}}, hash(o_2) | hash(v_2) , {Role}_A \land {Role}_B)
        \end{align*}
      \end{example}
    \item<+-> \emph{Access-Policy-Stripped} (APS) signature
      \begin{itemize}
        \item Replace $\Upsilon_i$ to \alert{$\hat{\Upsilon}_{\mathcal{A}} = a_1 \lor a_2 \lor \dots \lor a_n, a_i \in \mathbb{A}\backslash\mathcal{A}$}
        \item Be used to prove inaccessibility in \alert{zero-knowledge}
      \end{itemize}
      \begin{example}
        \begin{align*}
         & \mathbb{A} = \{ {Role}_A, {Role}_B, {Role}_C, {Role}_\emptyset \},
         \hat{\Upsilon}_{\{{Role}_C\}} = {Role}_A \lor {Role}_B \lor {Role}_\emptyset
         \\
         & \hat{\sigma}_2 \gets \textsf{ABS.Sign}({sk}_{\textrm{DO}}, hash(o_2) | hash(v_2) , {Role}_A \lor {Role}_B \lor {Role}_\emptyset)
        \end{align*}
      \end{example}
  \end{itemize}
\end{frame}

\begin{frame}{Query Processing}
  \begin{figure}
    \footnotesize
    \resizebox{.8\linewidth}{!}{\input{figs/access-control/equality-query.tex}}
    \caption{Equality Query Authentication}
  \end{figure}
  \begin{itemize}
    \item<1-> DO generates ADS and sends to the SP
    \item<2-> $u_1$ \alert{can access the data}, \onslide<3->{APP signature is the VO}
    \item<4-> $u_2$ \alert{cannot access the data},
      \onslide<5->{SP generates an \textcolor{Red}{APS signature} as VO}
  \end{itemize}
\end{frame}

\begin{frame}{Range Query Authentication}
  \begin{figure}
    \begin{subfigure}[b]{.5\linewidth}
      \centering
      \resizebox{\linewidth}{!}{\input{figs/access-control/access-tree.tex}}
      \caption{Structure}
    \end{subfigure}~%
    \begin{subfigure}[b]{.5\linewidth}
      \centering
      \resizebox{\linewidth}{!}{\input{figs/access-control/access-tree-index.tex}}
      \caption{Index}
    \end{subfigure}
    \caption{Access-Policy-Preserving Grid-Tree (AP$^2$G-Tree)}
  \end{figure}

  \begin{itemize}
    \item \alert{Non-Leaf Node} $p_i = p_{c_1}  \lor  p_{c_2}  \lor  \dots  \lor  p_{c_C}$, $sig_i = \textsf{ABS.Sign}({sk}_{\textrm{DO}}, gb_i , p_i)$
    \item \alert{Leaf Node} Identical to those of underlying record
  \end{itemize}
\end{frame}

\begin{frame}{Join Query Authentication}
  \begin{figure}
    \centering
    \resizebox{.65\linewidth}{!}{\input{figs/access-control/join.tex}}
    \caption{Join Query Authentication}
  \end{figure}

  \begin{itemize}
    \item Use \alert{APP signature} to prove soundness
    \item Use \alert{APS signature} to prove completeness
  \end{itemize}
\end{frame}

\subsection{Performance Evaluation}

\begin{frame}{Performance Evaluation}
  \begin{table}
    \footnotesize
    \centering
    \begin{tabular}{cccc}
      \toprule
      \multirow{2}{*}{\tabincell{c}{Database\\Scale}} &
      \multicolumn{2}{c}{DO CPU Time} &
      \multirow{2}{*}{\tabincell{c}{Index Size (Tree Structure~+~Signatures) \\(GB)}} \\
      \cmidrule(lr){2-3}
                                      &
      Sign APPs (h) & Build Index (h) &
      \\
      \midrule
      0.1  & 0.63 & 0.74 & 2.47 (0.49 + 1.98) \\
      0.3  & 0.77 & 0.95 & 2.93 (0.56 + 2.37) \\
      1    & 0.86 & 1.00 & 3.14 (0.58 + 2.56) \\
      3    & 0.87 & 1.01 & 3.16  (0.59 + 2.57) \\
      \bottomrule
    \end{tabular}
    \caption{DO Setup Overhead}\label{tab:access-control:do-setup}
  \end{table}
  \begin{itemize}
    \item Dataset:
      \begin{itemize}
        \item TPC-H dataset: \\
          0.1 ($\fnum{600000}$ records), \emph{0.3 ($\fnum{1800000}$ records)}, 1 ($\fnum{6000000}$ records), 3 ($\fnum{18000000}$ records)
        \item $10$ distinct policies ($10$ global roles, max policy length is $6$)
      \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}{Performance Evaluation}
  \savebox{\figbox}{%
    \includegraphics[height=.35\textheight]{exp-figs/access-control/range_sp.eps}%
  }
  \begin{figure}
    \centering
    \includegraphics[height=\ht\figbox]{exp-figs/access-control/range_sp.eps}\quad%
    \includegraphics[height=\ht\figbox]{exp-figs/access-control/range_user.eps}\quad%
    \includegraphics[height=\ht\figbox]{exp-figs/access-control/range_vo.eps}
    \caption{Range Query Performance vs. Range}
  \end{figure}
  \begin{figure}
    \centering
    \includegraphics[height=\ht\figbox]{exp-figs/access-control/join_sp.eps}\quad%
    \includegraphics[height=\ht\figbox]{exp-figs/access-control/join_user.eps}\quad%
    \includegraphics[height=\ht\figbox]{exp-figs/access-control/join_vo.eps}
    \caption{Join Query Performance vs. Range}
  \end{figure}
\end{frame}

\section{Authenticating {kNN} Queries in Distributed Settings}

\subsection{Problem Formulation}

\begin{frame}{Background}
  \begin{itemize}[<+->]
    \item \textbf{kNN Queries}
      \begin{itemize}[<1->]
        \item Return $k$ nearest neighbor of the target point
        \item Widely used in spatial data analysis
        \item \textcolor{Violet}{Examples}: $\langle Q, k=3\rangle \Rightarrow \{ P_1, P_2, P_3 \}$
      \end{itemize}
    \item Existing authenticated methods are confined to a centralized environment
    \item But in reality, big data demands distributed service provider
  \end{itemize}

  \begin{columns}[b,onlytextwidth]
    \begin{column}{0.4\linewidth}
      \begin{figure}
        \scalebox{0.65}{\input{figs/knn/knn.tex}}
        \caption{Example of kNN Queries}
      \end{figure}
    \end{column}
    \begin{column}{0.6\linewidth}
      \begin{figure}
        \onslide<3->{%
          \includegraphics[totalheight=1.5cm,valign=m]{figs/knn/spatial_hadoop.png}\quad%
          \includegraphics[totalheight=1cm,valign=m]{figs/knn/geospark.png}
          \caption{Distributed Spatial Query Engines}
        }
      \end{figure}
    \end{column}
  \end{columns}
\end{frame}

\begin{frame}{Problem Formulation}
  \begin{itemize}[<+->]
    \item \textbf{System Architecture}
      \begin{itemize}[<1->]
        \item Three parties: \emph{Data Owner (DO)}, \emph{Service Provider (SP)}, and \emph{Client}
        \item SP consists of several types of nodes
      \end{itemize}
    \item \textbf{Threat Model}
      \begin{itemize}[<1->]
        \item \alert{Soundness} violation: \\
          Return result: $P_1$, $P_2$, $P_3'$ ($P_3'$ is not in $P_i$, $i \in [1, 7]$)
        \item \alert{Completeness} violation: \\
          Return result: $P_1$, $P_2$, $P_4$ ($P_4$ is father than $P_3$)
      \end{itemize}
  \end{itemize}
  \begin{columns}[b,onlytextwidth]
    \begin{column}{0.5\linewidth}
      \begin{figure}
        \resizebox{\linewidth}{!}{\input{figs/knn/architecture.tex}}
        \caption{SP Architecture}
      \end{figure}
    \end{column}
    \begin{column}{0.5\linewidth}
      \begin{figure}
        \onslide<2->{%
          \scalebox{0.65}{\input{figs/knn/knn.tex}}
          \caption{Example of kNN Queries}
        }
      \end{figure}
    \end{column}
  \end{columns}
\end{frame}

\subsection{Solutions}

\begin{frame}{Local kNN Authentication~\cite{10.1007/s00778-008-0113-2}}
  \vspace{-2ex}
  \begin{figure}
    \centering
    \begin{subfigure}[b]{.35\linewidth}
      \centering
      \begin{tikzpicture}
        \node[anchor=south west,inner sep=0] (A) at (0,0)
          {\includegraphics[width=.7\linewidth]{figs/knn/local-mrtree-data.pdf}};
        \coordinate (N12-1) at (0.4, 0.4);
        \coordinate (N12-2) at (3.1, 3);
        \coordinate (N34-1) at (0.4, 1.7);
        \coordinate (N34-2) at (2.15, 3);
        \coordinate (abc-1) at (0.4, 1.7);
        \coordinate (abc-2) at (0.95, 2.3);
        \draw<3>[Red,ultra thick] (N12-1) rectangle (N12-2);
        \draw<4>[Red,ultra thick] (N34-1) rectangle (N34-2);
        \draw<5>[Red,ultra thick] (abc-1) rectangle (abc-2);
      \end{tikzpicture}
      \caption{Data}
    \end{subfigure}~%
    \begin{subfigure}[b]{.65\linewidth}
      \centering
      \begin{tikzpicture}
        \node[anchor=south west,inner sep=0] (A) at (0,0)
          {\includegraphics[width=.7\linewidth]{figs/knn/local-mrtree-tree.pdf}};
        \coordinate (N12-1) at (2.3, 1.7);
        \coordinate (N12-2) at (4.1, 2.1);
        \coordinate (N34-1) at (0.6, 1.2);
        \coordinate (N34-2) at (2.35, 1.6);
        \coordinate (abc-1) at (0.1, 0.8);
        \coordinate (abc-2) at (1.1, 1.1);
        \draw<3>[Red,ultra thick] (N12-1) rectangle (N12-2);
        \draw<4>[Red,ultra thick] (N34-1) rectangle (N34-2);
        \draw<5>[Red,ultra thick] (abc-1) rectangle (abc-2);
      \end{tikzpicture}
      \caption{Index}
    \end{subfigure}
    \caption{Local Authenticated {kNN} Processing}
  \end{figure}
  \vspace{-2ex}
  \begin{itemize}[<+->]
    \item DO constructs \alert{Merkle R-tree}
    \item SP executes a best first traversal using \alert{Priority Queue}
      \begin{itemize}
        \item PQ: enqueue $N_1$, $N_2$
        \item PQ: dequeue $N_1$ and enqueue $N_3$, $N_4$
        \item PQ: dequeue $N_3$ and enqueue $a$, $b$, $c$
        \item VO: $[[[a, b, c], [N_4, H(N_4)]] ,[N_2, H(N_2)]]$
      \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}{Distributed kNN Authentication}
  \vspace{-2ex}
  \begin{figure}
    \centering
    \begin{subfigure}[b]{.35\linewidth}
      \centering
      \includegraphics[width=.7\linewidth]{figs/knn/distributed-mrtree-data.pdf}
      \caption{Data}
    \end{subfigure}~%
    \begin{subfigure}[b]{.65\linewidth}
      \centering
      \includegraphics[width=.7\linewidth]{figs/knn/distributed-mrtree-tree.pdf}
      \caption{Index}
    \end{subfigure}
    \caption{Distributed MR-tree}
  \end{figure}
  \vspace{-2ex}
  \begin{itemize}[<+->]
    \item Partition the space into the Non-overlapped splits
    \item \textbf{Structure of Distributed MR-tree}
      \begin{itemize}[<1->]
        \item \alert{Local indexes} (stored by \emph{slaves}): several MR-trees built by the local partitions
        \item \alert{Global index} (stored by \emph{master}): contains the information of each MR-trees
      \end{itemize}
    \item DO signs the root of global index
  \end{itemize}
\end{frame}

\begin{frame}{Query Processing}
  \begin{figure}
    \includegraphics[width=.6\linewidth]{figs/knn/framework.pdf}
    \caption{Framework of Distributed Authenticated kNN Query}
  \end{figure}
  \vspace{-2ex}
  \begin{enumerate}[<+->]
    \item Master searches global index to find \alert{home index}
    \item HSlave draws a minimum circle \alert{\emph{rcircle}} to cover partial kNN results
    \item If \emph{rcircle} overlaps other partitions, send to corresponding CSlaves
    \item CSlaves execute \alert{range queries} to find all objects covered by \emph{rcircle}
    \item Reducer assembles final result and VO
    \item Client verifies results by reconstructing root of global index
  \end{enumerate}
\end{frame}

\begin{frame}{Query Processing}
  \vspace{-2ex}
  \begin{figure}
    \centering
    \begin{subfigure}[b]{.33\linewidth}
      \centering
      \includegraphics[width=.6\linewidth]{figs/knn/case1.pdf}
      \caption{Case 1}
    \end{subfigure}~%
    \begin{subfigure}[b]{.33\linewidth}
      \centering
      \includegraphics[width=.6\linewidth]{figs/knn/case2.pdf}
      \caption{Case 2}
    \end{subfigure}~%
    \begin{subfigure}[b]{.313\linewidth}
      \centering
      \includegraphics[width=.6\linewidth]{figs/knn/specialcase.pdf}
      \caption{Special Case}
    \end{subfigure}
    \caption{Three Cases of {kNN} Processing}
  \end{figure}
  \vspace{-2ex}
  \small
  \begin{description}[<+->]
    \item[Case 1]
      \begin{itemize}[<1->]
        \item \emph{rcircle} has no intersection with other local tree's MBR
        \item No range queries are executed by CSlaves
      \end{itemize}
    \item[Case 2]
      \begin{itemize}[<1->]
        \item \emph{rcircle} has intersection with other local tree's MBR
        \item The corresponding CSlaves execute range queries \alert{concurrently}
      \end{itemize}
    \item[Special Case]
      \begin{itemize}[<1->]
        \item \emph{rcircle} contains less than $k$ objects (when data is skewed)
        \item Enlarge \emph{rcircle} exponentially and run range queries
        \item Use \alert{\emph{Sort-Tile-Recursive} (STR)}~\cite{10.1109/ICDE.1997.582015} partition to avoid data skewness
      \end{itemize}
  \end{description}
\end{frame}

\subsection{Performance Evaluation}

\begin{frame}{Performance Evaluation}
  \begin{columns}
    \begin{column}{0.5\linewidth}
      \begin{figure}
        \centering
        \includegraphics[width=0.8\linewidth]{exp-figs/knn/indexconstructtime.eps}
        \caption{DO's Construction Time}
      \end{figure}
    \end{column}
    \begin{column}{0.5\linewidth}
      \begin{table}
        \centering
        \resizebox{\linewidth}{!}{%
          \begin{tabular}{cccccc}
            \toprule
            Cardinality (Million) & 1.28 & 3.84  & 6.4  & 8.96  & 11.52\\
            \midrule
            MR-tree (MB)              & 69.8 & 209.4 & 349 & 488.6 & 628.2\\
            R-tree (MB)               & 69.4 & 208.2 & 347 & 485.8  & 624.6\\
            \bottomrule
        \end{tabular}}
        \caption{The Size of Index with Different Cardinalities}
      \end{table}
    \end{column}
  \end{columns}

  \begin{itemize}
    \item Dataset: New York Map from OpenStreetMap (11.56 million data points)
    \item Queries: randomly select $\fnum{1000}$ data points
  \end{itemize}
\end{frame}

\begin{frame}{Performance Evaluation}
  \begin{figure}
    \centering
    \begin{subfigure}[t]{.33\linewidth}
      \centering
      \includegraphics[width=\linewidth]{exp-figs/knn/querycost.eps}
      \caption{Query Cost}
    \end{subfigure}~%
    \begin{subfigure}[t]{.33\linewidth}
      \centering
      \includegraphics[width=\linewidth]{exp-figs/knn/vosize.eps}
      \caption{VO Size}
    \end{subfigure}~%
    \begin{subfigure}[t]{.33\linewidth}
      \centering
      \includegraphics[width=\linewidth]{exp-figs/knn/verify.eps}
      \caption{Verification Cost}
    \end{subfigure}
    \caption{Query Authentication Performance}
  \end{figure}

  \small
  \begin{description}
    \item[Basic algorithm] Range queries are executed \alert{in parallel}
    \item[Optimized algorithm] Range queries are executed \alert{sequentially}
    \item[Hybird algorithm] Use \alert{one range query} to reduce the \emph{rcircle}, then execute range queries \alert{in parallel}
  \end{description}
\end{frame}

\section{Conclusions}

\begin{frame}{Contributions}
  \begin{itemize}
    \item We have tackled three query authentication problems
      \begin{itemize}
        \item Authentication of aggregate queries over set-valued data
        \item Authentication of relational queries with fine-grained access control
        \item Authentication of kNN queries in distributed settings
      \end{itemize}
    \item We proposed efficient algorithms and ADS to enable DO outsourcing the data while maintaining data integrity
    \item Security analysis and performance evaluation show that our solutions are robust and efficient
  \end{itemize}
\end{frame}

\begin{frame}{Future Directions}
  \begin{itemize}[<+->]
    \item \textbf{Accelerating Authenticated Query Processing}
      \begin{itemize}[<1->]
        \item Existing techniques still incur dramatic overhead on the computation efficiency
        \item Utilize parallelism computation such as GPGPU and distributed computation
      \end{itemize}
    \item \textbf{Supporting More Complex Query Types}
      \begin{itemize}[<1->]
        \item Supporting more complex query types helps to a broader adoption of query authentication
        \item Utilize general VC to support more query types while using ADS-based technique to accelerate its subtask
      \end{itemize}
    \item \textbf{Integrity-Assured Searchable Blockchain}
      \begin{itemize}[<1->]
        \item Blockchain offers a new solution to realize trustworthy storage and computation
        \item But it is costly to become a full node or execute computation using smart contract
      \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}[standout]
  Thanks \\
  Questions?
\end{frame}

\appendix%

\begin{frame}{PA$^2$ on Candidate Object Selection (Optimized)}
  \begin{figure}
    \includegraphics[width=.4\linewidth]{figs/aggregate-queries/grid_tree_opt.eps}
    \caption{Optimized MG-tree}
  \end{figure}
  \metroset{block=transparent}
  \begin{alertblock}{Optimized Digest for Non-Leaf Node}
    \begin{align*}
      dig_i = H(gb_{c_1} | H(acc(S_{c_1})| acc(U_{c_1})) | dig_{c_1} | \dotsb
      |gb_{c_C} | H(acc(S_{c_C})|acc(U_{c_C})) | dig_{c_C})
    \end{align*}
  \end{alertblock}
\end{frame}

\begin{frame}{Performance of Multiset Authentication Protocols}
  \begin{table}
    \centering
    \footnotesize
    \begin{minipage}[b]{\linewidth}
      \centering
      \begin{tabular}{lccccc}
        \toprule
        \multirow{3}{*}{Algorithm} & \multicolumn{3}{c}{SP CPU Time (s)} &
        \multirow{3}{*}{\tabincell{c}{Client\\CPU Time\\(ms)}}  &
        \multirow{3}{*}{\tabincell{c}{VO\\Size\\(Bytes)}} \\
                                                                & \multicolumn{3}{c} {\# Features per Multiset} &  & \\
                                                                \cmidrule{2-4}
                                                                &100 & 1,000 & 10,000 &  &  \\
                                                                \midrule
        $sub(\cdot, \cdot)$ & 0.03 & 0.5 & 16 & 2 & 384 \\
        $sum(\cdot)$  & 0.04 & 0.4 & 3.6 & 5 & 384 \\
        $union(\cdot)$  & 0.1 & 1.3 & 33 & 20 & 1,024 \\
        $empty(\cdot)$  & 0.04 & 0.5 & 16  & 5 & 512\\
        $times(\cdot, 10)$ & 0.4 & 4.1 & 43 & 20 & 640  \\
        \bottomrule
      \end{tabular}
      \caption{Performance vs. \# Features}
    \end{minipage}
    \begin{minipage}[b]{.5\linewidth}
      \centering
      \begin{tabular}{lcccc}
        \toprule
        \multirow{3}{*}{Algorithm} & \multicolumn{4}{c}{SP CPU Time (s)}  \\
                                   & \multicolumn{4}{c} {\# Multisets}  \\
                                   \cmidrule{2-5}
                                   & 5 & 10 &20  & 50 \\
                                   \midrule
        $sum(\cdot)$   & 0.1 & 0.3 & 1.4  & 8.3\\
        $union(\cdot)$   & 0.4 & 2.6 & 18 & 240 \\
        $empty(\cdot)$   & 0.01 & 0.01  & 0.01  & 0.01\\
        \bottomrule
      \end{tabular}
      \caption{Performance vs. \# Multisets}
    \end{minipage}~%
    \begin{minipage}[b]{.5\linewidth}
      \centering
      \begin{tabular}{lcccc}
        \toprule
        \multirow{3}{*}{Algorithm} & \multicolumn{4}{c}{SP CPU Time (s)}  \\
                                   & \multicolumn{4}{c} {\# Unique Features}  \\
                                   \cmidrule{2-5}
                                   &50 & 100 & 200 &500   \\
                                   \midrule
        $union(\cdot)$  & 0.14 & 0.26 & 0.33 &  0.39 \\
        \bottomrule
      \end{tabular}
      \caption{Performance of $union(\cdot)$ vs. \# Unique Features}
    \end{minipage}
  \end{table}
\end{frame}

\begin{frame}{Optimizations of Authenticating Queries with Fine-Grained Access Control}
  \begin{itemize}
    \item \alert{General Optimizations}:
      \begin{itemize}
        \item Hierarchical Role Assignment
        \item Parallelism
      \end{itemize}
    \item \alert{Relaxing Zero-Knowledge Requirement}:
      \begin{figure}
        \begin{subfigure}[b]{.5\linewidth}
          \centering
          \resizebox{\linewidth}{!}{\input{figs/access-control/access-kd-tree.tex}}
          \caption{Structure}
        \end{subfigure}~%
        \begin{subfigure}[b]{.5\linewidth}
          \centering
          \resizebox{\linewidth}{!}{\input{figs/access-control/access-kd-tree-index.tex}}
          \caption{Index}
        \end{subfigure}
        \caption{Access-Policy-Preserving $k$-d-Tree (AP$^2k$d-Tree)}
      \end{figure}
  \end{itemize}
\end{frame}

\begin{frame}{Sort Tile Recursive~\cite{10.1109/ICDE.1997.582015}}
  \begin{figure}
    \includegraphics[height=0.4\textheight]{figs/knn/str.png}
    \caption{Example of Sort Tile Recursive}
  \end{figure}

  \begin{itemize}
    \item Ensure each partition has the same number of objects
    \item Two rounds:
      \begin{itemize}
        \item partition space vertically to multiple slices
        \item partition each slice horizontally
      \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}{Optimizations of Distributed kNN Authentication}
  \begin{figure}
    \includegraphics[height=0.4\textheight]{figs/knn/optimize.pdf}
    \caption{Example of optimization of VO size}
  \end{figure}

  \begin{itemize}
    \item Larger \emph{rcircle} $\Rightarrow$ Points visited unnecessarily $\Rightarrow$ Larger VO
    \item CSlaves execute range queries \alert{sequentially}
    \item Reduce \emph{rcircle} in each iteration
  \end{itemize}
\end{frame}

\begingroup
\setbeamertemplate{frametitle continuation}{}
\begin{frame}[t,allowframebreaks]{\refname}
  \bookmark[page=\thepage,startatroot]{\refname}
  \setbeamertemplate{bibliography item}[text]
  \renewcommand*{\bibfont}{\scriptsize}
  \printbibliography[heading=none]%
\end{frame}
\endgroup

\end{document}