Polynomial Interpolation from Multiples Joachim von zur Gathen Abstract We are given an unknown polynomial f Z[x] by a black box which on input a Z returns a value ra · f (a) for some unknown nonzero rational numbers ra . If we have appropriate upper bounds on the numerator and denominator of ra and the degree of f , then the coefficients of f can be computed in probabilistic polynomial time. Keywords: Hidden polynomial, black box polynomial, approximate computation, short vectors, integer lattices. 1 Intro duction Igor E. Shparlinski we consider the interpolation task when the ratio to the true value is bounded appropriately. More precisely, we want to compute the coefficients of a polynomial f Z[x] of degree n for which we are given a multiplicatively approximate black box MABB(A, , ) which on input a Z, in time O (1) (n log(A|a| + 1)) returns a rational multiple ga = ra · f (a) of f (a) for some unknown nonzero ra Q. Here A, , and are positive real numbers such that we can write ra = ka /ma with integers ka , ma and (1.1) gcd(ka , ma ) = 1, 0 < |ka | A|a| , 0 < |ma | A|a| . There are several ways of representing a univariate polynomial over a ring. The two most important date structures are the list of coefficients, and a list of values, together with a bound on the degree. The transformations between these two representations, namely evaluation and interpolation, play a basic role in many applications. In more general domains, including the rings of interest in number theory, interpolation becomes the Chinese Remainder Algorithm. An interesting variation of the classical task of interpolation assumes that not the exact values are given, but only approximations to them. This may mean that each value may be "a little incorrect", or that some but not all values are correct. The usefulness of this problem first appeared in coding theory, with the classical Reed-Solomon codes and the more recent tool of list decoding. A number-theoretic version of importance in cryptography is the hidden number problem. It is, of course, necessary to have enough information in the incorrect values to allow reconstruction of the true ob ject. In this paper, we want to reconstruct a polynomial from approximate values all of which may be incorrect, in some controlled fashion. The case where the difference to the true values is bounded (and we work over a finite prime field), has been solved in [17]. In this paper, of Computer Science, Electrical Engineering and Mathematics, Universit¨t Paderborn, 33095 Paderborn, Gera many, gathen@upb.de, http://www-math.upb.de/~gathen/ Department of Computing, Macquarie University, Sydney, NSW 2109, Australia, igor@comp.mq.edu.au, http://www.comp.mq.edu.au/~igor/ Faculty The gcd condition is convenient but obviously not necessary. We assume that the response time of the MABB(A, , ) is polynomial in the bit length of |ga | (thus queries with large values of a are more expensive). We design a probabilistic polynomial time interpolation algorithm which works for an MABB(A, , ) with any + < 1/(n + 2). We also consider the same problem for polynomials f Fp [x] over a finite prime field Fp of p elements with a modular multiplicatively approximate black box, MMABB(, , p) , which on input a Z returns a multiple ga = ra · f (a) Fp of the value f (a) Fp with some factor ra F such that ra ka /ma mod p p for some integers ka , ma satisfying (1.2) gcd(ka , ma ) = 1, 0 < |ka | p , 0 < |ma | p . We obtain similar results for this problem, but the bound on the possible values of and is less generous. The corresponding additive problem, where a black box produces a shift sa + f (a) for some integer sa , has been solved in [16] over Fp , with a rather generous error bound on the size of sa (roughly speaking, |sa | could be up to p exp(- log1/2 p)). Loosely speaking, the problem we consider in this paper, as well as the above mentioned additive problem, are variants of the hidden number problem which has its origin in pioneering works of Boneh and Venkatesan [2, 3] and which has proved to be an invaluable tool for cryptography and computer science; see [19] and also surveys given in [17, 18]. Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688 1132 It is no surprise that, as in most other works on the hidden number problem, our main tool is a lattice basis reduction algorithm. Venkatesan Guruswami and Avi Wigderson have remarked that if the fudge factors ra are always integers with a polynomial bound on their value, then we can divide by all integers up to the bound (which evenly divide the approximate value) and obtain a list which contains sufficiently many correct values so that the list decoding approach of [7] recovers the polynomial. However in this paper, as well as in [16], these factors may be chosen from exponentially large sets. Lattices, linear homogeneous equations, and p olynomials Here we collect several well-known facts which form the background of our algorithm. We review several related results and definitions on lattices which can be found in [6]. For more details and more recent references, we recommend to consult the brilliant surveys of Nguyen and Stern [10, 11]. Let {b1 , . . . , bs } be a set of linearly independent vectors in Rr . The set L = {z : z = c1 b1 + . . . + cs bs , c1 , . . . , cs Z} 2 Sivakumar [1] lead to some (rather slight) improvements of our results. We also assume that the basis {b1 , . . . , bs } of L consists of vectors in Zr (rather than in Rr ), so one can talk about the bit size of the basis and the notion of a polynomial-time algorithm. Lemma 2.1. There exists a deterministic polynomialtime algorithm which, given a basis for an s-dimensional lattice L, finds a nonzero vector v L with v 2(s-1)/2 min { z : z L\{ 0}}. It is also useful to remember that when s is small (for example, constant), then in polynomial time one can find a nonzero vector v L with v = min { z : z L \ {0}}, see [1, 10, 11]. The set of integer solutions z = (z1 , . . . , zr ) Zr of a linear homogeneous Diophantine equation ir =1 zi ci = 0 forms a lattice of dimension r - 1 (unless c1 = · · · = cr = 0). The same is also true for the solutions z Zr of a linear homogeneous congruence ir is called an s-dimensional lattice with basis {b1 , . . . , bs }. zi ci 0 mod p If s = r, the lattice L is of ful l rank. =1 To each lattice L one can naturally associate its modulo a prime p, except that in this case the set of volume integer solutions forms a lattice of dimension r. d 1 /2 s Finally, for any polynomial f K[x] of degree at vol (L) = et ( bi , bj )i,j =1 , most n over any field K we have the well-known Newton where a, b denotes the inner product, which does not relations n f n+1 depend on the choice of the basis {b1 , . . . , bs }. i +1 i For a vector u, let u denote its Euclidean norm. (2.4) (x + i) = 0. (-1) i The famous Minkowski theorem, see Theorem 5.3.6 in =0 Section 5.3 of [6], gives the upper bound Moreover, if deg f = n and the characteristic of K is 1 /2 1 /s either greater than n + 1 or zero then, because f can min { z : z L \ {0}} s vol (L) (2.3) also be viewed as a linear recurrence sequence of order on the shortest nonzero vector in any s-dimensional exactly n + 1, any other linear relation between all lattice L via its volume. In fact s1/2 can be replaced by (n + 2)-tuples of consecutive values of f has coefficients 1 /2 the slightly smaller Hermite constant s , see [10, 11]. proportional to those in (2.4). That is, if for some The Minkowski bound (2.3) motivates a natural coefficients C0 , . . . , Cn+1 K question: how to find the shortest vector in a lattice. n +1 i Unfortunately, there are several indications that this (-1)i Ci f (x + i) = 0 problem is NP-complete (when the dimension grows), =0 see [10, 11]. However, for a relaxed task of finding a short vector, the celebrated LLL algorithm of Lenstra, for all positive integer x, then n , Lenstra and Lovasz [9] provides a desirable solution. ´ +1 i Ci = (-1) for 0 i n + 1, To simplify our calculations we use the LLL ali gorithm in its original form. Later developments of Schnorr [15] and quite recently by Ajtai, Kumar, and and some K. 1133 3 Polynomials over Z There is some nonuniqueness inherent in our problem. Namely, when the black box chooses all its fudge factors ra as even integers, then we can in principle not tell whether the original polynomial is f or 2f . Therefore we can at best expect a constant multiple of the original polynomial as output. We call an integer polynomial primitive if the greatest common divisor of its coefficients is 1, and its leading term is positive. Each nonzero integer polynomial has a unique constant multiple which is primitive, and we make this our target, thus removing the non-uniqueness just mentioned. As usual we define the height of a polynomial f (x) = in fi xi Z[x] and consider nonzero vectors b = (b0 , . . . , bn+1 ) [-B , B ]n+2 . We let B = {b [-B , B ]n+2 : b not proportional to c}. In particular, hb is not identically zero for any b B. A Taylor expansion at i of the ith summand of hb gives hb (x) = j n n+1 i =0 =0 bi f (j ) (i) j x j! n =j = j n n+1 i =0 =0 f j bi -j j x. i Estimating each term trivially we obtain for b B H(hb ) (n + 2)(n + 1)n+1 2n B H(f ) (n + 2)n+2 2n B H. Hence for b B, the absolute value of any zero of hb is less than H(hb ) + 1 < (n + 2)2n+2 B H . =0 We now set a = (n + 2)2n+2 B H and query the as approximate black box for f with inputs a + i to receive H(f ) = max |fi |. 0in the values ka+i We consider the family Pn (H ) of primitive polyno- g · f (a + i) for 0 i n + 1. a+i = ra+i · f (a + i) = ma+i mials of degree n and of height at most H : n All values ga+i are nonzero because a H(f ) + 1. i f (x) = i=0 fi x Z[x] : We consider the (n + 1)-dimensional lattice gcd(f0 , . . . , fn ) = 1, Pn (H ) = . n +1 z , fn 1, H(f ) H i L= = (z0 , . . . , zn+1 ) Zn+2 : zi ga+i = 0 Theorem 3.1. Let n and H be positive integers, and =0 let , , be nonnegative real numbers with 0 < < 1 and the integers and + (1 - )/(n + 2). There is a deterministic n+1 n +1 j j algorithm which, for any f Pn (H ), computes the K= ka+j , M = ma+j , coefficients of f in time polynomial in n, log H, log A, =0 =0 and -1 using an MABB(A, , ) for f . and Proof. For each factor ra we always write ra = ka /ma ka+i ma+i Ki = M , Mi = K for 0 i n + 1. with ka and ma of the form (1.1). ma+i ka+i n+2 be Let f Pn (H ) and c = (c0 , . . . , cn+1 ) Z Then the vector of coefficients in (2.4), that is, |Ki | An+2 (a + i)+ (n+1) , n , +1 (3.5) ci = (-1)i 0 i n + 1. |Mi | An+2 (a + i)(n+1)+ i for 0 i n + 1. We see that L contains the "short" For a vector b = (b0 , . . . , bn+1 ) Zn+2 , we consider the vector u = (u , . . . , u 0 n+1 ) with polynomial ui = ci Mi for 0 i n + 1. n +1 i By (3.5) its norm satisfies hb (x) = bi f (x + i) Z[x]. n+1 1 /2 =0 i n +2 (n+1)+ 2 u A (a + n + 1) ci In particular, we have hc = 0. Moreover, as discussed =0 in Section 2, hb = 0 if and only if the vectors b and c n+1 i are proportional. An+2 (a + n + 1)(n+1)+ |ci | We let =0 ( , 1 / B= n + 2)2n+2 (2A)2n+4 H = 2n+1 An+2 (a + n + 1)(n+1)+ 1134 and thus the algorithm of Lemma 2.1 returns a vector Proof. For each factor ra we always write ra = ka /ma v = (v0 , . . . , vn+1 ) L with with ka and ma are of the form (1.2). The assumptions imply that p > n + 1. We define v 2(n+1)/2 u 23(n+1)/2 An+2 (a + n + 1)(n+1)+ . the vector c Zn+2 and the polynomials h F [x] for b p b Zn+2 in exactly the same way as in the proof of We have Theorem 3.1. In particular, we have hc = 0, and hb = 0 |vi Ki | 23(n+1)/2 A2n+4 (a + n + 1)( +)(n+2) if and only if the vectors b and c are proportional modulo p (2A)2n+4 a( +)(n+2) 1 a. We let (2A)2n+4 a1- 1- ( = (2A)2n+4 n + 2)2n+2 B H B= 6 (p)1/(n+2) nd consider nonzero vectors b = (b0 , . . . , bn+1 ) [-B , B ]n+2 . We let B = {b [-B , B ]n+2 : b not proportional c over Fp }, n+1 i =0 (n + 2)2n+2 (2A)2n+4 H B 1- B for 0 i n + 1. Since 0= n +1 i =0 vi M ga+i = vi Ki f (a + i), and for b B, we consider Abb = {a Z : hb (a) = 0}. We have #Ab n, and A = B Ab has at most n(2B + 1)n+2 < n3n+2 B n+2 6n+2 B n+2 p it follows that (v0 K0 , . . . , vn+1 Kn+1 ) is proportional to c, say vi Ki = ci for some nonzero Q and all i n + 1. We now calculate the unique interpolation polynomial g Q[x] of degree at most n with g (a + i) = ga+i vi /ci for 0 i n. (The value for i = n + 1 is ignored.) Since elements. We choose a uniformly at random from Fp , so that Prob(a A) < . We now query the approximate black box for f with the inputs a + i to receive the values ga+i = ra+i · f (a + i) for 0 i n + 1. Because f is not identically zero, at least one value g (a + i) = ga+i vi /ci = ga+i /Ki = f (a + i)/M ga+i Fp is nonzero. We consider the (n + 1)for 0 i n, g is a nonzero constant multiple of dimensional lattice n +1 z . f . Finding f from g is trivial. The cost estimate is i L= = (z0 , . . . , zn+1 ) Zn+2 : zi ga+i = 0 immediate. =0 Polynomials over finite fields We also denote Here we show that the approach of Section 3 works for n+1 n +1 j j polynomials over Fp for a prime p. K= ka+j , M = ma+j To avoid the nonuniqueness problem in the case =0 =0 of polynomials over Fp it is more natural to consider monic polynomials rather than primitive ones. As in and any ring, multiplication by integers is well-defined, so ka+i ma+i Ki = M , Mi = K, 0 i n + 1. that ay Fp for any a Z and y Fp . Similarly, we ma+i ka+i have h(a) Fp for a Z and h Fp [x]. We consider the family Mn,p of monic polynomials In particular of degree n: |Ki | p+(n+1) , |Mi | p(n+1)+ (4.6) f . in for 0 i n + 1. We see that L contains the "short" Mn,p = (x) = fi xi Fp [x] : fn = 1 vector u = (u0 , . . . , un+1 ) L with =0 Theorem 4.1. Let n be a positive integer, and let ui = ci Mi for 0 i n + 1. , , , be nonnegative real numbers with 0 < , < 1 By (4.6) its norm satisfies and + = (1 - )/(n + 2)2 . Then for any prime n+1 1/2 p > 2(2n+6)(n+2)/ -1/ i u p(n+1)+ c2 i there is a probabilistic algorithm which for any f =0 Mn,p computes with probability at least 1 - the con+1 i efficients of f in time polynomial in n, log p, -1 and p(n+1)+ |ci | = 2n+1 p(n+1)+ , -1 log using an MMABB(, , p) for f . =0 4 1135 and the algorithm of Lemma 2.1 returns a vector v = zeros of linear recurrence sequences over Z and in finite (v0 , . . . , vn+1 ) L with fields; see [4], or the original papers [5, 12, 13, 14]. One can obtain an algorithm which interpolates v 2(n+2)/2 u 22n+2 p(n+1)+ . a t-sparse polynomial with only t + 1 queries to an MABB(A, , ) or an MMABB(, , p); the whole alThe assumption in the theorem implies that B 1, and gorithm however remains polynomial in n, not in t and therefore log n as one would desire for t-sparse polynomials. One can also consider polynomials with rational coB+1 1 1 / ( n +2) 1 / ( n+2) B 22n+2 p(1-)/(n+2) . efficients for which there is black box returning rational p 2 12 multiples of their values with controlled numerator and We have denominator. Our method, combined with the method of [16], can |vi Ka+i | 22n+2 p(+ )(n+2) 22n+2 p(1-)/(n+2) B be applied to the more general problem of recovering k polynomials f1 , . . . , fk from polynomially many vectors for all i n + 1. Now we assume that a A. Since Ra · (f1 (a), . . . , fk (a))T + sa for some "small" matrices Ra and vectors sa . n +1 n+1 i i Finally, our method can be extended to polynomials 0= vi M ga+i = vi Ki f (a + i), f (x1 , . . . , xm ) in m 2 variables by making Kaonecker r =0 =0 a d+1 (d+1)m-1 nd thus queries of the form f , a , . . . , a it follows that (v0 K0 , . . . , vn+1 Kn+1 ) is proportional reducing this case to the univariate case. modulo p to c, say vi Ki = ci for some integer with We conclude by mentioning that it would be in 0 mod p and all i n + 1. Since p > n + 1, each ci teresting to consider an analog of our problem over a with i n + 1 is nonzero modulo p. We now calculate the unique interpolation polynomial g Fp [x] of degree residue ring of the integers modulo an integer. One of at most n with g (a + i) = ga+i vi /ci Fp for 0 i n. our crucial ingredients, namely the fact that the number of roots of a polynomial is bounded by its degree, does (The value for i = n + 1 is ignored.) Since not apply anymore. However, over such rings one can try to use a much weaker bound of Konyagin [8]. g (a + i) = ga+i vi /ci = ga+i /Ki = f (a + i)/M Instead of recovering a hidden polynomial, we can for i n, g is a nonzero constant multiple of f , and ask to construct a number x given by a black box f = lc(g )-1 · g , where lc(g ) is the leading coefficient of returning rp x mod p on input p, for a prime p and a g . The cost estimate is immediate. small rational number rp . One will have additional constraints, such as bounds on |x| and on the primes. 5 Remarks This problem is now under consideration. -1 Our algorithm works with + = O(n ) over Z and Acknowledgement. The authors thank with + = O(n-2 ) over Fp . The example of two Venkatesan Guruswami and Avi Wigderson for useful polynomials xg and (x + 1)g where deg g = n - 1 shows discussions and in particular for attracting our attenthat it is impossible to solve this problem with > 1. tion to the possible application of list decoding as in [7], Indeed, the black box output a(a + 1)g (a) is consistent to the special case where the fudge factors are polynowith both polynomials. It is an open question by how mially bounded in value. much our bound on + can be relaxed. Is there a -1 polynomial-time method when + = O(n ) over Fp ? Finally, can the lower bound on p in Theorem 4.1 References be lowered? [1] M. Ajtai, R. Kumar and D. Sivakumar, A sieve alIt is easy to see that our method can also be applied gorithm for the shortest lattice vector problem, Proc. to interpolating linear recurrence sequences instead of 33rd ACM Symp. on Theory of Comput., ACM, 2001, polynomials, which satisfy a given linear recurrence 601­610. relation [2] D. Boneh and R. Venkatesan, Hardness of computn+1 i ing the most significant bits of secret keys in Diffie­ ci u(x + i) = 0. =0 The cost of the corresponding algorithm depends on the size of the coefficients in the above relation. To justify the algorithm one can use bounds on the number of Hel lman and related schemes, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 1109 (1996), 129­142. [3] , Rounding in lattices and its cryptographic applications, Proc. 8th Annual ACM-SIAM Symp. on Discr. Algorithms, SIAM, 1997, 675­681. 1136 [4] G. Everest, A. J. van der Poorten, I. E. Shparlinski and T. B. Ward, Recurrence sequences, AMS Surveys and Monographs, 2003. [5] J.-H. Evertse and H. P. Schlickewei The absolute subspace theorem and linear equations with unknowns from a multiplicative group, Number Theory in Progress, Vol. 1, de Gruyter, Berlin, 1999, 121­142. [6] M. Gr¨tschel, L. Lov´sz and A. Schrijver, Geometric o a algorithms and combinatorial optimization, SpringerVerlag, Berlin, 1993. [7] V. Guruswami and M. Sudan, Improved decoding of Reed-Solomon codes and algebraic-geometric codes, IEEE Trans. Inform. Theory, 45 (1999), 1757­1767. [8] S. V. Konyagin, On the number of solutions of an univariate congruence of nth degree, Matem. Sbornik, 102 (1979), 171­187 (in Russian). [9] A. K. Lenstra, H. W. Lenstra and L. Lov´sz, Factoring a polynomials with rational coefficients, Mathematische Annalen, 261 (1982), 515­534. [10] P. Q. Nguyen and J. Stern, Lattice reduction in cryptology: An update, Lect. Notes in Comp. Sci., SpringerVerlag, Berlin, 1838 (2000), 85­112. [11] , The two faces of lattices in cryptology, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 2146 (2001), 146­180. [12] A. J. van der Poorten and H. P. Schlickewei, Zeros of recurrence sequences, Bull. Austral. Math. Soc., 44 (1991), 215­223. [13] H. P. Schlickewei, W. M. Schmidt and M. Waldschmidt, Zeros of linear recurrence sequences, Manuscripta Math., 98 (1999), 225­241. [14] W. M. Schmidt, Zeros of linear recurrence sequences, Publ. Math. Debrecen, 56 (2000), 609­630. [15] C. P. Schnorr, A hierarchy of polynomial lattice basis reduction algorithms, Theor. Comp. Sci., 53 (1987), 201­224. [16] I. E. Shparlinski, Sparse polynomial approximation in finite fields, Proc. 33rd ACM Symp. on Theory of Comput., ACM, 2001, 209­215. [17] ,Playing "Hide-and-Seek" in finite fields: Hidden number problem and its applications, Proc. 7th Spanish Meeting on Cryptology and Information Security, Vol.1, Univ. of Oviedo, 2002, 49­72. [18] , Exponential sums and lattice reduction: Applications to cryptography, Finite Fields with Applications to Coding Theory, Cryptography and Related Areas, Springer-Verlag, Berlin, 2002, 286­298. [19] , Cryptographic applications of analytic number theory, Birkhauser, 2003. 1137