Dual BCH codes of design distance $d$
(I'm not an expert in this subject, but here's my understanding.)

The BCH code of code length $n=2^m-1$ and designed distance $2t+1$ is specified in terms of its generator polynomial.  Fix $\alpha$ to be a primitive element of $GF(2^m)$.  Then, $g$ is the polynomial of smallest degree with coefficients in $GF(2)$ which has its roots $\alpha, \alpha^2,\alpha^3,\dots,\alpha^{2t}$.  (The codewords are then given by all multiples of $g$ of degree at most $n-1$; see the wikipedia page for polynomial codes).  The designed distance is a lower bound on the distance of the code.

The dual BCH code of design distance $2t+1$ is just the dual of the BCH code in the usual sense, the set of vectors orthogonal to the codewords of the BCH code of design distance $2t+1$.  Its generator polynomial is given by $(X^n+1)/g(X)$.  I believe the matrix in the Ailon-Liberty paper has the codewords as its rows.

Here are some notes which describe the BCH code construction: http://www.uotiq.org/dep-eee/lectures/4th/Communication/Information%20theory/2.pdf