# (Complexity Theory) Given a large non-semiprime, is there a hard to compute but easy to verify problem?

Let's say I had an arbitrary number that was large, say 512 bits or bigger, but wasn't necessarily a semiprime. What is a computation that I could do on this number that would give me a unique solution that is guaranteed to be very inefficient to compute, but very quick to verify? I am looking for something in number theory / complexity theory. The problem needs to have a solution, rather than a decision problem of "yes" or "no".

• The usual factorization? I think your question lacks some details? Dec 13, 2023 at 9:06

What's asked is an algorithm implementing a hard to compute function of the input number $$x$$ with an easy way to check the result.

If we can use auxiliary fixed parameters, and are content with probabilistic algorithms to implement a deterministic function, we can use something based on the Discrete Logarithm Problem in $$\mathbb Z_p^*$$.

Parameters selection: we draw an arbitrary public prime $$p$$ with $$\ell=\left\lceil\log_2 p\right\rceil$$ suitably larger than 512 to adjust the difficulty (more on the choice of $$\ell$$ later), and $$q=(p-1)/2$$ prime (that is, $$p$$ and $$q$$ are a pair of safe and Sophie Germain primes). Then we select a public generator $$g$$, that is in the context an integer $$g\in[2,p-1)$$ with $$g^q\bmod p=p-1$$ (the smallest $$g$$ will do, it's always prime, and if we search $$g$$ among primes starting from $$2$$ we'll try on average about two candidates, with geometric distribution). This setup insures that $$y\mapsto g^y\bmod p$$ is a bijection over the integers in $$[1,p)$$.

The computation asked is to, on input $$x$$ and the parameters $$(p,g)$$, output the uniquely defined integer $$y\in[1,p)$$ with $$x+1=g^y\bmod p$$. Verification of $$y$$ is easy.

The best methods we have to solve that problem for $$\ell$$ somewhat above 512 and otherwise arbitrary $$x$$ $$p$$ are expensive, with cost \begin{align}\exp\biggl(\left(\sqrt[3]{\frac{32}{9}} + o(1)\right)(\ln p)^{\frac{1}{3}}(\ln \ln p)^{\frac{2}{3}}\biggr) &= L_p\left[\frac{1}{3},\sqrt[3]{\frac{32}{9}}\,\right]\\ &= L_{\bigl(2^\ell\bigr)}\left[\frac{1}{3},\sqrt[3]{\frac{32}{9}}\,\right] \end{align} and the current record is for $$\ell=795$$, see this.

If the problem is already too hard with $$\ell=513$$ (it already takes many CPU⋅days), we can lower $$\ell$$ and truncate $$x$$ to $$\ell-1$$ bits.

There are a few rough edges: the work to solve several instances sharing $$p$$ does not scale proportionally with the number of instances; and solutions are trivial for some $$x$$, including $$x=0$$, and more generally $$x=g^y-1$$ for integer $$y\in\bigl[0,\ (512/\log_2g) \bigr)$$. But these issues can be ironed out (for the later one: we can replace $$x$$ by a hash of $$x$$, which impairs neither computation nor verification). Also, other DLP-based solutions work, including on elliptic curve groups.

Notably, we have no proof of the work required, even with classical computers. And in some decades, hypothetical CRQC could conceivably lower the cost.

• Can I keep re-using the same $p$ without affecting the work required for each input? In other words, does re-using the same $p$ over and over again make it increasingly easier? Dec 15, 2023 at 14:53
• @Starscream512: There is some work that depends only on $p$ and can be shared for other $x$. I don't know exactly how much, and that's why I mention rough edges and that the work to solve several instances sharing $p$ does not scale proportionally with the number of instances. But that's solvable. One way is to make some bits of $p$ a function of $x$ (at the price of adding on average seconds to the verification). Another may be the use of an elliptic curve group. I will think about it. Update: I asked here.
– fgrieu
Dec 16, 2023 at 14:52
• Can you give us a small example of Discrete Log, using trivial values in your answer above? It would really help me solidify my understanding. Dec 18, 2023 at 8:42
• @Starscream512: pick $p$ in A269454, e.g. $p=587$ (or this), and $g=2$. The function $y\mapsto g^y\bmod p$ is a bijection on $[1,p)$. Solving the DLP is finding the input $y$ given the output $g^y\bmod p$. For example with $p=587$, finding that $y$ yielding the output $3$ is $y=478$. It's easier to check $2^{478}\bmod587=3$ than it is to find $478$ given $3$ and $587$. To get convinced of that, try to find $y$ yielding the output $5$.
– fgrieu
Dec 18, 2023 at 9:21
• If the output happened to be an edge case, say 16, we can (sha256(15) mod (p - 1)) + 1 to give us a new output? Dec 19, 2023 at 2:40

Factoring would be difficult. Your 512 bit number could be the product of three 171 bit primes. If one prime is smaller then the other two would be larger. As long as the second largest prime is large it’s hard to factor.

• One potential issue with this approach (asking for the factorization of the input, with some prescribed output format insuring uniqueness) is that it's easy for a sizable fraction of 512-bit input. For a start, >0.28% of the inputs are prime, making the problem trivial. And a much larger fraction can be factored with moderate effort and a combination of Pollard's Rho and Pollard's p-1 methods, and even more if we add Lenstra's ECM in the mix.
– fgrieu
Dec 13, 2023 at 12:18
• Ease of factoring would greatly depend on the number you happen to factor. Dec 13, 2023 at 12:45
• @fgrieu Not to mention that if the number happened to be semiprime, it would be hardest of all. Dec 16, 2023 at 9:22

Let's say I had an arbitrary number that was large, say 512 bits or bigger, but wasn't necessarily a semiprime. What is a computation that I could do on this number that would give me a unique solution that is guaranteed to be very inefficient to compute, but very quick to verify?

How about "given $$x$$, what's the value $$y$$ s.t. $$x = \text{SHAKE}( y || \text{arbitrary number} )$$ (with $$x$$ being long enough that the solution is guaranteed unique)?

Obviously, quick to verify, and if $$y$$ is long enough, very inefficient to compute...

• I see no way to match both "arbitrary" and "unique" in the problem statement with a hash-based system, as proposed. In fact, with symmetric cryptography, if we match both, it's hard to have sizably different execution time according to direction.
– fgrieu
Dec 13, 2023 at 20:45
• @fgrieu: if the length of y is less than the rate (which is large enough), then different y of the same size will always yield different SHAKE states (both absorbing identical strings, and during the squeezing). Hence, if two different $y$s yield the same SHAKE output, the differences will have to be consistently confined to the capacity. If $x$ is long enough (say, 2 or 3 times the rate), the probability of this happening consistently for all 2 or 3 permutations is tiny $\lll 2^{-1024}$ Dec 13, 2023 at 21:31
• I understand that we can make $y$ small enough that with certainty (for some meaning of that) there's no two $y$ for a given $x$; or even, no $x$ with two $y$. What I don't get is how it's simultaneously insured there exists a $y$ for any "arbitrary" $x$. I'm reading the question as requiring a true function of $x\in\{0,1\}^{512}$. Independently: I asked a question about the part of your argument that uses the sponge structure of SHAKE.
– fgrieu
Dec 14, 2023 at 7:46