---
abstract: 'In this paper, we propose a leveled fully homomorphic encryption scheme based on multivariate polynomial evaluation.  We first identify a decision problem called the Hidden Subspace Membership (HSM) problem and show that it is related to the well-known Learning with Errors (LWE) problem.  We show that an adversary against the LWE problem can be translated into an adversary against the HSM problem and on the contrary, solving the HSM problem is equivalent to solving the LWE problem with multiple secrets.  We then show that the security of the proposed scheme rely on the hardness of the Hidden Subspace Membership problem.  Further, we propose a batch variant of the scheme where multiple plaintext bits can be packed into a single ciphertext.' 
author:
- Uddipana Dowerah and Srinivasan Krishnaswamy
bibliography:
- 'HE\_ref.bib'
title: Homomorphic Encryption based on Hidden Subspace Membership
---

Introduction
============

Homomorphic encryption is the ability to perform mathematical functions on encrypted data without decryption.  In other words, if $\phi$ denotes a function to be performed on the plaintexts $m_1$ and $m_2$, then homomorphic encryption is the ability to compute $\phi(m_1,m_2)$ from their respective encryptions $Enc(m_1)$ and $Enc(m_2)$ without the knowledge of $m_1$ and $m_2$. An encryption scheme is said to be fully homomorphic if functions of arbitrary complexity can be evaluated on the ciphertexts.  If an encryption scheme can evaluate functions of only limited complexity, then it is said to be somewhat homomorphic.  Following the initial construction of Fully Homomorphic Encryption (FHE) [@gentry2009fully], many schemes were proposed [@van2010fully; @smart2010fully; @brakerski2011fully; @gentry2011implementing] based on a similar idea where a somewhat homomorphic scheme is converted to a fully homomorphic one using bootstrapping.  Bootstrapping is the ability to evaluate the decryption cicuit homomorphically and it relies on additional hardness assumptions.  Alternatively, a number of schemes were proposed [@brakerski2012fully; @gentry2013homomorphic; @brakerski2014efficient] where a (leveled) fully homomorphic scheme is obtained from a somewhat homomorphic one without bootstrapping.  The security of these schemes rely on the hardness of the well-known Learning with Errors (LWE) problem [@regev2005lattices; @regev2009lattices]. 

The starting point of an LWE-based scheme [@brakerski2012fully; @brakerski2014efficient] is the initial cryptosystem proposed in [@regev2005lattices; @regev2009lattices].  The ciphertext and the secret key are vectors of some size $n$ and the plaintext is decrypted by computing the inner product of these vectors.  Homomorphic multiplication is performed by tensoring two ciphertexts which is decryptable by a tensored secret key.  As a result, the size of the ciphertext increases to $n^2$ which is then multiplied with a re-linearization matrix, provided as the public evaluation key for multiplication.  This is called the *key switching* mechanism that takes a tensored ciphertext and a tensored secret key and converts it into a ciphertext of size $n$ that encrypts the same message under a different secret key of size $n$. The increase in noise due to homomorphic operations is countered using a noise management technique called *modulus switching* introduced in [@brakerski2014efficient]. 

Our Contribution
----------------

In this paper, we propose a leveled fully homomorphic encryption scheme based on multivariate polynomial evaluations.  In order to prove the security of the scheme, we introduce a generalization of the LWE problem called the Hidden Subspace Membership (HSM) problem.  Given a subspace $\mathcal{S}$ of a vector space $\mathcal{V}$, the HSM problem is to distinguish a noisy vector of $\mathcal{S}$ from a random vector sampled from the uniform distribution on $\mathcal{V}$ with probability close to 1.  We show that if there exists an adversary against the HSM problem, then it can be used to solve the LWE problem.  On the other hand, an adversary against the ‘LWE problem with multiple secrets’ can be used to solve an instance of the HSM problem.  We discuss the symmetric key variant of the scheme and show that it can be converted to its public key variant using state of the art ‘symmetric to asymmetric’ transformations. 

The proposed scheme is based on the evaluation of multivariate polynomials of a secret ideal $\mathcal{I}$. Given noisy evaluations of a random polynomial in $\mathcal{I}$ at a set of secret points, the ciphertext is obtained by adding the scaled plaintext bit to each of these evaluations.  Hence, the ciphertext is a noisy vector of the subspace obtained by evaluating polynomials in $\mathcal{I}$. The secret key is a vector in its perpendicular space and decryption is performed by computing the inner product of the ciphertext with the secret key.  Multiplication in the scheme is performed by evaluating a tensor on the ciphertexts.  Unlike other LWE-based schemes, homomorphic multiplication does not increase the size of the ciphertexts.  However, the noise associated with them increases with each operation.  Homomorphic multiplication squares the noise whereas homomorphic addition increases it by a factor of two.  We then use modulus switching to convert the scheme into a leveled fully homomorphic one. 

Further, we show that the proposed scheme can be used to encrypt multiple plaintext bits into a single ciphertext.  This leads to a decrease in the ciphertext expansion ratio by a polynomial factor in the security parameter.  Homomorphic operations can be performed in an SIMD (Single Instruction Multiple Data) style which means homomorphic addition and multiplication can be performed simultaneously on multiple plaintext bits.  A number of schemes that explores this property are [@smart2014fully; @brakerski2013packed; @peikert2008framework; @gentry2012fully]. 

Related Work
------------

A family of cryptosystems based on multivariate polynomial algebra is the Polly Cracker schemes [@fellows1993combinatorial; @barkee1994you].  The secret key is a Gröbner basis $\mathcal{G}$ of an ideal $\mathcal{I} \subseteq \mathcal{R}$ and the security depends on the hardness of computing $\mathcal{G}$. These schemes are vulnerable to attacks using Gröber basis construction algorithms as well as attacks using linear algebra [@barkee1994you; @levy2009survey].  Noisy variants of these cryptosystems have been proposed to overcome these vulnerabilities [@albrecht2011polly; @herold2012polly]. 

The proposed scheme can also be seen as a coding theory based scheme.  If the polynomial chosen from the ideal $\mathcal{I}$ is $f$ and a plaintext is denoted by $m \in \{0,1\}$, then the ciphertext can be seen as a noisy punctured Reed-Muller encoding of the polynomial $f+m$. A similar construction based on coding theory was proposed in [@armknecht2011constructing] where the ciphertexts are noisy codewords with fixed noise locations and the secret key allows to identify these locations.  The encryptions of zero form a vector subspace and given sufficient samples, one can distinguish an encryption of zero from that of a random message with probability equal to 1. 

Paper Organization
------------------

The remainder of the paper is organized as follows.  Section \[HSM:sec2\] contains the preliminaries for the proposed work.  In section \[HSM:sec3\], we describe the Hidden Subspace Membership problem and discuss its hardness with respect to the LWE problem.  In section \[HSM:sec4\] we propose a homomorphic encryption scheme based on the hardness of the HSM problem.  Finally, in section \[batching\], we discuss a batch variant of the scheme. 

Preliminaries {#HSM:sec2}
=============

Notation
--------

The following notations are used in the paper.  We use $\lambda$ to denote the security parameter.  The set of integers and natural numbers are denoted by $\mathbb{Z}$ and $\mathbb{N}$ respectively.  Given a set ${S}$, $x{  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}}\mathcal{S}$ means that $x$ is sampled uniformly at random from ${S}$. For a real number $x$, $\lfloor x \rfloor$, $\lceil x \rceil $ and $\lfloor x \rceil$ denote the rounding of $x$ down, up or to the nearest integer.  We use $\mathbb{Z}_q$ to denote the set of integers in the interval $(-\frac{q}{2},\frac{q}{2}]$. $\mathbb{F}_{q}$ denotes a finite field of cardinality $q$, where $q$ is prime.  Here, $\mathbb{F}_q$ represents the integers in the interval $\left[-\left\lfloor \frac{q}{2} \right\rfloor,\left\lfloor \frac{q}{2} \right\rfloor \right] $.  $\mathbb{F}_q[x_1,\hdots,x_\ell]_{\leq d}$ denotes the set of polynomials in $x_1,\hdots,x_\ell$ with coefficients in $\mathbb{F}_q$ of degree $\leq d$. Given a set of points $\{\bm{z}_i\in \mathbb{F}_q^\ell\}_{1 \leq i \leq n} $ and a polynomial $f \in \mathbb{F}_q[x_1,\hdots,x_\ell]_{\leq r}$, $f(\bm{z}_1,\hdots,\bm{z}_n) \in \mathbb{F}_q^n$ denotes the evaluation of $f$ at these points.  We use ‘ln’ to denote natural logarithm and ‘log’ to denote logarithm base 2. 

We use uppercase script letters $\mathcal{A},\mathcal{B},\hdots$ to denote tensors, uppercase letters ${A}, {B}, \hdots$ to denote matrices and lowercase bold letters $\bm{a}, \bm{b},\hdots$ to denote vectors.  The notation $\bm{v}(i)$ is used to denote the $i^{th}$ element of $\bm{v}$. The $\ell_i$ norm of a vector $\bm{v}$ is denoted by ${\left\lVert\bm{v}\right\rVert}_{i}$ and the inner product of two vectors $\bm{v}_1, \bm{v}_2$ is denoted using $\langle \bm{v}_1,\bm{v}_2\rangle:=\bm{v}_1^T \bm{v}_2\).  We write $negl()$ to denote an arbitrary negligible function.  A function $negl(x): $ is called negligible if, for every $c $, there exists an integer $n\_c$ such that $negl(x) n\^c$. 

\subsection{Lattices}
Given a set of $n$ linearly independent vectors $\_1,,\_n \^n$ for some $n $, a lattice $$ is defined as the set of all integer combinations of $\_1,,\_n$. The set of vectors $\_1,,\_n$ is called a basis for $$.  If $=(\_1,,\_n) \_q\^[n n]{}$ denotes the matrix with $\_i$ as the column vectors, then a lattice generated by $$ is defined as
\begin{align}
\Lambda(\bm{B})=\{\bm{B} \bm{v} ~\vert~\bm{v} \in \mathbb{Z}^n \}
\end{align} 
The \textit{volume} or the \textit{determinant} of a lattice is the absolute value of the determinant of the basis $$ i.e., $[vol]{}()=[()]{}$.
\begin{definition}
{\bf{\textup{($q$-ary Lattices).}}}  For some $q $, a lattice $ $ is called a $q$-ary lattice if it satisfies $q \^n \^n$. A $q$-ary lattice can be thought of as a subgroup of $\_q\^n$. A vector $$ is in the lattice $$ if $  q $.  Given a matrix $ \_q\^[n M]{}$, the following are two $M$ dimensional $q$-ary lattices. 
\begin{align*}
\Lambda_q(\bm{A})&=\left\lbrace \bm{v} \in \mathbb{Z}_q^M~\vert~\bm{v}=\bm{A}^T \bm{w} ~\text{mod}~q\text{ for some }\bm{w} \in \mathbb{Z}_q^n  \right\rbrace \\
\Lambda_q^{\perp}(\bm{A})&=\left\lbrace \bm{v} \in \mathbb{Z}_q^M~\vert~\bm{A} \bm{v}=\bm{0}~\text{mod}~q \right\rbrace
\end{align*}
\end{definition}
The first lattice corresponds to the linear code generated by the rows of $$ and the second lattice corresponds to a linear code whose parity check matrix is given by $$.  The dual of a lattice $$ is the set of vectors $ span()$ such that $, $ for all $ $.  By definition, the above two lattices are dual to each other \cite{micciancio2011lattice}.  

\subsection{Learning with Errors}
The LWE problem is to recover a secret $ \_q\^n$, given a set of noisy linear equations on $$.  It was introduced in \cite{regev2005lattices} and is an extension of the Learning Parity with Noise (LPN) problem to a higher modulus.  It can also be seen as the problem of decoding random linear codes.  Given that the noise is sampled from a discrete Gaussian distribution, there exists a quantum reduction of LWE from the worst-case lattice problems like the decisional Shortest Vector Problem (G{ap}SVP) and the Shortest Integer Vector Problem (SIVP)\cite{regev2005lattices,regev2009lattices}.  Further, \cite{peikert2009public} and \cite{brakerski2013classical} gave classical reductions of LWE from the worst-case lattice problems for an exponential modulus and a polynomial modulus respectively.  The search variant of Learning with Errors can be defined as follows. 
\begin{definition}
{\bf(Learning With Errors)}.   For positive integers $q,n $, let $$ be a probability distribution on $$ and $$ be a secret vector in $\_q\^n$. Given polynomially many samples of the form \((\bm{a}_i,b_i)\in \mathbb{Z}_q^n \times \mathbb{Z}_q \) where $\_i $ is sampled uniformly at random from $ \_q\^n $ and $b\_i:=\_i,+e\_i ( q)$ for some $e\_i [ ]{} $, the learning with Errors problem \textup{LWE}$\_[n,q,]{}$ is to output the vector $ \_q\^n$ with overwhelming probability. 

The decisional variant of the problem, called decisional {LWE} and denoted by \textup{DLWE}$\_[n,q,]{}$, is to distinguish LWE samples from samples chosen according to the uniform distribution over \(\mathbb{Z}_q^n \times \mathbb{Z}_q\).  $$ wins the game if it can guess the value of $$ with non-negligible advantage given by $$, where  $:= Pr\[=\^\] $.  \end{definition}

In terms of the code-based game playing framework adopted from \cite{bellare1997concrete}, the LWE problem (search and decision) can be defined in terms of the games shown in Figure \ref{box:box1} \cite{albrecht2011polly} and  \ref{box:box2}.  A PPT adversary $$ wins the game LWE$\_[n,q,]{}$ if it can guess the value of $$ with non-negligible advantage given by $$, where  $:= Pr\[=\^\] $. {  \begin{align} 
Adv_{n,q,\mathcal{X}}^{\text{LWE},\mathcal{A}}(\lambda):=Pr\left[\text{LWE}_{n,q,\mathcal{X}}^{\mathcal{A}}(\lambda)=1\right]
\end{align}}A PPT adversary $$ wins the game DLWE$\_[n,q,]{}$ if it can guess the value of $c$ with a non-negligible advantage given by 
{ \begin{align} 
Adv_{n,q,\mathcal{X}}^{\textup{LWE},\mathcal{A}}(\lambda):=\Bigg|Pr\left[\textup{LWE}_{n,q,\mathcal{X}}^{\mathcal{A}}(\lambda) = 1\right]-\frac{1}{2} \Bigg|
\end{align}}\begin{story}[H] \scriptsize
  {
  \centering
  \tikzstyle{mybox} = [draw=black,line width=1.2pt,inner sep=8pt]
  \begin{tikzpicture}
   \node [mybox] (fig){    \begin{minipage}{0.95\textwidth}{\begin{multicols}{3} 
  \setlength{\columnsep}{.55cm}
  
\underline{\textbf{ Initialize}} 
\begin{algorithmic} \scriptsize
\Begin
\State $n\gets $ $n(\lambda)$
\State $\bm{s} {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\tiny{\$}$}\vss}}}} \mathbb{Z}_q^{n}$
\End \\~\\
\end{algorithmic}

