2
$\begingroup$

I would like to know the cryptographic hard problem that is most closely tied to recovering integer $r$ from the modular product $r\times p\mod q$. (This is a simplification of an earlier post that had some errors). It really looks like integer factorization to me; if not, what else would it be?

More specifically, select two prime numbers $p$ and $q$, $q>p$, and a random positive integer $r$, large enough such that $q/p<r<q$. Publish $q$, but keep $p$ and $r$ private. Further, assume there are several instances of $r$ for a given pair of $\langle p, q\rangle$ to work with. Assuming existence of a hardness problem X, such that a polynomial-time solution of X could be reduced to finding either $r$ or $p$ from the integer $$r\times p\mod q$$in polynomial time, what is this problem X?

I am relatively new to this. I looked at a few hard problems; none of the residuosity or discrete logarithmic problems seem to apply, but I'm hesitant to say that it's integer factorization or RSA in case there is some problem with a stronger assumption that fits. I want to get a good characterization of the construct so that I may describe it accurately.

Thanks for your help and patience!

$\endgroup$
  • 1
    $\begingroup$ Should we assume that for each instance we get freshly chosen values of $(r,p,q)$? $\endgroup$ – SEJPM Jun 19 '17 at 15:44
  • 3
    $\begingroup$ The problem's definition is fuzzy. Are $p$ and/or $q$ known? If not, what is known about them? Are multiple $r\times p\bmod q$ with the same $p$ and $q$ available, which could help in recovering $p$ and $q$, from which $r$ comes immediately as $r=(r\times p\bmod q)\times p^{-1}\bmod q$?. In that likely related question it appears $p$ and $q$ are unknown, but $N=p\,q$ might be known, and multiple $r$ are a possibility. $\endgroup$ – fgrieu Jun 19 '17 at 15:47
  • $\begingroup$ Another update. It's many instances of r, for a fixed tuple of p and q. Also, $p^{-1}$ exists, but $p$ is not known. $\endgroup$ – Russ Jun 19 '17 at 17:15
2
$\begingroup$

When given a single triple consisting of $(p,q,x)$ with $x = r \cdot p \mod q$, then there is no hard problem. It takes one inversion and one multiplication (both in modular arithmetic) to calculate $r$.

If just $x$ is given, then you can choose $p$ and $q$ arbitrarily and calculate a matching $r$ to fullfill $x = rp \mod q$.

If the actual question is about recovering the original values: That's not possible. This is exactly the same situation like only giving some bounds for random values (e.g. $q>x$) and nothing else.

$\endgroup$
  • $\begingroup$ Good points. I edited the description to note that q is published, and for every q, there exist several values of $r$ for a given tuple of $\langle p, q\rangle$ with the challenge of trying to determine one of $r$, $p$ ... just saw another mistake, fixing momentarily. $\endgroup$ – Russ Jun 19 '17 at 17:13
2
$\begingroup$

In the currently stated problem, $p$ and $q$ are primes with $p$ secret and $q$ known, $p<q$, it is chosen some number of (I'll assume: uniformly) random $r_i$ with $q/p<r_i<q$, and revealed $x_i=X(r_i)=r_i\times p\bmod q$. The problem is finding $p$ (or otherwise finding some $r_i$, which in practice will lead to $p$).

If we replace the selection of $r_i$ by $0<r_i<q$, then the problem is demonstrably intractable, since $X$ is a mapping of the set $\{1,2,\dots,q-1\}$, thus the distribution of the $x_i$ is uniformly random no matter what $p$ is.

If $q/p<2$, then $r_i=1$ can't happen (since $p$ does not divide $q$). Thus, $p$ cannot be one of the $x_i$ among $\{1,2,\dots,q-1\}$, and the problem becomes finding that missing value $p$. The number of necessary $x_i$ is related to the well-studied coupon collector's problem, and reaching certainty about $p$ requires $O(q\log(q))$ values of $x_i$, and is intractable for large $q$.

More generally, we can only be certain of $p$ when we have found that $x_i$ reached all but one of $q-\lfloor q/p\rfloor$ values, and the problem is untractable unless both $p$ and $q$ are small.

That's not a well-studied problem that I know of. It has nothing to do with the Integer Factorization problem or the Discrete Logarithm problem, which both have relatively small input, when here the input includes a large number of $x_i$.

$\endgroup$
  • $\begingroup$ Very insightful, thanks. Is there a well-known hard problem that this seems to reduce to, e.g., integer factorization? What are your thoughts? $\endgroup$ – Russ Jun 19 '17 at 17:58
  • $\begingroup$ @Russ What is your goal? As far as I can tell, there is no trapdoor in the coupon collector's problem. It is just not feasable for large bitsize of $q$. Since factorization does have a trapdoor, it is quite unlikely (I would like to say impossible, but I can't prove it) to find a reduction between those. The question remains: What is your actual goal? I can't see this being useful for an encryption scheme - because of the missing trapdoor. $\endgroup$ – tylo Jun 20 '17 at 7:45
  • $\begingroup$ @tylo, this is an abstraction of an idea related to my previous post. In the abstraction above, $r$ is an actual message, something like the $E_I(M)$ function in the post, not a random value, and $p^{-1}$ is the trapdoor to recovering $r$. However, $r$ can take on values between $q/p$ and $q$ as stated. $\endgroup$ – Russ Jun 20 '17 at 13:03
  • $\begingroup$ @Russ There is no trapdoor in this problem, so I doubt that's going to work. but you could consider it as an exercise: Write down exactly what is required to be able to encrypt and has to be part of the public key. And then write down what is required to decrypt. And then try figure out if you can decrypt with just the values given in the public key. $\endgroup$ – tylo Jun 20 '17 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.