Factoring and diophantine equations

Dan Boneh is one of the top cryptographers in the world, one of the best. He combines the ability to prove deep mathematical theorems with the ability to design and build real systems. He combines the ability to break crypto-systems with the ability to create new ones. I believe these are hard combinations to find: who else can use Weil Pairings while building real running systems. Not many.

I remember when he was a graduate student at Princeton–I was his advisor–I asked him if he knew of any “simple” proxy engines. A proxy engine is a piece of software that acts as a kind of repeater for Internet packets. A packet from ${A}$ arrives at the proxy engine, the engine sends the packet on to ${B}$; on the return path the packet from ${B}$ is redirected back to ${A}$. Often some other processing is done to the packets, sometimes as simple as logging, sometimes much more. Proxy engines can be quite complex, since they must deal with various failures modes and other issues, but the simplest possible one would act like an identity function: how complex can that be?

At the time I was working on a problem and needed a proxy engine that would be easy to modify. The ones I found on the Internet were quite complex: huge general purpose systems. They were like huge gray battleships–big and complex, great for some tasks, but way beyond what you might want for a day cruise around the bay.

So I asked Dan if he knew of any simple proxy engines. He replied that he did, but he had a sheepish grin. He knew of one because he had written his own in Perl, and it was one page of code. One page. I was surprised, and asked him the obvious question, “why did you do that?” He said, partly to learn how the Internet protocols worked and partly for another reason that I will not say. His code was great and for a while, after he put it on his home-page, there was a small “Dan Boneh’s Proxy Users Group”. Many used his proxy engine, it was complete, yet elegant. Great for a day cruise on the bay.

Factoring Again: Always Factoring

One of the themes that we pursed, while Dan was a graduate student, was: is factoring easy? I believed (and still do) that factoring could be easy. I cannot speak for Dan then or now, but as long as the complexity of factoring is open, it makes sense to look at what are the consequences of assuming that factoring is hard. One possibility is that we could show that assuming it is hard yields a contradiction: this would be great, but seems unlikely. A more interesting outcome we felt was that we might be able to show that it has strong mathematical consequences. Our dream was to prove some deep mathematical theorem based on the asssumption that factoring was hard.

Let’s call the assumption that factoring is hard ${{\cal FH}}$. You can think of this as saying that there are no polynomial size circuits for factoring. Later on I will state the exact assumption more carefully. In any event, the assumption we are making concerns circuits, not algorithms. This is an important difference. There could be a polynomial size circuit that can factor each size of numbers, without there being a polynomial time algorithm for factoring. Circuits are a type of non-uniform model of computation. Most people who believe that factoring is hard probably also believe that factoring does not have small circuits. The ideas we will discuss today only apply to circuits.

Dan and I tried to prove theorems of the form:

$\displaystyle {\cal FH} \implies D$

where ${D}$ was the statement that some Diophantine equation had only a finite number of solutions. What was interesting about these results was that proving the same result without ${{\cal FH}}$ looks beyond the ability of current number theory.

Here is an example that I have thought about recently. Let ${p_{k}}$ be the primes in the interval ${[2^{n-1},2^{n}]}$ and let ${\lambda_{k} >0}$. Suppose that we could compute

$\displaystyle T = \displaystyle\prod_{k} p_{k}^{\lambda_{k}}$

by a straight-line computation of length polynomial in ${n.}$ (Recall a straight-line computation is one that starts with the input variables, and at each step performs an arithmetic operation. The length of the computation is the number of operations performed, and the last step is the answer or the output.) Then, factoring based crypto-systems would be broken. The proof is quite simple–I will explain the details shortly.

We can make this even more concrete. Suppose that

$\displaystyle T = \displaystyle\prod_{k} p_{k}^{\lambda_{k}}$

was equal to

$\displaystyle \displaystyle\sum_{i=1}^{m} a_{i}b_{i}^{c_{i}}$

