alex-retrieval/pres/pres.tex

\documentclass{beamer}
\setbeamertemplate{note page}[plain]
\usetheme[progressbar=frametitle]{metropolis}

\usepackage{pgfpages}
\usepackage[final]{pdfpages}
%\setbeameroption{show notes on second screen=right}


\usepackage{dirtytalk}
\usepackage{setspace}
\usepackage[T1]{fontenc}
\usepackage[sfdefault,scaled=.85]{FiraSans}
%\usepackage{newtxsf}

\title{Private Information Retrieval}
\subtitle{Transfering data in a sneaky way}
\author{Casper Vestergaard Kristensen \and Thomas Carlsen \and Alexander Munch-Hansen}
\institute{Aarhus University}
\date{\today}

\begin{document}
\begin{frame}
\titlepage
\end{frame}

\begin{frame}
  \setbeamertemplate{section in toc}[sections numbered]
  \frametitle{Outline}
  \setstretch{0.5}
  \tableofcontents

\end{frame}

\section{Background}
\subsection{Introduction}
\begin{frame}
  \frametitle{What have we done?}
  \begin{itemize}
  \item We have implemented several protocols, which we will briefly discuss
  \item We have tested these protocols on multiple setups
    \begin{itemize}
    \item Changing server size
    \item Amount of databases
    \item The block size
    \end{itemize}
  \item We have benchmarked on the same parameters
  \item Reached the conclusion again, that oftentimes big-O notation won't give the most practical solution.
  \end{itemize}
\end{frame}

\subsection{Protocols}

\subsection{Blockification}
\begin{frame}
  \frametitle{Turning single-bit PIR into block schemes}
  \includegraphics[width=\textwidth]{graphics/blockProp.png}
  \begin{itemize}
  \item TLDR; Run the scheme blocksize amount of times, asking for consecutive bits is not ideal
  \end{itemize}
\end{frame}

\subsubsection{Simple}
\begin{frame}
  \frametitle{The most simple protocol}

  \begin{block}{}

    \begin{columns}[onlytextwidth,T]
      \column{\dimexpr\linewidth-40mm-5mm}

      \begin{itemize}
      \item Most simple PIR protocol
      \item Client has to send a total of $1$ bit and has to receive $n$ bits
      \item Server has to send $n$ bits and receive $1$ bit
      \item Client can then figure out what data he wants
      \end{itemize}
      \column{40mm}
      \includegraphics[width=40mm]{graphics/simple_protocol.png}

    \end{columns}
  \end{block}
  
\end{frame}

\subsubsection{XOR-based}
\begin{frame}
  \frametitle{Less simple protocol for $2$ databases}

  \begin{block}{}

    \begin{columns}[onlytextwidth,T]
      \column{\dimexpr\linewidth-50mm-5mm}
      \setstretch{0.9}
      \begin{itemize}
      \item Less simple PIR protocol
      \item Client has to worst case send $2n$ bits
        \begin{itemize}
        \item Expected is only on $n$ bits though
          \item Has to do quite a bit of work though, sampling randomness
        \end{itemize}
      \item Client receives only $1$ bit from each server though
      \item Server has to send $1$ bit and receive worst-case $2n$ bits
        \item Server has to compute a lot of XORs though
      \item Client can then XOR the results from the two servers
      \end{itemize}
      \column{60mm}
     
      \includegraphics[width=70mm]{graphics/less_simple_protocol.png}

    \end{columns}
  \end{block}
    
\end{frame}

\begin{frame}
  \frametitle{Improving the previous scheme!}
  \includegraphics[width=\textwidth]{graphics/balancedScheme.png}
\end{frame}

\begin{frame}
  \frametitle{Easy XOR-based block-version}
  \includegraphics[width=\textwidth]{graphics/XORBlock.png}
\end{frame}

\begin{frame}
  \frametitle{Computations of the XOR-based block-version}
  \includegraphics[width=\textwidth]{graphics/MathStuff.png}
\end{frame}

\section{Expected Results}
\begin{frame}
  \frametitle{Overall expected results}
  \begin{itemize}
  \item We expect the scheme before to perform the best
    \begin{itemize}
    \item The client has to sent less, so less bandwidth
    \item The client has to compute less
    \item But the server has to compute and send more, which is acceptable, as we expect server to be stronger than client
    \end{itemize}
  \item We expect the simple scheme of $2$ databases to be outperformed by the scheme where the server simply sends the entire database
    \begin{itemize}
    \item User sending data of expected size n
    \item Both server and user has to do XOR computations
      \end{itemize}
      \item We expect the Interpoly scheme to be the worst in all regards
  \end{itemize}
\end{frame}


\begin{frame}
  \frametitle{Interpoly scheme}
  Won't cover again, but expected to be worse:
  \begin{itemize}
  \item We have to send BigIntegers from client to server
  \item We have to send either all of the random sequences or the seed
    \begin{itemize}
    \item If sequences are sent, server does not have to compute, but heavy on bandwidth
      \item If seed is sent, low on bandwidth but the server also to compute the sequences
      \end{itemize}
      \item In general, all of the computations regarding the polynomials, are likely to slow down the response time of the servers
  \end{itemize}
\end{frame}



\section{Results}
\begin{frame}
  \frametitle{Initial Results}
  \begin{itemize}
  \item Booleans we like - much faster
  \item Storage issues
  \item Bit-vectors of length database are nice in theory
  \end{itemize}
\end{frame}

\begin{frame}
  \includegraphics[width=0.5\textwidth]{graphics/Fixed_8-bit_block_size.pdf}
  \includegraphics[width=0.5\textwidth]{graphics/Fixed_8-bit_block_size_log.pdf}
\end{frame}
\begin{frame}
  \includegraphics[width=0.5\textwidth]{graphics/Fixed_8-bit_block_size_-_simulated_1MiBs_tx,_5MiBs_rx.pdf}
  \includegraphics[width=0.5\textwidth]{graphics/Fixed_8-bit_block_size_-_simulated_1MiBs_tx,_5MiBs_rx_log.pdf}
\end{frame}




\section{Future Work}
\begin{frame}
  \frametitle{Future Work}
  \begin{itemize}
  \item Fixing database
  \item Implement networking
  \item Further optimise implementations
  \item Further improve benchmarking (i.e. find a more suitable set of metrics)
  \end{itemize}
\end{frame}

\section{Struggles}
\begin{frame}
  \frametitle{How real pain feels}
  \begin{itemize}
  \item Java
  \item Very poor papers
  \end{itemize}
\end{frame}

\section{Thank You!}

\end{document}