The MMO problem
This addresses a theoretical problem in cryptography with potential applications, but it is incremental as it builds on known lattice-based methods.
The paper tackles the Mixing Modular Operations (MMO) problem of recovering two polynomials from their mixed modular sums at multiple points, showing that when moduli are known, it reduces to a lattice problem with a heuristic polynomial-time algorithm, but remains unsolved when moduli are secret.
We consider a two polynomials analogue of the polynomial interpolation problem. Namely, we consider the Mixing Modular Operations (MMO) problem of recovering two polynomials $f\in \Z_p[x]$ and $g\in \Z_q[x]$ of known degree, where $p$ and $q$ are two (un)known positive integers, from the values of $f(t)\bmod p + g(t)\bmod q$ at polynomially many points $t \in \Z$. We show that if $p$ and $q$ are known, the MMO problem is equivalent to computing a close vector in a lattice with respect to the infinity norm. We also implemented in the SAGE system a heuristic polynomial-time algorithm. If $p$ and $q$ are kept secret, we do not know how to solve this problem. This problem is motivated by several potential cryptographic applications.