Faster Algorithms for Approximate Common Divisors

Explore faster algorithms for approximate common divisors in this 25-minute conference talk from Eurocrypt 2012. Delve into the security of Fully Homomorphic Encryption (FHE) schemes and the Approximate Common-Divisor Problem. Learn about classical tools like Product Trees and Evaluation, and discover applications to various cryptographic problems including noisy factoring, RSA-CRT with noisy messages, and low-exponent RSA. Gain insights into key recovery attacks and message recovery techniques. Conclude with an analysis of FHE schemes and their implications for cryptographic security.

Intro
Motivation: Security of FHE schemes
FHE based on Approx-GCD
Our work
Approximate Common-Divisor Problem
Our Algorithm
Classical Tools
Tool (1): Product Tree
Tool (2): Evaluation
Result
Noisy Factoring Problem: Key Recovery Attack
Noisy Factoring On Unknown Positions: Key Recovery Attack
RSA-CRT With Noisy Message: Key Recovery Attack
Low-Exponent RSA problem: Message Recovery Attack
Conclusion
Analysis of FHE Schemes