Current Search:   Khadka, Bal K. (x)

View All Items

  • CSV Spreadsheet
(1 - 3 of 3)
Solving approximate SVP in an Ideal Lattice using a cluster
Title
Solving approximate SVP in an Ideal Lattice using a cluster.
Creator
Khadka, Bal K., Magliveras, Spyros S., Graduate College
Abstract/Description
The shortest vector problem SVP is de ned as follows: For a given basis B of an integral lattice L fi nd a vector v in L whose length is minimal. Here we present the result of our experiments based on a hill climbing algorithm using a computer cluster and a number of parallel executions of a standard basis reduction technique, such as LLL, to successfully reduce an initial basis of L. We begin by reducing ideal lattices of relatively small dimension and progressively reduce ideal lattices of...
Show moreThe shortest vector problem SVP is de ned as follows: For a given basis B of an integral lattice L fi nd a vector v in L whose length is minimal. Here we present the result of our experiments based on a hill climbing algorithm using a computer cluster and a number of parallel executions of a standard basis reduction technique, such as LLL, to successfully reduce an initial basis of L. We begin by reducing ideal lattices of relatively small dimension and progressively reduce ideal lattices of higher dimension, beating several earlier published solutions to the approximate SVP problem.
Show less
Date Issued
2014
PURL
http://purl.flvc.org/fau/fd/FA00005827
Format
Document (PDF)
New LS[3][2,3,2^8] Geometric Large Sets
Title
New LS[3][2,3,2^8] Geometric Large Sets.
Creator
Hurley, Michael Robert, Khadka, Bal K., Magliveras, Spyros S., Graduate College
Abstract/Description
Let V be an n-dimensional vector space over the field of q elements. By a geometric t-[qn,k,λ] design we mean a collection D of k-dimensional subspaces if V, called blocks, such that every tdimensional subspace T of V appears in exactly λ blocks in D. In a recent paper Braun, Kohnert, Ӧstergård, and Wassermann constructed the first ever known large set LS[N][2,k,qn], namely an LS[3][2,3,28] under a cyclic group G of order 255. In this work we construct an additional 8 large sets with the same...
Show moreLet V be an n-dimensional vector space over the field of q elements. By a geometric t-[qn,k,λ] design we mean a collection D of k-dimensional subspaces if V, called blocks, such that every tdimensional subspace T of V appears in exactly λ blocks in D. In a recent paper Braun, Kohnert, Ӧstergård, and Wassermann constructed the first ever known large set LS[N][2,k,qn], namely an LS[3][2,3,28] under a cyclic group G of order 255. In this work we construct an additional 8 large sets with the same parameters, using the L3 algorithm for lattice basis-reduction.
Show less
Date Issued
2015
PURL
http://purl.flvc.org/fau/fd/FA00005885
Format
Document (PDF)
Techniques in Lattice Basis Reduction
Title
Techniques in Lattice Basis Reduction.
Creator
Khadka, Bal K., Magliveras, Spyros S., Florida Atlantic University, Charles E. Schmidt College of Science, Department of Mathematical Sciences
Abstract/Description
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...
Show moreThe 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.
Show less
Date Issued
2016
PURL
http://purl.flvc.org/fau/fd/FA00004678
Subject Headings
Cryptography., Combinatorial analysis., Group theory.
Format
Document (PDF)