Cryptography.

High processing time and implementation complexity of the fully homomorphic
encryption schemes intrigued cryptographers to extend partially homomorphic
encryption schemes to allow homomorphic computation for larger classes of polynomials.
In this thesis, we study several public key and partially homomorphic schemes
and discuss a recent technique for boosting linearly homomorphic encryption schemes.
Further, we implement this boosting technique on CGS linearly homomorphic encryption
scheme to allow one single multiplication as well as arbitrary number of additions
on encrypted plaintexts. We provide MAGMA source codes for the implementation
of the CGS scheme along with the boosted CGS scheme.

The mathematical theory of nding a basis of shortest possible vectors in a
given lattice L is known as reduction theory and goes back to the work of Lagrange,
Gauss, Hermite, Korkin, Zolotarev, and Minkowski. Modern reduction theory is voluminous
and includes the work of A. Lenstra, H. Lenstra and L. Lovasz who created
the well known LLL algorithm, and many other researchers such as L. Babai and C. P.
Schnorr who created signi cant new variants of basis reduction algorithms. The shortest
vector (SVP) and closest vector (CVP) problems, presently considered intractable,
are algorithmic tasks that lie at the core of many number theoretic problems, integer
programming, nding irreducible factors of polynomials, minimal polynomials of algebraic
numbers, and simultaneous diophantine approximation. Lattice basis reduction
also has deep and extensive connections with modern cryptography, and cryptanalysis
particularly in the post-quantum era. In this dissertation we study and compare
current systems LLL and BKZ, and point out their strengths and drawbacks. In
addition, we propose and investigate the e cacy of new optimization techniques, to
be used along with LLL, such as hill climbing, random walks in groups, our lattice
di usion-sub lattice fusion, and multistage hybrid LDSF-HC technique. The rst two methods rely on the sensitivity of LLL to permutations of the
input basis B, and optimization ideas over the symmetric group Sm viewed as a
metric space. The third technique relies on partitioning the lattice into sublattices,
performing basis reduction in the partition sublattice blocks, fusing the sublattices,
and repeating. We also point out places where parallel computation can reduce runtimes
achieving almost linear speedup. The multistage hybrid technique relies on the
lattice di usion and sublattice fusion and hill climbing algorithms. Unlike traditional
methods, our approach brings in better results in terms of basis reduction towards
nding shortest vectors and minimal weight bases. Using these techniques we have
published the competitive lattice vectors of ideal lattice challenge on the lattice hall of
fame. Toward the end of the dissertation we also discuss applications to the multidimensional
knapsack problem that resulted in the discovery of new large sets of
geometric designs still considered very rare. The research introduces innovative techniques
in lattice basis reduction theory and provides some space for future researchers
to contemplate lattices from a new viewpoint.