$\newcommand{\Cat}{{\rm Cat}}$ $\newcommand{\A}{\mathcal A}$ $\newcommand{\freestar}{ \framebox[7pt]{\star} }$

## 3. Cryptanalysis

1. #### Problem 3.1.

[Nadia Heninger] Find an algorithm for the approximate-gcd problem for general parameters. In particular, given a set of integers $\{n_i=qp_i+r_i\}$ where the $r_i$ are small, find q in polynomial time.

As one example, what if r has $\ell-1$ bits, q has $\ell$ bits, and p has $\ell^2$ bits.
1. Remark. If the r_i are the same size as q, we have a reduction to LWE.
• Remark. [Heninger] It seems likely that Coppersmith-type attacks could work?
• #### Problem 3.2.

[Jung Hee Cheon] Is there a CRT-style result for Approximate GCD?

In particular, given X as a product of distinct primes, can we find any of the primes if we are allowed a polynomial number of sample numbers n so that n is small mod p for each of the primes?
1. Remark. Being able to do this would allow us to break CLT Mmap.
• Remark. [Dan Boneh] Might also be interesting if the primes are not distinct.

Cite this as: AimPL: Constructing cryptographic multilinear maps, available at http://aimpl.org/cryptomultilin.