CWI Cryptology Group

Abstract: In this talk, I will overview Schnorr's approach to factoring (1991), by means of finding short vectors in Lattices. Such a connection may appear surprising at first, but is only one logarithm away: after all, factoring is nothing more than a multiplicative knapsack problem, i.e. a subset-product problem, where the weights are given by a bounded set of primes.
The actual strategy is of course more subtle, and I will attempt to explain this approach with minimum prerequisite on factoring algorithms. I'll conclude with some --rather unencouraging-- experimental results, as well as a discussion of the technical difficulties toward a precise average-case analysis of this approach.

Abstract: The prime number lattice, originally proposed by Schnorr (1991) to heuristically factor integers, played a fundamental role in establishing the NP-hardness of the Shortest Vector Problem (SVP) in point lattices, through the work of Adleman (1995), Ajtai (1998), and myself (1998).
SVP is the most prominent example of a problem which is known to be NP-hard only under randomized reductions. In this talk I will review the history of the prime number lattice, describe the geometric properties that make it so useful, obstacles to establishing the NP-hardness of SVP under deterministic reductions, and alternative constructions (Micciancio, 2012, 2014) of lattices and codes with similar geometric properties.