Algorithms for the approximate common divisor problem

DOI10.1112/S1461157016000218MaRDI QIDQ2970999zbMATH OpenWikidataFDO

Authors Steven D. Galbraith, Shishay W. Gebregiyorgis, Sean Murphy

Publication date 4 April 2017

Published in LMS Journal of Computation and Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1112/S1461157016000218

Mathematics Subject Classification ID

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

Recommendations

• Approximate common divisors via lattices
• Faster algorithms for approximate common divisors: breaking fully-homomorphic-encryption challenges over the integers
• Algorithms for CRT-variant of approximate greatest common divisor problem
• The polynomial approximate common divisor problem and its application to the fully homomorphic encryption
• Approximate common divisor problem and lattice sieving

Cites work

• Batch fully homomorphic encryption over the integers
• Factoring polynomials with rational coefficients
• Fully homomorphic encryption over the integers
• Fully homomorphic encryption over the integers with shorter public keys
• Noise-tolerant learning, the parity problem, and the statistical query model
• Security analysis of multilinear maps over the integers

Cited in

(23)

• The polynomial approximate common divisor problem and its application to the fully homomorphic encryption
• Algorithms for CRT-variant of approximate greatest common divisor problem
• Homomorphic encryption systems statement: trends and challenges
• Bootstrapping fully homomorphic encryption over the integers in less than one second
• Revisiting orthogonal lattice attacks on approximate common divisor problems
• Revisiting approximate polynomial common divisor problem and noisy multipolynomial reconstruction
• Efficient AGCD-based homomorphic encryption for matrix and vector arithmetic
• Cryptanalysis of the CLT13 multilinear map
• Fully homomorphic encryption over the integers for non-binary plaintexts without the sparse subset sum problem
• Faster algorithms for approximate common divisors: breaking fully-homomorphic-encryption challenges over the integers
• Approximate common divisors via lattices
• Approximate common divisor problem and continued fractions
• Approximate common divisor problem and lattice sieving
• Cryptanalysis of the co-ACD assumption
• scientific article; zbMATH DE number 1113848 (Why is no real title available?)
• scientific article; zbMATH DE number 1852136 (Why is no real title available?)
• scientific article; zbMATH DE number 3341178 (Why is no real title available?)
• FHE over the Integers: Decomposed and Batched in the Post-Quantum Regime
• Simultaneous diagonalization of incomplete matrices and applications
• Fast practical lattice reduction through iterated compression
• New Results of Breaking the CLS Scheme from ACM-CCS 2014
• Noiseless homomorphic encryption for complex numbers and fully homomorphic encryption with modular arithmetic
• Efficient evaluation algorithms for noiseless fully homomorphic encryption scheme and their applications

This page was built for publication: Algorithms for the approximate common divisor problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2970999)