\underline{\textbf{ Sample}} 
\begin{algorithmic} \scriptsize
\Begin
\State $\bm{a} {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} \mathbb{Z}_q^{n}$
\State $ {e} {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} \mathcal{X} $
\State $b \!= \left( \bm{a}\!^{T} \bm{s} +{e}\right)\,\text{mod}\,q$
\State \Return $(\bm{a},b)$
\End 
\end{algorithmic}

\underline{\textbf{ Finalize ($\bm{s}^{\prime}$)}} 
\begin{algorithmic} \scriptsize
\Begin
\State \!\!\Return $(\bm{s}\!=\!\bm{s}^{\prime})$
\End \\~\\~\\
\end{algorithmic}
  \end{multicols}}\end{minipage}
   };
  \end{tikzpicture}
}
\caption[]{LWE$_{n,q,\mathcal{X}}$ Game}
  \label{box:box1}
\end{story}
$$ on $$ and an integer $q$, the DLWE problem can be defined in terms of the game shown in Figure \ref{box:box2}.  A PPT adversary $$ wins the game if it can guess the value of $c$ with a non-negligible advantage given by 
\begin{story}[H] \scriptsize
  {
  \centering
  \tikzstyle{mybox} = [draw=black,line width=1.2pt,inner sep=8pt]
  \begin{tikzpicture}
   \node [mybox] (fig){    \begin{minipage}{0.95\textwidth}{\begin{multicols}{4} 
  \setlength{\columnsep}{.55cm}
  
\underline{\textbf{ Initialize}} 
\begin{algorithmic} \scriptsize
\Begin
\State $n\gets $ $n(\lambda)$
\State $\bm{s} {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\tiny{\$}$}\vss}}}} \mathbb{Z}_q^{n}$
\State $c {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} \{0,1\} $
\End \\~\\~\\~\\~\\
\end{algorithmic}

\underline{\textbf{ Sample}( )} 
\begin{algorithmic} \scriptsize
\Begin
\State $\bm{a} {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} \mathbb{Z}_q^{n}$
\State $ {e} {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} \mathcal{X} $
\State $b = \left[ \bm{a}\!^{T} \!\!\bm{s} \!+\!{e}\right]_q$
\State \Return $(\bm{a},b)$
\End \\~\\~\\
\end{algorithmic}

\underline{\textbf{ Challenge}( )} 
\begin{algorithmic} \scriptsize
\Begin
\State $(\bm{a},b) {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} \mathbb{Z}_{q}^{n+1}$
\If {$c =1 $}
\State    $ \bm{a} {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} \mathbb{Z}_q^{n}$
\State ${e} {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} \mathcal{X}$
\State $b = \left[ \bm{a}\!^{T} \!\!\bm{s} \!+\!{e}\right]_{\!q}$
\EndIf
\State \Return $(\bm{a},b)$
\End 
\end{algorithmic}

\underline{\textbf{ Finalize ($c^{\prime}$)}} 
\begin{algorithmic} \scriptsize
\Begin
\State \!\!\Return $( c = c^{\prime})$
\End \\~\\~\\~\\~\\~\\
\end{algorithmic}
  \end{multicols}}\end{minipage}
   };
  \end{tikzpicture}
}
\caption[]{DLWE$_{n,q,\mathcal{X}}$ Game}
  \label{box:box2}
\end{story}



$\_$ on $\_q$ such that $q &gt; 2 $, where $ &gt; 0$ is a real number and $n$ is the dimension of the lattice for a polynomial modulus $q=q(n)$.
\subsubsection{Discrete Gaussian distribution}

The noise in the LWE problem is usually sampled from a discrete Gaussian distribution.  For $&gt;0$ and $q=q(n)$, 
$ \_ $ over $$ is given by, 
 $\_$ is a discrete Gaussian distribution on $$ with mean zero and standard deviation $:=q$
 $x D\_$ and outputting $x q   q$.
 such that
 \begin{align}
 Pr\left[x {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} \mathcal{X}_{\alpha}\right]:= \frac{exp\left(-\pi x^2/\sigma^2\right)}{\sum_{y \in \mathbb{Z}} exp\left(-y^2/\sigma^2 \right)}
\end{align}  
For $q &gt; 2 $, the decisional variant of the shortest vector problem (G{\footnotesize{AP}}SVP) reduces to the LWE problem \cite{regev2009lattices,peikert2009public,brakerski2013classical} and the best known algorithms in solving G{\footnotesize{AP}}SVP runs in exponential time. 
$$ is the quality of approximation for the shortest vector problem \cite{micciancio2011lattice,regev2010learning}.  
  The hardness of LWE can be summarized in terms of the following theorem derived from the works of \cite{regev2009lattices,peikert2009public,brakerski2013classical}. 
\begin{theorem}
\textup{({\cite{regev2009lattices,peikert2009public,brakerski2013classical}}).}  Let $q=q(n)$ be prime and $n$ be an integer.  Let $(0,1)$ be such that $q 2$ and let $:=\_$ be a discrete Gaussian distribution on $\_q$ with mean 0 and standard deviation $q$. Given samples from the distribution of LWE$\_[n,q,]{}$, if there exists an algorithm that solves the LWE problem for parameters $n,q,$, then 
\begin{itemize}
\item There exists an efficient quantum algorithm for solving the problems G{\scriptsize AP}SVP$\_[(n/)]{}$ and SIVP$\_[(n/)]{}$ on any $n$-dimensional lattice. 

\item There exists an efficient classical algorithm for solving a worst-case lattice problem on any lattice of dimension $$. 

\item If $q 2\^[n/2]{}$, then there exists an efficient classical algorithm that solves the G{\scriptsize AP}SVP$\_[(n/)]{}$ problem on any $n$-dimensional lattice. 
\end{itemize}
\end{theorem}

 A distribution over the integers is said to be bounded when it takes values within a specific interval.  $B$ with very high probability.   
\begin{definition}
{\bf(${B}$-bounded distribution)}.  A distribution $$ over the set of integers is said to be $B$-bounded if $\[-B,B\]$. 
\begin{align}
Pr\left[{\left\lvertx\right\rvert}>B ~\vert~ x {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} \mathcal{X}\right]=\text{negl}(n)
\end{align}
\end{definition}

$ denotes a function to be performed on the plaintexts $m_1,\hdots,m_t$, then homomorphically evaluating $\phi$ involves calculating a new ciphertext $\bm{c}_{\scriptscriptstyle eval} $ such that $Dec(\bm{c}_{\scriptscriptstyle eval},sk)=\phi(m_1,\hdots,m_t)$.

Tensors
-------

A tensor can be defined as a multilinear map $\mathcal{T}: \mathcal{V}_1 \times \mathcal{V}_2 \times \cdots \times \mathcal{V}_n \rightarrow \mathcal{W}$, where $\mathcal{V}_1,...,\mathcal{V}_n$ and $\mathcal{W}$ are finite-dimensional vector spaces.  Given fixed bases for the vector spaces, a tensor can be represented by a multidimensional array.  The order of a tensor or the dimension of the corresponding array is the number of indices required to represent a component of the array. 

*Slices* in a tensor are two-dimensional sections generated by fixing all indices except two.  In a third order tensor, slices generated by keeping the last index fixed are called frontal slices analogous to matrices.  Therefore a third order tensor $\mathcal{A}^{I_1 \times I_2 \times I_3}$ is an $I_3$ array of $I_1 \times I_2$ matrices.  A *Bilinear map* is a function $\phi:\mathcal{V}_1 \times \mathcal{V}_2 \rightarrow \mathcal{V}_3$ that takes two elements from two vector spaces $\mathcal{V}_1$ and $\mathcal{V}_2$ and maps it to an element of a third vector space $\mathcal{V}_3$ such that it is linear in each of its elements; i.e., for a fixed $\bm{v}_1 \in \mathcal{V}_1$, $\bm{v}_1 \mapsto \phi(\bm{v}_1,\bm{v}_2)$ is a linear function from $\mathcal{V}_1$ to $\mathcal{V}_3$ and for a fixed $\bm{v}_2 \in \mathcal{V}_2$, $\bm{v}_2 \mapsto \phi(\bm{v}_1,\bm{v}_2)$ is a linear function from $\mathcal{V}_2$ to $\mathcal{V}_3$. An order-3 tensor $\mathbfcal{M}$ can be used to represent a bilinear map $\phi:\mathcal{V} \times \mathcal{V} \rightarrow \mathcal{V}$, on the vector space $\mathcal{V}$ over $\mathbb{F}$. If $dim(\mathcal{V})=n$ and $\{\bm{b}_1,...,\bm{b}_n \}$ denotes a basis for $\mathcal{V}$, then $$\begin{aligned}
\phi(\bm{b}_i,\bm{b}_j)= \sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n} M_{ijk} \cdot \bm{b}_k\end{aligned}$$ For a fixed $k$, $\bm{M}_k:=(M_{ijk})_{{{1 \leq i,j \leq n}}}$ represents a unique matrix $\bm{M}_k$ of order $n \times n$. For $1 \leq k \leq n$, $\bm{M}_k$ forms the frontal slices of the tensor $\mathbfcal{M}$. The bilinear map $\phi$ then acts on two arbitrary vectors $\bm{v}_1=[{v}_{1,1} ~ v_{2,1} ~ \cdots ~ v_{n,1}]^{T},\bm{v}_2=[v_{1,2} ~ v_{2,2}~\cdots ~v_{n,2}]^{T} \in \mathcal{V}$ as follows: $$\begin{aligned}
 \label{bilinear map}
\phi(\bm{v}_1,\bm{v}_2) = \phi\big(\sum_{i=1}^{n} v_{i,1}\bm{b}_i, \sum_{j=1}^{n} v_{j,2}\bm{b}_j \big) 
            &= \sum_{i,j=1}^{n} v_{i,1} \phi(\bm{b}_i,\bm{b}_j )v_{j,2} \notag\\
            &= \begin{bmatrix}
        \bm{v}_1^{T} \bm{M}_{1} \bm{v}_2  & \hdots & \bm{v}_1^{T} \bm{M}_{n} \bm{v}_2
        \end{bmatrix}^{T}   $$

### The $n$-mode Product

The $n$-mode product defines multiplication of a tensor by a matrix.  In general, the elementwise $n$-mode product of a tensor $\mathbfcal{T} \in \mathbb{F}^{I_1 \times I_2 \times \cdots \times I_N}$ and a matrix $\bm{M} \in \mathbb{F}^{J \times I_n}$ is defined as: $$\begin{aligned}
{(\mathbfcal{T}\times \bm{M})}_{i_1 i_2 \cdots i_{n-1} j i_{n+1} \cdots i_N} &=& \sum_{i_n=1}^{I_n} \mathbfcal{T}_{i_1 i_2 \cdots i_{n-1} i_n i_{n+1} \cdots i_N} \bm{M}_{j,i_n}\end{aligned}$$ The resultant tensor is of the order of $(I_1 \times I_2 \times \cdots \times I_{n-1} \times J \times I_{n+1} \times \cdots \times I_N)$.

