Being Fearless And Doing Theory

Adi Shamir is one of the great problem solvers of all times; certainly in the area of complexity theory. He is the “S” in the famous RSA crypto-system, and is a Turing Award winner—with Ron Rivest and Len Adleman.

Today we want to talk about a new approach to integer factoring.

Shamir has a vested interest in hoping that factoring is hard, since a good factoring algorithm would destroy RSA. Of course it still has had a pretty good run: as far as we know it is “unbreakable” for large enough parameters. He has voiced the opinion in public, see for instance here, that there may indeed be a way to break RSA. Ken heard him give a talk in Oxford in the mid-1980’s in which he supported the hypothesis of an exponential lower bound for factoring, but he has also designed devices for attacking it.

One of the great attributes of Adi is that he is fearless. That may sound like a strange attribute to attach to a great theorist, but he is indeed fearless. He attacks problems that others have avoided, and he also is willing to make conjectures on really small evidence. Some of these conjectures were eventually proved true, some were found to be false, and others are still open. In cryptography every time you suggest a new system or protocol you are really making a conjecture. He has suggested systems that were later broken—sometimes by him—and he has suggested systems that are still open. Of course the RSA system can really be viewed as a conjecture:

Conjecture: There is no polynomial time algorithm to break the RSA system.

I (Dick) would like to try to be a bit fearless and discuss a new conjecture that is related to joint work with Ken and with Atri Rudra. We will see if we are too fearless or not.

A Game

Let’s consider, first, a simple game played between Alice and Bob. Alice has a secret odd number that is bits long, and Bob’s job is to determine her secret. Nothing new here, yet.

Alice stipulates that she will give Bob information about her secret in the following manner: She and Bob agree on the and on . Alice then selects an integer uniformly at random in the range among numbers relatively prime to . She next determines so that

for some such that .

She then kindly tells Bob the value of . Bob can ask for any polynomial number of ‘s in this manner, and he wins provided he can determine the value of . Note that each time Bob asks, Alice selects a new and determines a potentially new to give to Bob, but her stays the same.

An important fact is that the value of is unique once is selected. Suppose there were another so that

with . Then subtracting the two equations shows that . But since is odd,

which implies that must be zero and so . Saying this another way: there is a function whose value is .

A Winning Play

It is not hard to see that Bob can win given just one . For instance, he can just solve the integer program

where the variables are , and the values of and are given. The system has a solution, by the way that Alice generated , so the only issue is to show that Bob gets the right . Suppose that he solves the system and gets another set of values . Then,

But we have that

This implies that

which is a contradiction since is too large. Thus Bob will find the correct value for . Further, it is known that integer programming is hard in general, but for a fixed number of variables it is in polynomial time (see also this recent improvement). Thus, Bob can find Alice’s secret with one in polynomial time.

Hmmmm

You may notice that this problem seems like one that you have seen before. It is the last step of the famous quantum factoring algorithm of Peter Shor, with a small twist. One twist is that in Peter’s case the is not restricted to be an odd integer.

In the quantum factoring algorithm the last step is not done by using integer programming. Rather Peter notes that needs only to be rounded down to recover . This is essentially a very special integer program that can be solved in polynomial time by the computation of the continued fraction approximations to .

A Harder Game

Let’s make things harder for poor Bob. Alice will select a and compute as before. But now she will reveal to Bob not all the bits of , but only some of them. Fix a number ; then she will reveal only bits of . Call this version of the game .

More precisely, after Alice generates , Bob can ask for any particular of the bits. For example, if he could ask for the value of modulo ; if , he could ask for the top three bits of . Each time that Alice selects an , Bob can ask for another bits.

We have just argued that Bob wins the game in polynomial time. This is essentially the argument used by Peter in his famous factoring algorithm. Now we ask the following: what is the computational complexity of the game if is much smaller than ? The reason this is interesting, I think, is the following theorem:

Theorem 1 If the game can be solved in polynomial time where is logarithmic in , then integer factoring is in polynomial time.

Ken and I, with Atri Rudra, have proved this theorem together. Curiously the only proof we know right now is via a general theorem in our paper on the simulation of quantum algorithms. Our Theorem 5.1 allows taking (there called ““) to be much larger, at the cost of getting a less efficient algorithm for factoring. For example, if , then it gives an -time probabilistic algorithm for factoring, which is better than the roughly time currently known. There are also possibilities for using other kinds of partial information about the period, along lines we began describing at the end of this post.

Hard But Interestingly Hard?

The reason the game is hard is that each successive gift of bits comes from a different . Even though Bob can ask for the topmost bits on one query, the second bits on the next query, down to the last bits, these do not allow piecing together all the bits of a single .

If the values of were random, then the sequences of bits would be random, and Bob would gain no useful information. However, even though is generated uniformly at random, the domain of corresponding ‘s has large gaps owing to being bigger than . The question is whether the length- segments of that Alice reveals would look random. We might expect that the lower is, and the lower the order of bits in the segment selected by Bob, the closer the distribution of of Alice’s answers would be to random. At what low points does Bob stop having useful distributional information to win the game ? That is the question.

We see a potential win-win situation here. If the game is easy to solve, then we have a new efficient factoring algorithm—or at least a better one in cases of . If, on the other hand, it is hard to solve even for such , then becomes a simple new type of function with potentially useful cryptographic properties. The function is easy to compute—just a few operations. Could it be used to create very efficient crypto-system?

Open Problems

What is the status of this game , for various ?

Another open problem is, can we prove the above theorem by a direct argument that avoids any use of quantum methods?

Developing: We note last week’s story on the paper by Arjen Lenstra and James Hughes and Maxime Augier and Joppe Bos and Thorsten Kleinjung and Christophe Wachter on vulnerabilities en-masse of public RSA keys, and further developments. This is not related to the above post, which we originally drafted last month. We also note the recent discovery (by declassification) of John Nash’s 1955 letter to the NSA; here is Noam Nisan’s post on it.