2
$\begingroup$

I can't understand how Niederreiter cryptosystem works. If $c=mH^{'T}$ than why we cannot compute $m$ directly by multiplying $c$ with the $(H^{'T})^{-1}$? Can you give me an example of a "fast decoding algorithm"?

Thank you!

$\endgroup$
2
  • $\begingroup$ did you consider the noise removal by $D$? $\endgroup$
    – kelalaka
    Feb 8, 2019 at 11:43
  • $\begingroup$ What noise? That's confuses me. In the McEliece cryptosystem we add some error $e$ but in all Niederreiter documentations I didn't see any error adding to the plaintext message $\endgroup$
    – mip
    Feb 8, 2019 at 11:46

2 Answers 2

1
$\begingroup$

In the Niederreiter system, the plaintext is mapped to some error vector of weight $t$, where the code correction capability is $d=2t+1.$

With the trapdoor information (permutation) this can be decoded by the legitimate receiver by syndrome decoding.

Without the trapdoor information, this is equivalent to decoding a random vector, which is hard, as in the McEliece cryptosystem.

$\endgroup$
6
  • $\begingroup$ Is $2t+1$ excessive? $\endgroup$
    – kelalaka
    Feb 9, 2019 at 15:33
  • $\begingroup$ It is always guaranteed that the matrix H' doesn't has an inverse? $\endgroup$
    – mip
    Feb 10, 2019 at 6:44
  • 1
    $\begingroup$ @kelalaka If you took $d=t+k+1$ you might be unlucky and the actual codeword might only be Hamming distance $k+1$ away which can be found with $O(2^{k+1})$ effort. $\endgroup$
    – kodlu
    Feb 10, 2019 at 20:46
  • $\begingroup$ $H'$ is rectangular, so has no inverse. $\endgroup$
    – kodlu
    Feb 10, 2019 at 20:48
  • $\begingroup$ Can be uniquely and correctly found? $\endgroup$
    – kelalaka
    Feb 10, 2019 at 20:51
0
$\begingroup$

Since the parity check matrix H' is not squared (it has dimensions $n-k \times n$), one can not ouput the message $m$ from the ciphertext $c$.

Nevertheless, there is an attack named Lee-Brickell, which defines the security McEliece, but was later found that can also be adapted to Niederreiter, showcasing the equivalence in security of both cryptosystems. The Lee-Brickell attack is based on extracting a full rank submatrix $H_{n-k} \in \mathbb{F}_2^{n-k \times n-k} $ which can be inversed so that the message is find randomly in a much smaller configuration space in $\mathbb{F}_2^{k}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.