Category Archives: Hacking
IBM Watson outperforms humans at Jeopardy
List Decoding of Algebraic Geometric Codes
PhD of University Paris VI
(now UPMC Sorbonne University)
Research carried out, between 1997 and 2001, at Project CODES (now SECRET) at l’INRIA, under the supervision of Pascale Charpin, Research Director at INRIA, Project CODES Director, and of Daniel Augot, Researcher at INRIA.
For a general public introduction to coding theory, you may read my article L’algèbre qui corrige les erreurs (in French). A description of my work for scientists who are not specialists of coding theory is available here
Abstract: Algebraicgeometric codes were introduced by Goppa in 1981 and are built using algebraic curves over finite fields. In 1982, Tsfasman, Vladuts and Zink showed that one could build a family of such codes that beats the GilbertVarshamov bound. In 1996, Sudan proposed a list decoding algorithm for ReedSolomon codes. This algorithm was adapted in 1997 to onepoint strongly algebraicgeometric codes by Shokrollahi and Wasserman, then improved by Guruswami and Sudan.
In this thesis, we extend these methods to all algebraicgeometric codes and their subfield subcodes, and to a generalized Hamming distance that allows to reformulate algebraically the soft decision decoding problem and to propose a maximum likelihood list decoding algorithm over any discrete memoryless channel. We illustrate these new results with an implementation in the computer algebra system Magma.
NB: there are still a few errors I never had the courage to correct.
2000 Mathematics Subject Classification: 11T71 Algebraic coding theory; cryptography; 94B35 Decoding; 94B27 Geometric methods (including applications of algebraic geometry) [See also 11T71, 14G50]; 11Yxx Computational number theory [See also 1104]; 14Qxx Computational aspects in algebraic geometry [See also 12Y05, 13Pxx, 68W30]; 68W30 Symbolic computation and algebraic computation [See also 11Yxx, 12Y05, 13Pxx, 14Qxx, 16Z05, 1708, 33F10].
Keywords: List decoding; maximumlikelihood softdecision decoding; algebraicgeometric codes; ReedSolomon codes; subfield subcodes; GuruswamiSudan’s algorithm; effective algebraic geometry; algorithmic number theory; roots of polynomials on function fields of curves over a finite field; computer algebra; Magma implementation.
Defense: This thesis as awarded summa cum laude after a defense that took place on Tuesday Decembrer 18th, 2001 at 14:00, Jussieu Campus, 4, place Jussieu, 75005 Paris, France. The jury was consisting of:
 Daniel Lazard: Professor (Paris VI), President of the Jury
 Pascale Charpin: Research Director (INRIA), PhD Advisor
 Daniel Augot: Researcher (INRIA), PhD Coadvisor
 Claude Carlet: Professor (Caen), Referee
 Tom Høholdt: Professor (DTU, Denmark), Referee
 François Morain: Professeur (Polytechnique), Examiner
“Non technical” description for scientists who are not specialists in coding theory
Context
Coding Theory’s main goal is to improve mathematically the reliability of telecommunications. Its foundations were built in the middle of the 20th century with the work of Claude Shannon, Richard Hamming, and others.
The introduction of algebraicgeometric tools by Goppa allowed him to build in 1981 some codes, naturally called “algebraicgeometric”, from curves over finite fields. These codes beneficiate from the powerful RiemannRoch Theory that allows, in particular, to estimate the fundamental parameters of such codes that are their minimum distance and their dimension.
In 1982, Michael Tsfasman, Serge Vladuts and Thomas Zink could exhibit a family of explicit algebraicgeometric codes that were better than all known codes at that time and whose performance was beating the GilbertVarshamov bound that was (wrongly) conjectured to be optimal.
In 1996, Madhu Sudan proposed a method for the list decoding of ReedSolomon codes, that was adapted in 1997 by Amin Shokrollahi and Hal Wasserman to onepoint strongly algebraicgeometric codes, and improved again by Venkatesan Guruswami and Sudan.
Contributions of this thesis
 The generalization of GuruswamiSudan’s algorithm to all algebraicgeometric codes
 The description of a list decoding algorithm for a distance that generalizes the Hamming distance and that allows an algebraic soft decision decoding that maximizes the likelihood on any discrete memoryless channel
 Some refinements of existence conditions for auxilliary polynomials that are used in list decoding algorithms
 An evaluation that takes into account the data structures and algorithmic primitives that are required to use the geometric structure of codes (curve, normalized curve, genus, divisors, RiemannRoch spaces) for their list decoding
 An implementation in Magma of a desingularization algorithm of a plane model of a curve and of an improved version of the BrillNoether algorithm. This allows in particular, the computation of padic series of fonctions in any closed point p of the curve and its genus (joint work with Pawel Wocjan)
 The implementation in Magma of a communication channels library that allows to test our soft decision algorithm
 The adaptation of NewtonPuiseux’s algorithm for finding roots of polynomials over function fields, that provides one of the primitives used in the list decoding algorithm
 The proof of a combinatoric property of lowrate codes that allows to use, in that case, NewtonHensel’s algorithm, which dramatically reduces the complexity of their list decoding to essentially quadratic time (joint work with Daniel Augot)
 The proof that one can precompute sufficient information for not having to use effective RiemannRoch Theory during list decoding
 A complete implementation in Magma of the above methods, in particular of our generalized list decoding algorithm and its soft decision version
