\r
\section{Assumptions}\r
\r
-Some assumptions.\r
+We consider operations over the finite Galois Field $\GF(p)$ of prime order $p$. The field has addition $+$ and multiplication $.$ which are commutative, associative and distributive. It also has additive and multiplicative identities $0$ and $1$ respectively.\r
\r
-\section{Method}\r
+Every element $x \in \GF(p)$ has an additive inverse ${-x} = p - x$ and every non-zero element $x \in \GF(p)^* = \GF(p) \setminus \{ 0 \}$ has a multiplicative inverse $x^{-1}$. By Lagrange's Theorem we have that $x^p = 1$, except where $x = 0$, in which case $x^p = 0$.\r
\r
-A method.\r
+We consider only the $n$-bit numbers in $\GF(p)$ where $p > 2^{n}$. For example if $n = 8$ we're considering 8-bit numbers with a maximum value of 255 and where $p$ is a prime number likely to be considerably larger than this.\r
\r
+\section{Method}\r
\r
-%\bibliographystyle{IEEEtran}\r
-%\bibliography{main}\r
+We start by defining a function that allows us to determine whether a number is larger than or equal to the constant value $m$.\r
+\r
+\begin{lemma}\r
+\label{lemma:comparison}\r
+Let\r
+\begin{equation}\r
+\label{equation:comparison}\r
+d_m(x) = \left( \vphantom\prod \smash{\prod_{i = 0}^{m}} (x - i) \right)^p.\r
+\end{equation}\r
+We claim that\r
+$$\r
+d_m(x) = \r
+\begin{cases}\r
+0 & x \le m \\\r
+1 & \text{otherwise}\r
+\end{cases}\r
+$$\r
+\end{lemma}\r
+\begin{proof}\r
+We start by showing that $\prod_{i = 0}^{m} (x - i) = 0$ iff $x \le m$.\r
+\r
+Suppose $x \le m$. Then for some $0 \le i \le m$ we must have $x - i = 0$. Hence $\prod_{i = 0}^{m} (x - i) = 0$ as required.\r
+\r
+For the counterfactual, suppose that $\prod_{i = 0}^{m} (x - i) = 0$. We aim to show that in this case $x \le m$. We do this by induction on $m$.\r
+\r
+For the base case, set $m = 0$. Hence we have\r
+\begin{align*}\r
+\prod_{i = 0}^{m} (x - i) & = 0, \\\r
+\prod_{i = 0}^{0} (x - i) & = 0, \\\r
+(x - 0) & = 0, \\\r
+x & = 0.\r
+\end{align*}\r
+\r
+For the inductive step we assume it's true for $x = a$ and want to show it's therefore true for $x = a + 1$. We have (by our inductive hypothesis) that if $\prod_{i = 0}^{a} (x - i) = 0$ then $x \le a$.\r
+\r
+Now suppose $\prod_{i = 0}^{a + 1} (x - i) = 0$. By rearranging terms (commutativity) we can write this as\r
+$$\r
+(x - (a + 1)) \times \prod_{i = 0}^{a} (x - i).\r
+$$\r
+Suppose $\prod_{i = 0}^{a} (x - i) = 0$, then the result immediately follows by the inductive hypothesis since therefore $x \le a < a + 1$. If we assume this isn't the case, then by the existence of inverses we can post-multiply by the inverse of the product to get\r
+$$\r
+(x - (a + 1)) = 0.\r
+$$\r
+Again, by rearranging we see that in this case $x = (a + 1)$ and hence that $x \le a + 1$ as required.\r
+\r
+From the above discussion we know that\r
+$$\r
+\prod_{i = 0}^{m} (x - i) = 0 \qquad \iff \qquad x \le m.\r
+$$\r
+For any value $v \in \GF(p)$ we know that \r
+$$\r
+v^p = \r
+\begin{cases}\r
+0 & v = 0 \\\r
+1 & \text{otherwise}\r
+\end{cases}\r
+$$\r
+We conclude that \r
+$$\r
+d_m(x) = \left( \vphantom\prod \smash{\prod_{i = 0}^{m}} (x - i) \right)^p = \r
+\begin{cases}\r
+0 & x \le m \\\r
+1 & \text{otherwise}\r
+\end{cases}\r
+$$\r
+\end{proof}\r
+\r
+For notational simplicity, we define the following function.\r
+\begin{definition}\r
+Let $d_m'(x) = d_{2^m}(x).$\r
+\end{definition}\r
+\r
+We're now in a position to define the function that will output the bits of our $n$-bit number. We define separate functions $b_i : \GF(p) \to \{0, 1 \}$ for each bit $1 \le i \le n$ starting at $n$ and working downwards.\r
+\begin{definition}\r
+Define $b_n : \GF(p) \to \{0, 1\}$ to be the function\r
+$$\r
+b_n (x) = d_{n - 1}'(x).\r
+$$\r
+Starting from $m = n - 1$ and decreasing to $m = 1$ we define functions $b_m : \GF(p) \to \{0, 1 \}$ inductively as follows.\r
+\begin{equation}\r
+\label{equation:getbit}\r
+b_m (x) = d_{m - 1}' \left( x - \vphantom{\sum} \smash{\sum_{m}^{n - 1}} 2^i b_i (x) \right).\r
+\end{equation}\r
+\end{definition}\r
+We claim that the functions $b_m (x)$ for $1 \le m \le n$ will generate the binary bits of any number $x < 2^n$ where $b_n$ is the MSB and $b_1$ is the LSB.\r
+\begin{theorem}\r
+For any number $x \in \GF(p)$ where $x < 2^n < p$ the function $b_m (x)$ will output the $m$-th binary digit of $x$ for $1 \le m \le n$.\r
+\end{theorem}\r
+\begin{proof}\r
+We start by noting that for any number $x \le 2^i$, the $i$-th bit is 0 if and only if $x \le 2^{i - 1}$. We also note that if $b_i \in \{0, 1 \}$ is this $i$-th bit, then $x - 2^{i - 1} b_i \le 2^{i - 1}$.\r
+\r
+We now prove the result by induction on $m$ starting at $m = n$ and working downwards. So for the base case take $m = n$. Then $b_n (x) = d_{n - 1}'(x)$. However, we also know that $x \le 2^n$ and that the $n$-th bit is zero iff $x \le 2^{n - 1}$. But this therefore follows directly from Lemma \ref{lemma:comparison} setting $m = 2^{n - 1}$.\r
+\r
+For the inductive step, assume the result holds for $m = a + 1$. Our inductive hypothesis is that $b_i$ will output the binary bits for $a + 1 \le i \le n$ and we want to show that $b_a$ will output the $a$-th bit.\r
+\r
+Set\r
+$$\r
+x' = x - \sum_{a + 1}^{n - 1} 2^i b_i (x).\r
+$$\r
+From the results noted at the start of the proof, and the inductive hypothesis, we can deduce that\r
+$$\r
+x' \le 2^{a}\r
+$$\r
+(the proof of this is also by induction on $a$, but is straightforward and omitted for clarity). It follows that the $a$-th bit of $x'$ is 0 if and only if $x' \le 2^{a - 1}$, and so from Lemma \ref{lemma:comparison} we see that $d_{2^{a - 1}} (x')$ will output the $a$-th bit of $x'$ which is also the $a$-th but of $x$. Going back to our original definition of $b_a$ we see that\r
+$$\r
+b_a (x) = d_{a - 1}' (x') = d_{2^{a - 1}} (x')\r
+$$\r
+and so have the result we need.\r
+\end{proof}\r
+\r
+\section{Notes}\r
+Although this gives a function we can use in $\GF(p)$ to determine the binary digits of a number, we haven't quite proved everything we need. In order to ensure the function is usable in the context of homomorphic encryption, we can only use multplication and addition. This introduces restrictions on the algebra we can perform on encrypted data. For example, although exponentiation is a special case of multiplication (performing the same multiplication multiple times), it turns out we can only do this where the exponent is a {\it constant\/} value. The reason is that, if the exponent were a variable depending on some other value in the formula, we would need to know how many multiplications to perform, which wouldn't be possible for an encrypted exponent. Similarly for ranged sums, the ranges must be constat values, otherwise we wouldn't know how many additions to perform.\r
+\r
+In the functions defined above, we use exponentiation and ranged sums in several places. For example, in Equation \ref{equation:comparison} we exponentiate by the power $p$. It's clear that in this case $p$ is a constant and so can also be represented as a fixed number of multiplications.\r
+\r
+Less clear may be the ranged sum of Equation \ref{equation:getbit}. In this case we're saved by the fact each $b_m (x)$ is defined as a separate function. Hence both $m$ and $n$ are constant for each $b_m$ and so we can alternatively represent the sum as a fixed number of individual additions.\r
+\r
+The catch is that each $b_m (x)$ involves a large number of operations, each of which will introduce noise into the homomorphically encrypted data. Calculation of the inverse (exponentiation by $p$) in Equation \ref{equation:comparison} is particularly problemmatic, since the noise will grow with $p$ (and hence we can't just choose a larger $p$ to compensate). The purpose of the exponentiation is simply to map 0 to 0 and any other number to 1; although fundamental to the process, there may be a way to achieve it without introducing so much noise. A possible avenue to consider might be the use of the Extended Euclidean Algorithm \cite{Cormen01} for calculating the inverse instead.\r
+\r
+\r
+\bibliographystyle{IEEEtran}\r
+\bibliography{main}\r
\r
% that's all folks\r
\end{document}\r
% Initialise AMS maths package
\usepackage{amsmath}
\interdisplaylinepenalty=2500
-%\usepackage{amsthm}
+\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{array}
%\usepackage{subfig}
\def\R{\mathord{{\mathbb R}}} % Reals
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
-\def\ave{\mathop{\rm ave}\nolimits} % memory set
\ No newline at end of file
+\def\ave{\mathop{\rm ave}\nolimits} % memory set
+\def\GF{\mathop{\bf GF}\nolimits} % Galois Field
+\def\iff{\Longleftrightarrow}
+
+\newtheorem{theorem}{Theorem}[section]
+\newtheorem{lemma}{Lemma}[theorem]
+\newtheorem{proposition}{Proposition}[theorem]
+\newtheorem{corollary}{Corollary}[theorem]
+
+\newenvironment{definition}[1][Definition]{\begin{trivlist}
+\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
+
projects / binaryfield.git / commitdiff