where ${m = n^{O(1)}}$ and ${a_{i},b_{i},c_{i}}$ all are less than ${2^{n^{O(1)}}}$. Then, again we could break factoring based crypto-systems. When Dan was still a student he gave a talk on earlier versions of these ideas to an audience that contained a very strong number theorist. After hearing Dan’s talk, he sent us a multi-page “outline” of a potential proof that a much weaker Diophantine problem had no solutions. It was only a sketch, it used another unproved hypothesis, and was incomplete. Our reply was we could show that the Diophantine equation in question had only a finite number of solutions with a trivial argument, provided we could assume ${{\cal FH}}$. I think the number theorist missed the point: we were showing how powerful ${\cal FH}$ was.

How To Break Crypto-Systems

Let’s get back to showing that if the above Diophantine problems have solutions, then we can break crypto-systems based on factoring. The key is a basic idea from computational number theory: called the fast modular exponentiation method. I will discuss this in detail in a later post, but for now you need to know that one can compute

$\displaystyle a^M \bmod N$

in time that is polynomial in the number of bits in $a,M,N.$ Note, the number $a^M$ could be huge. But the value of $a^M$ modulo $N$ must lie between $0$ and $N-1.$ This “trick” also uses repeated squaring, but for now, if you do not know this method, please accept that $a^M \bmod N$ is easy to compute even for large numbers.

Suppose that the crypto-system selects two random primes ${p}$ and ${q}$ from a given range. Then, ${N=pq}$ is made public. Our goal is to find the value of ${p}$ and ${q}$. Assume that ${p}$ lies in the range ${[2^{n-1},2^{n}]}$ and that ${q}$ does not. Then, recall that ${T}$ is equal to

$\displaystyle \displaystyle\prod_{k} p_{k}^{\lambda_{k}}$

where ${p_{k}}$ are the primes in the interval ${[2^{n-1},2^{n}]}$. Note, that the greatest common divisor (gcd) of ${T}$ and ${N}$ is equal to ${p}$. Thus, we are done if we can compute this value in polynomial time. But the assumption is that ${T}$ is also equal to

$\displaystyle S = \displaystyle\sum_{i=1}^{m} a_{i}b_{i}^{c_{i}}$

where ${m = n^{O(1)}}$ and ${a_{i},b_{i},c_{i}}$ all are less than ${2^{n^{O(1)}}}$. The critical point is that we cannot compute ${S}$ it’s way too big, but we can use the exponential trick to compute ${S \bmod N}$. Call this last value ${\alpha}$. By basic properties of the gcd ( denote the gcd of ${x}$ and ${y}$ by ${(x,y)}$), it follows that

$\displaystyle p = (T,N) = (S,N) = (\alpha,N).$

There is a point that was already raised in one comment: The existence of an $S$ that is equal to $T$ is enough to guarantee the existence of a circuit that factors. A circuit is not an algorithm, so the fact that finding the values of the $a_i,b_i,c_i$ could be very hard is immaterial. If they exist, then there has to be a circuit that can break the systems as described. Note, this is weaker than an algorithm, but would be, I believe, be upsetting to the crypto-community.

This is what happens. If the above Diophantine equation $T= S$ has a solution for a given size $n,$ then, there exists a series of gates that make up a boolean circuit of size at most polynomial in $n.$ This is a “magic” object. Its gates describe a computation that runs fast, and breaks any crypto-system that uses primes as above. It is magic because we do not know the actual circuit. But someone could be smarter than us and find the magic circuit, they could then program their laptop so that it would smash our crypto-systems as described above. This is the threat.

There are two more points to make about this approach. It clearly depends on “knowing” an interval that contains one prime and not the other. There is nothing special about the range ${[2^{n-1},2^{n}]}$ any suitable range would work. We only need that there is a range where it is likely that one prime lies and not the other. More exactly if the crypto-system selects the primes $p$ and $q$ from some range, then we only need that there is an interval $[X,Y]$ so that we can compute

