Algorithms for CRT-variant of approximate greatest common divisor problem

DOI10.1515/jmc-2019-0031zbMath1466.11097OpenAlexW3095958347MaRDI QIDQ2025331

Jiseung Kim, Jung Hee Cheon, Wonhee Cho, Minki Hhan, Changmin Lee

Publication date: 12 May 2021

Published in: Journal of Mathematical Cryptology (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1515/jmc-2019-0031

zbMATH Keywords

latticeCCK-ACDorthogonal lattice attackSDA

Mathematics Subject Classification ID

Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16) Multiplicative structure; Euclidean algorithm; greatest common divisors (11A05)

Uses Software

• fpLLL
• GitHub
• fhe

Cites Work

• Unnamed Item
• On Lovász' lattice reduction and the nearest lattice point problem
• Factoring polynomials with rational coefficients
• Random matrices: law of the determinant
• Candidate Indistinguishability Obfuscation and Functional Encryption for All Circuits
• Practical Multilinear Maps over the Integers
• Public Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers
• Faster Algorithms for Approximate Common Divisors: Breaking Fully-Homomorphic-Encryption Challenges over the Integers
• Cryptanalysis of the Multilinear Map over the Integers
• Fully Homomophic Encryption over the Integers Revisited
• Algorithms for the approximate common divisor problem
• Fully Homomorphic Encryption over the Integers
• Batch Fully Homomorphic Encryption over the Integers