The Hidden Subspace Membership Problem {#HSM:sec3}
======================================

In this section, we introduce the Hidden Subspace membership (HSM) problem and discuss its hardness in relation to the Learning with Errors problem.  If $\mathcal{S}$ denotes an $\ell$-dimensional subspace of the vector space $\mathbb{Z}_q^n$ for some $\ell,n \in \mathbb{N}$ and $\mathcal{N}$ denotes a noise distribution on $\mathbb{Z}_q^n$, then the input to the problem are samples of the form $\bm{v}+\bm{e}$ where $\bm{v} {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} \mathcal{S}$ and $\bm{e} {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} \mathcal{N}$. Given a vector $\bm{v}^{\prime}$, the Hidden Subspace Membership problem is to decide whether $\bm{v}^{\prime} \in \mathcal{S}+\mathcal{N}$ or is sampled uniformly at random from $\mathbb{Z}_q^n$.

Observe that, the noise-free variant of the problem is extremely easy to solve.  We can find $\ell$-linearly independent samples of $\mathcal{S}$ that can be used to construct a basis for $\mathcal{S}$ which in turn can be used to construct a basis for its perpendicular space $\mathcal{S}^{\perp}$. Then, one can check whether a given vector lies in $\mathcal{S}$ by checking if it lies in the kernel of $\mathcal{S}^{\perp}$. We now show that the HSM problem is a generalization of the Learning with Errors (LWE) problem.  Consider the LWE problem with parameters $n-1,q,\mathcal{X}$ denoted by LWE$_{n-1,q,\mathcal{X}}$. Given an LWE$_{n-1,q,\mathcal{X}}$ sample $(\bm{a}_i,b_i)\in \mathbb{Z}_q^{n-1} \times \mathbb{Z}_q$, where $\langle \bm{a}_i, \bm{s}\rangle +e_i =b_i~(\text{mod}~q)$, we can write [ $$\begin{aligned}
 \label{lwe}
\begin{bmatrix} \bm{a}_i^T & -{b}_i \end{bmatrix}\begin{bmatrix}
\bm{s} \\ 1
\end{bmatrix} \approx_{\mathcal{X}} {0}~(\text{mod}~q)\end{aligned}$$]{} which is a noisy equation with the noise being sampled from the distribution $\mathcal{X}$ on $\mathbb{Z}_q$. Observe that, $(\bm{a}_i,b_i)$ is a noisy element of the $(n-1)$-dimensional subspace $(\bm{s},1)^{\perp} \subseteq \mathbb{Z}_q^{n}$ where the noise is added only to the last element of the vector.  We generalize it to a subspace $\mathcal{S} \subseteq \mathbb{Z}_q^n$ of dimension $\ell$, for any $\ell \in \mathbb{N},\ell \geq 1$ where the last $(n-\ell)$ entries of a vector in $\mathcal{S}$ are corrupted with noise from the distribution $\mathcal{X}$.

Let $\bm{v}$ be a vector in $\mathcal{S}$. We can always write $\bm{v}$ in such a way that the last $n-\ell$ elements are linear combinations of the first $\ell$ elements.  Let $\bm{e}:=(0,\hdots,0,e_{\ell+1},\hdots,e_n)$ be the error vector where the non-zero entries of $\bm{e}$ are chosen independently from the distribution $\mathcal{X}$. If $\bm{w}=\bm{v}+\bm{e}$, then for some $\bm{s} \in \mathcal{S}^{\perp}$, we have $$\begin{aligned}
\langle \bm{w}, \bm{s}\rangle \approx_{\mathcal{X}^{\prime}} 0\,(\text{mod}\,q)\end{aligned}$$ where $\mathcal{X}^{\prime}$ is a zero-mean Gaussian with a slightly wider standard deviation than that of $\mathcal{X}$. The HSM problem can be formally defined as follows. 

[**(Hidden Subspace Membership)**]{}.  For positive integers $n,q,\ell \in \mathbb{N}$ where $q=q(n)$ is prime and $\ell \geq 1$, let $\mathcal{S}$ be an $\ell$-dimensional subspace of the vector space $\mathcal{V}:=\mathbb{Z}_q^n$. Let $\mathcal{N}:=(\bm{0},\mathcal{X}^{n-\ell})$ be a noise distribution on $\mathcal{V}$ where $\mathcal{X}:=\mathcal{X}_{\alpha}$ is the zero mean distribution on $\mathbb{Z}_q$ and $\bm{0}$ is the all zero vector of size $\ell$. Then, the HSM problem denoted by $_{\ell,n,q,\mathcal{N}}$ can be defined in terms of the game shown in Figure \[box:box3\].  A PPT adversary $\mathcal{A}$ wins the game if it can guess the value of $c\in\{0,1\}$ with a non-negligible advantage given by [ $$\begin{aligned}
Adv_{\ell,n,q,\mathcal{N}}^{\textup{HSM},\mathcal{A}}(\lambda):=\Bigg| Pr[\textup{HSM}_{\ell,n,q,\mathcal{N}}^{\mathcal{A}}(\lambda)= 1]-\frac{1}{2} \Bigg|\end{aligned}$$]{}

= \[draw=black,line width=1.2pt,inner sep=8pt\]

(fig)

[4]{}

$\!\bm{B} \gets {\mathcal{S}}(n,q,\ell)$ $c {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} \{0,1\} $\
 \
 \
 \
 \

$\bm{v} {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} \mathcal{S}$, $\bm{e} {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} \mathcal{N} $ $\bm{v} \gets\bm{v}+ \bm{e}$ $\bm{v}$\
 \
 \
 \

$\bm{v} {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} \mathbb{F}_{q}^{n}$ $ \bm{v} {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} \mathcal{S}$ $\bm{e} {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} \mathcal{N}$ $\bm{v} \leftarrow \bm{v}+\bm{e}$ $\bm{v}$

$(c \!=\!  c^{\prime})$\
 \
 \
 \
 \

;

We now show that if an adversary can solve the HSM$_{\ell,n,q,\mathcal{N}}$ problem, then it can be used to solve the LWE$_{\ell,q,\mathcal{X}}$ problem. 

\[ch3:Reduction from LWE to HSM\] Let $\mathcal{S}$ be an $\ell$-dimensional subspace of the vector space $\mathbb{Z}_q^n$ for some $\ell \leq n$. Let $\mathcal{X}:=\mathcal{X}_{\alpha}$ be the discrete Gaussian distribution on $\mathbb{Z}_q$ with mean 0 and standard deviation $\alpha q$. Let $\mathcal{N}:=(\bm{0},\mathcal{X}^{n-k})$ be the noise distribution on $\mathbb{Z}_q^n$, where $\bm{0}$ is the all zero vector of size $\ell$. If there is an efficient algorithm $\mathcal{A}$ that can solve an instance of the HSM$_{\ell,n,q,\mathcal{N}}$ problem, then there exists an efficient algorithm $\mathcal{B}$ against the DLWE$_{\ell,q,\mathcal{X}}$ problem such that [$$\begin{aligned}
Adv_{\ell,n,q,\mathcal{N}}^{\textup{HSM},\mathcal{A}}(\lambda)=Adv_{\ell,q,\mathcal{X}}^{\textup{DLWE},\mathcal{B}}(\lambda) \notag\end{aligned}$$]{}

We construct an adversary $\mathcal{B}$ against the LWE problem from an adversary $\mathcal{A}$ against the HSM problem.  In other words, we need to generate samples for the HSM problem from samples of the LWE problem.  When $\mathcal{A}$ calls the $\textbf{Sample}$ oracle of HSM$_{\ell,n,q,\mathcal{N}}$, $\mathcal{B}$ queries the $\textbf{Sample}$ oracle of DLWE$_{\ell,q,\mathcal{X}}$ to obtain $(\bm{a},b)$ where $\bm{a}=(a_1,\hdots,a_\ell) {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} \mathbb{Z}_q^\ell$ and $b=\langle \bm{a}, \bm{s}\rangle+e~(\text{mod}\,q)$ for LWE secret $\bm{s} \in \mathbb{Z}_q^\ell$ and an error $e {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} \mathcal{X}$. It then returns a vector $\bm{v}=(v_1,\hdots,v_n) \in \mathbb{Z}_q^n$ where $v_i=a_i$ for $1 \leq i \leq \ell$, $v_{\ell+1}=b$ and for $\ell+2 \leq i \leq n$, $$\begin{aligned}
v_i= \langle \bm{a}, \bm{s}_i\rangle+e_i~(\text{mod}\,q)\end{aligned}$$ for some $\bm{s}_i {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} \mathbb{Z}_q^\ell$ and $e_i {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} \mathcal{X}$. When $\mathcal{A}$ queries the **Challenge** oracle of HSM, $\mathcal{B}$ chooses $c \leftarrow \{0,1\}$ uniformly at random and generates $\bm{v}$ as above if $c=1$. For $c=0$, $\bm{v}$ is chosen uniformly at random from $\mathbb{Z}_q^n$. If $\mathcal{A}$ outputs 1 with non-negligible probability on inputs from the distribution $\mathcal{S}+\mathcal{N}$ and 0 with non-negligible probability on inputs from the uniform distribution over $\mathbb{Z}_q^n$, then $\mathcal{A}$ can distinguish an LWE sample from a sample chosen from the uniform distribution over $ \mathbb{Z}_q^{\ell} \times \mathbb{Z}_q $ with the same advantage.  Hence, $\mathcal{B}$ can solve the DLWE problem if $\mathcal{A}$ solves the HSM problem.  Further, it can be easily verified that $\mathcal{B}$ runs in polynomial time and uses a polynomial number of samples. 

The HSM$_{\ell,n,q,\mathcal{N}}$ problem can be solved by constructing a basis for $\mathcal{S}^{\perp}$. Let $\{\bm{s}_{\ell+1}^{\prime},\hdots,\bm{s}_{n}^{\prime}\}$ be a basis for $\mathcal{S}^{\perp}$. Then, given any HSM$_{\ell,n,q,\mathcal{N}}$ sample $\bm{w} \leftarrow \bm{v}+\bm{e} \in \mathcal{S}+\mathcal{N}$, we have $$\begin{aligned}
\langle \bm{w}, \bm{s}_i^{\prime}\rangle = \langle\bm{v}+\bm{e}, \bm{s}_i^{\prime}\rangle =\langle \bm{e},\bm{s}_i^{\prime}\rangle ~\text{for}~\ell+1 \leq i \leq n\end{aligned}$$ where $\langle \bm{e},\bm{s}_i^{\prime}\rangle$ is a normal variable with mean 0 and standard deviation ${\left\lVert\bm{s}_i\right\rVert}\alpha q$. On the other hand, if $\bm{w}$ is uniform in $\mathbb{Z}_q^n$, then $\langle \bm{w}, \bm{s}_i^{\prime}\rangle$ is a random element in $\mathbb{Z}_q$ for $\ell+1 \leq i \leq n$. Thus, the HSM$_{\ell,n,q,\mathcal{N}}$ problem can be solved by distinguishing between these two cases. 

A PPT algorithm $\mathcal{A}$ that solves the LWE$_{\ell,q,\mathcal{X}}$ problem for a set of secret vectors $\{\bm{s}_{i} \in \mathbb{Z}_q^\ell\}_{1\leq i\leq n-\ell}$ can be used to construct a basis for the perpendicular space $\mathcal{S}^{\perp} \subseteq \mathbb{Z}_q^n$. The LWE problem with multiple secrets is proved to be as hard as the LWE problem with single secret.  An instance of the LWE problem with multiple secrets is given by $(\bm{a},b_1=\langle \bm{a},\bm{s}_1 \rangle+e_1,\hdots,b_{n-\ell}=\langle \bm{a},\bm{s}_{n-\ell} \rangle+e_{n-\ell} ) \in \mathbb{Z}_q^\ell \times \mathbb{Z}_q^{n-\ell}$ where $\bm{s}_i {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} \mathbb{Z}_q^{\ell}$, $\bm{a} {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} \mathbb{Z}_q^{\ell}$ and $e_i {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} \mathcal{X}$ for $1 \leq i \leq n-\ell$.

The HSM$_{\ell,n,q,\mathcal{N}}$ problem for an $\ell$-dimensional subspace $\mathcal{S}$ can be reduced to the LWE$_{\ell,q,\mathcal{X}}$ problem with multiple secrets $\{\bm{s}_{i}\}_{1 \leq i \leq n-\ell}$.

A basis for the subspace $\mathcal{S}$ can be written in terms of the matrix $$\begin{aligned}
\bm{B}=\begin{bmatrix}
\begin{array}{c}
\bm{B}_1\\
\hline
\bm{B}_2
\end{array}
\end{bmatrix} \in \mathbb{Z}_q^{n \times\ell}\end{aligned}$$ where $\bm{B}_1 \in \mathbb{Z}_q^{\ell\times\ell}$ is a full rank matrix and every row of $\bm{B}_2 \in \mathbb{Z}_q^{(n-\ell) \times\ell}$ is a linear combination of the rows of $\bm{B}_1$. Then, for some $\bm{v}=(\bm{v}_1,\bm{v}_2) \in \mathcal{S}^{\perp}$, we can write $$\begin{aligned}
 \label{subspace}
\bm{v}_1\bm{B}_1=-\bm{v}_2\bm{B}_2\end{aligned}$$ which implies that for any given $\bm{v}_2 {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}}\mathbb{Z}_q^{n-\ell}$, we can find a $\bm{v}_1 \in \mathbb{Z}_q^\ell$ such that the above equation is satisfied.  Therefore, we can find a basis $\{\bm{s}_{\ell+1}^{\prime},\hdots,\bm{s}_{n}^{\prime}\}$ for $\mathcal{S}^{\perp}$ such that $\bm{s}_{\ell+1}^{\prime}:=(s_{\ell+1}^1,\hdots ,s_{\ell+1}^\ell,1,0,\hdots,0)^T$, $\bm{s}_{\ell+2}^{\prime}:=(s_{\ell+2}^1,\hdots ,s_{\ell+2}^\ell,0,1,\hdots,0)^T,\hdots,\bm{s}_{n}^{\prime}:=(s_{n}^1,\hdots ,s_{n}^\ell,0,0,\hdots,1)^T$ for some $s_j^i \in \mathbb{Z}_q$ for $1 \leq i \leq \ell$ and $\ell+1 \leq j \leq n$. Given a sample $\bm{v}=(v_1,\hdots,v_\ell,v_{\ell+1}+e_{\ell+1},\hdots,v_n+e_n) \in \mathcal{S}+\mathcal{N}$, observe that for $\ell+1 \leq j \leq n$ $$\begin{aligned}
\langle \bm{v},\bm{s}_j^{\prime} \rangle =\sum_{i=1}^{\ell} v_i s_{j}^i-v_j+e_j\approx_{\mathcal{X}} 0~(\text{mod}\,q)\end{aligned}$$ where $ \sum_{i=1}^{\ell} v_i s_{j}^i-v_j=0 $ and hence, $v_j=\sum_{i=1}^{\ell} v_i s_{j}^i$. Thus, a query to the sample oracle of LWE with multiple secrets $\{\bm{s}_{i}\}_{1 \leq i \leq n-\ell}$ can be answered with $(\bm{a},b_1,\hdots,b_{n-\ell}) \in \mathbb{Z}_q^{\ell+1}$ where $\bm{a}=(v_1,\hdots,v_\ell)$ and $b_i=v_{\ell+i}$ for $1 \leq i \leq n-\ell$. Then, the LWE secret $\bm{s}_i$ is the vector $\bm{s}_i=(s_{\ell+i}^1,\hdots,s_{\ell+i}^\ell)$ for $1 \leq i \leq n-\ell$.

The LWE$_{\ell,q,\mathcal{X}}$ problem with the discrete Gaussian distribution with mean 0 and standard deviation $\alpha q$ such that $\alpha q \geq 2\sqrt{\ell}$ is considered to be hard when $$\begin{aligned}
\alpha \geq \frac{3}{2} \cdot \text{max} \left( \frac{1}{q},{2^{-2\sqrt{\ell\,\text{log}\,q\,\text{log}\,\delta}}}  \right)\end{aligned}$$ where $\delta$ is the quality of approximation for the shortest vector problem.  For state of the art lattice reduction algorithms, $\delta=1.01$ is hard and $\delta=1.005$ is infeasible [@micciancio2011lattice; @albrecht2011polly]. 