$\displaystyle \displaystyle\prod_{k} p_{k}^{\lambda_{k}}$

for the primes $p_k$ in this interval. And also that when the primes are selected randomly with a reasonable probability only one of the primes will be in the interval $[X,Y]$.

Second, the assumption that ${T}$ contains all the primes in the interval is over-kill. Even if many of the exponents ${\lambda_{k}}$ were ${0}$, then the method would still work. As long as a polynomial fraction of the primes had positive exponents, the method would still break the system with a reasonable probability.

Open Problems

I promised earlier to state what ${{\cal FH}}$ means. For us it will mean there is no boolean circuit (not algorithm) that can break a crypto-system that selects random primes $p$ and $q.$ We must know an interval that is likely to contain only one of the primes. That’s the assumption. Note, almost all schemes that use primes can be made to fit this model. For schemes that are more complex we can generalize the methods here to handle them too.

There are two types of open problems. First, can we show that the above equations have no solutions. In particular, can we show that

$\displaystyle \displaystyle\prod_{k} p_{k}^{\lambda_{k}}$

cannot be equal to

$\displaystyle \displaystyle\sum_{i=1}^{m} a_{i}b_{i}^{c_{i}}$

where ${m = n^{O(1)}}$ and ${a_{i},b_{i},c_{i}}$ all are less than ${2^{n^{O(1)}}}$ A challenge:

If you believe that factoring has no small circuits, then you must also believe that the above Diophantine equations have no solutions. Prove it.

Things are even worse. Even if the equations had solutions for an infinite number of ${n}$, there would still be a problem for cryptography. Actually, even if the above equation held for, say, $n=1000$, then certain systems would be broken. This seems to me to be worrisome. This and other ideas make me believe that it is quite possible that ${\cal FH}$ is false. That the conventional wisdom is wrong.

Second, are there similar questions that can be proved based on assuming that discrete logarithm is hard? One of the great mysteries in computational number theory is why are factoring and discrete logarithm linked. Almost every time a better algorithm is discovered for one, there is shortly a similar improvement for the other. This is true for classic algorithms as well as for quantum algorithms. More on this in a future post. A most perplexing question, since there is no known direct reduction from one to the other.

March 11, 2009 12:51 pm

1) We need an interval [X,Y] such that p is in the interval and q is not. Why not just choose [sqrt{N}, N]?

2) How does assuming the existence of S help? It seems that finding a_i, b_i, and c_i take too long, since S has exponential size.

I’m not sure I follow the reduction here.

We’re given N=pq, and we want to find T, since the GCD of N and T is p. The claim is that if T=S, then we can break

March 11, 2009 1:51 pm

On the interval, any one will work as long as has the desired properties: only one prime in it and can compute the needed product fast.

We do not find S. The whole point is that the existence only of S implies that there is a circuit. Circuits do not need to have an algorithm that describes them. They are what is called a non-uniform model of computation.

Last point is if T=S we can compute T fast since raising numbers to a power modulo N is fast.

Again thanks for the comment–I did update the post, I hope it is clearer now.

March 11, 2009 5:56 pm

Thanks. It makes a lot more sense now.

Somehow I find it a lot easier to believe that factoring is solvable in P/poly than in P, so it’s nice to see evidence to the contrary.

Taking the contrapositive, we see that having finitely many solutions implies P\not=NP. Such a number-theoretic proof avoids relativization issues. Does it also avoid the other known barriers (algebrazation, natural proofs, etc)?

March 12, 2009 11:22 am

Whoops. Never mind. That would be the converse.

I shouldn’t write posts when tired…..

5. October 19, 2009 12:40 am

Please make a followup post to this very, very interesting topic.

6. December 22, 2012 6:59 pm

I’m amazed, I have to admit. Seldom do I encounter a blog that’s equally educative and engaging, and let me tell you, you’ve hit the nail on the head. The problem is something that too few folks are speaking intelligently about. I am very happy that I found this during my hunt for something relating to this.