Curves for Coding and Cryptography
In this elementary and introductory talk at INRIA‘s Junior Colloquium, we present the usual problems that occur in the theory of errorcorrecting codes and of cryptography. We show how the use of effective algebraic geometry over finite fields can help to solve some of the questions that arise in these disciplines.
Building AlgebraicGeometric Codes with Magma
I this talk given at the 3rd European Congress of Mathematics (3ECM, Barcelona, Spain, July 2000), we illustrate how the computer algebra system MAGMA can be used for the implementation of sophisticated algorithms requiring many primitives in various branches of effective mathematics like finite fields, algebraic geometry or errorcorrecting codes. We give the example of the construction of Goppa’s algebraicgeometric codes in this system.
This is a joint work with Pawel WOCJAN.
A Hensel Lifting for List Decoding
This article describes an algorithmic improvement on Sudan’s algorithm for ReedSolomon codes and its generalization to algebraicgeometric codes by Shokrollahi and Wasserman. Instead of completely factoring the interpolation polynomial over the function field of the curve, we compute fast sufficiently many coefficients of the padic expansion of the functions corresponding to codewords we are looking for, using Newton’s method.
This is a joint work with Daniel Augot, published in IEEE Transactions on Information Theory, vol. 46, n°7, pp. 26052614, 2000. A preliminary version was available in the INRIA Research Report, n° 3532, November 1998.
ReedSolomon coding and decoding in one page
Aesthetic Hacking
A few aesthacking examples
A RPN Calculator in many languages by Frederik
A RPN calculator in 30 languages:, Ada, Assembler (MC68000), AWK, Bash, Brainfuck, C, C#, C++, Chef, Common Lisp, Emacs Lisp, Erlang, Fortran, Haskell, Io, Java, JavaScript, K, O’Caml, Pascal, Perl, PHP, PostScript, Python, Ruby, Scala, Scheme, Sed, Standard ML, TCL.
Polyglot program, by Kevin Bungard, Peter Lisle, and Chris Tham
Can be compiled in the 7 following langages: ANSI COBOL, ISO Pascal, ANSI Fortran, ANSI C, PostScript, Bourne shell script, and is a binary for 8086 machine language. A few examples:
% cp polyglot polyglot.c % gcc polyglot.c polyglot.c: 1: warning: data definition has no type or storage class % ./a.out hello polyglots % cp polyglot polyglot.sh % chmod 755 polyglot.sh % ./polyglot.sh hello polyglots ...
C palindrome, unknown author and date
A C palindrome program.
Ultimately cyclic ASCII art C program
To see the behaviour of this wonderful program that combines the art of ASCII images and of C programming, type the following lines in a shell:
% gcc dhyang.c % ./a.out > 1.c % cat 1.c % gcc 1.c % ./a.out > 2.c % cat 2.c % gcc 2.c % ./a.out > 3.c % cat 3.c % gcc 3.c % ./a.out > 4.c % diff 4.c 1.c
Programming Langages & Formats
 Ada
 Actionscript: Flex, the opensource actionscript compiler
 Assembler
 Bash: Guide avancé d’écriture des scripts Bash
 C specs
 Character coding and fonts
 GNU emacs
 GNUplot
 Icons: PNG factory.
 Postscript & PDF
 TCPIP
 TeX & Metafont

A Zip file which contains an example of Metafont file (
lpeuro.mf
), a filelpeuro.sty
to display the euro symbol in LaTeX documents andlpeuro.pdf
(compiled fromlpeuro.tex
, both included in the .zip archive) which describes how to use the package.  TeX references and examples by David Bausum
 pstricks by Timothy van Zandt

 Unix
 WWW
 Reverse engineering
 Reverse Engineering: Memory Analysis, nologin.org (2003)
 Reconstructing binaries to C for beginners, DTORS Security Research
 Reverse Engineering Hostile Code, Joseph Stewart, GCIH
IT Architecture and Operating Systems
Sorry, this entry is only available in Français.
Game Theory and Strategy
Sorry, this entry is only available in Français.