A new technique to lower-bound the minimum distance of certain types of quasi-cyclic codes with large dimension by reducing the problem to lower-bounding the minimum distance of a few significantly smaller codes has been developed. These codes have the property that they have extremely efficient software encoders. Using this technique, it is proved that a code which is similar to the SHA-1 (Secure Hash Algorithm, to be explained shortly) message expansion code has minimum distance 82, and that too in just the last 64 of the 80 expanded words. In fact, the proposed code has much greater distance than that of SHA-1 code, which makes our proposed hashing scheme robust against cryptographic attacks. The technique is further used to find the minimum weight of the SHA-1 code itself (25 in last 60 words), which was an open problem. Estimating minimum distance of a code given by its parity-check matrix is well known to be a hard problem. Our technique is expected to be helpful in estimating minimum distance of similar codes as well as in designing future practical cryptographic hash functions.

We define a new family of error-correcting codes based on algebraic curves over finite fields, and develop efficient list decoding algorithms for them. Our codes extend the class of algebraic-geometric (AG) codes via a (non-obvious) generalization of the approach in the recent breakthrough work of F. Parvaresh and A. Vardy (2005). Our work shows that the PV framework applies to fairly general settings by elucidating the key algebraic concepts underlying it. Also, more importantly, AG codes of arbitrary block length exist over fixed alphabets Sigma, thus enabling us to establish new trade-offs between the list decoding radius and rate over a bounded alphabet size. Similar to algorithms for AG codes from V. Guruswami and M. Sudan (1999, 2001), our encoding/decoding algorithms run in polynomial time assuming a natural polynomial-size representation of the code. For codes based on a specific "optimal" algebraic curve, we also present an expected polynomial time algorithm to construct the requisite representation. This in turn fills an important void in the literature by presenting an efficient construction of the representation often assumed in the list decoding algorithms for AG codes

We present an efficient randomized algorithm to test if a given function f : F/sub p/ /sup n/ /spl rarr/ F/sub p/ (where p is a prime) is a low-degree polynomial. This gives a local test for generalized Reed-Muller codes over prime fields. For a given integer t and a given real /spl epsiv/ > 0, the algorithm queries f at 1//spl epsiv/ + t/spl middot/p/sup 2r/p-1+O(1)/ points to determine whether f can be described by a polynomial of degree at most t. If f is indeed a polynomial of degree at most t, our algorithm always accepts, and if f has a relative distance at least e from every degree t polynomial, then our algorithm rejects f with probability at least 1/2. Our result is almost optimal since any such algorithm must query f on at least /spl Omega/(1//spl epsiv/ + p/sup r+1/p-1/) points.