## Abstract

The security of several homomorphic encryption schemes depends on the hardness of variants of the Approximate Common Divisor (ACD) problem. We survey and compare a number of lattice-based algorithms for the ACD problem, with particular attention to some very recently proposed variants of the ACD problem. One of our main goals is to compare the multivariate polynomial approach with other methods. We find that the multivariate polynomial approach is not better than the orthogonal lattice algorithm for practical cryptanalysis.

We also briefly discuss a sample-amplification technique for ACD samples and a pre-processing algorithm similar to the Blum-Kalai-Wasserman (BKW) algorithm for learning parity with noise. The details of this work are given in the full version of the paper.

We also briefly discuss a sample-amplification technique for ACD samples and a pre-processing algorithm similar to the Blum-Kalai-Wasserman (BKW) algorithm for learning parity with noise. The details of this work are given in the full version of the paper.

Original language | English |
---|---|

Pages (from-to) | 58-72 |

Number of pages | 15 |

Journal | LMS Journal of Computation and Mathematics |

Volume | 19 |

Issue number | A |

Early online date | 26 Aug 2016 |

DOIs | |

Publication status | Published - 26 Aug 2016 |