I am trying to understand the two main hard problems that have been explored in the context of homomorphic encryption: Learning with Errors Problem (LWE) and the Approximate-GCD (AGCD) problem. I have some idea of the LWE problem and its variants such as the Ring-LWE. Recently, I have been reading about the Approximate-GCD problem from articles such as: https://eprint.iacr.org/2009/616.pdf, https://perso.ens-lyon.fr/damien.stehle/downloads/AGCD.pdf. I would like to know if there is also some literature on a polynomial version of the AGCD problem (like Ring-LWE was formulated from LWE), that is, if the AGCD problem has been shown to be 'hard' over polynomial rings as well.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.