Crypto Aspects of The Jacobian Conjecture
Crypto concepts promise partial progress via partial inversion
cropped from source. |
Shafi Goldwasser and Silvio Micali recently won the prestigious Turing Award. Our congratulations again to both of them. Shafi asked that we help announce the upcoming 8/22 deadline for the 5th Innovations in Theoretical Computer Science (ITCS) conference. We never do this kind of thing, so we will discuss something else.
Today I wish to talk about the Jacobian Conjecture, one of my favorite problems. Ken wanted to talk about it also, and he’s posting this during our travel to the kind of workshop we never announce, but he’s been enmeshed all week in the second story here.
The conjecture recently came up as an aside to the recent breakthrough work of Yitang Zhang on the Twin Prime Conjecture. Apparently his PhD work was on the Jacobian conjecture, and initially he thought he had solved the problem—see here for more details. While he did not succeed on that, he has—much later in life—pushed and almost proved the Twin Prime Conjecture. There is some lesson there for all of us.
The Conjecture
The Jacobian Conjecture in its purest form concerns polynomial mappings from to . The Jacobian matrix has - entries defined by
Then is a single polynomial over the same variables . Since is algebraically closed, the only way can avoid having a zero is if it cancels out to be a nonzero constant. The Jacobian Conjecture is:
(JC) If is a nonzero constant, then is an invertible mapping.
The intuition for this comes from the local inverse function theorem. If , then the mapping is locally invertible at the point —that is, there is an open set containing on which is invertible.
Thus if never vanishes, is locally invertible everywhere. Offhand we would not expect this to imply the global 1-1 property, but perhaps the strong fact that must in this case be constant makes this so? That is the question. It is open even for , and has attracted many false proofs, some from quite strong researchers.
With war clouds looming, Ott-Heinrich Keller posed this question in 1939, but it emerged only during the algebraic-geometry renaissance of the 1950′s and 1960′s. Shreeram Abyankhar raised it as an example of a problem that drew on its deeper aspects but required only elementary calculus to understand. He returned to it late in life, in papers published by the Journal of Algebra in 2008 that total over 300 pages. He passed away only recently, last November.
Arno van den Essen, whose work on JC we covered before, wrote his own thoughts into 292 fewer pages. Well he also wrote a book of 329 pages. JC has been proved when each has degree at most 2, while degree 3 is equivalent to the general case. This should remind us of complexity facts about and , and makes us ask whether lurking behind all the words are issues that connect to complexity and crypto.
A Reduction
In computer theory we do reductions between problems all the time. In math this is also a normal mode of thinking. One of the neat theorems around the JC problem is that it is easy if all the polynomials are degree two, but has full generality if they are degree three, cubic. This is a standard transition from two to three that seems to repeat itself over and over, as with and .
One can even do better than just reduce the degree to three; it is possible to have the polynomials take a special form. We give the definition for an arbitrary ring .
Definition 1 Say a polynomial function from to is a D-polynomial provided where each is of the form
Further the matrix of satisfies the condition that .
A notation for such maps is . These maps are named for Ludwik Drużkowski, who proved this beautiful theorem:
Theorem 2 If for equal to the complex numbers, all -polynomials are invertible, then the full JC is true.
A Crypto Attack On JC
Crypto has grown to study multivariate polynomial maps. There have been several systems based on such maps that have been put forward as potentially hard to break. Unfortunately, most—all?—of these to date have been broken. The appeal of such systems is that polynomial functions are possibly inherently fast, since they avoid raising to high exponents in the manner of RSA, for instance. However, the attacks to date have, not surprisingly, exploited the polynomial nature of the systems.
One theorem that is used as “evidence” of the potential hardness is actually an upper bound on the degree of the inverse of a polynomial function that is invertible. It is known that the degree of the inverse is bounded by , and importantly, this bound is tight in certain situations. Despite many cases where it is not tight, this suggests that the inverse could in general be large and complex, and therefore there is hope in using polynomial maps for crypto. However, the difficulty again is that the heretofore suggested systems do not work.
My idea that I wish to discuss is the use of crypto-style arguments to perhaps shed light on the JC. I think that crypto tools may not prove the conjecture, but they could definitely help us understand the conjecture better. There are two themes:
- Given an invertible how hard is it to find a fast inversion algorithm? Note that the algorithm does not have to be: construct and apply the polynomial inverse. The inversion algorithm could use some other indirect method.
- Given an invertible is it possible to get some information about the input given the output? This is a classic crypto question. Even if we cannot fully invert fast, it would be great to show that some information is leaked.
Polynomial Maps Leak Information
The goal here is to make some simple observations about how polynomial maps can be shown to leak information. This is not enough to invert them, which would be a way to show that the JC is true. It is still an interesting insight that suggests to me that there may be even deeper results.
One small observation that I think deserves mention is the following:
Theorem 3 Suppose that is a D-mapping. Then, for any integer vector , given we can correctly guess more than half of the values modulo .
The proof of this is quite trivial. We guess for where is a random variable that uniformly selects a value from the set . The reason this works is that the cube of any number modulo is in the set . Thus we are exponentially likely to get more that one-half of the ‘s right. Actually we get each right with probability .
Note that this can be extended to get more bits of information, since we can replace by any prime such that divides . Of course the primes grow in a way that the fraction of the time we are correct goes, unfortunately, to zero. Perhaps there is some clever way to get more bits of information about . I do not know what the maximum we can get is.
In Drużkowski’s form of JC, however, we focus on polynomials with an associated coefficient matrix of special type. Can we use its nilpotency to get even more bits? Indeed we can.
Theorem 4 Suppose that is a D-mapping over the ring . If satisfies the polynomial identity for all elements , then is invertible.
The proof is quite simple. Note that the inverse of the matrix where is the matrix . This follows since,
Now let . In the ring this implies that . Thus we can use the inverse matrix on to recover the input .
There are many rings that satisfy this polynomial identity. The ring is of course one, but there are an infinite number of such rings. This follows from both a direct product argument and a compactness argument from model theory. We can also work in quotient rings modulo this identity.
Suppose that we work instead over the integers. Then the polynomial identity is no longer true, of course, but we can still get some information.
Theorem 5 Suppose that is a D-mapping over the integers. Then given , we can determine the elements of modulo in polynomial time.
Thus a D-map leaks quite a bit of information.
Polynomial Maps Over Two Variables
It is known that JC in two dimensions is true for all degrees up to 100. It seems also that 100 can be improved with more computer searching. This yields a result:
Theorem 6 Let be an integer polynomial map with Jacobian equal to . Let . Then we can determine and modulo in polynomial time for
where is the set of primes less than and relatively prime to .
The proof is simple. Take the mod each prime . The point is that modulo maps to an invertible polynomial of degree at most for each prime in . Then we invert and get modulo .
We note that the product of all the primes less than 100 is quite large
and so if is relatively prime to all of these, then we recover the inputs exactly for all inputs up to this number.
Open Problems
Can we prove that polynomial maps leak even more information? Does this shed any light on the actual JC? Or does it help understand the capabilities of polynomial maps in crypto?
This looks very interesting to me, but it may be a month before I can get back to it.
Just off the top of my head, it may be of interest in our computational (polynomial, propositional) context to investigate the Boolean, characteristic 2, or logical analogues of this and other topics in differential geometry, especially the question of finding the right logical analogue of the tangent functor.
cf. Differential Logic and Dynamic Systems
Nice article.
I don’t understand the reasoning–I must be dense–that “we get each right with probability 4/7″. $\Delta_i$ is distributed as P=(3/7,1/7,3/7) over the set {-1,0,1}. If we draw $Z$ from the probability distribution $Q=(1/3,1/3,1/3)$ as suggested, and let Z be our guess, our probability of success for guessing each $\Delta_i$ correctly is $(1/3)*((3/7)+(1/7)+(1/7))=1/3,$ no?
If we always guess $Z=+1$ or $Z=-1$ our probability of success is (3/7). If we are allowed to make a single guess for each $\Delta_i$ we can’t do any better than this, whereby we guess (one of) the most likely outcome(s).
Nice post attacking the Jacobian conjecture from a refreshing angle. I am a bit confused by theorem 1, are you sure that A^2=0 ? I may be mistaken, but I cannot see this in the original paper of Drużkowski. Moreover if you take as matrix A={{0, 1, 0}, {-1, 0, 1}, {0, 1, 0}}, then A is a Drużkowski matrix, but A^2 is not null…. (as pointed in this (Gorni et al, Druikowski matrix search and D-nilpotent automorphisms, 1999))
Me
I believe in later paper this follows. But even if high power was zero the inverse is still of the claimed form. Right?