diapo_qcrypt.tex

\documentclass[table]{beamer}

%% Good expressions:
%% UBQC: include rotated qubits in the graph
%% Measure n-1 qubits

%% Sécurité: blindness of the output (theta hidden)

\input{includes.tex}
\usepackage{blindtext, multicol}
\usepackage{MyMnSymbol}

% \usepackage{thmtools}
% \let\definition\relax
% \declaretheorem[name=Definition]{definition}
% \declaretheorem[name=Theorem]{theorem}
% \declaretheorem[name=Lemma,sibling=theorem]{lemma}


\setbeamerfont{subsection in toc}{size=\small}
\AtBeginSection[]
{
  % \begin{frame}<beamer>
  %   \frametitle{Plan}
  %   \tableofcontents[currentsection]
  % \end{frame}
}

\defbeamertemplate*{footline}{shadow theme}{%
  \leavevmode%
  \hbox{\begin{beamercolorbox}[wd=.5\paperwidth,ht=2.5ex,dp=1.125ex,leftskip=.3cm plus1fil,rightskip=.3cm]{author in head/foot}%
      \usebeamerfont{author in head/foot}\hfill\insertshortauthor
    \end{beamercolorbox}%

    \begin{beamercolorbox}[wd=.5\paperwidth,ht=2.5ex,dp=1.125ex,leftskip=.3cm,rightskip=.3cm plus1fil]{title in head/foot}%
      \usebeamerfont{title in head/foot}\insertshorttitle\hfill%
      \insertframenumber\,/\,\inserttotalframenumber
    \end{beamercolorbox}}%
  \vskip0pt%
}

