You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@pirk.apache.org by ra...@apache.org on 2016/09/20 15:36:56 UTC
incubator-pirk git commit: Move the math deck files into a named
directory for readability.
Repository: incubator-pirk
Updated Branches:
refs/heads/master 0e3ecc4d8 -> d2bf6a029
Move the math deck files into a named directory for readability.
Project: http://git-wip-us.apache.org/repos/asf/incubator-pirk/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-pirk/commit/d2bf6a02
Tree: http://git-wip-us.apache.org/repos/asf/incubator-pirk/tree/d2bf6a02
Diff: http://git-wip-us.apache.org/repos/asf/incubator-pirk/diff/d2bf6a02
Branch: refs/heads/master
Commit: d2bf6a029cb93a1f6f49e2705f25aa69aa7bf7a9
Parents: 0e3ecc4
Author: Walter Ray-Dulany <ra...@gmail.com>
Authored: Tue Sep 20 11:36:02 2016 -0400
Committer: Walter Ray-Dulany <ra...@gmail.com>
Committed: Tue Sep 20 11:36:02 2016 -0400
----------------------------------------------------------------------
contrib/ApachePirkCircle.png | Bin 23093 -> 0 bytes
contrib/ApachePirk_1.png | Bin 54992 -> 0 bytes
contrib/math_deck.tex | 970 ----------------------------
contrib/math_deck/ApachePirkCircle.png | Bin 0 -> 23093 bytes
contrib/math_deck/ApachePirk_1.png | Bin 0 -> 54992 bytes
contrib/math_deck/math_deck.tex | 970 ++++++++++++++++++++++++++++
contrib/math_deck/pirkImage.png | Bin 0 -> 54992 bytes
contrib/math_deck/random_number.png | Bin 0 -> 7457 bytes
contrib/pirkImage.png | Bin 54992 -> 0 bytes
contrib/random_number.png | Bin 7457 -> 0 bytes
10 files changed, 970 insertions(+), 970 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-pirk/blob/d2bf6a02/contrib/ApachePirkCircle.png
----------------------------------------------------------------------
diff --git a/contrib/ApachePirkCircle.png b/contrib/ApachePirkCircle.png
deleted file mode 100644
index 6742f6a..0000000
Binary files a/contrib/ApachePirkCircle.png and /dev/null differ
http://git-wip-us.apache.org/repos/asf/incubator-pirk/blob/d2bf6a02/contrib/ApachePirk_1.png
----------------------------------------------------------------------
diff --git a/contrib/ApachePirk_1.png b/contrib/ApachePirk_1.png
deleted file mode 100644
index 45805ea..0000000
Binary files a/contrib/ApachePirk_1.png and /dev/null differ
http://git-wip-us.apache.org/repos/asf/incubator-pirk/blob/d2bf6a02/contrib/math_deck.tex
----------------------------------------------------------------------
diff --git a/contrib/math_deck.tex b/contrib/math_deck.tex
deleted file mode 100644
index 370dadd..0000000
--- a/contrib/math_deck.tex
+++ /dev/null
@@ -1,970 +0,0 @@
-\documentclass{beamer}
-\usepackage[T1]{fontenc}
-\usepackage{amsmath}
-\usepackage{amssymb}
-\usepackage{amsthm}
-\usepackage{algorithm}
-\usepackage{varwidth}
-\usepackage{bm}
-\usepackage[noend]{algpseudocode}
-\usepackage{xspace}
-\usepackage{multirow}
-\usepackage{xcolor}
-\DeclareRobustCommand{\NAME}{Wideskies\xspace}
-\newcommand{\from}{\rightarrow}
-
-\algnewcommand{\algorithmicgiven}{\textbf{given }}
-\algnewcommand{\Given}{\algorithmicgiven}
-
-\algnewcommand{\algorithmicselect}{\textbf{select }}
-\algnewcommand{\Select}{\algorithmicselect}
-
-\algnewcommand{\algorithmicset}{\textbf{set }}
-\algnewcommand{\Set}{\algorithmicset}
-
-\algnewcommand{\algorithmiccompute}{\textbf{compute }}
-\algnewcommand{\Compute}{\algorithmiccompute}
-
-\algnewcommand{\algorithmicgoto}{\textbf{go to}}
-\algnewcommand{\Goto}[1]{\algorithmicgoto~\ref{#1}}
-
-\newcommand{\Z}{\ensuremath{\mathbf{Z}}}
-\newcommand{\zmodn}{\ensuremath{\Z/N\Z}}
-\newcommand{\zmodntunits}{\ensuremath{\left(\Z/N^{2}\Z\right)^{\times}}}
-\newcommand{\lcm}{\ensuremath{\text{lcm}}}
-
-\mode<presentation> { \usetheme{default} }
-
-\usepackage{graphicx}
-\usepackage{booktabs}
-\usepackage{array}
-\newcolumntype{L}[1]{>{\raggedright\let\newline\\\arraybackslash\hspace{0pt}}p{#1}}
-\newcolumntype{C}[1]{>{\centering\let\newline\\\arraybackslash\hspace{0pt}}p{#1}}
-\newcolumntype{R}[1]{>{\raggedleft\let\newline\\\arraybackslash\hspace{0pt}}p{#1}}
-
-\makeatletter
-\DeclareRobustCommand*{\&}{%
- \nfss@text{%
- \fontfamily{LinuxBiolinumT-TLF}%
- \selectfont
- \symbol{`\&}%
- }%
-}
-
-\usepackage{eso-pic}
-\beamertemplatenavigationsymbolsempty
-\setbeamertemplate{footline}[frame number]
-\newcommand\AtPagemyUpperLeft[1]{\AtPageLowerLeft{%
-\put(\LenToUnit{0.9\paperwidth},\LenToUnit{0.9\paperheight}){#1}}}
-
-\AtBeginSection[]{
- \begin{frame}
- \vfill
- \centering
- \begin{beamercolorbox}[sep=8pt,center,shadow=true,rounded=true]{title}
- \usebeamerfont{title}\insertsectionhead\par%
- \end{beamercolorbox}
- \vfill
- \end{frame}
-}
-\title[Apache Pirk Math
-Walkthrough]{\includegraphics[width=2.5in,keepaspectratio]{ApachePirk_1.png}\\ \bigskip Mathematics $\&$ Algorithms}
-
-\author{Walter Ray-Dulany}
-\institute[Apache Pirk]
-{
-\medskip
-\textit{raydulany@apache.org}
-}
-% I decided against a date. - Walter
-\date{}
-
-\begin{document}
-
-\begin{frame}
-\titlepage
-\end{frame}
-
-\AddToShipoutPictureFG{
- \AtPagemyUpperLeft{{\includegraphics[width=.5cm,keepaspectratio]{ApachePirkCircle.png}}}
-}
-
-\section{Introduction}
-
-\begin{frame}
-\frametitle{Pirk's Wideskies Algorithm}
- Pirk uses the Wideskies algorithm to accomplish scalable PIR.\\~\\
- This algorithm can be broken down into two distinct conceptual pieces:
- \begin{itemize}
- \item Paillier Encryption
- \item The Query-Response-Result algorithms
- \end{itemize}
- ~\\ Before we begin those however, we take a (happily brief) diversion into
- the language of the mathematics involved in this deck.
-\end{frame}
-
-
-\section{Language Preliminaries}
-\begin{frame}
- \frametitle{Language Preliminaries}
- The Paillier scheme employs a small amount of group theoretic notation. Let's
- go over that notation briefly.
-\end{frame}
-
-\begin{frame}
- \frametitle{Language Preliminaries}
- \begin{itemize}
- \item \zmodn: This is the group of integers modulo $N$; it can be thought of
- as all numbers $0\leq k < N$, with modular addition (e.g.\ for $N=5$,
- $1+7 \equiv 3\mod N$).\\~\\ This is a group under addition.\\~\\
- \item $(\zmodn)^\times$: This is the multiplicative group of integers modulo
- $N$, also called the units of $\zmodn$. Sometimes denoted
- $(\mathbf{Z}/N\mathbf{Z})^*$, this is the set of $0\leq k < N$ that are
- relatively prime to $N$ (that is, $k$ and $N$ share no factors, or
- equivalently the greatest common denominator ($\gcd$) of $k$ and $N$ is $1$). One
- can also think of this as the set of $k\in\zmodn$ such that there exists
- a $k^{-1}\in\zmodn$ with $k\cdot k^{-1} \equiv 1\mod N$.\\~\\
- This is a group under multiplication.
- \end{itemize}
-\end{frame}
-
-\begin{frame}
- \frametitle{Language Preliminaries}
-Using the above notation, we can see that
-\begin{equation*}
- \zmodntunits = \{0\leq k<N^2: \gcd(k,N^2) = 1\}.
-\end{equation*}~\\
-If $N$ happens to be an RSA modulus,
-$N=pq$, $p$ and $q$ primes, then $\zmodntunits$ is just all numbers between $0$
-(inclusive) and $N^2$ (exclusive) that are not divisible by either $p$ or
-$q$.
-\end{frame}
-
-\begin{frame}
- \frametitle{Language Preliminaries}
- \begin{itemize}
- \item Order In \zmodn: The order of an element $k\in\zmodn$ is the least integer $e$
- such that $e\cdot k = 0\mod N$.
- \item Order in \zmodntunits: The order of an element $a\in\zmodntunits$ is
- the least integer $e$ such that $a^e = 1\mod N^2$.
- \end{itemize}
- In both cases, order is well defined (i.e.\ it exists and makes sense) for
- all elements of the groups.
-\end{frame}
-
-\begin{frame}
- \frametitle{Language Preliminaries}
- For a more in depth discussion of these, and closely related, terms, please
- see
- \mbox{\scriptsize \url{http://www.math.nagoya-u.ac.jp/~richard/teaching/s2015/Group_2.pdf}}
-\end{frame}
-
-\section{Paillier Encryption}
-\begin{frame}
-\frametitle{Paillier Encryption}
-Paillier encryption is a partially homomorphic public key scheme that relies on
-the function $$\mathcal{E}_g:\zmodn\times(\zmodn)^\times\rightarrow
-\zmodntunits$$ given by $$\mathcal{E}_g(x,y) = g^x y^N \mod N^2,$$
-$g\in\zmodntunits$. Here, $\zmodn$ is the plaintext space and $\zmodntunits$ is
-the ciphertext space.\\~\\
-When the order of $g$ is a non-zero multiple of $N$, $\mathcal{E}_g$ is a bijection.
-\end{frame}
-
-\begin{frame}
- \frametitle{Paillier Prerequisites}
-\begin{itemize}
- \item Public key: $(N,g)$, $N$ an RSA modulus $N=pq$, $p$ and $q$ primes of
- approximately the same bit-length, and $g\in \zmodntunits$ such that the
- order of $g$ is a nonzero multiple of $N$.
- \item Private key: $\lambda(N)$, where $\lambda$ is the Carmichael function
- \begin{align*}
- \lambda(N) &= \lcm(p-1,q-1)
- \end{align*}
- that gives the exponent of $(\zmodn)^\times$.
- \item Plaintext space: \zmodn.
- \item Ciphertext space: \zmodntunits.
-\end{itemize}
-~\\
-{\footnotesize We can also consider the pair $(p,q)$ to be the private key, as $\lambda(N)$ is
-quickly and easily derived from it. Note that $\lambda(N)$ is coprime to $N$.}
-\end{frame}
-
-\begin{frame}
- \frametitle{What Do We Mean By `Homomorphic Encryption'?}
- An encryption scheme is fully homomorphic if it is a homomorphism from
- plaintext space to ciphertext space for arbitrary operations and arbitrary
- numbers of such operations. If this definition seems squishy and not very
- mathematical, that's because it is; it's hard to find a proper mathematical
- definition of this term.\\~\\
-
- An encryption scheme is partially homomorphic if it is a homomorphism for
- only some operations, or for only a few consecutive operations.\\~\\
-\end{frame}
-
-\begin{frame}
- \frametitle{Paillier Encryption is Homomorphic}
- Paillier encryption is a partial homomorphism between addition in \zmodn\ and
- multiplication in \zmodntunits.\\~\\
-
- Denote Paillier encryption by $\mathcal{E}_g$ and decryption by $\mathcal{D}_g$,
- and let $m$ and $m'\in \zmodn$. Then
- \begin{align*}
- D(\mathcal{E}(m) \mathcal{E}(m') \bmod N^2) &= (m + m') \bmod N \\
- D(\mathcal{E}(m)^k \bmod N^2) &= km \bmod N, \, k \in \mathbf{N}
- \end{align*}
- ~\\
- Note that the second equality follows immediately from the first.
-\end{frame}
-
-\section{General Paillier Algorithm}
-
-\begin{frame}
-\frametitle{Paillier Supporting Function}
-Let $X=\{u<N^2 : u = 1 \mod N\}$ and let $L:X\rightarrow \zmodn$ be
-defined by
-\begin{equation*}L(u) = \frac{u-1}{N} \mod N.\end{equation*}
-This function is well defined over \zmodntunits.
-\end{frame}
-
-\begin{frame}
-\frametitle{General Paillier Encryption}
-The general Paillier algorithm differs only slightly from Pirk's version.
-\begin{algorithm}[H]
- \caption{General Paillier encryption and decryption.}\label{alg.paillier_encrypt_original}
- \begin{algorithmic}[1]
- \Procedure{Paillier encryption}{}
- \State \begin{varwidth}[t]{\linewidth}
- \Given \(N\), a random \(g \in \zmodntunits\) of order a nonzero\par
- multiple of $N$, and a message \(m\in\zmodn\)
- \end{varwidth}
- \State \Select a random value \(\zeta\in \left(\zmodn\right)^{\times}\)
- \State \Return \(\mathcal{E}(m) = g^m \zeta^{N}\bmod{N^{2}}\)
- \EndProcedure
- \end{algorithmic}
- \begin{algorithmic}[1]
- \Procedure{Paillier decryption}{}
- \State \Given \(N\), \(\lambda(N)\), \(g\), and ciphertext \(c \in \zmodntunits\)
- \State \Return m = \(\frac{L( c^{\lambda(N)}\bmod N^{2})}{L( g^{\lambda(N)}\bmod N^{2})}\bmod N\)
- \EndProcedure
- \end{algorithmic}
-\end{algorithm}
-\end{frame}
-
-\begin{frame}
-\frametitle{Paillier Works}
- It is a straightforward exercise to check that
- \begin{itemize}
- \item $D(\mathcal{E}(m)) = m$
- \item $D(\mathcal{E}(m)\mathcal{E}(m')\bmod N^2) = (m + m') \bmod N $
- \end{itemize}
-\end{frame}
-
-\section{Paillier As Used In \NAME}
-\begin{frame}
-\frametitle{Paillier As Used In \NAME}
-The version of Paillier used in \NAME is a computationally simpler variant of the
-full Paillier scheme that sacrifices no security over the general case.
-\end{frame}
-
-\begin{frame}
- \frametitle{Converting Between The Two}
- Pirk's simplified version of Paillier simply uses
- \begin{align*}
- g &\equiv 1 + N \mod N^2\\
- \implies L(g^{\lambda(N)} \mod N^2) &= \lambda(N),
- \end{align*}
- the proof of which is a straightforward exercise.
-\end{frame}
-
-\begin{frame}
-\frametitle{Paillier As Used In \NAME}
-\begin{algorithm}[H]
- \caption{Paillier encryption and decryption}\label{alg.paillier_encrypt}
- \begin{algorithmic}[1]
- \Procedure{Paillier encryption}{}
- \State \Given \(N\) and a message \(m\in\zmodn\)
- \State \Select a random value \(\zeta\in\zmodntunits\)
- \State \Return \(\mathcal{E}(m) = (1+mN)\zeta^{N}\bmod{N^{2}}\)
- \EndProcedure
- \end{algorithmic}
-
- \begin{algorithmic}[1]
- \Procedure{Paillier decryption}{}
- \State \Given \(N\), \(\lambda(N)\), and a ciphertext \(c\in\zmodntunits\)
- \State \Set \(\mu = \lambda(N)^{-1}\bmod N\)
- \Comment Recall \(\gcd(\lambda(N), N) = 1\)
- \State \Set \(\hat{c} = c^{\lambda(N)}\bmod N^{2}\)
- \State\label{step.div}\Set \(\hat{m} = L(c^{\lambda(N)}\bmod N^{2})\)
- \State \Return \(\hat{m}\mu\bmod N\)
- \EndProcedure
- \end{algorithmic}
-\end{algorithm}
-\end{frame}
-
-\begin{frame}
- \frametitle{Paillier Reference}
- For more on Paillier encryption and the (hypothesized) hard problem upon
- which it is based, see\\~\\
- \mbox{\scriptsize \url{https://pirk.incubator.apache.org/papers/1999_asiacrypt_paillier_paper.pdf}}\\~\\
- on Pirk's website.
-\end{frame}
-
-\section{Wideskies}
-
-\begin{frame}
- \frametitle{Wideskies Parameters}
- The algorithm requires the following parameters, which are not independent
- (see the next slide).
- \begin{itemize}
- \item $N$, the Paillier modulus
- \item $B$, the bit-length of $N$
- \item $H$ (or $H_k$), a keyed hash function (with key k)
- \item $\ell$, the bit length of the output of $H$, i.e.\
- $H_k:\mathbf{Z}\rightarrow (\mathbf{Z}/2\mathbf{Z})^\ell$
- \item $\tau$, the number of search terms
- \item $\delta$, the number of bits of data returned for each search hit
- \item $b$ the chunk size, in bits, determining how data is split among
- responses.
- \item $r$, the number of responses that can be returned per query request
- period per search term
- \end{itemize}
-\end{frame}
-
-\begin{frame}
- \frametitle{Parameter Relationships}
- \begin{itemize}
- \item $2^{b\tau} < N$: there must be space in the modulus to hold all the
- data, even if each search term hits as often as possible.
- \item $\tau < 2^\ell$: Although the paper permits search term hash
- collisions, Pirk does not permit them. Typically $\tau \ll 2^\ell$
- \item $b|\delta$: Chunk size must evenly divide the data size
- \item $\frac{\delta}{b} | r$: the number of chunks per returned datum must
- divide the number of responses, for bandwidth efficiency.
- \item $H$: Must be pseudo-random but need not be cryptographically secure.
- \end{itemize}
-\end{frame}
-
-\begin{frame}
- \frametitle{Public Parameters}
- All of \begin{equation*}H, \ell, N, B, \delta, b, \text{and } r\end{equation*}
- are public, that is, must be shared between the client and server.\\~\\
-
- Note that the fact that $2^{b\tau} < N$ gives some information on the number
- of search terms the client is using; the amount of this information can be
- decreased without bound by choosing $N$ and $\ell$ to be much larger than
- would be otherwise necessary; this necessarily causes a performance hit.
-\end{frame}
-
-\section{Wideskies Algorithm, Without Encryption}
-\begin{frame}
- \frametitle{Wideskies Without Encryption?}
- The Wideskies algorithm is of sufficient complexity that it can be useful to
- go through the algorithm without the encryption and decryption steps first,
- in order to orient ourselves.\\~\\
- After, it will be straightforward to see the
- changes that using the Paillier encryption requires.
-\end{frame}
-
-\section{Query, Without Encryption}
-\begin{frame}
- \frametitle{The Query Algorithm, Without Encryption}
- Let $T_0,\ldots,T_{\tau-1}\in\zmodn$ be our search terms.
- \begin{algorithm}[H]
- \caption{Query Formation Algorithm version
- 1}\label{alg.plain_form_1}
-\begin{algorithmic}[1]
- \State\label{step.key}Choose a random key \(k\) for \(H\).
- \State Compute \(H_{k}(T_{0}),\ldots,H_{k}(T_{\tau-1})\).
- \While{\(\mathrm{card}\left(\{H_{k}(T_{0}),\ldots,H_{k}(T_{\tau-1})\}\right)
- < \tau\)}
- \State \Goto{step.key}
- \Comment If there are hash collisions, pick a new key.
- \EndWhile
- \For{\(i=0,\ldots,2^{\ell}-1\)}
- \State\label{step.set}Set \begin{equation*}
- E_{i} = \left\{\begin{array}{l l}
- 2^{jb} & \mbox{ if } i = H_{k}(T_{j}); \\
- 0 & \mbox{otherwise.}
- \end{array}
- \right.
- \end{equation*}
- \EndFor
- \State\Return \(\{E_{0},\ldots,E_{2^{\ell}-1}, H, k, N\}\)
-\end{algorithmic}
-\end{algorithm}
-\end{frame}
-
-\begin{frame}
- \frametitle{Query Notes, Without Encryption}
- Since $\tau \ll 2^\ell$, we expect most of the $E_i$ to be zero.\\~\\
- We will typically denote $H_k(T)$ by $\mathcal{T}$ and its associated $E$ by
- $E_\mathcal{T}$. If we wish to keep track of a specific $T$ we will write
- $\mathcal{T}_j$ and $E_{\mathcal{T}_j}$.
-\end{frame}
-
-\section{Response, Without Encryption}
-\begin{frame}
- \frametitle{Response Initialization, Without Encryption}
- We must initialize some values before forming the response.
- \begin{enumerate}
- \item $c_0,\ldots,c_{2^\ell - 1} = 0$, counters to keep track of the number
- of times each $E_\mathcal{T}$ has been seen.
- \item $Y_0,\ldots,Y_{r-1} = 0$, response vectors.
- \end{enumerate}
-\end{frame}
-
-\begin{frame}
- \frametitle{Response Data, Without Encryption}
- Responder information comes in pairs $(T, D)$ where $T$ is a (potential)
- search term, and $D$ is $T$'s associated response datum, which will be
- returned if $T$ is a search term.\\~\\
-
- We view $D$ as a $\delta$-long bit stream $(d_0,\ldots,d_{\delta-1})$, and
- break $D$ up into $\delta/b$ chunks $D_i$ as
- \begin{equation*}
- D_i = (d_{i\cdot b}, d_{i\cdot b+1},\ldots,d_{(i+1)\cdot b-1}),\ i=0,\ldots,\delta/b-1.
- \end{equation*}\\~\\
- For example, if $D=011010$ and $b=3$, then
- \begin{align*}
- D_0 &= 011\\
- D_1 &= 010
- \end{align*}
-\end{frame}
-
-\begin{frame}
- \frametitle{Response Algorithm, Without Encryption}
- \begin{algorithm}[H]
- \caption{Stream processing, plaintext version}\label{alg.plain_stream}
-\begin{algorithmic}[1]
-\State \textbf{Input}: $\mathbf{T} = \{ (T,D) \}$
-\For{$(T,D) \in \mathbf{T}$}
- \State Compute \(\mathcal{T} = H_{k}(T)\)
- \If{\(c_{\mathcal{T}} + \frac{\delta}{b} > r\)}\label{step.if}
- \Comment The space allocated for term \(T\) is full.
- \State \Return \label{step.return}
-\Else
- \State Split \(D\) into \(b\)-bit chunks
- \(D_{0},\ldots,D_{(\delta/b)-1}\).
- \For{\(i=0,\ldots,(\delta/b)-1\)}
- \State\label{step.multiply}Set \(\mathcal{D}_{i} = D_{i}E_{\mathcal{T}}\bmod N\)
- \Comment Nonzero only if \(E_{\mathcal{T}}\neq 0\).
- \State Set \(Y_{i+c_{\mathcal{T}}} =
- Y_{i+c_{\mathcal{T}}}+\mathcal{D}_{i}\bmod N\)
- \EndFor
- \State Set \(c_{\mathcal{T}} = c_{\mathcal{T}}+(\delta/b)\)
-\EndIf
-
-\EndFor
-\State{\textbf{Output}}: \(Y_{0},\ldots,Y_{r-1}\)
-\end{algorithmic}
-\end{algorithm}
-\end{frame}
-
-\begin{frame}
- \frametitle{Response Example, Without Encryption}
- Let's look at how the response would look on the first four $(T,D)$ pairs that
- pass through the algorithm.
-\end{frame}
-
-\begin{frame}
- \frametitle{Response Example Setup, Without Encryption}
- Suppose that among our search terms are $T$ and $T'$, with
- \begin{align*}
- H_k(T) &= j\text{ and}\\
- H_k(T') &= j'.
- \end{align*}~\\
-
-
- Suppose that $T''$, with $H_k(T'')=j''$, is \emph{not} a search term.\\~\\
-
- Let the responder see, in order, the pairs $(T, D^0)$, $(T', D^1)$,
- $(T'', D^2)$, $(T, D^3)$.\\~\\
-
- The $Y_i$ are formed by summing down the columns in following matrices.
-\end{frame}
-
-\begin{frame}
- \frametitle{Response Example Start, Without Encryption}
- No terms have yet been evaluated.
- \begin{center}
- \begin{tabular}{c C{1.55cm} c C{1.55cm} C{1.55cm} c C{1.55cm} }
- {\scriptsize Index} & $Y_0$\qquad & $\cdots$\qquad & $Y_{\delta/b-1}$\qquad & $Y_{\delta/b}$\qquad & $\cdots$\qquad & $Y_{2\delta/b-1}$\qquad\\\toprule
- $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
- {\footnotesize$j$} & 0 & $\cdots$ & 0 & 0 & $\cdots$ & 0 \\
- $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
- {\footnotesize$j'$} & 0 & $\cdots$ & 0 & 0 & $\cdots$ & 0\\
- $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
- {\footnotesize$j''$} & 0 & $\cdots$ & 0 & 0 & $\cdots$ & 0\\
- $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\\bottomrule
- \end{tabular}
- \end{center}
- $c_{j} = 0$, $c_{j'} = 0$, $c_{j''} = 0$.
-\end{frame}
-
-\begin{frame}
- \frametitle{Response Example: First Term, Without Encryption}
- $(T, D^0)$ enters and is proccessed; hit:
- \begin{center}
- \begin{tabular}{c C{1.55cm} c C{1.55cm} C{1.55cm} c C{1.55cm} }
- {\scriptsize Index} & $Y_0$\qquad & $\cdots$\qquad & $Y_{\delta/b-1}$\qquad & $Y_{\delta/b}$\qquad & $\cdots$\qquad & $Y_{2\delta/b-1}$\qquad\\\toprule
- $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
- {\footnotesize$j$} & {\footnotesize $\bm{D^0_0} 2^{jb}$} & $\cdots$ & {\footnotesize $\bm{D^0_{\delta/b-1}} 2^{jb}$} & 0 & $\cdots$ & 0 \\
- $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
- {\footnotesize$j'$} & 0 & $\cdots$ & 0 & 0 & $\cdots$ & 0\\
- $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
- {\footnotesize$j''$} & 0 & $\cdots$ & 0 & 0 & $\cdots$ & 0\\
- $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\\bottomrule
- \end{tabular}
- \end{center}
- $\bm{c_{j} = \delta/b}$, $c_{j'} = 0$, $c_{j''} = 0$.
-\end{frame}
-
-\begin{frame}
- \frametitle{Response Example Second Term, Without Encryption}
- $(T', D^1)$ enters and is proccessed; hit:
- \begin{center}
- \begin{tabular}{c C{1.55cm} c C{1.55cm} C{1.55cm} c C{1.55cm} }
- {\scriptsize Index} & $Y_0$\qquad & $\cdots$\qquad & $Y_{\delta/b-1}$\qquad & $Y_{\delta/b}$\qquad & $\cdots$\qquad & $Y_{2\delta/b-1}$\qquad\\\toprule
- $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
- {\footnotesize$j$} & {\footnotesize ${D^0_0} 2^{jb}$} & $\cdots$ & {\footnotesize ${D^0_{\delta/b-1}} 2^{jb}$} & 0 & $\cdots$ & 0 \\
- $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
- {\footnotesize$j'$} & {\footnotesize $\bm{D^1_0} 2^{j'b}$} & $\cdots$ & {\footnotesize $\bm{D^1_{\delta/b-1}} 2^{j'b}$} & 0 & $\cdots$ & 0\\
- $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
- {\footnotesize$j''$} & 0 & $\cdots$ & 0 & 0 & $\cdots$ & 0\\
- $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\\bottomrule
- \end{tabular}
- \end{center}
- $c_{j} = \delta/b$, $\bm{c_{j'} = \delta/b}$, $c_{j''} = 0$.
-\end{frame}
-
-\begin{frame}
- \frametitle{Response Example Third Term, Without Encryption}
- $(T'', D^2)$ enters and is proccessed; no hit:
- \begin{center}
- \begin{tabular}{c C{1.55cm} c C{1.55cm} C{1.55cm} c C{1.55cm} }
- {\scriptsize Index} & $Y_0$\qquad & $\cdots$\qquad & $Y_{\delta/b-1}$\qquad & $Y_{\delta/b}$\qquad & $\cdots$\qquad & $Y_{2\delta/b-1}$\qquad\\\toprule
- $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
- {\footnotesize$j$} & {\footnotesize ${D^0_0} 2^{jb}$} & $\cdots$ & {\footnotesize ${D^0_{\delta/b-1}} 2^{jb}$} & 0 & $\cdots$ & 0 \\
- $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
- {\footnotesize$j'$} & {\footnotesize ${D^1_0} 2^{j'b}$} & $\cdots$ & {\footnotesize ${D^1_{\delta/b-1}} 2^{j'b}$} & 0 & $\cdots$ & 0\\
- $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
- {\footnotesize$j''$} & {\footnotesize $\bm{D^2_0} \cdot 0$} & $\cdots$ & {\footnotesize $\bm{D^2_{\delta/b-1}} \cdot 0$} & 0 & $\cdots$ & 0\\
- $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\\bottomrule
- \end{tabular}
- \end{center}
-$c_{j} = \delta/b$, $c_{j'} = \delta/b$, $\bm{c_{j''} = \delta/b}$.
-\end{frame}
-
-\begin{frame}
- \frametitle{Response Example Fourth Term, Without Encryption}
- $(T, D^3)$ enters and is proccessed; hit:
- \begin{center}
- \begin{tabular}{c C{1.55cm} c C{1.55cm} C{1.55cm} c C{1.55cm} }
- {\scriptsize Index} & $Y_0$\qquad & $\cdots$\qquad & $Y_{\delta/b-1}$\qquad & $Y_{\delta/b}$\qquad & $\cdots$\qquad & $Y_{2\delta/b-1}$\qquad\\\toprule
- $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
- {\footnotesize$j$} & {\footnotesize ${D^0_0} 2^{jb}$} & $\cdots$ & {\footnotesize ${D^0_{\delta/b-1}} 2^{jb}$} & {\footnotesize $\bm{D^3_0} 2^{jb}$} & $\cdots$ & {\footnotesize $\bm{D^3_{\delta/b-1}} 2^{jb}$} \\
- $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
- {\footnotesize$j'$} & {\footnotesize ${D^1_0} 2^{j'b}$} & $\cdots$ & {\footnotesize ${D^1_{\delta/b-1}} 2^{j'b}$} & 0 & $\cdots$ & 0\\
- $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
- {\footnotesize$j''$} & {\footnotesize $\bm{D^2_0} \cdot 0$} & $\cdots$ & {\footnotesize $\bm{D^2_{\delta/b-1}} \cdot 0$} & 0 & $\cdots$ & 0\\
- $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\\bottomrule
- \end{tabular}
- \end{center}
- $\bm{c_{j} = 2\delta/b}$, $c_{j'} = \delta/b$, $c_{j''} = \delta/b$.
-\end{frame}
-
-\section{Result, Without Encryption}
-\begin{frame}
- \frametitle{Result, Without Encryption}
- The algorithm for getting the results out of the response return is
- straightforward. To begin,\\~\\
- \begin{itemize}
- \item Write $Y_i = \sum_{k=0}^{\tau - 1} 2^{kb}P_{ki}$ in base $2^b$, where
- $P_{ki}$ is the value of the $k^{\text{th}}$ row in the
- $i^{\text{th}}$ column. Note each $P_{ki}$ is $b$-bits long, and therefore
- $Y_i < N$.
- \item $Y_i$ will have data on search term $T$ if and only if $T$ was
- seen $i+1$ times before the responder returned.
- \end{itemize}
-\end{frame}
-
-\begin{frame}
- \frametitle{Result Algorithm, Without Encryption}
- \begin{algorithm}[H]
-
- \caption{Data recovery, plaintext version}\label{alg.plain_recover}
-\begin{algorithmic}[1]
- \State Set \(M = 2^{j b}(2^{b}-1)\)
- \Comment $b$ $1$s left-shifted $jb$ places.
- \For{\(\eta=1,\ldots,(rb/\delta)\)}
- \Comment At most \(rb/\delta\) hits can be returned.
- \For{\(i=0,\ldots,(\delta/b)-1\)}
- \Comment Each hit uses \(\delta/b\) chunks.
- \State\label{step.mask}Set \(D_{i} = Y_{(\eta-1)(\delta/b)+i}\&M\)
- \Comment ``\(\&\)'' denotes bit-wise \texttt{AND}.
- \State\label{step.shift}Set \(D_{i} = D_{i}/2^{jb}\)
- \Comment Step \ref{step.mask} ensures \(2^{jb}\mid D_{i}\)
- \EndFor
- \State Set \(X_{\eta} = D_{0}\|D_{1}\|\ldots\|D_{(\delta/b)-1}\)
- \EndFor
- \State \Return \(X_{1},\ldots,X_{(rb/\delta)}\)
- \Comment the data corresponding to selector \(T_{j}\)
-\end{algorithmic}
-\end{algorithm}
-\end{frame}
-
-\section{Wideskies Algorithm, With Encryption}
-\begin{frame}
- \frametitle{Adding Encryption To The Mix}
- Adding encryption is straightforward. The following slides have the
- encryption-enabled algorithms, with the differences from the earlier slides
- in bold.
-\end{frame}
-
-\section{Query, Encrypted}
-\begin{frame}
- \frametitle{Query, Encrypted}
- \begin{algorithm}[H]
- \caption{Query formation, ciphertext version 1}\label{alg.cipher_form_1}
-\begin{algorithmic}[1]
- \State\label{step.key_2}Choose a random key \(k\) for \(H\).
- \State Compute \(H_{k}(T_{0}),\ldots,H_{k}(T_{\tau-1})\).
- \While{\(\mathrm{card}\left(\{H_{k}(T_{0}),\ldots,H_{k}(T_{\tau-1})\}\right)
- < \tau\)}
- \State \Goto{step.key_2}
- \EndWhile
- \For{\(i=0,\ldots,2^{\ell}-1\)}
- \State Set
- {
- \bfseries\boldmath
- \begin{equation*}
- \mathcal{E}_{i} = \left\{\begin{array}{l l}
- \mathcal{E}(2^{jb}) & \mbox{ if }i=H_{k}(T_{j})\mbox{ for some
- }j\in\{0,\ldots,\tau-1\} \\
- \mathcal{E}(0) & \mbox{ otherwise.}
- \end{array}
- \right.
- \end{equation*}}
- \EndFor
- \State \Return \(\{\mathcal{E}_{0},\ldots,\mathcal{E}_{2^{\ell}-1}, H,
- k, N\}\)
-\end{algorithmic}
-\end{algorithm}
-\end{frame}
-
-\section{Response, Encrypted}
-\begin{frame}
- \frametitle{Response Initialization, Encrypted}
- As before, we must initialize some values before forming the response.
- \begin{enumerate}
- \item $c_0,\ldots,c_{2^\ell - 1} = 0$, counters to keep track of the number
- of times each {\boldmath $\mathcal{E}_\mathcal{T}$} has been seen.
- \item {\bfseries\boldmath $Y_0,\ldots,Y_{r-1} = 1$, response vectors.}
- \end{enumerate}
-\end{frame}
-
-\begin{frame}
- \frametitle{Response, Encrypted}
- \begin{algorithm}[H]
- \caption{Stream processing, ciphertext version}\label{alg.cipher_processing}
-\begin{algorithmic}[1]
-\State \textbf{Input}: $\mathbf{T} = \{ (T,D) \}$
-\State \textbf{Initialize:}
-\State \qquad Counters $c_i = 0 \, , \, 0 \leq i \leq (2^l -1)$
-\State \qquad Paillier ciphertext values $\mathcal{Y}_{j} = 1 \, , \, 0 \leq j \leq (r-1)$
-\For{$(T,D) \in \mathbf{T}$}
- \State Compute \(\mathcal{T} = H_{k}(T)\)
- \If{\(c_{\mathcal{T}}+\frac{\delta}{b} > r\)}
- \State \Return
- \Else
- \State Split \(D\) into \(b\)-bit chunks,
- \(D=D_{0},\ldots,D_{(\delta/b)-1}\) \label{step.datachunk}
- \For{\(i=0,\ldots,(\delta/b)-1\)}
- \State {\bfseries\boldmath Set \(\mathcal{D}_{i} =
- \mathcal{E}_{\mathcal{T}}^{D_{i}}\bmod N^{2}\)}
- \State {\bfseries\boldmath Set \(\mathcal{Y}_{i+c_{\mathcal{T}}} =
- \mathcal{Y}_{i+c_{\mathcal{T}}}\mathcal{D}_{i}\bmod N^{2}\)}
- \EndFor
- \State Set \(c_{\mathcal{T}} = c_{\mathcal{T}}+(\delta/b)\)
- \EndIf
-\EndFor
-\State{\textbf{Output}}: \(\mathcal{Y}_{0},\ldots,\mathcal{Y}_{r-1}\)
-\end{algorithmic}
-\end{algorithm}
-\end{frame}
-
-\section{Result, Encrypted}
-\begin{frame}
- \frametitle{Result, Encrypted (and then Decrypted)}
- Actually literally the same algorithm as before is used; the only difference
- is that we first decrypt the encrypted $\mathcal{Y}_i$.
-\end{frame}
-
-\section{Distributed Version}
-\begin{frame}
- \frametitle{Distributed Version}
- The paper goes over how to do the distributed version; the change is
- straightforward, and our earlier example slides make it easy to see how it
- works.
-\end{frame}
-
-\begin{frame}
- \frametitle{Distributed Difference:\\ Unencrypted Sums, Encrypted Products}
- Recall our example matrix:
- \begin{center}
- \begin{tabular}{c C{1.55cm} c C{1.55cm} C{1.55cm} c C{1.55cm} }
- {\scriptsize Index} & $Y_0$\qquad & $\cdots$\qquad & $Y_{\delta/b-1}$\qquad & $Y_{\delta/b}$\qquad & $\cdots$\qquad & $Y_{2\delta/b-1}$\qquad\\\toprule
- $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
- {\footnotesize$j$} & {\footnotesize ${D^0_0} 2^{jb}$} & $\cdots$ & {\footnotesize ${D^0_{\delta/b-1}} 2^{jb}$} & {\footnotesize ${D^3_0} 2^{jb}$} & $\cdots$ & {\footnotesize ${D^3_{\delta/b-1}} 2^{jb}$} \\
- $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
- {\footnotesize$j'$} & {\footnotesize ${D^1_0} 2^{j'b}$} & $\cdots$ & {\footnotesize ${D^1_{\delta/b-1}} 2^{j'b}$} & 0 & $\cdots$ & 0\\
- $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
- {\footnotesize$j''$} & {\footnotesize $\bm{D^2_0} \cdot 0$} & $\cdots$ & {\footnotesize $\bm{D^2_{\delta/b-1}} \cdot 0$} & 0 & $\cdots$ & 0\\
- $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\\bottomrule
- \end{tabular}
- \end{center}
-\end{frame}
-
-\begin{frame}
- \frametitle{Distributed Difference:\\ Unencrypted Sums, Encrypted Products}
- When we moved to an encrypted algorithm, all of the $D_i$-long sums of
- $E_i$ became
- $\mathcal{E}_i^{\mathcal{D}_i}$.\\~\\
- In the distributed version, we actually make matrix components rather than
- the fake matrix of $D_i$ in certain bit-positions we had earlier.\\~\\
-
- In the matrix, rows are indexed by $0 \leq \mathcal{T} \leq 2^\ell
- -1$, columns by $0 \leq j \leq r-1$.
-\end{frame}
-
-
-\begin{frame}
- \frametitle{Distributed Difference:\\ Unencrypted Sums, Encrypted Products}
- As before, let
- \begin{align*}
- H_k(T) &= j,\\
- H_k(T') &= j',\text{ and}\\
- H_k(T'') &= j'',
- \end{align*}
- with $T$ and $T'$ search terms and $T''$ not.\\~\\
- Notice that this time we won't simply discard the data $D_2$ from $T''$;
- we no longer multiply it by zero, but use it as the exponent of
- $\mathcal{E}_{j''}$, which is an encryption of $0$.
-\end{frame}
-
-\begin{frame}
- \frametitle{Distributed Difference:\\ Unencrypted Sums, Encrypted Products}
- The matrix in the encrypted setting:
- \begin{center}
- \begin{tabular}{c C{1.35cm} c C{1.35cm} C{1.35cm} c C{1.35cm} }
- {\scriptsize Index} & $\mathcal{Y}_0$\qquad & $\cdots$\qquad & $\mathcal{Y}_{\delta/b-1}$\qquad & $\mathcal{Y}_{\delta/b}$\qquad & $\cdots$\qquad & $\mathcal{Y}_{2\delta/b-1}$\qquad\\\toprule
- $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
- {\footnotesize$j$} & {\footnotesize $\mathcal{E}_j^{D^0_0}$} & $\cdots$ & {\footnotesize $\mathcal{E}_j^{D^0_{\delta/b-1}}$} & {\footnotesize $\mathcal{E}_j^{D^3_0}$} & $\cdots$ & {\footnotesize $\mathcal{E}_j^{D^3_{\delta/b-1}}$} \\
- $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
- {\footnotesize$j'$} & {\footnotesize $\mathcal{E}_{j'}^{D^1_0}$} & $\cdots$ & {\footnotesize $\mathcal{E}_{j'}^{D^1_{\delta/b-1}}$} & 1 & $\cdots$ & 1\\
- $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
- {\footnotesize$j''$} & {\footnotesize $\mathcal{E}_{j''}^{D^2_0}$} & $\cdots$ & {\footnotesize $\mathcal{E}_{j''}^{D^2_{\delta/b-1}}$} & 1 & $\cdots$ & 1\\
- $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\\bottomrule
- \end{tabular}
- \end{center}
-\end{frame}
-
-\begin{frame}
- \frametitle{Algorithm In Matrix Form}
- \begin{algorithm}[H]
- \caption{Responder - Matrix Variant}\label{alg.matrix_processing}
-\begin{algorithmic}[1]
- \State {\scriptsize \textbf{Input:} $\mathbf{T} = \{ (T,D) \}$}
-\State{\scriptsize \textbf{Initialize:}}
-\State{\scriptsize \qquad Counters $c_i = 0 \, , \, 0 \leq i \leq (2^l -1)$}
-\State{\scriptsize \qquad Paillier ciphertext values $\mathcal{Y}_{j} = 1 \, , \, 0 \leq j \leq (r-1)$}
-\For{\scriptsize {$(T,D) \in \mathbf{T}$}}
-\State{\scriptsize Compute \(\mathcal{T} = H_{k}(T)\)}
-\Comment{\scriptsize View as the row index of $M: m_{\mathcal{T}, \, j}$}
- \If{\scriptsize {\(c_{\mathcal{T}}+\frac{\delta}{b} > r\)}}
- \State{\scriptsize \Return}
-\Else{\scriptsize }
- \State{\scriptsize Split \(D\) into \(b\)-bit chunks, \(D=D_{0}\|D_{1}\|\ldots\|D_{(\delta/b)-1}\)}
- \For{\scriptsize {\(k=0,\ldots,(\delta/b)-1\)}}
- \State{\scriptsize Set \(m_{\mathcal{T}, \, c_{\mathcal{T}}+k} = \mathcal{E}_{\mathcal{T}}^{D_{k}}\bmod N^{2}\)}
- \EndFor{\scriptsize }
- \State{\scriptsize Set \(c_{\mathcal{T}} = c_{\mathcal{T}}+(\delta/b)\)}
- \EndIf{\scriptsize }
-\EndFor{\scriptsize }
-\For{\scriptsize {$0\leq j \leq (r-1)$}:}
-\State{\scriptsize \qquad \qquad $\mathcal{Y}_{j} \, = \, \prod_{i = 0}^{2^l -1} m_{i,j}$ }
-\EndFor{\scriptsize }
-\State{\scriptsize {\textbf{Output}}: \(\mathcal{Y}_{0},\ldots,\mathcal{Y}_{r-1}\)}
-\end{algorithmic}
-\end{algorithm}
-\end{frame}
-
-\begin{frame}
- \frametitle{Distributed Algorithm}
- \begin{algorithm}[H]
- \caption{Responder - Distributed Variant}\label{alg.dist_processing}
-\begin{algorithmic}[1]
- \State {\scriptsize \textbf{Input:} $\mathbf{T} = \{ (T,D) \}$}
-\For{\scriptsize {$(T,D) \in \mathbf{T}$} in parallel}
-\State{\scriptsize Compute \(\mathcal{T} = H_{k}(T)\)}
-\Comment{\scriptsize View as the row index of $M: m_{\mathcal{T}, \, j}$}
- \State{\scriptsize Split \(D\) into \(b\)-bit chunks, \(D=D_{0}\|D_{1}\|\ldots\|D_{(\delta/b)-1}\)}
-\State{\scriptsize Form $\mathbf{D} = \{D_k : 0 \leq k \leq (\delta/b)-1\}$}
-\State{\scriptsize \textbf{Emit} $(\mathcal{T}, \mathbf{D})$}
- \EndFor{\scriptsize }
- \For{\scriptsize {each $\mathcal{T}$} in parallel}
-\State{\scriptsize Initialize $c_{\mathcal{T}} = 0$}
-\While{\scriptsize {$c_{\mathcal{T}} < r$}}
-\For{\scriptsize {each $(\mathcal{T}, \mathbf{D})$} }
-\For{\scriptsize {each $D_k \in \mathbf{D} \, , \, 0 \leq k \leq \ldots,(\delta/b)-1$}}
- \State{\scriptsize Set \(m_{\mathcal{T}, \, c_{\mathcal{T}}} = \mathcal{E}_{\mathcal{T}}^{D_{k}}\bmod N^{2}\)}
-\State{\scriptsize \textbf{Emit} $(c_{\mathcal{T}}, m_{\mathcal{T}, \, c_{\mathcal{T}}})$}
-\State{\scriptsize $ c_{\mathcal{T}} = c_{\mathcal{T}} + 1$}
-\EndFor{\scriptsize }
-\EndFor{\scriptsize }
-\EndWhile{\scriptsize }
-\EndFor{\scriptsize }
-\For{\scriptsize {$0\leq j \leq (r-1)$ in parallel}:}
-\State{\scriptsize \qquad \qquad $\mathcal{Y}_{j} \, = \, \prod_{i = 0}^{2^l -1} m_{i,j}$ }
-\EndFor{\scriptsize }
-\State{\scriptsize {\textbf{Output}}: \(\mathcal{Y}_{0},\ldots,\mathcal{Y}_{r-1}\)}
-\end{algorithmic}
-\end{algorithm}
-\end{frame}
-
-\section{`Actual' Example}
-\begin{frame}
- \frametitle{Actual Example Setup}
-We run through the above with actual numbers.\\~\\
-Let
-\begin{itemize}
- \item $N = 35$, $p=5$, $q=7$, $\lambda(N) = 12$, $B=5$.
- \item $\tau$, the number of terms we'll search for, is $2$. These terms are
- $T_0 = 0$ and $T_1 = 3$.
- \item We won't specify most of $H$; only that $\ell=4$, $H(T_0) = 0110 = 6$ and
- $H(T_3) = 0010 = 2$.
- \item Our return data are $\delta=4$ bits long; let $b=2$. We limit ourselves
- to $r=4$.
- \item Let's consult an RNG to choose values of $\zeta$ for use in Paillier.
-\end{itemize}
-\end{frame}
-
-\begin{frame}
- \frametitle{Let's Consult an RNG}
- \begin{center}
- \includegraphics[width=2.5in,keepaspectratio]{random_number.png}
-\end{center}
-\bigskip \bigskip {\scriptsize Source:
- \url{http://imgs.xkcd.com/comics/random_number.png}, used under
- \url{http://www.xkcd.com/license.html}}
-\end{frame}
-
-\begin{frame}
- \frametitle{Actual Example Setup}
- Great, we will randomly set $\zeta = 4$ for all encryptions.
-\end{frame}
-
-\begin{frame}
- \frametitle{Example Query}
- \begin{itemize}
- \item Since $H(T_0) = 6$,
- \begin{align*}
- \mathcal{E}_6 &= \mathcal{E}(2^{0\cdot2})\\
- &= 639
- \end{align*}
- \item Similarly, since $H(T_1) = 2$,
- \begin{align*}
- \mathcal{E}_2 &= \mathcal{E}(2^{1\cdot2})\\
- &= 359.
- \end{align*}
- \item All other terms are encryptions of $0$; we will write these as $1$
- even though they would in fact be distributed across a wide array of
- values in \zmodntunits.
- \end{itemize}
-\end{frame}
-
-
-\begin{frame}
- \frametitle{Example Response}
- Suppose, as in our example above, that the responder inputs, in order, are
- $(T_0,D^0)$, $(T_1,D^1)$, $(5, D^2)$, and $(T_0,D^3)$, after
- which point the responder returns (perhaps another $T_0$ comes in, thus causing
- $c_{\mathcal{T}_0}$ to be greater than $r$). Here,
- \begin{align*}
- D^0 &= 0000 = (D^0_0, D^0_1) = (00, 00),\\
- D^1 &= 0110 = (D^1_0, D^1_1) = (01, 10),\\
- D^2 &= 0111 = (D^2_0, D^2_1) = (01, 11),\\
- D^3 &= 0010 = (D^3_0, D^3_1) = (00, 10),\\
- \end{align*}~\\
-
- Note that since $5$ is not a search term, it will result in raising an
- encrypted zero to $D^2=7$; again, we're just going to write $1$, even though the
- acutal algorithm may (will) have any encryption of $0$ instead.
-\end{frame}
-
-\begin{frame}
- \frametitle{Example Response Matrix}
- The responder forms the matrix
- \begin{center}
- \begin{tabular}{c C{2.25cm} C{2.25cm} C{2.25cm} C{2.25cm} }
- {\scriptsize Index} & $\mathcal{Y}_0$ & $\mathcal{Y}_1$ & $\mathcal{Y}_2$ & $\mathcal{Y}_{3}$\\\toprule
- $\vdots$ & \multicolumn{4}{l}{$\qquad$}\\
- {\footnotesize{\tiny $2$}} & {\tiny $\mathcal{E}_2^{D^1_0}\mod N^2 = 359$} & {\tiny $\mathcal{E}_2^{D^1_1}\mod N^2 = 256$} & 1 & 1\\
- {\tiny $\vdots$} & \multicolumn{4}{l}{{\tiny $\qquad$}}\\
- {\footnotesize{\tiny $6$}} & {\tiny $\mathcal{E}_6^{D^0_0} \mod N^2 = 1$} & {\tiny$\mathcal{E}_6^{D^0_1}\mod N^2 = 1$} & {\tiny $\mathcal{E}_6^{D^3_0}\mod N^2 = 1$} & {\tiny $\mathcal{E}_6^{D^3_1}\mod N^2 = 396$} \\
- {\footnotesize{\tiny $7$}} & 1 & 1 & 1 & 1\\
- {\tiny $\vdots$} & \multicolumn{4}{l}{{\tiny $\qquad$}}\\\bottomrule
- \end{tabular}
- \end{center}
-\end{frame}
-
-\begin{frame}
- \frametitle{Example Responses}
- The only interesting responses are $\mathcal{Y}_0 = 359$, $\mathcal{Y}_1=256$, and $\mathcal{Y}_3 = 396$ (products are taken down columns).
-\end{frame}
-
-\begin{frame}
- \frametitle{Example Result}
- We decrypt to $Y_0=0100$, $Y_1 =8 = 1000 $ and $Y_3 = 2 = 0010$, and then run through the processing algorithm:
- \begin{itemize}
- \item Data For $T_0$: $M=0011$
- \begin{itemize}
- \item $X_1 = 0$:
- \begin{itemize}
- \item $D_0 = (Y_0 \& 0011)/2^0 = 00$
- \item $D_1 = (Y_1 \& 0011)/2^0 = 00$
- \end{itemize}
- \item $X_2 = 2$:
- \begin{itemize}
- \item $D_0 = (Y_2 \& 0011)/2^0 = 00$
- \item $D_1 = (Y_3 \& 0011)/2^0 = 10$
- \end{itemize}
- \end{itemize}
- \end{itemize}
-\end{frame}
-
-\begin{frame}
- \frametitle{Example Result}
- We decrypted to $Y_0 = 0100$, $Y_1 =8 = 1000 $ and $Y_3 = 2 = 0010$, and then run through the processing algorithm:
- \begin{itemize}
- \item Data For $T_1$: $M=1100$.
- \begin{itemize}
- \item $X_1 = 6$:
- \begin{itemize}
- \item $D_0 = (Y_0 \& 1100)/2^2 = 01$
- \item $D_1 = (Y_1 \& 1100)/2^2 = 10$
- \end{itemize}
- \item $X_2 = 0$:
- \begin{itemize}
- \item $D_0 = (Y_2 \& 1100)/2^2 = 00$
- \item $D_1 = (Y_3 \& 1100)/2^2 = 00$
- \end{itemize}
- \end{itemize}
- \end{itemize}
- These results are precisely the data the responder had.$^*$\\~\\
- {\tiny *: We cannot distinguish the fact that $X_2$ is a non-response
- from the possibility that $X_2$ represents an actual return of a datum $D=0$
-from the responder. In practice, one must avoid using $D=0$ to eliminate this
-ambiguity}
-\end{frame}
-\end{document}
http://git-wip-us.apache.org/repos/asf/incubator-pirk/blob/d2bf6a02/contrib/math_deck/ApachePirkCircle.png
----------------------------------------------------------------------
diff --git a/contrib/math_deck/ApachePirkCircle.png b/contrib/math_deck/ApachePirkCircle.png
new file mode 100644
index 0000000..6742f6a
Binary files /dev/null and b/contrib/math_deck/ApachePirkCircle.png differ
http://git-wip-us.apache.org/repos/asf/incubator-pirk/blob/d2bf6a02/contrib/math_deck/ApachePirk_1.png
----------------------------------------------------------------------
diff --git a/contrib/math_deck/ApachePirk_1.png b/contrib/math_deck/ApachePirk_1.png
new file mode 100644
index 0000000..45805ea
Binary files /dev/null and b/contrib/math_deck/ApachePirk_1.png differ
http://git-wip-us.apache.org/repos/asf/incubator-pirk/blob/d2bf6a02/contrib/math_deck/math_deck.tex
----------------------------------------------------------------------
diff --git a/contrib/math_deck/math_deck.tex b/contrib/math_deck/math_deck.tex
new file mode 100644
index 0000000..370dadd
--- /dev/null
+++ b/contrib/math_deck/math_deck.tex
@@ -0,0 +1,970 @@
+\documentclass{beamer}
+\usepackage[T1]{fontenc}
+\usepackage{amsmath}
+\usepackage{amssymb}
+\usepackage{amsthm}
+\usepackage{algorithm}
+\usepackage{varwidth}
+\usepackage{bm}
+\usepackage[noend]{algpseudocode}
+\usepackage{xspace}
+\usepackage{multirow}
+\usepackage{xcolor}
+\DeclareRobustCommand{\NAME}{Wideskies\xspace}
+\newcommand{\from}{\rightarrow}
+
+\algnewcommand{\algorithmicgiven}{\textbf{given }}
+\algnewcommand{\Given}{\algorithmicgiven}
+
+\algnewcommand{\algorithmicselect}{\textbf{select }}
+\algnewcommand{\Select}{\algorithmicselect}
+
+\algnewcommand{\algorithmicset}{\textbf{set }}
+\algnewcommand{\Set}{\algorithmicset}
+
+\algnewcommand{\algorithmiccompute}{\textbf{compute }}
+\algnewcommand{\Compute}{\algorithmiccompute}
+
+\algnewcommand{\algorithmicgoto}{\textbf{go to}}
+\algnewcommand{\Goto}[1]{\algorithmicgoto~\ref{#1}}
+
+\newcommand{\Z}{\ensuremath{\mathbf{Z}}}
+\newcommand{\zmodn}{\ensuremath{\Z/N\Z}}
+\newcommand{\zmodntunits}{\ensuremath{\left(\Z/N^{2}\Z\right)^{\times}}}
+\newcommand{\lcm}{\ensuremath{\text{lcm}}}
+
+\mode<presentation> { \usetheme{default} }
+
+\usepackage{graphicx}
+\usepackage{booktabs}
+\usepackage{array}
+\newcolumntype{L}[1]{>{\raggedright\let\newline\\\arraybackslash\hspace{0pt}}p{#1}}
+\newcolumntype{C}[1]{>{\centering\let\newline\\\arraybackslash\hspace{0pt}}p{#1}}
+\newcolumntype{R}[1]{>{\raggedleft\let\newline\\\arraybackslash\hspace{0pt}}p{#1}}
+
+\makeatletter
+\DeclareRobustCommand*{\&}{%
+ \nfss@text{%
+ \fontfamily{LinuxBiolinumT-TLF}%
+ \selectfont
+ \symbol{`\&}%
+ }%
+}
+
+\usepackage{eso-pic}
+\beamertemplatenavigationsymbolsempty
+\setbeamertemplate{footline}[frame number]
+\newcommand\AtPagemyUpperLeft[1]{\AtPageLowerLeft{%
+\put(\LenToUnit{0.9\paperwidth},\LenToUnit{0.9\paperheight}){#1}}}
+
+\AtBeginSection[]{
+ \begin{frame}
+ \vfill
+ \centering
+ \begin{beamercolorbox}[sep=8pt,center,shadow=true,rounded=true]{title}
+ \usebeamerfont{title}\insertsectionhead\par%
+ \end{beamercolorbox}
+ \vfill
+ \end{frame}
+}
+\title[Apache Pirk Math
+Walkthrough]{\includegraphics[width=2.5in,keepaspectratio]{ApachePirk_1.png}\\ \bigskip Mathematics $\&$ Algorithms}
+
+\author{Walter Ray-Dulany}
+\institute[Apache Pirk]
+{
+\medskip
+\textit{raydulany@apache.org}
+}
+% I decided against a date. - Walter
+\date{}
+
+\begin{document}
+
+\begin{frame}
+\titlepage
+\end{frame}
+
+\AddToShipoutPictureFG{
+ \AtPagemyUpperLeft{{\includegraphics[width=.5cm,keepaspectratio]{ApachePirkCircle.png}}}
+}
+
+\section{Introduction}
+
+\begin{frame}
+\frametitle{Pirk's Wideskies Algorithm}
+ Pirk uses the Wideskies algorithm to accomplish scalable PIR.\\~\\
+ This algorithm can be broken down into two distinct conceptual pieces:
+ \begin{itemize}
+ \item Paillier Encryption
+ \item The Query-Response-Result algorithms
+ \end{itemize}
+ ~\\ Before we begin those however, we take a (happily brief) diversion into
+ the language of the mathematics involved in this deck.
+\end{frame}
+
+
+\section{Language Preliminaries}
+\begin{frame}
+ \frametitle{Language Preliminaries}
+ The Paillier scheme employs a small amount of group theoretic notation. Let's
+ go over that notation briefly.
+\end{frame}
+
+\begin{frame}
+ \frametitle{Language Preliminaries}
+ \begin{itemize}
+ \item \zmodn: This is the group of integers modulo $N$; it can be thought of
+ as all numbers $0\leq k < N$, with modular addition (e.g.\ for $N=5$,
+ $1+7 \equiv 3\mod N$).\\~\\ This is a group under addition.\\~\\
+ \item $(\zmodn)^\times$: This is the multiplicative group of integers modulo
+ $N$, also called the units of $\zmodn$. Sometimes denoted
+ $(\mathbf{Z}/N\mathbf{Z})^*$, this is the set of $0\leq k < N$ that are
+ relatively prime to $N$ (that is, $k$ and $N$ share no factors, or
+ equivalently the greatest common denominator ($\gcd$) of $k$ and $N$ is $1$). One
+ can also think of this as the set of $k\in\zmodn$ such that there exists
+ a $k^{-1}\in\zmodn$ with $k\cdot k^{-1} \equiv 1\mod N$.\\~\\
+ This is a group under multiplication.
+ \end{itemize}
+\end{frame}
+
+\begin{frame}
+ \frametitle{Language Preliminaries}
+Using the above notation, we can see that
+\begin{equation*}
+ \zmodntunits = \{0\leq k<N^2: \gcd(k,N^2) = 1\}.
+\end{equation*}~\\
+If $N$ happens to be an RSA modulus,
+$N=pq$, $p$ and $q$ primes, then $\zmodntunits$ is just all numbers between $0$
+(inclusive) and $N^2$ (exclusive) that are not divisible by either $p$ or
+$q$.
+\end{frame}
+
+\begin{frame}
+ \frametitle{Language Preliminaries}
+ \begin{itemize}
+ \item Order In \zmodn: The order of an element $k\in\zmodn$ is the least integer $e$
+ such that $e\cdot k = 0\mod N$.
+ \item Order in \zmodntunits: The order of an element $a\in\zmodntunits$ is
+ the least integer $e$ such that $a^e = 1\mod N^2$.
+ \end{itemize}
+ In both cases, order is well defined (i.e.\ it exists and makes sense) for
+ all elements of the groups.
+\end{frame}
+
+\begin{frame}
+ \frametitle{Language Preliminaries}
+ For a more in depth discussion of these, and closely related, terms, please
+ see
+ \mbox{\scriptsize \url{http://www.math.nagoya-u.ac.jp/~richard/teaching/s2015/Group_2.pdf}}
+\end{frame}
+
+\section{Paillier Encryption}
+\begin{frame}
+\frametitle{Paillier Encryption}
+Paillier encryption is a partially homomorphic public key scheme that relies on
+the function $$\mathcal{E}_g:\zmodn\times(\zmodn)^\times\rightarrow
+\zmodntunits$$ given by $$\mathcal{E}_g(x,y) = g^x y^N \mod N^2,$$
+$g\in\zmodntunits$. Here, $\zmodn$ is the plaintext space and $\zmodntunits$ is
+the ciphertext space.\\~\\
+When the order of $g$ is a non-zero multiple of $N$, $\mathcal{E}_g$ is a bijection.
+\end{frame}
+
+\begin{frame}
+ \frametitle{Paillier Prerequisites}
+\begin{itemize}
+ \item Public key: $(N,g)$, $N$ an RSA modulus $N=pq$, $p$ and $q$ primes of
+ approximately the same bit-length, and $g\in \zmodntunits$ such that the
+ order of $g$ is a nonzero multiple of $N$.
+ \item Private key: $\lambda(N)$, where $\lambda$ is the Carmichael function
+ \begin{align*}
+ \lambda(N) &= \lcm(p-1,q-1)
+ \end{align*}
+ that gives the exponent of $(\zmodn)^\times$.
+ \item Plaintext space: \zmodn.
+ \item Ciphertext space: \zmodntunits.
+\end{itemize}
+~\\
+{\footnotesize We can also consider the pair $(p,q)$ to be the private key, as $\lambda(N)$ is
+quickly and easily derived from it. Note that $\lambda(N)$ is coprime to $N$.}
+\end{frame}
+
+\begin{frame}
+ \frametitle{What Do We Mean By `Homomorphic Encryption'?}
+ An encryption scheme is fully homomorphic if it is a homomorphism from
+ plaintext space to ciphertext space for arbitrary operations and arbitrary
+ numbers of such operations. If this definition seems squishy and not very
+ mathematical, that's because it is; it's hard to find a proper mathematical
+ definition of this term.\\~\\
+
+ An encryption scheme is partially homomorphic if it is a homomorphism for
+ only some operations, or for only a few consecutive operations.\\~\\
+\end{frame}
+
+\begin{frame}
+ \frametitle{Paillier Encryption is Homomorphic}
+ Paillier encryption is a partial homomorphism between addition in \zmodn\ and
+ multiplication in \zmodntunits.\\~\\
+
+ Denote Paillier encryption by $\mathcal{E}_g$ and decryption by $\mathcal{D}_g$,
+ and let $m$ and $m'\in \zmodn$. Then
+ \begin{align*}
+ D(\mathcal{E}(m) \mathcal{E}(m') \bmod N^2) &= (m + m') \bmod N \\
+ D(\mathcal{E}(m)^k \bmod N^2) &= km \bmod N, \, k \in \mathbf{N}
+ \end{align*}
+ ~\\
+ Note that the second equality follows immediately from the first.
+\end{frame}
+
+\section{General Paillier Algorithm}
+
+\begin{frame}
+\frametitle{Paillier Supporting Function}
+Let $X=\{u<N^2 : u = 1 \mod N\}$ and let $L:X\rightarrow \zmodn$ be
+defined by
+\begin{equation*}L(u) = \frac{u-1}{N} \mod N.\end{equation*}
+This function is well defined over \zmodntunits.
+\end{frame}
+
+\begin{frame}
+\frametitle{General Paillier Encryption}
+The general Paillier algorithm differs only slightly from Pirk's version.
+\begin{algorithm}[H]
+ \caption{General Paillier encryption and decryption.}\label{alg.paillier_encrypt_original}
+ \begin{algorithmic}[1]
+ \Procedure{Paillier encryption}{}
+ \State \begin{varwidth}[t]{\linewidth}
+ \Given \(N\), a random \(g \in \zmodntunits\) of order a nonzero\par
+ multiple of $N$, and a message \(m\in\zmodn\)
+ \end{varwidth}
+ \State \Select a random value \(\zeta\in \left(\zmodn\right)^{\times}\)
+ \State \Return \(\mathcal{E}(m) = g^m \zeta^{N}\bmod{N^{2}}\)
+ \EndProcedure
+ \end{algorithmic}
+ \begin{algorithmic}[1]
+ \Procedure{Paillier decryption}{}
+ \State \Given \(N\), \(\lambda(N)\), \(g\), and ciphertext \(c \in \zmodntunits\)
+ \State \Return m = \(\frac{L( c^{\lambda(N)}\bmod N^{2})}{L( g^{\lambda(N)}\bmod N^{2})}\bmod N\)
+ \EndProcedure
+ \end{algorithmic}
+\end{algorithm}
+\end{frame}
+
+\begin{frame}
+\frametitle{Paillier Works}
+ It is a straightforward exercise to check that
+ \begin{itemize}
+ \item $D(\mathcal{E}(m)) = m$
+ \item $D(\mathcal{E}(m)\mathcal{E}(m')\bmod N^2) = (m + m') \bmod N $
+ \end{itemize}
+\end{frame}
+
+\section{Paillier As Used In \NAME}
+\begin{frame}
+\frametitle{Paillier As Used In \NAME}
+The version of Paillier used in \NAME is a computationally simpler variant of the
+full Paillier scheme that sacrifices no security over the general case.
+\end{frame}
+
+\begin{frame}
+ \frametitle{Converting Between The Two}
+ Pirk's simplified version of Paillier simply uses
+ \begin{align*}
+ g &\equiv 1 + N \mod N^2\\
+ \implies L(g^{\lambda(N)} \mod N^2) &= \lambda(N),
+ \end{align*}
+ the proof of which is a straightforward exercise.
+\end{frame}
+
+\begin{frame}
+\frametitle{Paillier As Used In \NAME}
+\begin{algorithm}[H]
+ \caption{Paillier encryption and decryption}\label{alg.paillier_encrypt}
+ \begin{algorithmic}[1]
+ \Procedure{Paillier encryption}{}
+ \State \Given \(N\) and a message \(m\in\zmodn\)
+ \State \Select a random value \(\zeta\in\zmodntunits\)
+ \State \Return \(\mathcal{E}(m) = (1+mN)\zeta^{N}\bmod{N^{2}}\)
+ \EndProcedure
+ \end{algorithmic}
+
+ \begin{algorithmic}[1]
+ \Procedure{Paillier decryption}{}
+ \State \Given \(N\), \(\lambda(N)\), and a ciphertext \(c\in\zmodntunits\)
+ \State \Set \(\mu = \lambda(N)^{-1}\bmod N\)
+ \Comment Recall \(\gcd(\lambda(N), N) = 1\)
+ \State \Set \(\hat{c} = c^{\lambda(N)}\bmod N^{2}\)
+ \State\label{step.div}\Set \(\hat{m} = L(c^{\lambda(N)}\bmod N^{2})\)
+ \State \Return \(\hat{m}\mu\bmod N\)
+ \EndProcedure
+ \end{algorithmic}
+\end{algorithm}
+\end{frame}
+
+\begin{frame}
+ \frametitle{Paillier Reference}
+ For more on Paillier encryption and the (hypothesized) hard problem upon
+ which it is based, see\\~\\
+ \mbox{\scriptsize \url{https://pirk.incubator.apache.org/papers/1999_asiacrypt_paillier_paper.pdf}}\\~\\
+ on Pirk's website.
+\end{frame}
+
+\section{Wideskies}
+
+\begin{frame}
+ \frametitle{Wideskies Parameters}
+ The algorithm requires the following parameters, which are not independent
+ (see the next slide).
+ \begin{itemize}
+ \item $N$, the Paillier modulus
+ \item $B$, the bit-length of $N$
+ \item $H$ (or $H_k$), a keyed hash function (with key k)
+ \item $\ell$, the bit length of the output of $H$, i.e.\
+ $H_k:\mathbf{Z}\rightarrow (\mathbf{Z}/2\mathbf{Z})^\ell$
+ \item $\tau$, the number of search terms
+ \item $\delta$, the number of bits of data returned for each search hit
+ \item $b$ the chunk size, in bits, determining how data is split among
+ responses.
+ \item $r$, the number of responses that can be returned per query request
+ period per search term
+ \end{itemize}
+\end{frame}
+
+\begin{frame}
+ \frametitle{Parameter Relationships}
+ \begin{itemize}
+ \item $2^{b\tau} < N$: there must be space in the modulus to hold all the
+ data, even if each search term hits as often as possible.
+ \item $\tau < 2^\ell$: Although the paper permits search term hash
+ collisions, Pirk does not permit them. Typically $\tau \ll 2^\ell$
+ \item $b|\delta$: Chunk size must evenly divide the data size
+ \item $\frac{\delta}{b} | r$: the number of chunks per returned datum must
+ divide the number of responses, for bandwidth efficiency.
+ \item $H$: Must be pseudo-random but need not be cryptographically secure.
+ \end{itemize}
+\end{frame}
+
+\begin{frame}
+ \frametitle{Public Parameters}
+ All of \begin{equation*}H, \ell, N, B, \delta, b, \text{and } r\end{equation*}
+ are public, that is, must be shared between the client and server.\\~\\
+
+ Note that the fact that $2^{b\tau} < N$ gives some information on the number
+ of search terms the client is using; the amount of this information can be
+ decreased without bound by choosing $N$ and $\ell$ to be much larger than
+ would be otherwise necessary; this necessarily causes a performance hit.
+\end{frame}
+
+\section{Wideskies Algorithm, Without Encryption}
+\begin{frame}
+ \frametitle{Wideskies Without Encryption?}
+ The Wideskies algorithm is of sufficient complexity that it can be useful to
+ go through the algorithm without the encryption and decryption steps first,
+ in order to orient ourselves.\\~\\
+ After, it will be straightforward to see the
+ changes that using the Paillier encryption requires.
+\end{frame}
+
+\section{Query, Without Encryption}
+\begin{frame}
+ \frametitle{The Query Algorithm, Without Encryption}
+ Let $T_0,\ldots,T_{\tau-1}\in\zmodn$ be our search terms.
+ \begin{algorithm}[H]
+ \caption{Query Formation Algorithm version
+ 1}\label{alg.plain_form_1}
+\begin{algorithmic}[1]
+ \State\label{step.key}Choose a random key \(k\) for \(H\).
+ \State Compute \(H_{k}(T_{0}),\ldots,H_{k}(T_{\tau-1})\).
+ \While{\(\mathrm{card}\left(\{H_{k}(T_{0}),\ldots,H_{k}(T_{\tau-1})\}\right)
+ < \tau\)}
+ \State \Goto{step.key}
+ \Comment If there are hash collisions, pick a new key.
+ \EndWhile
+ \For{\(i=0,\ldots,2^{\ell}-1\)}
+ \State\label{step.set}Set \begin{equation*}
+ E_{i} = \left\{\begin{array}{l l}
+ 2^{jb} & \mbox{ if } i = H_{k}(T_{j}); \\
+ 0 & \mbox{otherwise.}
+ \end{array}
+ \right.
+ \end{equation*}
+ \EndFor
+ \State\Return \(\{E_{0},\ldots,E_{2^{\ell}-1}, H, k, N\}\)
+\end{algorithmic}
+\end{algorithm}
+\end{frame}
+
+\begin{frame}
+ \frametitle{Query Notes, Without Encryption}
+ Since $\tau \ll 2^\ell$, we expect most of the $E_i$ to be zero.\\~\\
+ We will typically denote $H_k(T)$ by $\mathcal{T}$ and its associated $E$ by
+ $E_\mathcal{T}$. If we wish to keep track of a specific $T$ we will write
+ $\mathcal{T}_j$ and $E_{\mathcal{T}_j}$.
+\end{frame}
+
+\section{Response, Without Encryption}
+\begin{frame}
+ \frametitle{Response Initialization, Without Encryption}
+ We must initialize some values before forming the response.
+ \begin{enumerate}
+ \item $c_0,\ldots,c_{2^\ell - 1} = 0$, counters to keep track of the number
+ of times each $E_\mathcal{T}$ has been seen.
+ \item $Y_0,\ldots,Y_{r-1} = 0$, response vectors.
+ \end{enumerate}
+\end{frame}
+
+\begin{frame}
+ \frametitle{Response Data, Without Encryption}
+ Responder information comes in pairs $(T, D)$ where $T$ is a (potential)
+ search term, and $D$ is $T$'s associated response datum, which will be
+ returned if $T$ is a search term.\\~\\
+
+ We view $D$ as a $\delta$-long bit stream $(d_0,\ldots,d_{\delta-1})$, and
+ break $D$ up into $\delta/b$ chunks $D_i$ as
+ \begin{equation*}
+ D_i = (d_{i\cdot b}, d_{i\cdot b+1},\ldots,d_{(i+1)\cdot b-1}),\ i=0,\ldots,\delta/b-1.
+ \end{equation*}\\~\\
+ For example, if $D=011010$ and $b=3$, then
+ \begin{align*}
+ D_0 &= 011\\
+ D_1 &= 010
+ \end{align*}
+\end{frame}
+
+\begin{frame}
+ \frametitle{Response Algorithm, Without Encryption}
+ \begin{algorithm}[H]
+ \caption{Stream processing, plaintext version}\label{alg.plain_stream}
+\begin{algorithmic}[1]
+\State \textbf{Input}: $\mathbf{T} = \{ (T,D) \}$
+\For{$(T,D) \in \mathbf{T}$}
+ \State Compute \(\mathcal{T} = H_{k}(T)\)
+ \If{\(c_{\mathcal{T}} + \frac{\delta}{b} > r\)}\label{step.if}
+ \Comment The space allocated for term \(T\) is full.
+ \State \Return \label{step.return}
+\Else
+ \State Split \(D\) into \(b\)-bit chunks
+ \(D_{0},\ldots,D_{(\delta/b)-1}\).
+ \For{\(i=0,\ldots,(\delta/b)-1\)}
+ \State\label{step.multiply}Set \(\mathcal{D}_{i} = D_{i}E_{\mathcal{T}}\bmod N\)
+ \Comment Nonzero only if \(E_{\mathcal{T}}\neq 0\).
+ \State Set \(Y_{i+c_{\mathcal{T}}} =
+ Y_{i+c_{\mathcal{T}}}+\mathcal{D}_{i}\bmod N\)
+ \EndFor
+ \State Set \(c_{\mathcal{T}} = c_{\mathcal{T}}+(\delta/b)\)
+\EndIf
+
+\EndFor
+\State{\textbf{Output}}: \(Y_{0},\ldots,Y_{r-1}\)
+\end{algorithmic}
+\end{algorithm}
+\end{frame}
+
+\begin{frame}
+ \frametitle{Response Example, Without Encryption}
+ Let's look at how the response would look on the first four $(T,D)$ pairs that
+ pass through the algorithm.
+\end{frame}
+
+\begin{frame}
+ \frametitle{Response Example Setup, Without Encryption}
+ Suppose that among our search terms are $T$ and $T'$, with
+ \begin{align*}
+ H_k(T) &= j\text{ and}\\
+ H_k(T') &= j'.
+ \end{align*}~\\
+
+
+ Suppose that $T''$, with $H_k(T'')=j''$, is \emph{not} a search term.\\~\\
+
+ Let the responder see, in order, the pairs $(T, D^0)$, $(T', D^1)$,
+ $(T'', D^2)$, $(T, D^3)$.\\~\\
+
+ The $Y_i$ are formed by summing down the columns in following matrices.
+\end{frame}
+
+\begin{frame}
+ \frametitle{Response Example Start, Without Encryption}
+ No terms have yet been evaluated.
+ \begin{center}
+ \begin{tabular}{c C{1.55cm} c C{1.55cm} C{1.55cm} c C{1.55cm} }
+ {\scriptsize Index} & $Y_0$\qquad & $\cdots$\qquad & $Y_{\delta/b-1}$\qquad & $Y_{\delta/b}$\qquad & $\cdots$\qquad & $Y_{2\delta/b-1}$\qquad\\\toprule
+ $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
+ {\footnotesize$j$} & 0 & $\cdots$ & 0 & 0 & $\cdots$ & 0 \\
+ $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
+ {\footnotesize$j'$} & 0 & $\cdots$ & 0 & 0 & $\cdots$ & 0\\
+ $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
+ {\footnotesize$j''$} & 0 & $\cdots$ & 0 & 0 & $\cdots$ & 0\\
+ $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\\bottomrule
+ \end{tabular}
+ \end{center}
+ $c_{j} = 0$, $c_{j'} = 0$, $c_{j''} = 0$.
+\end{frame}
+
+\begin{frame}
+ \frametitle{Response Example: First Term, Without Encryption}
+ $(T, D^0)$ enters and is proccessed; hit:
+ \begin{center}
+ \begin{tabular}{c C{1.55cm} c C{1.55cm} C{1.55cm} c C{1.55cm} }
+ {\scriptsize Index} & $Y_0$\qquad & $\cdots$\qquad & $Y_{\delta/b-1}$\qquad & $Y_{\delta/b}$\qquad & $\cdots$\qquad & $Y_{2\delta/b-1}$\qquad\\\toprule
+ $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
+ {\footnotesize$j$} & {\footnotesize $\bm{D^0_0} 2^{jb}$} & $\cdots$ & {\footnotesize $\bm{D^0_{\delta/b-1}} 2^{jb}$} & 0 & $\cdots$ & 0 \\
+ $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
+ {\footnotesize$j'$} & 0 & $\cdots$ & 0 & 0 & $\cdots$ & 0\\
+ $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
+ {\footnotesize$j''$} & 0 & $\cdots$ & 0 & 0 & $\cdots$ & 0\\
+ $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\\bottomrule
+ \end{tabular}
+ \end{center}
+ $\bm{c_{j} = \delta/b}$, $c_{j'} = 0$, $c_{j''} = 0$.
+\end{frame}
+
+\begin{frame}
+ \frametitle{Response Example Second Term, Without Encryption}
+ $(T', D^1)$ enters and is proccessed; hit:
+ \begin{center}
+ \begin{tabular}{c C{1.55cm} c C{1.55cm} C{1.55cm} c C{1.55cm} }
+ {\scriptsize Index} & $Y_0$\qquad & $\cdots$\qquad & $Y_{\delta/b-1}$\qquad & $Y_{\delta/b}$\qquad & $\cdots$\qquad & $Y_{2\delta/b-1}$\qquad\\\toprule
+ $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
+ {\footnotesize$j$} & {\footnotesize ${D^0_0} 2^{jb}$} & $\cdots$ & {\footnotesize ${D^0_{\delta/b-1}} 2^{jb}$} & 0 & $\cdots$ & 0 \\
+ $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
+ {\footnotesize$j'$} & {\footnotesize $\bm{D^1_0} 2^{j'b}$} & $\cdots$ & {\footnotesize $\bm{D^1_{\delta/b-1}} 2^{j'b}$} & 0 & $\cdots$ & 0\\
+ $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
+ {\footnotesize$j''$} & 0 & $\cdots$ & 0 & 0 & $\cdots$ & 0\\
+ $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\\bottomrule
+ \end{tabular}
+ \end{center}
+ $c_{j} = \delta/b$, $\bm{c_{j'} = \delta/b}$, $c_{j''} = 0$.
+\end{frame}
+
+\begin{frame}
+ \frametitle{Response Example Third Term, Without Encryption}
+ $(T'', D^2)$ enters and is proccessed; no hit:
+ \begin{center}
+ \begin{tabular}{c C{1.55cm} c C{1.55cm} C{1.55cm} c C{1.55cm} }
+ {\scriptsize Index} & $Y_0$\qquad & $\cdots$\qquad & $Y_{\delta/b-1}$\qquad & $Y_{\delta/b}$\qquad & $\cdots$\qquad & $Y_{2\delta/b-1}$\qquad\\\toprule
+ $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
+ {\footnotesize$j$} & {\footnotesize ${D^0_0} 2^{jb}$} & $\cdots$ & {\footnotesize ${D^0_{\delta/b-1}} 2^{jb}$} & 0 & $\cdots$ & 0 \\
+ $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
+ {\footnotesize$j'$} & {\footnotesize ${D^1_0} 2^{j'b}$} & $\cdots$ & {\footnotesize ${D^1_{\delta/b-1}} 2^{j'b}$} & 0 & $\cdots$ & 0\\
+ $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
+ {\footnotesize$j''$} & {\footnotesize $\bm{D^2_0} \cdot 0$} & $\cdots$ & {\footnotesize $\bm{D^2_{\delta/b-1}} \cdot 0$} & 0 & $\cdots$ & 0\\
+ $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\\bottomrule
+ \end{tabular}
+ \end{center}
+$c_{j} = \delta/b$, $c_{j'} = \delta/b$, $\bm{c_{j''} = \delta/b}$.
+\end{frame}
+
+\begin{frame}
+ \frametitle{Response Example Fourth Term, Without Encryption}
+ $(T, D^3)$ enters and is proccessed; hit:
+ \begin{center}
+ \begin{tabular}{c C{1.55cm} c C{1.55cm} C{1.55cm} c C{1.55cm} }
+ {\scriptsize Index} & $Y_0$\qquad & $\cdots$\qquad & $Y_{\delta/b-1}$\qquad & $Y_{\delta/b}$\qquad & $\cdots$\qquad & $Y_{2\delta/b-1}$\qquad\\\toprule
+ $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
+ {\footnotesize$j$} & {\footnotesize ${D^0_0} 2^{jb}$} & $\cdots$ & {\footnotesize ${D^0_{\delta/b-1}} 2^{jb}$} & {\footnotesize $\bm{D^3_0} 2^{jb}$} & $\cdots$ & {\footnotesize $\bm{D^3_{\delta/b-1}} 2^{jb}$} \\
+ $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
+ {\footnotesize$j'$} & {\footnotesize ${D^1_0} 2^{j'b}$} & $\cdots$ & {\footnotesize ${D^1_{\delta/b-1}} 2^{j'b}$} & 0 & $\cdots$ & 0\\
+ $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
+ {\footnotesize$j''$} & {\footnotesize $\bm{D^2_0} \cdot 0$} & $\cdots$ & {\footnotesize $\bm{D^2_{\delta/b-1}} \cdot 0$} & 0 & $\cdots$ & 0\\
+ $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\\bottomrule
+ \end{tabular}
+ \end{center}
+ $\bm{c_{j} = 2\delta/b}$, $c_{j'} = \delta/b$, $c_{j''} = \delta/b$.
+\end{frame}
+
+\section{Result, Without Encryption}
+\begin{frame}
+ \frametitle{Result, Without Encryption}
+ The algorithm for getting the results out of the response return is
+ straightforward. To begin,\\~\\
+ \begin{itemize}
+ \item Write $Y_i = \sum_{k=0}^{\tau - 1} 2^{kb}P_{ki}$ in base $2^b$, where
+ $P_{ki}$ is the value of the $k^{\text{th}}$ row in the
+ $i^{\text{th}}$ column. Note each $P_{ki}$ is $b$-bits long, and therefore
+ $Y_i < N$.
+ \item $Y_i$ will have data on search term $T$ if and only if $T$ was
+ seen $i+1$ times before the responder returned.
+ \end{itemize}
+\end{frame}
+
+\begin{frame}
+ \frametitle{Result Algorithm, Without Encryption}
+ \begin{algorithm}[H]
+
+ \caption{Data recovery, plaintext version}\label{alg.plain_recover}
+\begin{algorithmic}[1]
+ \State Set \(M = 2^{j b}(2^{b}-1)\)
+ \Comment $b$ $1$s left-shifted $jb$ places.
+ \For{\(\eta=1,\ldots,(rb/\delta)\)}
+ \Comment At most \(rb/\delta\) hits can be returned.
+ \For{\(i=0,\ldots,(\delta/b)-1\)}
+ \Comment Each hit uses \(\delta/b\) chunks.
+ \State\label{step.mask}Set \(D_{i} = Y_{(\eta-1)(\delta/b)+i}\&M\)
+ \Comment ``\(\&\)'' denotes bit-wise \texttt{AND}.
+ \State\label{step.shift}Set \(D_{i} = D_{i}/2^{jb}\)
+ \Comment Step \ref{step.mask} ensures \(2^{jb}\mid D_{i}\)
+ \EndFor
+ \State Set \(X_{\eta} = D_{0}\|D_{1}\|\ldots\|D_{(\delta/b)-1}\)
+ \EndFor
+ \State \Return \(X_{1},\ldots,X_{(rb/\delta)}\)
+ \Comment the data corresponding to selector \(T_{j}\)
+\end{algorithmic}
+\end{algorithm}
+\end{frame}
+
+\section{Wideskies Algorithm, With Encryption}
+\begin{frame}
+ \frametitle{Adding Encryption To The Mix}
+ Adding encryption is straightforward. The following slides have the
+ encryption-enabled algorithms, with the differences from the earlier slides
+ in bold.
+\end{frame}
+
+\section{Query, Encrypted}
+\begin{frame}
+ \frametitle{Query, Encrypted}
+ \begin{algorithm}[H]
+ \caption{Query formation, ciphertext version 1}\label{alg.cipher_form_1}
+\begin{algorithmic}[1]
+ \State\label{step.key_2}Choose a random key \(k\) for \(H\).
+ \State Compute \(H_{k}(T_{0}),\ldots,H_{k}(T_{\tau-1})\).
+ \While{\(\mathrm{card}\left(\{H_{k}(T_{0}),\ldots,H_{k}(T_{\tau-1})\}\right)
+ < \tau\)}
+ \State \Goto{step.key_2}
+ \EndWhile
+ \For{\(i=0,\ldots,2^{\ell}-1\)}
+ \State Set
+ {
+ \bfseries\boldmath
+ \begin{equation*}
+ \mathcal{E}_{i} = \left\{\begin{array}{l l}
+ \mathcal{E}(2^{jb}) & \mbox{ if }i=H_{k}(T_{j})\mbox{ for some
+ }j\in\{0,\ldots,\tau-1\} \\
+ \mathcal{E}(0) & \mbox{ otherwise.}
+ \end{array}
+ \right.
+ \end{equation*}}
+ \EndFor
+ \State \Return \(\{\mathcal{E}_{0},\ldots,\mathcal{E}_{2^{\ell}-1}, H,
+ k, N\}\)
+\end{algorithmic}
+\end{algorithm}
+\end{frame}
+
+\section{Response, Encrypted}
+\begin{frame}
+ \frametitle{Response Initialization, Encrypted}
+ As before, we must initialize some values before forming the response.
+ \begin{enumerate}
+ \item $c_0,\ldots,c_{2^\ell - 1} = 0$, counters to keep track of the number
+ of times each {\boldmath $\mathcal{E}_\mathcal{T}$} has been seen.
+ \item {\bfseries\boldmath $Y_0,\ldots,Y_{r-1} = 1$, response vectors.}
+ \end{enumerate}
+\end{frame}
+
+\begin{frame}
+ \frametitle{Response, Encrypted}
+ \begin{algorithm}[H]
+ \caption{Stream processing, ciphertext version}\label{alg.cipher_processing}
+\begin{algorithmic}[1]
+\State \textbf{Input}: $\mathbf{T} = \{ (T,D) \}$
+\State \textbf{Initialize:}
+\State \qquad Counters $c_i = 0 \, , \, 0 \leq i \leq (2^l -1)$
+\State \qquad Paillier ciphertext values $\mathcal{Y}_{j} = 1 \, , \, 0 \leq j \leq (r-1)$
+\For{$(T,D) \in \mathbf{T}$}
+ \State Compute \(\mathcal{T} = H_{k}(T)\)
+ \If{\(c_{\mathcal{T}}+\frac{\delta}{b} > r\)}
+ \State \Return
+ \Else
+ \State Split \(D\) into \(b\)-bit chunks,
+ \(D=D_{0},\ldots,D_{(\delta/b)-1}\) \label{step.datachunk}
+ \For{\(i=0,\ldots,(\delta/b)-1\)}
+ \State {\bfseries\boldmath Set \(\mathcal{D}_{i} =
+ \mathcal{E}_{\mathcal{T}}^{D_{i}}\bmod N^{2}\)}
+ \State {\bfseries\boldmath Set \(\mathcal{Y}_{i+c_{\mathcal{T}}} =
+ \mathcal{Y}_{i+c_{\mathcal{T}}}\mathcal{D}_{i}\bmod N^{2}\)}
+ \EndFor
+ \State Set \(c_{\mathcal{T}} = c_{\mathcal{T}}+(\delta/b)\)
+ \EndIf
+\EndFor
+\State{\textbf{Output}}: \(\mathcal{Y}_{0},\ldots,\mathcal{Y}_{r-1}\)
+\end{algorithmic}
+\end{algorithm}
+\end{frame}
+
+\section{Result, Encrypted}
+\begin{frame}
+ \frametitle{Result, Encrypted (and then Decrypted)}
+ Actually literally the same algorithm as before is used; the only difference
+ is that we first decrypt the encrypted $\mathcal{Y}_i$.
+\end{frame}
+
+\section{Distributed Version}
+\begin{frame}
+ \frametitle{Distributed Version}
+ The paper goes over how to do the distributed version; the change is
+ straightforward, and our earlier example slides make it easy to see how it
+ works.
+\end{frame}
+
+\begin{frame}
+ \frametitle{Distributed Difference:\\ Unencrypted Sums, Encrypted Products}
+ Recall our example matrix:
+ \begin{center}
+ \begin{tabular}{c C{1.55cm} c C{1.55cm} C{1.55cm} c C{1.55cm} }
+ {\scriptsize Index} & $Y_0$\qquad & $\cdots$\qquad & $Y_{\delta/b-1}$\qquad & $Y_{\delta/b}$\qquad & $\cdots$\qquad & $Y_{2\delta/b-1}$\qquad\\\toprule
+ $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
+ {\footnotesize$j$} & {\footnotesize ${D^0_0} 2^{jb}$} & $\cdots$ & {\footnotesize ${D^0_{\delta/b-1}} 2^{jb}$} & {\footnotesize ${D^3_0} 2^{jb}$} & $\cdots$ & {\footnotesize ${D^3_{\delta/b-1}} 2^{jb}$} \\
+ $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
+ {\footnotesize$j'$} & {\footnotesize ${D^1_0} 2^{j'b}$} & $\cdots$ & {\footnotesize ${D^1_{\delta/b-1}} 2^{j'b}$} & 0 & $\cdots$ & 0\\
+ $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
+ {\footnotesize$j''$} & {\footnotesize $\bm{D^2_0} \cdot 0$} & $\cdots$ & {\footnotesize $\bm{D^2_{\delta/b-1}} \cdot 0$} & 0 & $\cdots$ & 0\\
+ $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\\bottomrule
+ \end{tabular}
+ \end{center}
+\end{frame}
+
+\begin{frame}
+ \frametitle{Distributed Difference:\\ Unencrypted Sums, Encrypted Products}
+ When we moved to an encrypted algorithm, all of the $D_i$-long sums of
+ $E_i$ became
+ $\mathcal{E}_i^{\mathcal{D}_i}$.\\~\\
+ In the distributed version, we actually make matrix components rather than
+ the fake matrix of $D_i$ in certain bit-positions we had earlier.\\~\\
+
+ In the matrix, rows are indexed by $0 \leq \mathcal{T} \leq 2^\ell
+ -1$, columns by $0 \leq j \leq r-1$.
+\end{frame}
+
+
+\begin{frame}
+ \frametitle{Distributed Difference:\\ Unencrypted Sums, Encrypted Products}
+ As before, let
+ \begin{align*}
+ H_k(T) &= j,\\
+ H_k(T') &= j',\text{ and}\\
+ H_k(T'') &= j'',
+ \end{align*}
+ with $T$ and $T'$ search terms and $T''$ not.\\~\\
+ Notice that this time we won't simply discard the data $D_2$ from $T''$;
+ we no longer multiply it by zero, but use it as the exponent of
+ $\mathcal{E}_{j''}$, which is an encryption of $0$.
+\end{frame}
+
+\begin{frame}
+ \frametitle{Distributed Difference:\\ Unencrypted Sums, Encrypted Products}
+ The matrix in the encrypted setting:
+ \begin{center}
+ \begin{tabular}{c C{1.35cm} c C{1.35cm} C{1.35cm} c C{1.35cm} }
+ {\scriptsize Index} & $\mathcal{Y}_0$\qquad & $\cdots$\qquad & $\mathcal{Y}_{\delta/b-1}$\qquad & $\mathcal{Y}_{\delta/b}$\qquad & $\cdots$\qquad & $\mathcal{Y}_{2\delta/b-1}$\qquad\\\toprule
+ $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
+ {\footnotesize$j$} & {\footnotesize $\mathcal{E}_j^{D^0_0}$} & $\cdots$ & {\footnotesize $\mathcal{E}_j^{D^0_{\delta/b-1}}$} & {\footnotesize $\mathcal{E}_j^{D^3_0}$} & $\cdots$ & {\footnotesize $\mathcal{E}_j^{D^3_{\delta/b-1}}$} \\
+ $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
+ {\footnotesize$j'$} & {\footnotesize $\mathcal{E}_{j'}^{D^1_0}$} & $\cdots$ & {\footnotesize $\mathcal{E}_{j'}^{D^1_{\delta/b-1}}$} & 1 & $\cdots$ & 1\\
+ $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\
+ {\footnotesize$j''$} & {\footnotesize $\mathcal{E}_{j''}^{D^2_0}$} & $\cdots$ & {\footnotesize $\mathcal{E}_{j''}^{D^2_{\delta/b-1}}$} & 1 & $\cdots$ & 1\\
+ $\vdots$ & \multicolumn{6}{l}{$\qquad$}\\\bottomrule
+ \end{tabular}
+ \end{center}
+\end{frame}
+
+\begin{frame}
+ \frametitle{Algorithm In Matrix Form}
+ \begin{algorithm}[H]
+ \caption{Responder - Matrix Variant}\label{alg.matrix_processing}
+\begin{algorithmic}[1]
+ \State {\scriptsize \textbf{Input:} $\mathbf{T} = \{ (T,D) \}$}
+\State{\scriptsize \textbf{Initialize:}}
+\State{\scriptsize \qquad Counters $c_i = 0 \, , \, 0 \leq i \leq (2^l -1)$}
+\State{\scriptsize \qquad Paillier ciphertext values $\mathcal{Y}_{j} = 1 \, , \, 0 \leq j \leq (r-1)$}
+\For{\scriptsize {$(T,D) \in \mathbf{T}$}}
+\State{\scriptsize Compute \(\mathcal{T} = H_{k}(T)\)}
+\Comment{\scriptsize View as the row index of $M: m_{\mathcal{T}, \, j}$}
+ \If{\scriptsize {\(c_{\mathcal{T}}+\frac{\delta}{b} > r\)}}
+ \State{\scriptsize \Return}
+\Else{\scriptsize }
+ \State{\scriptsize Split \(D\) into \(b\)-bit chunks, \(D=D_{0}\|D_{1}\|\ldots\|D_{(\delta/b)-1}\)}
+ \For{\scriptsize {\(k=0,\ldots,(\delta/b)-1\)}}
+ \State{\scriptsize Set \(m_{\mathcal{T}, \, c_{\mathcal{T}}+k} = \mathcal{E}_{\mathcal{T}}^{D_{k}}\bmod N^{2}\)}
+ \EndFor{\scriptsize }
+ \State{\scriptsize Set \(c_{\mathcal{T}} = c_{\mathcal{T}}+(\delta/b)\)}
+ \EndIf{\scriptsize }
+\EndFor{\scriptsize }
+\For{\scriptsize {$0\leq j \leq (r-1)$}:}
+\State{\scriptsize \qquad \qquad $\mathcal{Y}_{j} \, = \, \prod_{i = 0}^{2^l -1} m_{i,j}$ }
+\EndFor{\scriptsize }
+\State{\scriptsize {\textbf{Output}}: \(\mathcal{Y}_{0},\ldots,\mathcal{Y}_{r-1}\)}
+\end{algorithmic}
+\end{algorithm}
+\end{frame}
+
+\begin{frame}
+ \frametitle{Distributed Algorithm}
+ \begin{algorithm}[H]
+ \caption{Responder - Distributed Variant}\label{alg.dist_processing}
+\begin{algorithmic}[1]
+ \State {\scriptsize \textbf{Input:} $\mathbf{T} = \{ (T,D) \}$}
+\For{\scriptsize {$(T,D) \in \mathbf{T}$} in parallel}
+\State{\scriptsize Compute \(\mathcal{T} = H_{k}(T)\)}
+\Comment{\scriptsize View as the row index of $M: m_{\mathcal{T}, \, j}$}
+ \State{\scriptsize Split \(D\) into \(b\)-bit chunks, \(D=D_{0}\|D_{1}\|\ldots\|D_{(\delta/b)-1}\)}
+\State{\scriptsize Form $\mathbf{D} = \{D_k : 0 \leq k \leq (\delta/b)-1\}$}
+\State{\scriptsize \textbf{Emit} $(\mathcal{T}, \mathbf{D})$}
+ \EndFor{\scriptsize }
+ \For{\scriptsize {each $\mathcal{T}$} in parallel}
+\State{\scriptsize Initialize $c_{\mathcal{T}} = 0$}
+\While{\scriptsize {$c_{\mathcal{T}} < r$}}
+\For{\scriptsize {each $(\mathcal{T}, \mathbf{D})$} }
+\For{\scriptsize {each $D_k \in \mathbf{D} \, , \, 0 \leq k \leq \ldots,(\delta/b)-1$}}
+ \State{\scriptsize Set \(m_{\mathcal{T}, \, c_{\mathcal{T}}} = \mathcal{E}_{\mathcal{T}}^{D_{k}}\bmod N^{2}\)}
+\State{\scriptsize \textbf{Emit} $(c_{\mathcal{T}}, m_{\mathcal{T}, \, c_{\mathcal{T}}})$}
+\State{\scriptsize $ c_{\mathcal{T}} = c_{\mathcal{T}} + 1$}
+\EndFor{\scriptsize }
+\EndFor{\scriptsize }
+\EndWhile{\scriptsize }
+\EndFor{\scriptsize }
+\For{\scriptsize {$0\leq j \leq (r-1)$ in parallel}:}
+\State{\scriptsize \qquad \qquad $\mathcal{Y}_{j} \, = \, \prod_{i = 0}^{2^l -1} m_{i,j}$ }
+\EndFor{\scriptsize }
+\State{\scriptsize {\textbf{Output}}: \(\mathcal{Y}_{0},\ldots,\mathcal{Y}_{r-1}\)}
+\end{algorithmic}
+\end{algorithm}
+\end{frame}
+
+\section{`Actual' Example}
+\begin{frame}
+ \frametitle{Actual Example Setup}
+We run through the above with actual numbers.\\~\\
+Let
+\begin{itemize}
+ \item $N = 35$, $p=5$, $q=7$, $\lambda(N) = 12$, $B=5$.
+ \item $\tau$, the number of terms we'll search for, is $2$. These terms are
+ $T_0 = 0$ and $T_1 = 3$.
+ \item We won't specify most of $H$; only that $\ell=4$, $H(T_0) = 0110 = 6$ and
+ $H(T_3) = 0010 = 2$.
+ \item Our return data are $\delta=4$ bits long; let $b=2$. We limit ourselves
+ to $r=4$.
+ \item Let's consult an RNG to choose values of $\zeta$ for use in Paillier.
+\end{itemize}
+\end{frame}
+
+\begin{frame}
+ \frametitle{Let's Consult an RNG}
+ \begin{center}
+ \includegraphics[width=2.5in,keepaspectratio]{random_number.png}
+\end{center}
+\bigskip \bigskip {\scriptsize Source:
+ \url{http://imgs.xkcd.com/comics/random_number.png}, used under
+ \url{http://www.xkcd.com/license.html}}
+\end{frame}
+
+\begin{frame}
+ \frametitle{Actual Example Setup}
+ Great, we will randomly set $\zeta = 4$ for all encryptions.
+\end{frame}
+
+\begin{frame}
+ \frametitle{Example Query}
+ \begin{itemize}
+ \item Since $H(T_0) = 6$,
+ \begin{align*}
+ \mathcal{E}_6 &= \mathcal{E}(2^{0\cdot2})\\
+ &= 639
+ \end{align*}
+ \item Similarly, since $H(T_1) = 2$,
+ \begin{align*}
+ \mathcal{E}_2 &= \mathcal{E}(2^{1\cdot2})\\
+ &= 359.
+ \end{align*}
+ \item All other terms are encryptions of $0$; we will write these as $1$
+ even though they would in fact be distributed across a wide array of
+ values in \zmodntunits.
+ \end{itemize}
+\end{frame}
+
+
+\begin{frame}
+ \frametitle{Example Response}
+ Suppose, as in our example above, that the responder inputs, in order, are
+ $(T_0,D^0)$, $(T_1,D^1)$, $(5, D^2)$, and $(T_0,D^3)$, after
+ which point the responder returns (perhaps another $T_0$ comes in, thus causing
+ $c_{\mathcal{T}_0}$ to be greater than $r$). Here,
+ \begin{align*}
+ D^0 &= 0000 = (D^0_0, D^0_1) = (00, 00),\\
+ D^1 &= 0110 = (D^1_0, D^1_1) = (01, 10),\\
+ D^2 &= 0111 = (D^2_0, D^2_1) = (01, 11),\\
+ D^3 &= 0010 = (D^3_0, D^3_1) = (00, 10),\\
+ \end{align*}~\\
+
+ Note that since $5$ is not a search term, it will result in raising an
+ encrypted zero to $D^2=7$; again, we're just going to write $1$, even though the
+ acutal algorithm may (will) have any encryption of $0$ instead.
+\end{frame}
+
+\begin{frame}
+ \frametitle{Example Response Matrix}
+ The responder forms the matrix
+ \begin{center}
+ \begin{tabular}{c C{2.25cm} C{2.25cm} C{2.25cm} C{2.25cm} }
+ {\scriptsize Index} & $\mathcal{Y}_0$ & $\mathcal{Y}_1$ & $\mathcal{Y}_2$ & $\mathcal{Y}_{3}$\\\toprule
+ $\vdots$ & \multicolumn{4}{l}{$\qquad$}\\
+ {\footnotesize{\tiny $2$}} & {\tiny $\mathcal{E}_2^{D^1_0}\mod N^2 = 359$} & {\tiny $\mathcal{E}_2^{D^1_1}\mod N^2 = 256$} & 1 & 1\\
+ {\tiny $\vdots$} & \multicolumn{4}{l}{{\tiny $\qquad$}}\\
+ {\footnotesize{\tiny $6$}} & {\tiny $\mathcal{E}_6^{D^0_0} \mod N^2 = 1$} & {\tiny$\mathcal{E}_6^{D^0_1}\mod N^2 = 1$} & {\tiny $\mathcal{E}_6^{D^3_0}\mod N^2 = 1$} & {\tiny $\mathcal{E}_6^{D^3_1}\mod N^2 = 396$} \\
+ {\footnotesize{\tiny $7$}} & 1 & 1 & 1 & 1\\
+ {\tiny $\vdots$} & \multicolumn{4}{l}{{\tiny $\qquad$}}\\\bottomrule
+ \end{tabular}
+ \end{center}
+\end{frame}
+
+\begin{frame}
+ \frametitle{Example Responses}
+ The only interesting responses are $\mathcal{Y}_0 = 359$, $\mathcal{Y}_1=256$, and $\mathcal{Y}_3 = 396$ (products are taken down columns).
+\end{frame}
+
+\begin{frame}
+ \frametitle{Example Result}
+ We decrypt to $Y_0=0100$, $Y_1 =8 = 1000 $ and $Y_3 = 2 = 0010$, and then run through the processing algorithm:
+ \begin{itemize}
+ \item Data For $T_0$: $M=0011$
+ \begin{itemize}
+ \item $X_1 = 0$:
+ \begin{itemize}
+ \item $D_0 = (Y_0 \& 0011)/2^0 = 00$
+ \item $D_1 = (Y_1 \& 0011)/2^0 = 00$
+ \end{itemize}
+ \item $X_2 = 2$:
+ \begin{itemize}
+ \item $D_0 = (Y_2 \& 0011)/2^0 = 00$
+ \item $D_1 = (Y_3 \& 0011)/2^0 = 10$
+ \end{itemize}
+ \end{itemize}
+ \end{itemize}
+\end{frame}
+
+\begin{frame}
+ \frametitle{Example Result}
+ We decrypted to $Y_0 = 0100$, $Y_1 =8 = 1000 $ and $Y_3 = 2 = 0010$, and then run through the processing algorithm:
+ \begin{itemize}
+ \item Data For $T_1$: $M=1100$.
+ \begin{itemize}
+ \item $X_1 = 6$:
+ \begin{itemize}
+ \item $D_0 = (Y_0 \& 1100)/2^2 = 01$
+ \item $D_1 = (Y_1 \& 1100)/2^2 = 10$
+ \end{itemize}
+ \item $X_2 = 0$:
+ \begin{itemize}
+ \item $D_0 = (Y_2 \& 1100)/2^2 = 00$
+ \item $D_1 = (Y_3 \& 1100)/2^2 = 00$
+ \end{itemize}
+ \end{itemize}
+ \end{itemize}
+ These results are precisely the data the responder had.$^*$\\~\\
+ {\tiny *: We cannot distinguish the fact that $X_2$ is a non-response
+ from the possibility that $X_2$ represents an actual return of a datum $D=0$
+from the responder. In practice, one must avoid using $D=0$ to eliminate this
+ambiguity}
+\end{frame}
+\end{document}
http://git-wip-us.apache.org/repos/asf/incubator-pirk/blob/d2bf6a02/contrib/math_deck/pirkImage.png
----------------------------------------------------------------------
diff --git a/contrib/math_deck/pirkImage.png b/contrib/math_deck/pirkImage.png
new file mode 100644
index 0000000..45805ea
Binary files /dev/null and b/contrib/math_deck/pirkImage.png differ
http://git-wip-us.apache.org/repos/asf/incubator-pirk/blob/d2bf6a02/contrib/math_deck/random_number.png
----------------------------------------------------------------------
diff --git a/contrib/math_deck/random_number.png b/contrib/math_deck/random_number.png
new file mode 100644
index 0000000..71b768c
Binary files /dev/null and b/contrib/math_deck/random_number.png differ
http://git-wip-us.apache.org/repos/asf/incubator-pirk/blob/d2bf6a02/contrib/pirkImage.png
----------------------------------------------------------------------
diff --git a/contrib/pirkImage.png b/contrib/pirkImage.png
deleted file mode 100644
index 45805ea..0000000
Binary files a/contrib/pirkImage.png and /dev/null differ
http://git-wip-us.apache.org/repos/asf/incubator-pirk/blob/d2bf6a02/contrib/random_number.png
----------------------------------------------------------------------
diff --git a/contrib/random_number.png b/contrib/random_number.png
deleted file mode 100644
index 71b768c..0000000
Binary files a/contrib/random_number.png and /dev/null differ