1
$\begingroup$

Shor's algorithm can (efficiently) solve equations of the form:

$$n = pq$$

and

$$n = x^{2} + y^{2}$$

This question is simple: Can Shor's algorithm solve these equations in polynomial time when they are performed with finite arithmetic instead of over integers? i.e.

$$n = pq \bmod k$$

and

$$n = x^{2} + y^{2} \bmod k$$

Sizes of the Terms

At least in the factoring case if $\log_{2}(p) = \log_{2}(q) = \log_{2}(k)$ then solving the equation is information-theoretically impossible since it's basically a one-time pad. So for the purposes of this question assume that $\log_{2}(p) <= \log_{2}(q) < \log_{2}(k)$. It is not immediately clear to me if this issue applies to the sum of two squares case as well; Similar constraints may be placed on the terms if necessary to prevent trivial impossibility of a solution.

Nature of the Terms

Traditionally factoring is presumed to be about semiprimes. Does the nature of $p, q$ (and/or $x, y$) make any difference in this context? As in, does it matter if $p, q, x, y$ are prime or if they satisfy certain congruences (e.g. $x = 1 \bmod 4$)? Over the integers these conditions matter, do they still matter with finite arithmetic?

$\endgroup$
4
  • $\begingroup$ It is easy to find solutions, given $n, p$, to $n \equiv xy \pmod p$ - pick an arbitrary $x$ r.p. to $p$, and compute $y = x^{-1} \bmod p$ - that's a solution - no Quantum Computer needed... $\endgroup$
    – poncho
    Mar 9 at 18:27
  • $\begingroup$ @poncho While I see that, it's not clear that the ability to pick any solution would necessarily help to actually solve a cryptographic problem: e.g. for the one-time pad one can choose any pair of terms and count it as a valid solution but that doesn't help someone actually learn your message? Basically it seems like that feature is not necessarily a bug? Unless I'm missing something? $\endgroup$
    – anon
    Mar 9 at 18:31
  • $\begingroup$ Normally, in crypto, there is enough information to verify a solution (OTP is an exception, as is secret sharing). If $n \equiv xy \pmod p$ doesn't give enough information to derive the Right Answer then most likely there is other information available... $\endgroup$
    – poncho
    Mar 9 at 19:10
  • $\begingroup$ Unfortunately due to the terms of use of this site I am obligated to ask my questions in a roundabout and generic manner rather than actually presenting what I have and any specific questions about it. I don't know how else to phrase my question in an acceptable manner that won't get voted closed. $\endgroup$
    – anon
    Mar 9 at 19:55

1 Answer 1

0
$\begingroup$

I'll first answer your question (which has a rather straightforward answer that you may be disappointed by), before discussing a mild extension of your problem that we think quantum computers cannot solve, which may interest you.

As a quick side-note regarding the comment

At least in the factoring case if $\log_2(p)=\log_2(q)=\log_2(k)$ then solving the equation is information-theoretically impossible since it's basically a one-time pad.

Generally, how this is handled is to say that an adversary wins if they recover any solution to $x^2+y^2\bmod k$, rather than some specific solution. This can be seen in things like

  1. the consistent key recovery game (rather than the target key recovery game), and
  2. how one-way functions need to recover any preimage of $y$, e.g. any $x$ such that $f(x) = y$, rather than some "exact" $x'$ that is chosen internally during the game.

I will describe things in these terms, as it is standard. If this isn't suitable for your application, you should perhaps try to describe your application more.

This question is simple: Can Shor's algorithm solve these equations in polynomial time when they are performed with finite arithmetic instead of over integers?

My understanding is that Shor's algorithm being described over $\mathbb{Z}$ rather than $\mathbb{Z}_n$ is not a serious issue with its "real world" implementation. In particular, while one does need to be careful that the finite-precision representations one work with are not too "lossy", my understanding is that these details are much easier to work out than things like building a quantum computer.

