restpond.blogg.se - Lattice definition

Problem Set 3 posted, due Dec 22 at 11:59pm.Problem Set 2 posted, due Oct 31 at 11:59pm.Use the style file here to compile the tex. Problem Set 1 posted, due Oct 3 at 11:59pm.We will NOT assume any prior knowledge of cryptography or advanced complexity theory. We will assume knowledge of basic math (linear algebra and probability) and introductory level algorithms (analysis of algorithms, polynomial time and NP-hardness). While they were first used to break cryptosystems, they have more recently been instrumental in designing a wide range of secure cryptographic primitives, including public key encryption, digital signatures, encryption resistant to key leakage attacks, identity based encryption, and most notably, the first fully homomorphic encryption scheme.

Lattices have proven themselves to be a double-edged sword in cryptography. We will study lattice algorithmsĪnd their applications to combinatorial optimization.

The asymptotically fastest Integer Programming algorithm

Algorithms and Combinatorial Optimization:.

This course will touch several related areas and applications: Gives an introduction to the theory of integer lattices - their algorithms and applications toĬombinatorial optimization, their recent use in cryptography culminating in the first construction of aįully homomorphic encryption scheme, and the fascinating complexity landscape associated with lattice problems. Integer lattices are powerful mathematical objects that have found applications in many diverse facets ofĬomputer science, most notably in the areas of cryptography and combinatorial optimization. īased on four Problem Sets, Scribing 1-2 Lectures and Class ParticipationĪll this information (and more) can be found in the course information sheet. In addition, for the first few lectures, we may refer to the bookĬomplexity of Lattice Problems: A Cryptographic Perspectiveĭaniele Micciancio and Shafi Goldwasser.

Instead, we will use material from the references below. Office Hours Tuesday 5:10-6:10pm in SF2301B, or by appointment Previous Announcements Course Information INSTRUCTORĮ-mail: New Location for the rest of the term: University College UC 87.Once you get in through the main entrance, you need to take the flight of stairs to your right down to the basement. The class has been moved to University College Room 87 (basement) for the remainder of the term.Ĭlick here for a map.Due October 31 (deadline extended to November 4, Friday). Per Austrin will give the lecture on December 6 Tuesday.