Approximate common divisors via lattices

zbMath1344.11085arXiv1108.2714MaRDI QIDQ2949498

Henry Cohn, Nadia Heninger

Publication date: 1 October 2015

Full work available at URL: https://arxiv.org/abs/1108.2714

zbMATH Keywords

fully homomorphic encryptionlist decodinglattice basis reductionapproximate common divisorsCoppersmith's algorithmnoisy polynomial reconstructionParvaresh-Vardy codes

Mathematics Subject Classification ID

Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16) Decoding (94B35)

Related Items (19)

Polly cracker, revisited ⋮ Computing minimal interpolation bases ⋮ Revisiting approximate polynomial common divisor problem and noisy multipolynomial reconstruction ⋮ Privacy-Preserving Support Vector Machines with Flexible Deployment and Error Correction ⋮ Fast practical lattice reduction through iterated compression ⋮ Improved power decoding of interleaved one-point Hermitian codes ⋮ On smooth orthogonal and octilinear drawings: relations, complexity and Kandinsky drawings ⋮ CRT-based fully homomorphic encryption over the integers ⋮ The polynomial approximate common divisor problem and its application to the fully homomorphic encryption ⋮ Coppersmith's lattices and ``focus groups: an attack on small-exponent RSA ⋮ FHE over the Integers: Decomposed and Batched in the Post-Quantum Regime ⋮ Finding well approximating lattices for a finite set of points ⋮ Power decoding Reed-Solomon codes up to the Johnson radius ⋮ Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding ⋮ Towards Optimal Bounds for Implicit Factorization Problem ⋮ A new scale-invariant homomorphic encryption scheme ⋮ Simultaneous diagonalization of incomplete matrices and applications ⋮ On the greatest common divisor of shifted sets ⋮ Revisiting orthogonal lattice attacks on approximate common divisor problems

This page was built for publication: Approximate common divisors via lattices