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

3. Cryptanalysis


    1. Add remark

      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?


                • Add remark

                  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.