The Two Faces of Lattices in Cryptology

By Phong Q. Nguyen. ACM Symposium on Applied Computing, 2001

306 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/9e81935bd9e6f49a44e2b52a850d14a1f5546674

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions (2002, unknown): “Keywords: Knapsack problem, cyclic lattices, worst-case average-case connection, one-way functions”
Faster exponential time algorithms for the shortest vector problem (2010, background): “It is the core of many algorithmic applications (see survey papers [14, 6, 20]), and the problem underlying many cryptographic functions (e.”
Compact Ring-LWE Cryptoprocessor (2014, background): “The significant progress in the theory of lattice-based cryptography [19, 20, 25] has recently been followed by practical implementations [1, 7, 9, 22, 23, 28].”
Predicting Lattice Reduction (2008, background): “We refer to [29,23] for a bibliography on lattices.”
Fully Homomorphic Encryption over the Integers with Shorter Public Keys (2011, methodology): “We consider the attack based on Nguyen and Stern’s orthogonal lattice [10] (see Section B.”
A semidefinite programming method for integer convex quadratic minimization (2015, background): “The closest vector problem and shortest vector problem have numerous application areas in cryptanalysis of public key cryptosystem such as RSA [NS01].”
A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations (2010, background): “solvability by radicals [32], solving low density subset-sum problems [18] and breaking the Merkle-Hellman cryptosystem [44] (among many other cryptanalysis problems [29, 42].”
A fast private information retrieval protocol (2008, background): “In other words there is c > 0, parameters n > i1 > i2 and a family of circuits C = (Ck) with polynomial size in k such that for any K there is k > K such that Pr(Ck(α, i1, i2,Ppir) = i|Q← Γ[k];α← Q(i, n)) ≥ 1/2+k−c.”
Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes (2010, background): “However, the underlying lattice is a well-studied lattice in algorithmic number theory, see for example the applications of LLL described in [12,13,15].”
Lattice-Based Cryptography (2006, background): “, [14, 15] and also the lecture notes [16, 17].”