I am reading the paper The Steganographic File System by Ross Anderson, Roger Needham, and Adi Shamir. On page 4, paragraph 2, the authors write:
Finally, we use the Gram-Schmidt method to orthonormalise all the vectors from $i$ onwards by subtracting from the candidate $K_i$ all its components along later $K_j$ which the user knows by the chaining property of the $p_j$’s.
This simply means that the authors use the Gram-Schmidt algorithm with the ground field GF$(2)$, and from the context, each of the original vectors the algorithm is applied to has norm $1$. However, in this case the algorithm produces a basis which is not necessarily orthonormal, not even orthogonal. Am I right? Is this a serious flaw?
The answer below was posted before the piece of information about all the participating vectors get tagged with random bits to make sure their weights are odd.
IMHO a more serious problem with using Gram-Schmidt over $GF(2)$ is that Gram-Schmidt may call for division by zero! This is because in the projection formula $$ y\mapsto y-\frac{(y,x)}{(x,x)}x $$ the denominator $(x,x)$ vanishes when $x$ is orthogonal to itself.
For example consider the following subspace of $GF(2)^3$: $$ V=\{(a,b,c)\in GF(2)^3\mid a+b+c=0\}. $$ You will quickly realize that every vector of $V$ is orthogonal to itself. Have fun trying to Gram-Schmidt orthogonalize e.g. the basis $v_1=(1,1,0)$, $v_2=(1,0,1)$ of $V$ :-)