Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $C$ be a code over the finite field $GF(2)$ with generator matrix $G$ and parity matrix $H$. Let $e+C=C'$ be a coset of code $C$. Let $S$ be a non-singular matrix and $H'=H\times S$. Finally, let $C''\subset C'$. Is there any efficient way of finding any other element of the coset $C'$ by only using $C''$ and $H'$ (with appropriate parameters for the code $C$)?

share|improve this question
Do you want some structure on $C''$? It could be empty. Anyway, finding another element of the coset is equivalent to finding a non-zero vector in $\mathrm{Ker}\ G = \mathrm{Img}\ H = \mathrm{Img}\ H\times S$, which is trivial. – David Cash Jan 24 '14 at 20:31
@DavidCash Why finding another element of the coset is equivalent to finding ...?. Recall that $e$ is an fixed element. Here an example in SAGE H = matrix(GF(2),[[1,0,0,0,1,1,0],[0,1,0,0,1,0,1],[0,0,1,0,0,1,1],[0,0,0,1,1,1,1]]); Krnl = H.right_kernel(); G = Krnl.basis_matrix(); S = matrix(GF(2),[[1,1,0,1],[1,0,0,1],[0,1,1,1],[1,1,0,0]]) SH= SH m=vector(GF(2),[0,0,1]); m1=vector(GF(2),[1,0,1,1]); e=vector(GF(2),[0,1,0,0,0,0,0]) print 'mG+e=',(mG+e),'sindrome',H*((mG+e)) print 'm1*SH=',(m1*SH),'sindrome',H*((m1*SH)) – juaninf Jan 24 '14 at 23:50
in the last example (SAGE) m1 is a non-zero vetor in Ker G and that not belong to the same coset $C+e$. – juaninf Jan 24 '14 at 23:53
I meant in $\mathrm{Img}\ G$ (typo). – David Cash Jan 25 '14 at 3:12
@DavidCash I understand, – juaninf Jan 30 '14 at 13:57

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.