Provided this understanding is correct, the answer to both of these questions is roughly trivial --- solve the various equations over $\mathbb{Z}$, and then reduce the answers $\bmod k$ to obtain solutions over $\mathbb{Z}_k$. As poncho points out in the comments, the problem of solving $n = xy\bmod k$ for $x, y$ is even classically easy, so the moral of the story is that imposing modular constraints can make problems (perhaps) dramatically easier, but for these problems they do not make the problems harder.

There is a mild extension of the problem of solving for $n = xy \bmod k$ which is thought to be quantumly hard. Solving for this congruance can be seen as solving a single-variable (exact) linear equation. There are two natural ways to generalize this

  1. more than one variable, and
  2. more than one equation.

E.g., change the problem to where one is given $\vec b = A\vec s\bmod k$ where $\vec b\in\mathbb{Z}_k^n, A\in\mathbb{Z}_k^{n\times n}, \vec s\in\mathbb{Z}_k^n$. This is still trivial to "solve" though --- if you choose $A$ to be the identity matrix, then $\vec s = \vec b$ works. More generally, if you choose $A$ to be invertible over $\mathbb{Z}_k$, then $\vec s = \vec A^{-1}\vec b$ works. Even if $\vec A$ is non-invertible (say it is non-square) there are things you can do using general linear-algebraic techniques. All of this is both efficient, and classical, e.g. Shor's is still overkill.

Generally how one stops the above attacks is two-fold

  1. specify some matrix $A$ one must use (so one cannot set $A$ to be the identity, or a random invertible matrix), and

  2. inject some noise into the problem.

Note that the first point alone does suffice (Poncho's attack still works), so the second point should be seen as fundamental. Concretely, the problem is as follows

Learning With Errors: Let $A\in\mathbb{Z}_k^{n\times n}$ be uniformly random, and let $\vec s\in\mathbb{Z}_k^n$ be a "secret" vector. For a fixed distribution $\chi$ supported on $\mathbb{Z}_k$, we say the search learning with errors problem is to recover $\vec s$, given $(A, A\vec s + \vec e)$, where $\vec e \gets \chi^n$.

Depending on parameterization, the LWE problem is one of the leading candidates for a hardness assumption that is safe against quantum computers. This is to say, for a suitable generalization of solving $n \equiv xy\bmod k$, it is thought that Shor's algorithm cannot solve the problem. As seen above though, the generalization is many steps removed from your initial problem.

There are other similar generalizations in this direction (The Learning Parity with Noise problem, or the Approximate GCD problem) --- the fundamental similarity with all of them is that you have some "noisy" variant of a linear problem.


There is additionally a generalization of the $x^2+y^2\bmod k$ problem that is thought to be quantum-safe, but I do not know as many details, so will write less. Roughly, one replaces the quadratic polynomial $f(x, y) = x^2+y^2\bmod k$ with an arbitrary quadratic polynomial (or collection of polynomials) in $n$ variables. Then, the problem of recovering $(x_1,\dots, x_n)$ that are (simultaneous) zeros of multivariate quadratic polynomials $p_0, \dots,p_m$ is (roughly) related to breaking "Multivariate cryptosystems". Note that the insistence that one recovers zeros of the polynomials (rather than $p(x_0,\dots,x_n) = N$, as you ask for) comes with no loss of generality, as one can recover this by looking at a zero of $p(x_0,\dots,x_n) - N$.

This is all to say that

  1. Shor's is thought to break both of your problems, but
  2. there are generalizations of both of your problems that are thought to be quantum-safe. In fact, many of the "leading" quantum-safe hypothesis (everything I know except isogeny-stuff and rank-metric coding things) can be seen as generalizations of your problems.
$\endgroup$
2
  • $\begingroup$ Thanks again - the system still won't let me upvote (it will let me use chat though, oddly enough). I don't think there's an intermediate stage between the questions posed here and a description of the system in question. I could email a copy of the systems in question if you'd like. But I understand if that's going beyond the call of duty for crypto.se and if you don't have the time/interest. $\endgroup$
    – anon
    Mar 11 at 4:13
  • $\begingroup$ If you (or anyone) would like to see the specifics I can share an email address in chat $\endgroup$
    – anon
    Mar 11 at 20:24

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.