Generating hard instances of lattice problems (extended abstract)

By M. Ajtai. 1996

abstract

How researchers see this paper

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

Citations in the corpus

Prio: Private, Robust, and Scalable Computation of Aggregate Statistics (2017, methodology): “We optimistically estimate that each hash computation requires only 300 multiplication gates, using a subset-sum hash function [2, 17, 67, 77], and we ignore the cost of computing the Valid circuit in the SNARK.”
A Survey on Homomorphic Encryption Schemes (2017, methodology): “Two well-known modern problems suggested in [Ajtai 1996] for lattice-based cryptosystems are Closest Vector Problem (CVP) and Shortest Vector Problem (SVP) [Peikert 2015].”
Collision-Free Hashing from Lattice Problems (1996, background): “Ajtai proved the following theorem, reducing the worst-case complexity of (W3) to the average-case complexity of (A1): Ajtai's Theorem [1]: Suppose that it is possible to solve a uniformly selected instance of Problem (A1) in expected T (n;m; q)-time, where the expectation is taken over the choice o”
Predicting Lattice Reduction (2008, background): “And from any set of linearly independent lattice vectors, one can efficiently derive a basis whose vectors are not much longer (see for instance [2]).”
ALITHEIA: Towards Practical Verifiable Graph Processing (2014, methodology): “Roughly speaking, this scheme is a Merkle hash tree [23] that, instead of SHA-2, uses the lattice-based hash function h(x, y) = Lx + Ry mod q, where L,R ∈ Zk×m q and x, y ∈ [N ] [4].”
Hardness of SIS and LWE with Small Parameters (2013, background): “Since one ηi ∈ [1, 2) · η(Λ), our reduction solves SIVPγ with overwhelming probability, as claimed.”
Lattice Signatures and Bimodal Gaussians (2013, background): “If we let R = Z and K be the uniform distribution, then the resulting problem is the classical SIS problem first defined by Ajtai [1] in his seminal paper showing connections between worst-case lattice problems and the average-case SIS problem.”
Lattice-Based Cryptography (2006, background): “The study of lattice based cryptography has been largely stimulated by Ajtai’s discovery in 1996 [1] that certain variants of the knapsack problem are at least as hard to break on the average as the worst case instance of certain lattice problems, e.”
Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures (2009, background): “required Õ(n(2)) time and space [2,24], and in public-key cryptosystems, the keys were on the order of megabytes [3,33,34,28] (also see [25] for concrete parameter proposals for the scheme in [34]).”
Frodo: Take off the Ring! Practical, Quantum-Secure Key Exchange from LWE (2016, background): “raphy, beginning with Ajtai’s seminal work [4] (cf.”