The Proposed Scheme {#HSM:sec4}
===================

Let us consider an ideal $\mathcal{I} $ of the polynomial ring $ \mathbb{F}_q[x_1,\hdots,x_l]$, where $q=q(\lambda)$ is prime.  For some $r \in \mathbb{N}$, $ \mathbb{F}_q[x_1,\hdots,x_l]_{\leq r} $ is a vector space of dimension $N:=\binom{l+r}{r}$ over $\mathbb{F}_q$. Let $\mathcal{I}_{\leq r}$ denotes the set of polynomials in $\mathcal{I}$ with degree $\leq r$. Then, $\mathcal{I}_{\leq r}$ is a subspace of $ \mathbb{F}_q[x_1,\hdots,x_l]_{\leq r} $.  Let $ \ell $ be the dimension of the subspace $\mathcal{I}_{\leq r}$. It is very easy to see that a polynomial $f \in \mathbb{F}_q[x_1,\hdots,x_l]_{\leq r}$ evaluated at all points of $ \mathbb{F}_q^{l} $ generates a vector in $ \mathbb{F}_q^{\scaleto{q^l}{6.8pt}} $.  The set of such vectors obtained by evaluating all polynomials in $ \mathbb{F}_q[x_1,\hdots,x_l]_{\leq r} $ constitutes an $N$-dimensional subspace of $ \mathbb{F}_q^{\scaleto{q^l}{7pt}} $.  Similarly, evaluating polynomials in $\mathcal{I}_{\leq r}$ gives us an $ \ell $-dimensional subspace of $ \mathbb{F}_q^{\scaleto{q^l}{7pt}} $.  Let $ \{\bm{z}_1,\hdots,\bm{z}_n\} $ be $n$ distinct points in $ \mathbb{F}_q^{l} $ for some $n \in \mathbb{N}$ such that $\ell < n \leq N$. Then, evaluating polynomials in $\mathcal{I}_{\leq r}$ at $ (\bm{z}_1,\hdots,\bm{z}_n) $ gives us an $ \ell $-dimensional subspace $\mathcal{S}_{\scriptscriptstyle \mathcal{I}_{\leq r}}$ of $\mathbb{F}_q^n$.

Evaluating polynomials in $\mathcal{I}_{\leq r}\subseteq \mathbb{Z}_q[x_1,\hdots,x_l]_{\leq r}$ with $dim(I_{\leq r}):=\ell$ at $n$ distinct points $(\bm{z}_1,\hdots,\bm{z}_n)$ spans an $\ell$-dimensional subspace of the vector space $\mathbb{Z}_q^n$.

Let $\mathcal{S}_{\scriptscriptstyle \mathcal{I}_{\leq r}}$ be the set of evaluations of all polynomials in $\mathcal{I}_{\leq r}$ at the points $(\bm{z}_1,\hdots,\bm{z}_n)$. It can be easily verified that $\mathcal{S}_{\scriptscriptstyle \mathcal{I}_{\leq r}}$ is a subspace of $\mathbb{Z}_q^n$. A polynomial $f \in \mathcal{I}_{\leq r}$ can be written in terms of a vector $\bm{f} \in \mathbb{Z}_q^N$ by assigning the $i^{th}$ component of $\bm{f}$ the coefficient of the $i^{th}$ monomial.  Let $\mathcal{F}$ be the space of all such vectors where $dim(\mathcal{F})=\ell$. Hence, evaluating polynomials in $\mathcal{I}_{\leq r}$ at $\bm{z}_1,\hdots,\bm{z}_n$ can be represented by a linear map ${G}: \mathcal{F} \rightarrow \mathcal{S}_{\scriptscriptstyle \mathcal{I}_{\leq r}}$. By definition, ${G}$ is onto.  Hence, $dim(\mathcal{S}_{\scriptscriptstyle \mathcal{I}_{\leq r}})=rank({G})$ and if $\{\bm{f}_1,\hdots,\bm{f}_\ell\}$ is a basis for $\mathcal{F}$, then $\{{G}(\bm{f}_1),\hdots,{G}(\bm{f}_\ell)\}$ spans the subspace $ \mathcal{S}_{\scriptscriptstyle \mathcal{I}_{\leq r}} $.  Now, to show that the dimension of $ \mathcal{S}_{\scriptscriptstyle \mathcal{I}_{\leq r}} $ is $\ell$, consider a non-zero vector $\bm{f} \in \mathcal{F}$ such that ${G} (\bm{f})=\bm{0}$, i.e., $\bm{f} \in Ker(G)$. Then, $\{\bm{f}\}$ can be extended to a basis for $\mathcal{F}$. However, the image of the new basis contains a zero vector and hence, we can find a smaller spanning set for $ \mathcal{S}_{\scriptscriptstyle \mathcal{I}_{\leq r}} $ which leads to a contradiction.  Hence, $Ker({G})=\{\bm{0}\}$ and by the rank nullity theorem, $dim(\mathcal{S}_{\scriptscriptstyle \mathcal{I}_{\leq r}})=rank({G})=\ell$.

The set of evaluation points $ \{\bm{z}_1,\hdots,\bm{z}_n\} \in \mathbb{F}_q^{l} $ must satisfy the following conditions:

1.   Every vector in $ \mathbb{F}_q^n $ can be got by evaluating a polynomial in $ \mathbb{F}_q[x_1,\hdots,x_l]_{\leq r} $ at $ (\bm{z}_1,\hdots,\bm{z}_n )$. 

2.   Every vector in $\mathbb{F}_q^{\ell}$ can be got by evaluating a polynomial in $\mathcal{I}_{\leq r}$ at $ (\bm{z}_1,\hdots,\bm{z}_{\ell} )$. 

These conditions ensure that equation (\[subspace\]) is satisfied for the subspace $\mathcal{S}_{\scriptscriptstyle I_{\leq r}}$, i.e., for every given vector $\bm{s}_2 \in \mathbb{F}_q^{n-\ell}$, there exists a vector $\bm{s} \in (\mathcal{S}_{\scriptscriptstyle I_{\leq r}})^{\perp}$ such that $\bm{s}=(\bm{s}_1,\bm{s}_2)$.

The proposed encryption scheme consists of the following algorithms.  The plaintext space is $\{0,1\}$ and the ciphertexts are vectors of order $n$ over $\mathbb{F}_q$ and the noise is sampled from the distribution $\mathcal{N}$. All operations are performed over $\mathbb{Z}_q$.

-   **KeyGen**($1^{\lambda}$): Let $\{\bm{s}_{\ell+1},\bm{s}_{\ell+2},\hdots,\bm{s}_n\} \in \mathbb{Z}_q^n$ be a basis for $(\mathcal{S}_{\scriptscriptstyle I_{\leq r}})^{\perp}$ where $$\begin{aligned}
     \label{sk}
    \begin{rcases}
     \bm{s}_{\ell+1} &=(s_{\ell+1}^1,\hdots,s_{\ell+1}^\ell,1,0,\hdots,0)^T \\
     \bm{s}_{\ell+2} &=(s_{\ell+2}^1,\hdots,s_{\ell+2}^\ell,0,1,\hdots,0)^T \\
     &~\vdots \\
      \bm{s}_n &=(s_{n}^1,\hdots,s_{n}^\ell,0,0,\hdots,1)^T
      \end{rcases}
      \end{aligned}$$Set $\bm{s}=\bm{s}_j $ for any $\ell+1 \leq j \leq n$. Choose a constant $p \in \mathbb{N}$ such that $p  \leq \lfloor q/2 \rfloor $ and a matrix $\bm{R} \in \mathbb{Z}_q^{n \times n}$ such that $\bm{R}$ is of the form $$\begin{aligned}
     \label{R}
    \bm{R}:=\left[
    \begin{array}{c|c}
    \bm{I}_{\ell} &  \bm{R}_1^{\ell \times(n-\ell)}\\
    \midrule
    \bm{0}^{(n-\ell)\times \ell} & \bm{I}_{n-\ell}
    \end{array}
    \right]\end{aligned}$$ where the entries of $\bm{R}_1$ are chosen uniformly at random from $\mathbb{Z}_q$ and $\bm{I}_{x}$ denotes the identity matrix of size $x$. The secret key is the vector $\bm{s}$, the set of points $ \{\bm{z}_1,\hdots,\bm{z}_n \} $ and the matrix $\bm{R}_1$. The constant $p$ is a public parameter along with $n,\ell$ and $q$.

-   **Encrypt**$(sk,{m})$: To encrypt a message $m \in \{0,1\}$, sample a polynomial $f$ of degree $\leq r$, uniformly at random from the ideal $\mathcal{I}$ and a vector $\bm{e}=(\bm{0},{\bm{e}^{\prime}})$, where $\bm{e}^{\prime}$ is a vector of order $n-\ell$ and the entries of $\bm{e}^{\prime}$ are chosen according to the distribution $\mathcal{X}$. Let $f(\bm{Z}):=(f(\bm{z}_1),\hdots,f(\bm{z}_n))$ be the vector obtained by evaluating $f$ at the set of points $\bm{Z}:=\{\bm{z}_1,\hdots,\bm{z}_n\}$. Then, for $ \ell+1 \leq k \leq n $ $$\begin{aligned}
    f(\bm{z}_{k}):=-\sum_{j=1}^\ell s_k^{j} \cdot f(\bm{z}_j)\text{ for some }(s_k^1,\hdots,s_k^\ell) \in \mathbb{Z}_q^\ell\end{aligned}$$ where $s_k^i$ denotes the $i^{th}$ entry of the vector $\bm{s}_k$ for $1 \leq i \leq \ell$ and $\ell+1 \leq k \leq n$. Let $\bm{m}=mp(\bm{0}^{\ell},\bm{1}^{n-\ell}) \in \mathbb{Z}_q^n$ where $\bm{0}^\ell$ denotes the all zero vector of size $\ell$ and $\bm{1}^{n-\ell}$ denotes the all one vector of size $n-\ell$. Then the ciphertext can be computed as [ $$\begin{aligned}
    \textstyle \bm{c}=\textstyle  \bm{R} \left( \bm{m}+ {f}(\bm{Z})+  \bm{e} \right) \in \mathbb{Z}_q^n\end{aligned}$$]{}

-   **Decrypt**$(sk,\bm{c})$: Given the ciphertext $\bm{c}$ and the secret key $sk$, the plaintext $m$ can be recovered as [ $$\begin{aligned}
     {m}=\left\lfloor \frac{1}{p}\left(\langle \bm{s},\bm{R}^{-1}\bm{c}\rangle \,\text{mod}\,q\right)\right\rceil\,\text{mod}~2 \end{aligned}$$ ]{}

Correctness of Decryption. {# COD}
--------------------------

For correct decryption, the noise in the decryption process must be small.  In the following lemmas, we analyze the magnitude of the noise in encryption and decryption.  The noise in the encryption algorithm is analyzed in the following lemma. 

Let $q,n,{\left\lvert\mathcal{X}\right\rvert} \leq B$ be as described in the scheme.  Let $\bm{c}=\bm{R}\left(\bm{m}+f(\bm{Z})+\bm{e}\right)$ be the encryption of a message $m \in\{0,1\}$ under the key $\bm{s}$. Then, for some ${e} $ with ${\left\lverte\right\rvert} \leq B$, it holds that

$ \langle \bm{s},\bm{R}^{-1}\bm{c}\rangle =m \cdot p + {e}~(\textup{mod}~q)$

Since $\bm{s} \in (\mathcal{S}_{\scriptscriptstyle I_{\leq r}})^{\perp}$ and $\bm{R}^{-1} \bm{c}=\bm{m}+f(\bm{Z})+\bm{e}$, $ \langle \bm{s},f(\bm{Z}) \rangle=0~(\text{mod}~q)$. If $e_n$ denotes the $n^{th}$ entry of $\bm{e}$, then $$\begin{aligned}
\langle \bm{s},\bm{R}^{-1}\bm{c}\rangle &= \langle \bm{s},  \bm{m}+f(\bm{Z})+\bm{e} \rangle ~(\text{mod}~q)\notag\\
&=m \cdot p+ \langle \bm{s},\bm{e} \rangle ~(\text{mod}~q) \notag\\
&= m\cdot p+ e_n~(\text{mod}~q)\end{aligned}$$ Since, ${\left\lverte_i\right\rvert} \leq B$ for $\ell+1 \leq i \leq n$, the lemma follows. 

The correctness of the decryption algorithm is expressed in terms of the following corollary. 

\[CoD\] Let $\bm{c}$ be the encryption of a message $m \in\{0,1\}$ under the key $\bm{s}$ such that $ \langle \bm{s},\bm{R}^{-1}\bm{c}\rangle =m\cdot p+ e_n~(\text{mod}~q)$. If ${\left\lverte_n\right\rvert} < \left\lfloor \frac{p}{2} \right\rfloor$, then $Dec(\bm{s},\bm{c})=m$.

If ${\left\lverte_n\right\rvert} < \left\lfloor \frac{p}{2} \right\rfloor$, then for $m=0$, $\langle \bm{s},\bm{R}^{-1}\bm{c}\rangle =e_n~(\text{mod}~q)$ is less than $p/2$ and hence the decryption function outputs 0.  Similarly, for $m=1$, $ \langle \bm{s},\bm{R}^{-1}\bm{c}\rangle = p+ e_n~(\text{mod}~q) $ is close $p$ and hence, the decryption function outputs 1. 

Security
--------

We show that the proposed scheme is IND-CPA secure based on the hardness of the Hidden Subspace Membership problem.  The IND-CPA security of a symmetric encryption scheme can be defined in terms of the game shown in Figure \[box:box4\].  A PPT adversary $\mathcal{A}$ selects two messages $(m_0,{m}_1)$ such that one of them is 0 and the Left-Right oracle outputs the encryption of one of the messages by choosing $c {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} \{0,1\}$. $\mathcal{A}$ wins the game if it can guess the value of $c \in \{0,1\}$ with a non-negligible advantage defined by [ $$\begin{aligned}
   {Adv}^{\text {IND-CPA},\mathcal{A}}(\lambda) := \Bigg| Pr[{\mathcal{A}}^{\text{ IND-CPA}}_{\text{Enc}_{sk}(\cdot)}(\lambda)=1]-Pr[\mathcal{A}^{\text{ IND-CPA}}_{\text{Enc}_{sk}(0)}(\lambda)=1] \Bigg|\end{aligned}$$]{}

= \[draw=black,line width=1.2pt,inner sep=8pt\]

(fig)

[4]{}

$sk \!\leftarrow\!   { \textbf{KeyGen}()}$ $c {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} \{0,1\} $

$\bm{c} \!\leftarrow\! { \textbf{Enc}({m},sk)}$ ${\bm{c}}$

$\bm{c} \!\leftarrow\! { \textbf{Enc}({m}_{c},\!sk\!)}$ $\bm{c}$

$(c =c^{\prime})$

;

A PPT adversary $\mathcal{A}$ that breaks the IND-CPA security of the proposed scheme with non-negligible advantage $\epsilon$ can be converted into a PPT adversary $\mathcal{B}$ that can solve an instance of the HSM problem with advantage at least $\frac{\epsilon}{2}$.

$\mathcal{B}$ initializes $\mathcal{A}$ with the parameters $(q,\ell,n,\mathcal{X})$. When $\mathcal{A}$ asks for an encryption of $0$, $\mathcal{B}$ queries the procedure **Sample** of the HSM game to get $\bm{v} \leftarrow \bm{v}+ \bm{e}$, where $\bm{e}{  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} \mathcal{N}$ and returns the vector $\bm{c}=\bm{v}$. Similarly, when $\mathcal{A}$ queries the **Left-Right** oracle of the IND-CPA game, $\mathcal{B}$ queries the procedure **Challenge** of the HSM game to get $\bm{v} $ and returns a vector $\bm{c}$ after choosing $c {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}}\{0,1\}$ and setting $\bm{c}=\bm{v}+( m_c \cdot p )\cdot (\bm{0},\bm{1})^T$ where $\bm{0}$ denotes the all zero vector of size $\ell$ and $\bm{1}$ denotes the all ones vector of size $n-\ell$.

If the sample obtained from the **Challenge** oracle of HSM is a noisy element of $\mathcal{S}$, then $\mathcal{A}$ runs in a similar environment to that of the IND-CPA game and hence, $\mathcal{B}$ outputs $c$ with probability $\frac{1}{2}+\epsilon$. On the other hand, if the sample returned is uniform in $\mathbb{F}_q^{ n}$, then $\mathcal{B}$ outputs $c$ with probability $\frac{1}{2}$. Therefore, the probability that $\mathcal{B}$ solves the HSM problem is $\geq \frac{1}{2}+\frac{\epsilon}{2}$. Hence, the advantage of $\mathcal{B}$ in solving the HSM problem is $\geq \frac{\epsilon}{2}$.

Homomorphic Properties {#HP}
----------------------

The proposed scheme is somewhat homomorphic and can be used to homomorphically evaluate a function $\phi:\{0,1\}^\tau \rightarrow \{0,1\}$. In the proposed scheme, $\phi$ represents an arithmetic circuit over $\mathbb{F}_2$. Hence, it is a combination of binary addition and multiplication gates.  We now show how to perform homomorphic addition and multiplication of two ciphertexts in the proposed scheme. 


\subsubsection{Addition.}  Given two ciphertexts \(\bm{c}_1=\bm{R}\left(\bm{m}_1+{f}_1(\bm{Z})+\bm{e}_1\right)$ and $\bm{c}_2= \bm{R}\left(\bm{m}_2+{f}_2(\bm{Z})+\bm{e}_2\right)$ of the respective plaintexts $m_1$ and $m_2$, compute [ $$\begin{aligned}
 \bm{c}_{\scriptscriptstyle add} &=\bm{c}_1+  \bm{c}_2~~(\text{mod}~q) \notag \\
  & = (\bm{m}_1+\bm{m}_2)+\bm{R}({f}_1(\bm{Z})+{f}_2(\bm{Z}))+(\bm{e}_1+\bm{e}_2)~~(\text{mod}~q)\end{aligned}$$]{}where ${f}_1(\bm{Z})+{f}_2(\bm{Z}) \in \mathcal{S}_{\scriptscriptstyle I_{\leq r}}$. Hence $ \langle \bm{s}, {f}_1(\bm{Z})+{f}_2(\bm{Z}) \rangle =0~(\text{mod}~q)$. If $e_{1,n}$ and $e_{2,n}$ denotes the $n^{th}$ entries of $\bm{e}_1$ and $\bm{e}_2$, then $$\begin{aligned}
\langle \bm{s},\bm{R}^{-1}\bm{c}_{\scriptscriptstyle add}\rangle =(m_1+ m_2) \cdot p+ (e_{1,n}+e_{2,n})~(\text{mod}~q)\end{aligned}$$ If $q$ is odd and $p \leq \left\lfloor \frac{q}{2} \right\rfloor$, then the above equation can be written as: $$\begin{aligned}
\langle \bm{s},\bm{R}^{-1}\bm{c}_{\scriptscriptstyle add}\rangle =(m_1 \oplus m_2)\cdot p+2p \cdot \left\lfloor \frac{m_1+m_2}{2} \right\rfloor+( e_{1,n}+e_{2,n})~(\text{mod}~q) \end{aligned}$$ If ${e}_{\scriptscriptstyle add}:=2 p \cdot \left\lfloor \frac{m_1+m_2}{2} \right\rfloor+( e_{1,n}+e_{2,n})$ and ${\left\lverte_{1,n}\right\rvert}, {\left\lverte_{2,n}\right\rvert} \leq E < \left\lfloor \frac{p}{2} \right\rfloor$, then $$\begin{aligned}
 {\left\lverte_{add}\right\rvert}={\left\lvert2p \cdot \left\lfloor \frac{m_1+m_2}{2} \right\rfloor+( e_{1,n}+e_{2,n})\right\rvert} \leq 1+2E
 \end{aligned}$$

### Multiplication. {# pk}

Given two ciphertexts $\bm{c}_1$ and $\bm{c}_2$ that encrypts the messages $m_1$ and $m_2$, homomorphic multiplication is performed by operating a tensor $\mathbfcal{M}$ on $\bm{c}_1$ and $\bm{c}_2$. The tensor $\mathbfcal{M} \in \mathbb{Z}_q^{n \times n \times n}$ is provided as the public evaluation key for multiplication and $\mathbfcal{M}$ acting on $\bm{c}_1$ and $\bm{c}_2$ is a ciphertext $\bm{c}_{mult} \in \mathbb{Z}_q^n$ where $\bm{c}_{mult}$ is a noisy encryption of $m_1m_2$ and is decryptable by the secret key $\bm{s}$. The rest of the section deals with constructing the tensor $\mathbfcal{M}$.

Multiplication is based on the fact that given two polynomials $f_1,f_2 \in \mathcal{I}_{\leq r}$ and an evaluation point $\bm{z} \in \mathbb{F}_q^l$, [ $$\begin{aligned}
f_1(\bm{z}) \cdot f_2(\bm{z})=\left(f_1 \cdot f_2\right) (\bm{z})\end{aligned}$$]{}However, $deg(f_1f_2) \leq 2r$ and hence, $f_1f_2 \in \mathcal{I}$ but is no longer an element of the subspace $\mathcal{I}_{\leq r}$. Therefore, if $\ell_1$ denotes the dimension of the subspace $\mathcal{I}_{\leq 2r}$ then, in order to perform multiplication in the proposed scheme, the number of evaluation points must be greater than $\ell_1$. Let $t \in \mathbb{N}$ be the total number of evaluation points such that $t-n+\ell=\ell_1$. Let $\tilde{\bm{c}}_1=\bm{m}_1+f_1(\bm{Z})+\bm{e}_1$ and $\tilde{\bm{c}}_2=\bm{m}_2+f_2(\bm{Z})+\bm{e}_2$. To multiply the vectors $ \tilde{\bm{c}}_1 $ and $ \tilde{\bm{c}}_2 $, we need evaluations of $f_1$ and $f_2$ at $t$ number of points.  For $n+1 \leq k \leq t$, if $f_{i}(\bm{z}_k)$ denotes the evaluations of $f_i$ at the additional $(t-n)$ distinct points $\{\bm{z}_{k}\in \mathbb{Z}_q^{l} \}_{n+1 \leq k \leq t} $, then $$\begin{aligned}
f_{i}(\bm{z}_k):=\sum_{j=1}^\ell \alpha_{k}^j \cdot f_{i}(\bm{z}_j)~\text{ for some}~ \bm{\alpha}_k:=(\alpha_{k}^1,\hdots,\alpha_{k}^\ell) \in \mathbb{Z}_q^\ell\end{aligned}$$ If $\bm{v}_1:=(\tilde{\bm{c}}_1,f_1(\bm{z}_{n+1}),\hdots,f_1(\bm{z}_{t})) \in \mathbb{Z}_q^t$ and $\bm{v}_2:=(\tilde{\bm{c}}_2,f_2(\bm{z}_{n+1}),\hdots,f_2(\bm{z}_{t}))\in \mathbb{Z}_q^t$, then

&

\_1=

f\_1(\_1)\
\
f\_1(\_)\
m\_1 p-\_[j=1]{}\^s\_[+1]{}\^jf\_1(\_j)+e\_[+1]{}\^1\
\
m\_1p-\_[j=1]{}\^s\_[n]{}\^jf\_1(\_j)+e\_[n]{}\^1\
\_[j=1]{}\^\_[n+1]{}\^jf\_1(\_j)\
\
\_[j=1]{}\^\_[t]{}\^jf\_1(\_j)

, &&

\_2=

f\_2(\_1)\
\
f\_2(\_)\
m\_2p-\_[j=1]{}\^s\_[+1]{}\^jf\_2(\_j)+e\_[+1]{}\^2\
\
m\_2p-\_[j=1]{}\^s\_[n]{}\^jf\_2(\_j)+e\_[n]{}\^2\
\_[j=1]{}\^\_[n+1]{}\^jf\_2(\_j)\
\
\_[j=1]{}\^\_[t]{}\^jf\_2(\_j)

If $v_{i,1}$ and $v_{i,2}$ denote the elements of $\bm{v}_1$ and $\bm{v}_2$ for $1 \leq i \leq t$, then for $\ell+1 \leq j \leq n$, the component-wise product of $\bm{v}_1$ and $\bm{v}_2$ yields $$\begin{aligned}
 \label{pointwise}
v_{j,1} \cdot v_{j,2} &=m_1m_2p^2+m_1pf_2(\bm{z}_j)+m_1pe_{j}^2 +m_2pf_1(\bm{z}_j) \notag \\
&\quad\quad+f_1f_2(\bm{z}_j)  +f_1(\bm{z}_j)e_j^2+m_2pe_j^1+f_2(\bm{z}_j)e_j^1+e_j^1e_j^2\end{aligned}$$ In order to cancel out the redundant terms as well as some of the error terms, we replace the product $ v_{j,1}  v_{j,2} $ with $ -v_{j,1}v_{j,2}+v_{j,1}f_2(\bm{z}_j)+v_{j,2}f_1(\bm{z}_j)$. The right hand side of equation (\[pointwise\]) now yields $ -m_1m_2p^2+f_1f_2(\bm{z}_j)-(m_1pe_j^2+m_2pe_j^1+e_j^1e_j^2) $.  We now take the component-wise product of $\bm{v}_1=(v_{1,1},\hdots,v_{t,1})^T$ and $\bm{v}_2=(v_{1,2},\hdots,v_{t,2})^T$ with these modifications such that the resultant product is given by the vector

[ $$\begin{aligned}
\bm{c}_{\scriptstyle mult}^{\prime}:=\begin{bmatrix}
v_{1,1}v_{1,2} \\
\vdots \\
v_{\ell,1}v_{\ell,2} \\
-v_{\ell+1,1}v_{\ell+1,2}+v_{\ell+1,1}f_2(\bm{z}_{\ell+1})+v_{\ell+1,2}f_1(\bm{z}_{\ell+1}) \\
\vdots \\
-v_{n,1}v_{n,2}+v_{n,1}f_2(\bm{z}_{n})+v_{n,2}f_1(\bm{z}_{n})  \\
v_{n+1,1}v_{n+1,2} \\
\vdots \\
v_{t,1}v_{t,2}
\end{bmatrix}\end{aligned}$$]{} where $\bm{c}_{mult}^{\prime}(k) = -v_{k,1}v_{k,2}+v_{k,1}\left(\sum_{j=1}^\ell s_k^jv_{j,2}\right)+v_{k,2}\left(\sum_{j=1}^\ell s_k^jv_{j,1}\right) $ for $\ell+1 \leq k \leq n$. The above operation is bilinear and can be represented by a tensor ${\mathbfcal{T}}$ of order $n \times n\times t$ over $\mathbb{Z}_q$. If $\bm{T}_1,\hdots,\bm{T}_{t}$ denotes the frontal slices of ${\mathbfcal{T}}$, then for $1 \leq k \leq \ell$, $\bm{T}_k$ is an $n \times n$ matrix with $\bm{T}_k(k,k)=1$ and $\bm{T}_k(i,j)=0$ for $1 \leq i,j \leq n$ such that $i =j \neq k$. For $\ell+1 \leq k \leq n$, $\bm{T}_k$ is an $n \times n$ matrix where $\bm{T}_k(k,j)=\bm{T}_k(j,k)=-s_k^j$ for $1 \leq j \leq \ell$ and $\bm{T}_k(k,k)=-1$ with the rest of the entries being equal to 0.  For example, if $\ell=2$ and $n=4$, then these matrices look like [$$\begin{aligned}
 \label{M1,M2}
\bm{T}_{1} =\begin{bmatrix}
1 & 0 & 0 & 0\\
0 & 0 & 0 & 0\\
0 & 0 & 0 & 0\\
0 & 0 & 0 & 0
\end{bmatrix},~
\bm{T}_{2} =\begin{bmatrix}
0 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 0 & 0\\
0 & 0 & 0 & 0
\end{bmatrix}\end{aligned}$$]{} [$$\begin{aligned}
 \label{M3,M4}
\bm{T}_{3} =\begin{bmatrix}
0 & 0 & -s_3^1 & 0\\
0 & 0 & -s_3^2 & 0\\
-s_3^1 & -s_3^2 & -1 & 0\\
0 & 0 & 0 & 0
\end{bmatrix},~
\bm{T}_{4} =\begin{bmatrix}
0 & 0 & 0 & -s_4^1\\
0 & 0 & 0 & -s_4^2\\
0 & 0 & 0 & 0\\
-s_4^1 & -s_4^2 & 0 & -1
\end{bmatrix}\end{aligned}$$]{} For $n+1 \leq k \leq t$, $\bm{T}_k$ is a matrix of the form $$\begin{aligned}
\bm{T}_k:=\left[
\begin{array}{c|c}
\widetilde{\bm{T}}_k^{\ell \times \ell} &~ \bm{0} \\
\midrule
\bm{0} &~ \bm{0}
\end{array}
\right]\end{aligned}$$ The entries of $\widetilde{\bm{T}}_k$ can be determined from the product $c_{k,1}c_{k,2}=f_1f_2(\bm{z}_k)$, where $f_{i}(\bm{z}_k):=\sum_{j=1}^\ell \alpha_{k}^j \cdot f_{i}(\bm{z}_j)$ for $i \in \{1,2\}$ and for $(n+1) \leq k \leq t$. Thus, given $\tilde{\bm{c}}_1=\bm{m}_1+f_1(\bm{Z})+\bm{e}_1$, $\tilde{\bm{c}}_2=\bm{m}_2+f_2(\bm{Z})+\bm{e}_2$ and the tensor ${\mathbfcal{T}}$, we can determine the vector $\bm{c}_{mult}^{\prime}$ as: $$\begin{aligned}
\bm{c}_{mult}^{\prime}:=\tilde{\bm{c}}_1^T {\mathbfcal{T}} \tilde{\bm{c}}_2= \begin{bmatrix}
\tilde{\bm{c}}_1^T \bm{T}_1 \tilde{\bm{c}}_2 ~&~\cdots~&~\tilde{\bm{c}}_1^T \bm{T}_t \tilde{\bm{c}}_2
\end{bmatrix}^T \in \mathbb{Z}_q^t\end{aligned}$$ Thus, multiplying two vectors of size $n$, we get a vector of size $t$. We use the following technique to reduce the size of the resultant vector back to $n$.

Let $ n^{\prime}$ be the number of monomials of degree $r+1$ in $\mathbb{Z}_q[x_1,\hdots, x_l]$. Then, consider a set of polynomials $\mathcal{G}:=\{g_1,\hdots,g_{n^{\prime}} \}\in \mathcal{I}_{\leq r}$ with each monomial of degree $r+1$ as the leading monomial of $g_i$. For some $f \in \mathcal{I}_{\leq 2r}$, divide $f$ by the set of polynomials $\mathcal{G}$ using the degree reverse lexicographic order.  Let $f_{\mathcal{G}}$ be the remainder obtained by dividing $f$ by $\mathcal{G}$. Let us now consider a linear map $\bm{Q}:\mathbb{Z}_q^t \rightarrow \mathbb{Z}_q^n$ that maps the evaluations of $f \in \mathcal{I}_{\leq 2r}$ at $(\bm{z}_1,\hdots,\bm{z}_t)$ to the evaluations of $f_{\mathcal{G}} \in \mathcal{I}_{\leq r}$ at $(\bm{z}_1,\hdots,\bm{z}_n)$. Let $(f^1,\hdots,f^{\ell_1})$ be a basis for $\mathcal{I}_{\leq 2r}$ and let $(f_{\mathcal{G}}^1,\hdots,f_{\mathcal{G}}^{\ell_1})$ be the corresponding polynomials when quotiented by ${\mathcal{G}}$. Let $\bm{F} \in \mathbb{Z}_q^{t \times \ell_1}$ and $\bm{G}\in \mathbb{Z}_q^{n \times \ell_1}$ be the matrices given by

&

   :=

f\^1(\_1) & & f\^[\_1]{}(\_1)\
& &\
f\^1(\_n) & & f\^[\_1]{}(\_n)\
& &\
f\^1(\_t) & & f\^[\_1]{}(\_t)

&           &

:=

f\_\^1(\_1) & & f\_\^[\_1]{}(\_1)\
& &\
f\_\^1(\_[n]{}) & & f\_\^[\_1]{}(\_n)

Then, $\bm{Q} \cdot \bm{F} = \bm{G}$, where each row vector of $\bm{Q}$ can be determined by solving a system of $\ell_1$ equations in $t$ unknowns.  Therefore, we have $t-\ell_1$ degrees of freedom and hence $\bm{Q}$ can take the form $$\begin{aligned}
=\left[
\begin{array}{c|c|c}
\bm{Q}_1^{\ell \times \ell} &~ \bm{0}^{\ell\times(n-\ell)} ~& \bm{Q}_2^{\ell \times(t-n)} \\
\midrule
\bm{Q}_3^{(n-\ell)\times \ell} & \bm{I}_{n-\ell} & \bm{Q}_4^{(n-\ell)\times(t-n)}
\end{array}
\right]\end{aligned}$$ where $ \bm{0}^{\ell\times(n-\ell)} $ denotes the all zero matrix of size $  \ell\times(n-\ell)$ and $\bm{I}_{n-\ell}  $ denotes the identity matrix of size $ n-\ell $.  We multiply the tensor ${\mathbfcal{T}}$ with the matrix $\bm{Q}$ to get $$\begin{aligned}
 \label{M2}
{\mathbfcal{U}}= {\mathbfcal{T}} \times_3 \bm{Q}\end{aligned}$$ where $\times_3$ denotes the mode-3 product of the tensor $ {\mathbfcal{T}}^{n \times n \times t} $ with the matrix $Q^{n \times t}$. Hence, $ {\bf\mathbfcal{U}} $ is a tensor of order $n \times n \times n$. If $\bm{U}_1,\hdots,\bm{U}_n$ denotes the frontal slices of $ {\mathbfcal{U}} $ and $f_g^{mult} \in \mathcal{I}_{\leq r}$ denotes the polynomial obtained by quotienting $(f_1 \cdot f_2) \in \mathcal{I}_{\leq 2r}$ by $g \in \mathcal{I}_{\leq r}$, then the product of $\tilde{\bm{c}}_1=\bm{m}_1+f_1(\bm{Z})+\bm{e}_1$ and $\tilde{\bm{c}}_2=\bm{m}_2+f_2(\bm{Z})+\bm{e}_2$ can be computed as: $$\begin{aligned}
 \label{mult}
\bm{c}_{mult}^{\prime\prime}=  \tilde{\bm{c}}_1^T  {\mathbfcal{U}} \tilde{\bm{c}}_2 
             &=\left[
             \tilde{\bm{c}}_1^T \bm{U}_1 \tilde{\bm{c}}_2 ~ \hdots ~ \tilde{\bm{c}}_1^T \bm{U}_n \tilde{\bm{c}}_2
             \right]^T  \in \mathbb{Z}_q^n
$$ Observe that, if $ \tilde{\bm{c}}_1 $ and $\tilde{\bm{c}}_2$ were the original ciphertexts without the matrix $\bm{R}$, then they can be multiplied using the tensor $\mathbfcal{U}$. But giving the tensor $\mathbfcal{U}$ as the public evaluation key directly reveals the secret vectors.  Hence, we multiply $ \tilde{\bm{c}}_1 $ and $\tilde{\bm{c}}_2$ by $\bm{R}$ to get the ciphertexts $\bm{c}_1=\bm{R}\cdot \tilde{\bm{c}}_1$ and $\bm{c}_2=\bm{R}\cdot\tilde{\bm{c}}_2$. To multiply $\bm{c}_1$ and $\bm{c}_2$, the tensor can be modified as: $$\begin{aligned}
\mathbfcal{M}= \mathbfcal{U}\times_1 \bm{R}^{-T} \times_2 \bm{R}^{-T} \times_3 \bm{R}\end{aligned}$$ where $\mathbfcal{M}$ is an order-3 tensor of size $n \times n \times n$ over $\mathbb{Z}_q$ and is given as the public evaluation key for multiplication.  If $\bm{M}_1,\hdots,\bm{M}_n$ denotes the frontal slices of $\mathbfcal{M}$, then given ${\bm{c}}_1,{\bm{c}}_2$, compute $$\begin{aligned}
\bm{c}_{mult}={\bm{c}}_1^T \mathbfcal{M} {\bm{c}}_2 
= \left[ {\bm{c}}_1^T \bm{M}_1 {\bm{c}}_2 ~\hdots ~   {\bm{c}}_1^T \bm{M}_n {\bm{c}}_2 \right]^T \in \mathbb{Z}_q^n\end{aligned}$$ To maintain the invariant structure $\langle \bm{s},\bm{R}^{-1}\bm{c}\rangle \approx m \cdot p$, we multiply the above equation with the inverse element of $-p$ in $\mathbb{Z}_q$. If $-p^{-1}$ denotes the inverse of $-p$ in $\mathbb{Z}_q$, then the ciphertext is given by the vector $$\begin{aligned}
\bm{c}_{mult}=-p^{-1} \left( {\bm{c}}_1^T \mathbfcal{M} {\bm{c}}_2 \right)  \in \mathbb{Z}_q^n\end{aligned}$$ For ${\tilde{\bm{c}}}_1 =\bm{m}_1+f_1(\bm{Z})+\bm{e}_1$ and ${\tilde{\bm{c}}}_2=\bm{m}_2+f_2(\bm{Z})+\bm{e}_2$, correctness follows from the following equation $$\begin{aligned}
-p^{-1} \left( {\bm{c}}_1^T \mathbfcal{M} {\bm{c}}_2 \right)
= -p^{-1}\bm{R}\left( \tilde{\bm{c}}_1^T \mathbfcal{U} \tilde{\bm{c}}_2 \right)
 =-p^{-1}\bm{R} \begin{bmatrix}
 f_{\mathcal{G}}^{mult}(\bm{z}_1) \\
 \vdots \\
 f_{\mathcal{G}}^{mult}(\bm{z}_\ell) \\
 -(m_1m_2)\cdot p^2+f_{\mathcal{G}}^{mult}(\bm{z}_{\ell+1})+e_{mult}^{\ell+1} \\
 \vdots \\
 -(m_1m_2)\cdot p^2+f_{\mathcal{G}}^{mult}(\bm{z}_{n})+e_{mult}^{n}
 \end{bmatrix}\end{aligned}$$ where $f_{\mathcal{G}}^{mult}=(f_1f_2)~\text{mod}~\mathcal{G} \in I_{\leq r}$ and $e_{mult}^i=-(m_1pe_i^2+m_2pe_i^1+e_i^1e_i^2)$ for $\ell+1 \leq i \leq n$. If $\bm{m}_{mult}=m_1m_2p(\bm{0}^{\ell},\bm{1}^{n-\ell})$, $ \tilde{f}_{\mathcal{G}}^{mult}=-p^{-1}{f}_{\mathcal{G}}^{mult} \in I_{\leq r}$ and ${\bm{e}}_{mult}=-p^{-1}(\bm{0}^\ell,{{e}}_{mult}^{\ell+1},\hdots,{{e}}_{mult}^{n}) $, then $$\begin{aligned}
\bm{c}_{mult}=\bm{m}_{mult}+ \bm{R}\cdot \tilde{f}_{\mathcal{G}}^{mult}(\bm{Z})+{\bm{e}}_{mult}  \in \mathbb{Z}_q^n\end{aligned}$$ Let us now analyze the noise in the decryption of $\bm{c}_{mult}$. Given a secret key $\bm{s}=\bm{s}_i$, $$\begin{aligned}
\langle \bm{s}_i, \bm{R}^{-1}\bm{c}_{mult} \rangle  =m_1m_2p+\bm{e}_{mult}(i)~(\text{mod}~q)\end{aligned}$$ Hence, the magnitude of the error in multiplication is $$\begin{aligned}
 \label{mult noise}
{\left\lvert\bm{e}_{mult}(i)\right\rvert} = {\left\lvertm_1e_i^2+m_2e_i^1+p^{-1} e_i^1e_i^2\right\rvert} \leq 2E+p^{-1}E^2\end{aligned}$$

Therefore, the proposed scheme is somewhat homomorphic and consists of an additional algorithm called **Evaluate** that takes as input the encryptions of two messages and the public evaluation key and generates the new ciphertexts $\bm{c}_{add}$ and $\bm{c}_{mult}$ as described above.  The key generation algorithm generates the public evaluation key along with the secret key in this case. 

### Pseudorandomness of $\mathbfcal{M}$ {#pseudorandomness-of-mathbfcalm .unnumbered}

We need to show that the public key is computationally indistinguishable from uniform over $\mathbb{Z}_q^{n \times n \times n}$ for any $\bm{s}\in \mathbb{Z}_q^n$ where $\bm{s} {  \mathrel{\mathop{\leftarrow}\limits^{
    \vbox to0ex{\kern-2\ex@
    \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} {\bf{KeyGen}}(1^{\lambda})$. The entries of $\mathbfcal{M}$ forms a system of polynomial equations in several variables.  This is known as the problem of Polynomial System Solving over a finite field denoted by PoSSo$_q$. It can be defined as:

[**[(PoSSo$_q$).]{}**]{}  Given $f_1(x_1,\hdots,x_u),\hdots,f_\nu(x_1,\hdots,x_u) \in \mathbb{F}_q[x_1,\hdots,x_u]$, find a vector $(z_1,\hdots,z_u) \in \mathbb{F}_q^u$ such that $$\begin{aligned}
f_1(z_1,\hdots,z_u)=\cdots=f_\nu(z_1,\hdots,z_u)=0\end{aligned}$$

The entries of the public key tensor $\mathbfcal{M}$ forms an underdetermined system of $\frac{1}{2}(n^3+n^2)$ equations in $\frac{1}{2}(6n\ell-4\ell^2+(t-n)(\ell^2+\ell+2n))$ variables of degree $\leq 4$. Hence, the pseudorandomness of $\mathbfcal{M}$ depends on the difficulty of solving this multivariate system of polynomial equations. 

Modulus Switching
-----------------

Modulus switching is a noise reduction technique used to tackle noise in evaluated ciphertexts [@brakerski2014leveled].  It allows to convert a somewhat homomorphic scheme to a (leveled) fully homomorphic one without bootstrapping.  Using modulus switching, a ciphertext $\bm{c}$ for a modulus $q$ can be transformed into a ciphertext $\bm{c}^{\prime}$ that encrypts the same message for a smaller modulus $q^{\prime}$ without the knowledge of the secret key.  In other words, given a constant $p^{\prime} \leq \lfloor {q^{\prime}}/{2} \rfloor$, it preserves the correctness of the scheme.  $$\begin{aligned}
\left\lfloor \frac{1}{p^{\prime}} \left(\langle \bm{s},\bm{R}^{-1}\bm{c}^{\prime} \rangle ~\text{mod}~q^{\prime} \right)\right\rceil=\left\lfloor \frac{1}{p} \left(\langle \bm{s},\bm{R}^{-1}\bm{c} \rangle ~\text{mod}~q \right)\right\rceil~\text{mod}~2\end{aligned}$$ The new ciphertext $\bm{c}^{\prime}$ is obtained by scaling $\bm{c}$ by the factor $(q^{\prime}/q)$ and rounding appropriately.  If $q^{\prime}$ is sufficiently smaller than $q$ and $\bm{s}$ has a small norm, then the noise associated with $\bm{c}^{\prime}$ is decreased. 

[**(Scaling).**]{}  For $\bm{c} \in \mathbb{Z}_q^n$ and integers $q>q^{\prime}>2$, define $\bm{c}^{\prime} \leftarrow \textbf{Scale}(\bm{c},q,q^{\prime},2)$ to be the vector nearest to $(q^{\prime}/q) \cdot \bm{c}$ such that $\bm{c}^{\prime}=\bm{c}~\textup{mod}~2$. For a constant $p \in \mathbb{Z}_q$, we define $p^{\prime} \leftarrow \textbf{Scale}(p,q,q^{\prime})$ to be the integer closest to $(q^{\prime}/q)\cdot p$ and $p^{\prime}=p~\textup{mod}~2$.

We apply the technique of modulus switching to the proposed scheme.  The following lemma is a variant of Lemma 5 in [@brakerski2014leveled]. 

\[Mod Switch\] Let $\bm{c}^{\prime} \leftarrow \textbf{Scale}(\bm{c},q,q^{\prime},2)$ and $p^{\prime} \leftarrow \textbf{Scale}(p,q,q^{\prime})$. Let $q>q^{\prime}>2$ be positive integers satisfying $q=q^{\prime}=1~\text{mod}~2$. For any $\bm{s} \leftarrow \textbf{KeyGen}(1^{k})$, if $ \langle \bm{s},\bm{R}^{-1}\bm{c} \rangle = m \cdot p+e~(\text{mod}~q)$ and $ \langle \bm{s},\bm{R}^{-1}\bm{c}^{\prime} \rangle = m \cdot p^{\prime}+e^{\prime}~(\text{mod}~q^{\prime})$ with ${\left\lverte\right\rvert} < p/2-(q/2q^{\prime}){\left\lVert\bm{s}\bm{R}^{-1}\right\rVert}_1$, then

$$\begin{aligned}
{\left\lverte^{\prime}\right\rvert} &< p^{\prime}/2 ~~\textup{and}\\
\left\lfloor \frac{1}{p^{\prime}} \left(\langle \bm{s},\bm{R}^{-1}\bm{c}^{\prime} \rangle ~\text{mod}~q^{\prime} \right)\right\rceil&=\left\lfloor \frac{1}{p} \left(\langle \bm{s},\bm{R}^{-1}\bm{c} \rangle ~\text{mod}~q \right)\right\rceil~\text{mod}~2\end{aligned}$$

For some $K \in \mathbb{N}$, we can write $e=\langle \bm{s},\bm{R}^{-1}\bm{c} \rangle -m \cdot p-qK$. For the same $K$, let $e^{\prime}= \langle \bm{s},\bm{R}^{-1}\bm{c}^{\prime} \rangle-m \cdot p^{\prime} -Kq^{\prime}$. Then $$\begin{aligned}
{\left\lverte^{\prime}\right\rvert} &= {\left\lvert\left\langle \bm{s}, \frac{q^{\prime}}{q}\bm{R}^{-1}\bm{c} \right\rangle-m \cdot p^{\prime}-Kq^{\prime}+\left\langle \bm{s},\bm{R}^{-1}\left( \bm{c}^{\prime}-\frac{q^{\prime}}{q}\bm{c}  \right) \right\rangle\right\rvert} \notag\\
&\leq \left(\frac{q^{\prime}}{q}\right){\left\lvert \left\langle \bm{s},\bm{R}^{-1}\bm{c} \right\rangle -m \cdot p-Kq\right\rvert}+{\left\lvert\left\langle \bm{s},\bm{R}^{-1} \left( \bm{c}^{\prime}-\frac{q^{\prime}}{q}\bm{c}  \right) \right\rangle\right\rvert} \notag\\
&\leq \left( \frac{q^{\prime}}{q}\right) \cdot {\left\lverte\right\rvert}+ \frac{1}{2}{\left\lVert\bm{s}\bm{R}^{-1}\right\rVert}_1 \notag \\
&<\frac{q^{\prime}}{q} \left( p/2-(q/2q^{\prime}){\left\lVert\bm{s}\bm{R}^{-1}\right\rVert}_1 \right)+\frac{1}{2}{\left\lVert\bm{s}\bm{R}^{-1}\right\rVert}_1 \notag\\ 
&< p^{\prime}/2\end{aligned}$$ For the second part of the proof, it is given that $\bm{c}^{\prime}=\bm{c}~\text{mod}~2$. Therefore, $$\begin{aligned}
\langle \bm{s},\bm{R}^{-1}\bm{c}^{\prime} \rangle -Kq^{\prime} = \langle \bm{s},\bm{R}^{-1}\bm{c}~\text{mod}~2 \rangle -Kq^{\prime} = \langle \bm{s},\bm{R}^{-1}\bm{c} \rangle -Kq~(\text{mod}~2) \end{aligned}$$ Since $p^{\prime}=p~\textup{mod}~2$, we have $$\begin{aligned}
\left\lfloor \frac{1}{p^{\prime}} \left(\langle \bm{s},\bm{R}^{-1}\bm{c}^{\prime} \rangle ~\text{mod}~q^{\prime} \right)\right\rceil&=\left\lfloor \frac{1}{p} \left(\langle \bm{s},\bm{R}^{-1}\bm{c} \rangle ~\text{mod}~q \right)\right\rceil~\text{mod}~2\end{aligned}$$

Hence, if $q^{\prime} < q$ and $\bm{s}\bm{R}^{-1}$ is a relatively short vector with respect to $q$, then the noise in an evaluated ciphertext can be reduced using this technique.  We have no control over ${\bm{s}}$ but we can modify the entries of $\bm{R}$ such that ${\left\lVert\bm{s}\bm{R}^{-1}\right\rVert}_1$ is small. 

The Leveled FHE Scheme
----------------------

We now describe the construction of the leveled FHE scheme using the technique of modulus switching. 

[**(Leveled Fully Homomorphic Encryption [@gentry2009fully])**]{}.  A family of homomorphic encryption schemes $\{\mathcal{E}^{(L)}: L \in \mathbb{Z}^+  \}$ is said to be leveled fully homomorphic if for all $L \in \ \mathbb{Z}^+$, they use the same decryption circuit, $\mathcal{E}^{(L)}$ compactly evaluates all circuits of depth at most $L$ and the computational complexity of $ \mathcal{E}^{(L)} $’s algorithms is polynomial (same polynomial for all $L$) in the security parameter $\lambda$, $L$ and for the evaluation algorithm, the size of the circuit. 

In the proposed scheme, homomorphic multiplication does not increase the size of the ciphertext.  As a result, the same secret key can be used throughout all levels and the public evaluatiuon key is the tensor $\mathbfcal{M}$. Hence, the ‘refresh’ procedure in the proposed scheme consists only of modulus switching.  Similar to [@brakerski2014leveled], we first choose a ladder of decreasing moduli $q_L$ down to $q_0$, where $L$ denotes the *depth* of the arithmetic circuit to be evaluated by the proposed scheme.  The plaintexts are encrypted using the largest modulus $q_L$.

-   **FHE.Setup**($1^{\lambda}, 1^{L}$): Takes as input the security parameter $\lambda$ and the number of levels $L$. Let $\mu$ be a parameter to be specified later.  Output a set of decreasing moduli $q_L,q_{L-1},\hdots,q_0$ and a set of constants $p_L,p_{L-1},\hdots,p_0$ such that $q_j$ has bit size $(j+1)\mu$ and $p_j \leq \left\lfloor q_j/2 \right\rfloor$ for $j=L$ down to 0. 

-   **FHE.KeyGen**($1^{\lambda}$): Run $(sk,pk) \leftarrow {\textbf{KeyGen}(1^{\lambda})}$. The secret key consists of $sk=(\bm{s},\bm{R},(\bm{z}_1,\hdots,\bm{z}_n))$ and the public key is the evaluation key $pk=\mathbfcal{M}$.

-   **FHE.Encrypt**($(sk,m,p_L,q_L)$): Encrypt a message $m \in \{0,1\}$ using the secret key $sk$ and output $$\begin{aligned}
    \bm{c}_L=\bm{R}(\bm{m}+f(\bm{Z})+\bm{e})~\text{mod}~q_L\end{aligned}$$

-   **FHE.Decrypt**($(\bm{s}_j,\bm{c}_j)$): Since, modulus switching preserves the correctness of decryption, given a ciphertext $\bm{c}_j$ at level $j$, output $m \leftarrow \textbf{Decrypt}(sk,\bm{c}_j)$.

-   **FHE.Add**($\bm{c}_{1,j},\bm{c}_{2,j}$): Take two ciphertexts $\bm{c}_{1,j}$ and $\bm{c}_{2,j}$ at level $j$ to compute $ \bm{c}_{add,j}^{\prime} \leftarrow  \bm{c}_{1,j}+\bm{c}_{2,j}~(\text{mod}~q_j)$ and output $$\begin{aligned}
    \bm{c}_{add,j} \leftarrow \textbf{FHE.Refresh}(\bm{c}_{add,j}^{\prime},q_j,p_j,q_{j-1},p_{j-1})\end{aligned}$$

-   **FHE.Mult**($pk,\bm{c}_{1,j},\bm{c}_{2,j}$): Take two ciphertexts $\bm{c}_{1,j}$ and $\bm{c}_{2,j}$ and the public evaluation key $\mathbfcal{M}$. Compute $\bm{c}_{mult,j}^{\prime}  \leftarrow  -{p_j}^{-1} \cdot \mathbfcal{M}\left(\bm{c}_{1,j}, \bm{c}_{2,j}\right) $ and then, output $$\begin{aligned}
    {\bm{c}}_{mult,j} \leftarrow  \textbf{FHE.Refresh}(\bm{c}_{mult,j}^{\prime}, q_j,p_j,q_{j-1},p_{j-1})\end{aligned}$$

-   **FHE.Refresh**(${\bm{c}},q_j,p_j,q_{j-1},p_{j-1}$): Set $ {\bm{c}^{\prime}} \leftarrow  \textbf{Scale}({\bm{c}},q_j,q_{j-1},2)$, where $ {\bm{c}}^{\prime} $ is a ciphertext under modulo $q_{j-1}$ and can be decrypted using the constant $p_{j-1}$ where $p_{j-1} \leftarrow \textbf{Scale}(p_j,q_j,q_{j-1})$.

Observe that the size of the public evaluation key in the proposed scheme is smaller than that in [@brakerski2014leveled].  This is because the key switching mechanism requires $L$ relinearization matrices of size $(n^2\,\text{log}^2 q) \times n$ in order to evaluate a circuit of depth $L$ and these matrices are given as the public evaluation key for multiplication. 

Correctness
-----------

The correctness of the leveled FHE scheme can be verified by examining the noise in each step of the scheme.  In other words, we analyze the noise in the ciphertext outputs from **FHE.Encrypt**, **FHE.Add**, **FHE.Mult** and **FHE.Refresh** such that it remains within a decryptable bound. 

A ciphertext output from **FHE.Encrypt** is given by $ \bm{c}_L=\bm{R}(\bm{m}+f(\bm{Z})+\bm{e})~\text{mod}~q_L $.  From Lemma \[CoD\], it can be easily verified that $\bm{c}_{L}$ decrypts correctly to $m$ when ${\left\lverte_n\right\rvert} < \left\lfloor \frac{p}{2} \right\rfloor \leq \left\lfloor \frac{q_L}{4} \right\rfloor $, where $e_n$ denotes the $n^{th}$ entry of $\bm{e}$. The output from **FHE.Add** is a ciphertext $\bm{c}_{add,j}=\bm{c}_{1,j}+\bm{c}_{2,j}$ at level $j$. If the noise in $\bm{c}_1$ and $\bm{c}_2$ has magnitude at most $B$, then the noise in $ \bm{c}_{add,j} $ has magnitude at most $2B$ and $ \bm{c}_{add,j} $ decrypts correctly to $m_1\oplus m_2$ when $2B < q_j/4$.

Given a ciphertext $ {\bm{c}}_{mult,j} =  -{p_j}^{-1} \cdot \mathbfcal{M}\left(\bm{c}_{1,j}, \bm{c}_{2,j}\right)  $ from **FHE.Mult**, it follows from equation (\[mult noise\]) that the noise in $\langle \bm{s}, \bm{R}^{-1} \bm{c}_{mult,j} \rangle $ has magnitude at most $p_j^{-1}B^2$ and hence, $ \bm{c}_{mult,j} $ decrypts correctly to $m_1\cdot m_2$ when $ p_j^{-1}B^2 < q_j/4 $. ** FHE.Refresh** takes a ciphertext $ \bm{c} $ under a modulus $q_j$ and outputs a ciphertext $ \bm{c}^{\prime} $ under modulus $q_{j-1}$. From Lemma \[Mod Switch\], if the noise in $\bm{c}$ is bounded by $B < p_j/2-(q_{j}/2q_{j-1}) \cdot {\left\lVert\bm{s}\bm{R}^{-1}\right\rVert}_1$, then $\bm{c}^{\prime}$ decrypts correctly and the noise in $\bm{c}^{\prime}$ is bounded by $(q_{j-1}/q_j) \cdot B+ \frac{1}{2} {\left\lVert\bm{s}\bm{R}^{-1}\right\rVert}_1$.

Parameters and Performance
--------------------------

In this section, we show how to set parameters for the proposed scheme.  We also analyze the performance of the scheme in terms of computational time. 

### Concrete Hardness of LWE

We determine a lower bound on $\ell$ required to achieve a security of $2^\lambda$ from the hardness analysis of LWE.  We consider the distinguishing attack against the LWE problem that focuses on computing a short vector in the lattice using state of the art lattice reduction algorithms.  It is used to distinguish an LWE instance from uniform which in turn can be used to break the semantic security of an LWE-based scheme.  Given $M$ samples $\{(\bm{a}_i,b_i)\}_{1 \leq i \leq M} \in \mathbb{Z}_q^\ell \times \mathbb{Z}_q$ we write an LWE instance as $(\bm{A},\bm{b}) \in \mathbb{Z}_q^{\ell \times M} \times \mathbb{Z}_q^M$ where $\bm{b}=\bm{A}^T\bm{s}+\bm{e}$ for an LWE secret $\bm{s} \in \mathbb{Z}_q^\ell$. The distinguishing attack or the dual attack reduces the problem of distinguishing an LWE instance from uniform to the Short Integer Solution (SIS) problem [@ajtai1996generating]. 

[**[(SIS).]{}**]{}  Given a matrix $\bm{A} \in \mathbb{Z}_q^{\ell \times M}$ and $\xi < q$, find a short non-zero vector $\bm{v}$ such that $ \bm{A}\bm{v}=\bm{0}~(\text{mod}~q)$ and ${\left\lVert\bm{v}\right\rVert} \leq \xi$.

### The Dual Attack {#the-dual-attack .unnumbered}

Given an LWE instance $(\bm{A},\bm{b}=\bm{A}^T\bm{s}+\bm{e})$, find a short non-zero vector $\bm{v} \in \mathbb{Z}_q^M$ such that $\bm{A}\cdot\bm{v} =\bm{0}~(\text{mod}~q)$. In other words find a vector $\bm{v}$ in the lattice $\Lambda_q^{\perp}(\bm{A})=\{\bm{w} \in \mathbb{Z}_q^M~\vert~\bm{A} \cdot \bm{w}=\bm{0}~(\text{mod}~q)\}$ where $ \Lambda_q^{\perp}(\bm{A}) $ is dual to the lattice generated by the rows of $\bm{A}$ given by $ \Lambda_q(\bm{A}) =\{\bm{w} \in \mathbb{Z}_q^M ~\vert~\bm{w}=\bm{A}^T\bm{s}~(\text{mod}~q)\}$. An adversary then computes $\langle \bm{v}, \bm{b} \rangle=\langle \bm{v},\bm{e}\rangle$ where $ \langle \bm{v},\bm{e}\rangle $ is a normal variable with parameter ${\left\lVert\bm{v}\right\rVert}\alpha q$. On the other hand, if $\bm{b}$ is uniform in $\mathbb{Z}_q^M$, then $ \langle \bm{v},\bm{e}\rangle $ is a random element in $\mathbb{Z}_q$. Thus, the decision LWE problem can be solved by distinguishing between these two cases. 

\[advantage\] [[@lindner2011better]]{}Given an LWE instance $(\bm{A},\bm{b})$ with parameters $\ell,q,\alpha$ and a vector $\bm{v}$ such that $\bm{A}\bm{v}=\bm{0}~\text{mod}~q$, the advantage of distinguishing $\langle \bm{v},\bm{b} \rangle$ from uniform is $\approx exp(-\pi({\left\lVert\bm{v}\right\rVert}\cdot {\sigma}/{q})^2))$.

The attack works with a non-negligible advantage when ${\left\lVert\bm{v}\right\rVert} \leq q/\sigma$. A short vector required to distinguish an LWE sample from uniform can be computed using state of the art lattice reduction algorithms [@schnorr1994lattice; @chen2011bkz].  The runtime of the algorithm then determines the hardness of the LWE problem.  The output of a lattice reduction algorithm is a basis $\bm{B}$ consisting of short vectors that are nearly orthogonal.  The quality of a basis is measured with the Hermite factor $\delta^M$ [@gama2008predicting] such that the length of the shortest non-zero vector in $\bm{B}$ is given by ${\left\lVert\bm{b}_1\right\rVert}=\delta^M \cdot q^{\ell/M}$ where $\delta$ is referred to as the root Hermite factor.  The runtime estimate (in clock cycles) of the BKZ algorithm [@schnorr1994lattice] to compute a basis with root Hermite factor $\delta$ as proposed in [@lindner2011better] is $$\begin{aligned}
 \label{runtime}
T_\text{BKZ} = 2^{\frac{1.8}{\text{log}\,\delta}-110} \times 2.3 \times 10^9\end{aligned}$$ Hence, in order to achieve a security level of $T_\text{BKZ}=2^{\lambda}$, the root Hermite factor can be computed as $$\begin{aligned}
 \label{quality}
\text{log}\,\delta=1.8/(\lambda+78.9)\end{aligned}$$ As per Lemma \[advantage\], we need $\delta^M \cdot q^{\ell/M}=q/\sigma$. The minimum of this function is achieved when $M=\sqrt{\frac{\ell\,\text{log}\,q}{\text{log}\,\delta}}$ [@micciancio2011lattice].  Taking $\sigma=1$ for simplicity and substituting for $M$, we have $$\begin{aligned}
 \label{length}
M\,\text{log}\,\delta+ \frac{\ell}{M}\,\text{log}\,q = \text{log}\,q\end{aligned}$$ We can solve for $\ell$ by plugging the value of $\text{log}\,\delta$ from equation (\[quality\]) in (\[runtime\]) such that $ \ell = \frac{\text{log}\,q(\lambda+78.9)}{7.2} $.  Replacing $q$ with $q/\sigma$, for a security of atleast $\lambda$ bits, we need to set $\ell$ to be at least $$\begin{aligned}
\ell \geq \frac{\text{log}(q/\sigma)(\lambda+78.9)}{7.2}\end{aligned}$$

### Decreasing ladder of moduli

In order to set the ladder of moduli and the error bound $B$, we follow a similar strategy to [@brakerski2014leveled] where a universal noise bound $B$ is chosen and at any level $j$, a ciphertext under a modulus $q_j$ is shown to have noise at most $B$. This bound is satisfied for fresh ciphertexts.  For homomorphically evaluated ciphertexts, it can be proved by induction, i.e., given two ciphertexts $\bm{c}_1$ and $\bm{c}_2$ satisfying the bound $B$ at level $j$, it can be shown that a ciphertext $\bm{c}^{\prime} \leftarrow \textbf{FHE.Mult}(pk,\bm{c}_{1,j},\bm{c}_{2,j})$ satisfies this bound at level $j-1$. It automatically implies that the bound is satisfied for **FHE.Add** since the increase in noise is slower than that in multiplication. 

Recall that, the noise after multiplication is at most $p^{-1}B^2$ and after the modulus switching step, it has a magnitude of $(q_{j-1}/q_j) \cdot (p_j^{-1}B^2)+\frac{1}{2}{\left\lVerts\bm{R}^{-1}\right\rVert}_1$. In order to make this bound at most $B$, consider the following two properties. 

-   Property 1: $B \geq 2{\left\lVerts\bm{R}^{-1}\right\rVert}_1$

-   Property 2: ${q_j}/{q_{j-1}} \geq 2 p_j^{-1}B$ for all $j$

Then, $$\begin{aligned}
(q_{j-1}/q_j) \cdot (p_j^{-1}B^2)+\frac{1}{2}{\left\lVerts\bm{R}^{-1}\right\rVert}_1 &< (q_{j-1}/q_j) \cdot (p_j^{-1}B^2)+{\left\lVerts\bm{R}^{-1}\right\rVert}_1 \\
&\leq \frac{1}{2p_j^{-1}B} \cdot p_j^{-1}B^2+\frac{B}{2} \\
&\leq B\end{aligned}$$ Property 1 is satisfied when $B \geq \lambda^{\kappa} \cdot 2^L$ for some constant $\kappa$. Then, set $q_j \geq 2^{(j+1)\mathcal{O}(L+\text{log}\,\lambda)}$. Since, $q_j/q_{j-1}$ is exponential in $L$ and $\lambda$, Property 2 is satisfied.  Hence, $q_j$ has bit size $(j+1)\mu$ where $\mu=\mathcal{O}(L+\text{log}\,\lambda)$. Therefore, the largest modulus $q_L$ is of size $ \mathcal{O}(L \cdot (L+\text{log}\,\lambda)) $ and the smallest modulus $q_0$ has size $\mathcal{O}(L+\text{log}\,\lambda)$.

For $\lambda=128$, the root Hermite factor $\delta=1.006$. For $\sigma=8$ as suggested in [@lindner2011better], we give a concrete set of parameters for 128 bit security level in Table \[para\]. 

\[t\][cccc]{} $L$ & $\text{log}\,q_L$ & $\text{log}\,q_0$ & $\ell$\
10 & 170 & 17 & 4800\
20 & 540 & 27 & 15432\
30 & 1110 & 37 & 31811\

### Performance

The computation required to multiply two ciphertexts is of the order of $\mathcal{O}(n^3)$. The computation in the modulus switching step is $\mathcal{O}(n)$. Therefore, the per gate computation of the leveled FHE scheme is $\mathcal{O}(n^3)$ independent of the circuit depth $L$.

### Instantiating the Ideal $\mathcal{I}$

We show how to instantiate the ideal $\mathcal{I}$ such that $dim(\mathcal{I}_{\leq r})=\ell$. Choose a polynomial $g \in \mathbb{Z}_q[x_1,\hdots,x_l]$ of degree $r_1 $ for some $r_1 \in \mathbb{N}$ such that $r_1 < r$ and if $r^{\prime}=r-r_1$, then it must satisfy the following equation.  $$\begin{aligned}
\label{monomials}
\ell=\binom{l+r^{\prime}}{r^{\prime}}\end{aligned}$$ Then, $\mathcal{I}_{\leq r}=\langle g \rangle$ spans an $\ell$-dimensional subspace of the polynomial vector space $ \mathbb{Z}_q[x_1,\hdots,x_l]_{\leq r} $.  The subspace $\mathcal{I}_{\leq r}$ is the set of polynomials given by $$\begin{aligned}
\mathcal{I}_{\leq r}=\{ g\cdot h~\vert~h \in \mathbb{Z}_q[x_1,\hdots,x_l]_{\leq r^{\prime}} \}\end{aligned}$$ The number of monomials in $ \mathbb{Z}_q[x_1,\hdots,x_l]_{\leq r^{\prime}} $ is given by equation (\[monomials\]).  A basis for $ \mathcal{I}_{\leq r} $ can be got by multiplying each monomial of degree $\leq r^{\prime}$ by the generator polynomial $g$. Hence, $ dim(\mathcal{I}_{\leq r})=\ell$.

Secret Key to Public Key Conversion
-----------------------------------

The proposed somewhat homomorphic scheme can be converted from symmetric key to a public key somewhat homomorphic scheme using the transformation proposed in [@rothblum2011homomorphic].  The public key is given by two lists $X_0$ and $X_1$ of size $d$ for some $d \in \mathbb{N}$ where $X_0$ is a list of $d$ encryptions of zero and $X_1$ is a list of $d$ encryptions of one.  To encrypt a message $m \in \{0,1\}$ choose a random subset $S \subseteq [d]$ such that ${\left\lvertS\right\rvert} = m ~\text{mod}~2$. Select $d$ ciphertexts $\bm{c}_i$ such that $\bm{c}_i \in X_0$ if $i \notin S$ and $\bm{c}_i \in X_1$ if $i \in S$. The decryption key is the secret key $sk$ of the symmetric key scheme.  The scheme can be summarized in terms of the following algorithms. 

-   [**[PK.KeyGen$(1^{\lambda})$]{}**]{}: A homomorphic encryption scheme is said to be compact if there exits a fixed polynomial bound $\eta=\eta(\lambda)$ such that the size of the evaluated ciphertexts is at most $\eta$ bits.  Set $d=10\eta$ [@rothblum2011homomorphic].  Sample $sk \leftarrow \textbf{KeyGen}(1^{\lambda})$. Let $X_0=(\bm{c}_1^0,\hdots,\bm{c}_d^0)$ and $X_1=(\bm{c}_1^1,\hdots,\bm{c}_d^1)$ where $\bm{c}_i^0$ and $\bm{c}_i^1$ denote an encryption of 0 and 1 respectively.  Output $sk$ and $pk=(X_0,X_1)$

-   [**[PK.Encrypt$(pk,sk,m)$]{}**]{}: To encrypt a message $m \in \{0,1\}$, select a random subset $S \subseteq [d]$ and compute the ciphertext as $$\begin{aligned}
    \bm{c}=\sum_{i=1}^d \left[ \sum_{i \notin S}\bm{c}_i^0 {  \mathrel{\mathop{\leftarrow}\limits^{
        \vbox to0ex{\kern-2\ex@
        \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} X_0 + \sum_{i \in S}\bm{c}_i^1 {  \mathrel{\mathop{\leftarrow}\limits^{
        \vbox to0ex{\kern-2\ex@
        \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} X_1 \right]\end{aligned}$$

-   [**[PK.Decrypt$(sk,\bm{c})$]{}**]{}: Output $m \leftarrow \textbf{Decrypt}(sk,\bm{c})$.

The correctness of the decryption function can be verified as follows.  Let $e_{i,n}$ be the $n^{th}$ entry of the noise associated with the ciphertext $\bm{c}_i^j$ for $j \in \{0,1\}$. Then, $$\begin{aligned}
\langle \bm{s},\bm{R}^{-1} \bm{c} \rangle &= \left\langle \bm{s}, \bm{R}^{-1}\left( \bm{c}_{add}^0+\bm{c}_{add}^1\right) \right\rangle \notag\\
  &=(0+m) \cdot p + \sum_{i=1}^d e_{i,n} \notag \\
  &= m \cdot p +e_{add}\end{aligned}$$ where $e_{add}=\sum_{i=1}^d e_{i,n}$. Hence, the noise distribution in the public key scheme is a discrete Gaussian with standard deviation $\sqrt{d}(\alpha q)$. The security of the scheme depends on the indistinguishability of ciphertexts of the public key scheme from the ones generated using the symmetric key scheme.  It has been shown in [@rothblum2011homomorphic] that the security of the public key scheme is equivalent to the security of the symmetric key scheme and if the symmetric key scheme is somewhat homomorphic with a depth $L$ circuit, then the public key scheme is somewhat homomorphic for circuits of depth $L-1$. This is because a ciphertext in level $j$ of the public key scheme is a ciphertext in level $j+1$ of the symmetric key scheme for $0 \leq j \leq L$ where $j=0$ denotes the level of fresh encryption of a message. 

Batching
========

The symmetric key variant of the proposed scheme can be naturally extended to a batch variant where several plaintext bits are ‘packed’ into the same ciphertext.  A batch variant of Regev’s encryption scheme was proposed in [@peikert2008framework] and its homomorphic properties were discussed in [@brakerski2013packed].  Similar to the notion of [@peikert2008framework], we can have several secret keys corresponding to the number of bits in the plaintext such that the $i^{th}$ secret key decrypts the $i^{th}$ bit using the same decryption function as that of the proposed scheme.  The scheme can be described as follows. 

For the subspace $ \mathcal{S}_{\scriptstyle I_{\leq r}} $ of dimension $\ell$, the maximum number of plaintext bits that can be packed into a ciphertext is $n-\ell$. Hence, the plaintext space is $\{0,1\}^{n-\ell}$ and the ciphertexts are vectors in $\mathbb{Z}_q^n$. The secret key is a matrix $\bm{S}$ of size $(n-\ell)\times n$. The noise distribution is $\mathcal{N}=(\bm{0},\mathcal{X}^{n-\ell})$ where $\mathcal{X}=\mathcal{X}_{\alpha}$ is the 0 mean discrete Gaussian with standard deviation $\alpha q$.

-   [**[BV.KeyGen($1^{\lambda}$)]{}**]{}: Choose $n-\ell$ secret vectors $\bm{s}_1,\hdots,\bm{s}_{n-\ell}$ where $\bm{s}_i \in (\mathcal{S}_{\scriptstyle I_{\leq r}})^{\perp}$ and the entries of $\bm{s}_i$ are given by $\bm{s}_i(j)=s_i^j$ for some $s_i^j \in \mathbb{Z}_q$ for $1 \leq j \leq \ell$ , $\bm{s}_i^{\ell+i}=1$ and $\bm{s}_i^j=0$ for $\ell+1 \leq j \leq n, j\neq \ell+i$. Then, $\bm{s}_1=(s_1^1,\hdots,s_1^\ell,1,0,\hdots,0)^T$, $\bm{s}_2=(s_2^1,\hdots,s_2^\ell,0,1,\hdots,0)^T, \hdots, \bm{s}_{n-\ell}=(s_{n-\ell}^1,\hdots,s_{n-\ell}^\ell,0,0,\hdots,1)^T$. The secret key is a matrix $\bm{S} \in \mathbb{Z}_q^{(n-\ell)\times n}$ whose rows are the vectors $\bm{s}_1,\hdots,\bm{s}_{n-\ell}$, the set of evaluation points $\{\bm{z}_1,\hdots,\bm{z}_n\}$ and the matrix $\bm{R}_1$ from equation (\[R\]).  Generate the public evaluation tensor $\mathbfcal{M}$ as described in section \[pk\]. 

-   [**[BV.Encrypt($\bm{S},\{0,1\}^\ell$)]{}**]{}: Let $\bm{b}=(m_1,\hdots,m_{n-\ell})^T \in \{0,1\}^{n-\ell}$ be the plaintext vector.  To encrypt $\bm{b}$, choose a polynomial $f {  \mathrel{\mathop{\leftarrow}\limits^{
        \vbox to0ex{\kern-2\ex@
        \hbox{$\scriptstyle\scriptscriptstyle{\$}$}\vss}}}} I_{\leq r}$ and an error $\bm{e} {\leftarrow} \mathcal{N}$. If ${\bm{m}}=(\bm{0},\bm{b} )^T \in \mathbb{Z}_q^n$, then the ciphertext can be computed as: $$\begin{aligned}
    \bm{c}=\bm{R}(\bm{m}\cdot p+f(\bm{Z})+\bm{e}) \in \mathbb{Z}_q^n\end{aligned}$$

-   [**[BV.Decrypt($\bm{S},\bm{c}$)]{}**]{}: The plaintext $\bm{b}$ can be decrypted by computing $$\begin{aligned}
    \bm{b}=\left\lfloor \frac{1}{p} \left(\bm{S} \bm{R}^{-1}\bm{c}~\text{mod}\,q\right) \right\rceil~\text{mod}~2 \in \{0,1\}^\ell\end{aligned}$$

For each entry of $\left(\bm{S}\bm{R}^{-1}\bm{c}~\text{mod}~q\right)$, correctness follows from Lemma \[CoD\] .  Decryption outputs 1 if the magnitude of an entry is $> p/2$ and 0 otherwise.  The ciphertext expansion ratio given by the ratio of ciphertext size to message size is reduced by a factor of $n-\ell$.

The rows of the secret matrix $\bm{s}_1,\hdots,\bm{s}_{n-\ell}$ forms a basis for the perpendicular space $ (\mathcal{S}_{\scriptstyle I_{\leq r}})^{\perp} $.  The IND-CPA security of the scheme is based on solving the HSM problem for the subspace $\mathcal{S}$ which in turn is equivalent to solving the LWE problem with multiple secrets $\{\bm{s}_i^{\prime}\}_{1 \leq i \leq n-\ell}$ where $\bm{s}_i^{\prime}=(s_i^1,\hdots,s_i^\ell) \in \mathbb{Z}_q^\ell$.

### Homomorphic Evaluation of Packed Ciphertexts

Let $\bm{c}_1$ and $\bm{c}_2$ be two packed ciphertexts that encrypts the plaintexts $\bm{b}_1$ and $\bm{b}_2$ under the secret key $\bm{S}$, i.e., $\bm{c}_1$ and $\bm{c}_2$ encrypts the $i^{th}$ bit of $\bm{b}_1$ and $\bm{b}_2$ with respect to the $i^{th}$ row of the secret key $\bm{s}_i \in \mathbb{Z}_q^n$ for $1 \leq i \leq n-\ell$.

Homomorphic addition can be performed by simply adding the ciphertexts.  If $\bm{m}_1=(\bm{0},\bm{b}_1)^T$ and $\bm{m}_2=(\bm{0},\bm{b}_2)^T$, then the ciphertext $\bm{c}_{add}=\bm{c}_1+\bm{c}_2~(\text{mod}~q)$ is an encryption of the sum of the plaintext vectors $\bm{b}_1 \oplus \bm{b}_2$. Similarly, $\bm{c}_{mult}= -p^{-1} \left( {\bm{c}}_1^T \mathbfcal{M} {\bm{c}}_2 \right) $ is an encryption of the bitwise product $\bm{b}_1 \odot \bm{b}_2 \in \{0,1\}^{n-\ell}$. In other words, $\bm{c}_{add}$ and $\bm{c}_{mult}$ are valid ciphertexts that encrypts the sum and product of the $i^{th}$ bits of the plaintetxs $\bm{b}_1$ and $\bm{b}_2$ under the secret vector $\bm{s}_i$ for $1 \leq i \leq n-\ell$.

Conclusion and Future Work {#ch4:sec:sum}
==========================

In this paper, we have proposed a decision problem called the Hidden Subspace Membership problem and discussed its hardness with respect to the Learning with Errors problem.  Further, we have described a leveled fully homomorphic encryption scheme based on the hardness of the HSM problem.  Finally, we have shown that the proposed scheme can be used to pack multiple plaintext bits into a single ciphertext.