Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 19 of 19 for “"Shortest vector problem"”.
-
Evolutionary Lattice Sieves
Traditional cryptography, rooted in problems, e.g., integer factorisation or discrete log, is inevitably vulnerable to a fully operational quantum computer. Although it remains an engineering frontier, the looming threat extends to encrypted data stored today, which could be decrypted in the future …
-
Lattice-Based Cryptography: A Comparative Study of GGH and NTRU
… theory such as lattice bases, lattice reduction, Shortest Vector Problem (SVP), and Closest Vector Problem (CVP) are introduced. Algorithms discussed are Gaussian's Lattice Reduction, Lenstra--Lenstra--Lovász (LLL), and Babai's algorithm for CVP. With these foundations, we demonstrate the …
-
INFORMATION THEORETIC AND ALGEBRAIC TECHNIQUES IN THEORETICAL COMPUTER SCIENCE
… improves the running time of the algorithm for Shortest Vector Problem and Closest Vector Problem on lattices in infinity norm.
-
EXPONENTIAL TIME/SPACE ALGORITHMS AND REDUCTIONS FOR LATTICE PROBLEMS
… A lattice of rank n is defined as the set of vectors generated by integer linear combinations of n linearly independent vectors. In this thesis, our focus is on two fundamental computational problems on lattices: the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP). We …
-
Reduction-Respecting Parameters for Lattice-Based Cryptosystems
… to the difficulty of solving variants of the shortest vector problem (Regev, STOC 2005; Peikert, ePrint 2008). As there are no known polynomial-time algorithms which solve these lattice problems, this implies the asymptotic security of the cryptosystem. However, current lattice-based …
-
LATTICE REDUCTION ALGORITHMS
… reduction algorithms. We discuss two latticeproblems: the shortest vector problem and the closest vector problem. Then we introducetwo types of lattice reduction algorithms: Guassian Lattice Reduction in two-dimensionsand the LLL Algortihm. We illustrate how both algorithms can provide …
-
Bridging Early and Modern Lattice Cryptosystems: A Theoretical Journey through SVP, LWE and Kyber
… to average-case reductions based on lattice problems. The thesis then details Regev's Learning with Errors (LWE) problem and shows its impact on the development of practical public-key schemes while maintaining the security guarantees from the well-studied worst-case lattice problems. …
-
Improving post-quantum cryptography through cryptanalysis
… of quantum search on sieving algorithms for the shortest vector problem. Cryptographers commonly assume that the cost of solving the shortest vector problem in dimension $d$ is $2^{(0.265\ldots +o(1))d}$ quantumly and $2^{(0.292\ldots + o(1))d}$ classically. These are upper bounds based on a near …
-
Recovering generators of principal ideals using subfield structure and applications to cryptography
The principal ideal problem (PIP) is the problem of determining if a given ideal of a number field is principal, and if so, of finding a generator.Algorithms for resolving the PIP can be efficiently adapted to solve many hard problems in algebraic number theory, such as the computation of the class …
-
Considerations on computational lattice problems
… of integer linear combinations of their basis vectors, it is possible to define NP-hard problems on them. Due to the existence of a class of lattices with favorable worst-case to average-case connection, these problems are well suited as basis for provable secure cryptosystems. The problems …
-
Explorations of the String Theory and Supergravity Landscapes
… construct many of the lowest order integral flux vectors, exhaustively in some cases. In the 1^9 model we solve the shortest vector problem finding, through an exhaustive search, that the shortest vector which can be used must have eight fluxes turned on. We use these vectors to then construct a …
-
IMPROVED ALGORITHMS AND PRIMITIVES FOR QUANTUM CRYPTOGRAPHY
… are secure against quantum attacks. A central problem in the study of lattices is that of finding the shortest non-zero vector in the lattice. Asymptotically, sieving is the best known technique for solving the shortest vector problem, however, sieving requires memory exponential in the …
-
Algorithms in Discrepancy Theory and Lattices
This thesis deals with algorithmic problems in discrepancy theory and lattices, and is based on two projects I worked on while at the University of Washington in Seattle. A brief overview is provided in Chapter 1 (Introduction). Chapter 2 covers joint work with Avi Levy and Thomas Rothvoss in the …
-
Efficient Post-Quantum and Compact Cryptographic Constructions for the Internet of Things
… scheme is based on conventional cryptographic problems and utilizes the message encoding with cover-free families and special property of ECDLP-based functions to achieve significant performance gain as compared to its counterparts. The second scheme is based on post-quantum primitives and is …
-
Bin packing, number balancing, and rescaling linear programs
… algorithm for a classical NP-complete problem, the bin packing problem. In this problem, the goal is to pack items of sizes $s_i\in [0,1]$ into as few bins as possible, where a set of items fits into a bin provided the sum of the item sizes is at most one. We give a polynomial-time …
-
New Algorithms and Reductions for Hard Cryptographic Problems
Conjectured hard problems are central to modern cryptography and thus to the security of the networked infrastructure on which modern society is built.We investigate the precise hardness of several such problems. In Chapter 1, we study preprocessing attacks aimed at the on-line inversion of …
-
Convex Optimization Over Integer Points
Many problems in discrete optimization can be succinctly encapsulated as the question of minimizing a convex function $f$, which captures the combinatorial structures of the problem, over integer points that are typically $\{0,1\}^n$, i.e. $\min_{x \in \{0,1\}^n} f(x)$. At a high level, this thesis …
-
Theoretical Aspects of Randomization in Computation
… bits? In this thesis, we consider important problems in these three prominent and diverse areas pertaining to randomness. In randomness extraction, we present extractors for "oblivious bit fixing sources". In (a non-traditional use of) randomization, we have obtained results in machine …
-
Alternativní metody v kryptografii
… obecně kryptografie, dále je všeobecně rozebrána problematika současných šifrovacích metod. Patří mezi ně asymetrické, symetrické a hybridní šifrovací metody. Druhá část práce je zaměřena na teorii mříží a jejich hlavní matematické problémy, tedy problém nejkratšího vektoru, problém nejbližšího …