3. Cryptanalysis

Problem 3.1.
[Nadia Heninger] Find an algorithm for the approximategcd 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 $\ell1$ bits, q has $\ell$ bits, and p has $\ell^2$ bits.
Remark. If the r_i are the same size as q, we have a reduction to LWE.

Remark. [Heninger] It seems likely that Coppersmithtype attacks could work?


Problem 3.2.
[Jung Hee Cheon] Is there a CRTstyle 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?
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.