% Bigger margin
\newcommand\Wider[2][3em]{%
\makebox[\linewidth][c]{%
  \begin{minipage}{\dimexpr\textwidth+#1\relax}
  \raggedright#2
  \end{minipage}%
  }%
}

\title[QFactory and classical blind quantum computing]{QCrypt 2018:\\On the possibility of classical client blind quantum computing}
\author[A. Cojocaru, L. Colisson, E. Kashefi, P. Wallden]{Alexandru Cojocaru, \underline{Léo Colisson},\\ Elham Kashefi, Petros Wallden}
% \institute{École Normale Supérieure (ENS) Paris-Saclay, Département Informatique\\Laboratory for Foundations of Computer Science, University of Edinburgh,\\sous la direction d'Elham Kashefi}

\begin{document}
% ==================================================

\begin{frame}
  \titlepage
\end{frame}
% ==================================================

% \begin{frame}
%   \tableofcontents
% \end{frame}

% ==================================================

\section{Motivations}

\subsection{Main Goal}

\begin{frame}{Robin Hood}
  \begin{figure}[ht]
    \centering
    \includegraphics[width=.8\textwidth]{figures/robin_hood.png}
  \end{figure}
\end{frame}


\begin{frame}{Main Goal}
  \begin{figure}[ht]
    \centering
    \includepdfpages{figures/slides_qfactory/goal.pdf}
    \caption{(Blind) Quantum Computing}
  \end{figure}
\end{frame}

% \subsection{Motivations}

% \begin{frame}{Motivations: Why classical client?}
%   \begin{figure}[ht]
%     \centering
%     \begin{tikzpicture}
%       \node(money) {\includegraphics[height=.5\textheight]{figures/money.png}};
%       \node[right=1cm of money] {\includegraphics[height=.5\textheight]{figures/bad_plug.png}};
%     \end{tikzpicture}
%   \end{figure}
% \end{frame}

\subsection{UBQC in a nutshell}

\begin{frame}{Our solution}
  \begin{figure}[ht]
    \centering
    \begin{tikzpicture}
      \node[align=center] (ubqc) {Universal Blind Quantum Computing (UBQC)\\{[A. Broadbent, J. Fitzsimons, E. Kashefi]}};
      \node[below=1mm of ubqc,scale=2] (plus) {+};
\node[below=1mm of plus, rounded corners,fill=blue!50,inner sep=2pt,label={[blue!60]below:QFactory}] (factory) {\includegraphics[width=15mm]{figures/factory.png}};
    \end{tikzpicture}
  \end{figure}
\end{frame}

\begin{frame}{UBQC in a nutshell}
  \begin{figure}[ht]
    \centering
    \includepdfpages{figures/slides_ubqc_nutshell/slides_ubqc_nutshell.pdf}
  \end{figure}
\end{frame}

\begin{frame}{UBQC in a nutshell}
  \begin{figure}[ht]
    \centering
        \includepdfpages{figures/slides_ubqc_nutshell/slides_ubqc_nutshell_alice_bob.pdf}
  \end{figure}
\end{frame}

\section{QFactory}

\subsection{Description of the QFactory gadget}

\begin{frame}{QFactory: description}
  \begin{figure}[ht]
    \centering
    \includepdfpages{figures/slides_qfactory/replacement.pdf}
    \caption{QFactory gadget: simulate quantum channel}
  \end{figure}
\end{frame}


\begin{frame}{QFactory: description}
  \begin{figure}[ht]
    \centering
    \includepdfpages{figures/slides_qfactory/ideal_functionality.pdf}
    \caption{QFactory: ideal functionality}
  \end{figure}
\end{frame}

\subsection{Cryptographic assumptions}

\begin{frame}{Cryptographic assumptions}
  \begin{figure}[ht]
    \centering
    \includepdfpageswidth{\linewidth}{figures/slides_qfactory/cryptographic_assumptions.pdf}
  \end{figure}
\end{frame}

\subsection{Construction}

\begin{frame}[t]{Construction}%
  \vspace{-6mm}%
  \begin{columns}
    \column{\dimexpr\paperwidth-10pt}
    \begin{figure}[ht]
      \centering
      \includepdfpageswidth{1\textwidth}{figures/slides_qfactory/protocol_explanation.pdf}
    \end{figure}
  \end{columns}
\end{frame}

\section{Security}

% \subsection{Hidden GHZ State and $\theta$}
% \begin{frame}[t]{Hidden GHZ State and $\theta$}
%   \begin{figure}[ht]
%     \centering%
%     \foreach \x in {1,2,3,4}{%
%       \only<\x>{\includegraphics[width=.6\textwidth]{figures/ghz_\x.pdf}}%
%     }%
%   \end{figure}
% \end{frame}

% \begin{frame}{Intuition security}
%   TODO: Intuition security, PostBQP...
% \end{frame}

\subsection{Hardcore function and Honest-but-curious model}
\begin{frame}[t]{Hardcore function and Honest-but-curious model}
  \begin{columns}
    \begin{column}{.5\textwidth}
    \begin{figure}[ht]
      \centering
      \begin{tikzpicture}
        \node[draw,rectangle,rounded corners,align=center,text width=2.5cm,minimum height=2.5cm,fill=blue!30] (adv) {Adversary};
        \coordinate (m) at ($(adv.north west)!.5!(adv.south west)$);
        \draw[arrows = {-Stealth[scale=1]}] ([xshift=-2cm]m) -- (m)
        node[midway,above,scale=.75] (ky) {$k,y,(\alpha_i),(b_i)$};
        \draw[arrows = {-Stealth[scale=1]}, double distance=1.5pt] (adv.south) -- ([yshift=-1cm]adv.south)
        node[below] (thetaprime) {$\theta'$};
        \node[inner sep=0pt, right=0pt of thetaprime,yshift=2pt] {$\overset{?}{=} \theta$};
        % Center the picture
        % \coordinate () at ;
        \path[] (adv.north east) -- ([xshift=3cm]adv.north east);
      \end{tikzpicture}%
    \end{figure}
    Cannot be better than random guess: $\theta$ \textbf{hard-core} function.
  \end{column}%
  % 
  \begin{column}{.5\textwidth}
    \begin{exampleblock}{Security}
     Blindness of the output $\theta$. \\
      Corollary: QFactory is secure in the
      honest-but-curious model.\\
      If adversary:
      \begin{itemize}
      \item follows the protocol
      \item can only access classical registers
      \end{itemize}
      $\Rightarrow $ he cannot determine $\theta$
    \end{exampleblock}
  \end{column}
\end{columns}
\end{frame}


\subsection{Intuition of proof}
\begin{frame}{Intuition of proof}
$\theta$ is a hardcore function: proof based on Goldreich-Levin Theorem:
\begin{theorem}
If f is a one-way function, then the predicate $hc(\textcolor{red}{x}, \textcolor{green!60!black}{r}) = \sum \textcolor{red}{x_i} \textcolor{green!60!black}{r_i} \bmod 2$ cannot be distinguished from a random bit, given \textcolor{green!60!black}{$r$} and $\textcolor{blue!60!black}{f(x)}$. 
\end{theorem}
Recall, in our case: \textcolor{blue!60!black}{$f(x) \approx y$} and\\
$$ \theta \approx \sum \underbrace{\textcolor{red}{(x_i - x_i')}}_{\substack{\text{Unknown} \\ \text{to server}}} \underbrace{\textcolor{green!60!black}{(4b_i + \alpha_i)}}_{\substack{\text{Known} \\ \text{to server}}}\mod 8$$
\end{frame}


% TODO: Compare work Urmila
\section{}
\begin{frame}{Summary and future work}
  \begin{block}{Summary}
    \begin{minipage}{.6\linewidth}
      \begin{itemize}
      \item QFactory: simulate quantum channel from classical channel
      \item \tcancel{quantum client} $\rightarrow$ classical clients
      \item For now, proof in honest-but-curious model
      \end{itemize}      
    \end{minipage}%
    \begin{minipage}{.4\linewidth}
      \includegraphics[width=\textwidth]{figures/money_fille.jpeg}        
    \end{minipage}
  \end{block}
  \begin{exampleblock}{Future work}
    \begin{itemize}
    \item Improve proof of security against fully malicious adversary
    \item Improve efficiency in blind computing
    \item Explore new possible applications, certified qubits (QFactory + Zero Knowledge proof) that could improve MPC, GHZ state\dots\dots
    \end{itemize}
  \end{exampleblock}
\end{frame}

% \subsection{Applications of QFactory}

\begin{frame}{Applications of QFactory}
  \begin{figure}[ht]
    \centering
    \scalebox{.7}{
      \begin{tikzpicture}[rotate=-90]
        \colorlet{color min hsb}[hsb]{red}
        \colorlet{color max hsb}[hsb]{magenta}
        \def\bl{90}
        \colorlet{colorA}[rgb]{color max hsb!0!color min hsb!\bl!black}
        \colorlet{colorB}[rgb]{color max hsb!17!color min hsb!\bl!black}
        \colorlet{colorC}[rgb]{color max hsb!33!color min hsb!\bl!black}
        \colorlet{colorD}[rgb]{color max hsb!50!color min hsb!\bl!black}
        \colorlet{colorE}[rgb]{color max hsb!67!color min hsb!\bl!black}
        \colorlet{colorF}[rgb]{color max hsb!83!color min hsb!\bl!black}
        \colorlet{colorG}[rgb]{color max hsb!100!color min hsb!\bl!black}

        % \colorlet{colorA}[rgb]{color max hsb!0!color min hsb!\bl!black}
        % \colorlet{colorB}[rgb]{color max hsb!20!color min hsb!\bl!black}
        % \colorlet{colorC}[rgb]{color max hsb!40!color min hsb!\bl!black}
        % \colorlet{colorD}[rgb]{color max hsb!60!color min hsb!\bl!black}
        % \colorlet{colorE}[rgb]{color max hsb!80!color min hsb!\bl!black}
        % \colorlet{colorF}[rgb]{color max hsb!100!color min hsb!\bl!black}

        \path[mindmap,
          every node/.style={concept, circular drop shadow,execute at begin node=\hskip0pt},
          concept color=black,text=black,font=\bfseries,
          grow cyclic,
          root concept/.append style={
            concept color=black, fill=white, line width=1ex, text=black,
            font=\large\scshape},
          level 1 concept/.append style={sibling angle=180/6}]
        
        node[concept, root concept] {Simulate quantum channel}
        child[concept color=colorA] {
          node[concept] {Delegated computing}
          child { node[concept] {Blind} }
          child { node[concept] {Verifiable} }
        }  
        child[concept color=colorB] {
          node[concept] {Multi-Party Computing}
        }
        child[concept color=colorC] {
          node[concept] {Quantum money}
        }
        child[concept color=colorD] {
          node[concept] {Quantum signature}
        }
        child[concept color=colorE] {
          node[concept] {Key distribution}
        }
        child[concept color=colorF] {
          node[concept] {Certified qubit}
        }
        child[concept color=colorG] {
          node[concept] {???}
        };
      \end{tikzpicture}
    }
  \end{figure}
\end{frame}

\begin{frame}{Questions}
  \begin{columns}
    \column{\dimexpr\paperwidth}
    \begin{center}
      Thank you for your attention!\\
    \end{center}
    % Questions?\\
    \begin{figure}[ht]
      \centering
      \includegraphics[width=.8\textwidth]{figures/millionnaire.png}
    \end{figure}
    \begin{center}
% \vspace{2cm}
    \href{https://arxiv.org/abs/1802.08759}{arxiv.org/abs/1802.08759}
    \end{center}
    \end{columns}
\end{frame}

\begin{frame}[noframenumbering]{Function construction}
  \begin{figure}[ht]
    \centering
    \includegraphics[width=.8\textwidth]{figures/example_dimension2.pdf}
  \end{figure}
  $$f_{A,y}((s,e),c) = Ax + e + c \times y$$
\end{frame}

\begin{frame}[noframenumbering]{Comparison with other works}
  \begingroup
  \fontsize{10pt}{10pt}\selectfont
  \begin{table}%
    \def\colorsure{green!50!black}
    \def\colorhonnest{green}
    \def\colornoproof{yellow}
    \def\colornotpossible{red}
    \newcommand\Tstrut{\rule{0pt}{2.6ex}}       % "top" strut
    \newcommand\Bstrut{\rule[-0.9ex]{0pt}{0pt}} % "bottom" strut
    \newcommand{\TBstrut}{\Tstrut\Bstrut} % top&bottom struts
    \begin{tabularx}{\linewidth}{ | c | X | X | X |}
      \hline
      Paper                   & \tiny Classical Homomorphic Encryption for Quantum Circuits & \tiny On the possibility of blind quantum computing & \tiny  Classical Verification of Quantum Computations \TBstrut\\
      \hline
      Blind input             & \cellcolor{\colorsure}                                      & \cellcolor{\colorhonnest}                           & \cellcolor{\colornoproof}                             \TBstrut\\
      \hline
      Blind algorithm         & \cellcolor{\colornoproof}                                   & \cellcolor{\colorhonnest}                           & \cellcolor{\colornoproof}                             \TBstrut\\
      \hline
      Verifiability           & \cellcolor{\colornotpossible}                               & \cellcolor{\colornoproof}                           & \cellcolor{\colorsure}                                \TBstrut\\
      \hline
      Non-Interactive         & \cellcolor{\colorsure}                                      & \cellcolor{\colornotpossible}                       & \cellcolor{\colornotpossible}                         \TBstrut\\
      \hline
      Efficiency/Requirements & FHE                                                         & UBQC/VBQC, Linear                                   & Post-hoc, poly degree 9?                              \TBstrut\\
      \hline
    \end{tabularx}
  \end{table}
  \endgroup
\end{frame}

\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: