Niederreiter cryptosystem

Signature scheme

Courtois, Finiasz and Sendrier showed how the Niederreiter cryptosystem can be used to derive a signature scheme .

1. Calculate ${\displaystyle s=h(d)}$, where ${\displaystyle h}$ is a Hash Function and ${\displaystyle d}$ is the signed document.
2. Calculate ${\displaystyle s_i=h(s|i),i=0,1,2,\dots }$, where ${\displaystyle |}$ denotes concatenation.
3. Attempt to decrypt ${\displaystyle s_i}$ until the smallest value of ${\displaystyle i}$ (denoted further as ${\displaystyle i_0}$) for which ${\displaystyle s_i}$ is decryptable is found.
4. Use the trapdoor function to compute such ${\displaystyle z}$ that ${\displaystyle H{z}^T=s_{i_0}}$, where ${\displaystyle H}$ is the public key.
5. Compute the index ${\displaystyle I_z}$ of ${\displaystyle z}$ in the space of words of weight 9.
6. Use ${\displaystyle \left[I_z|z\right]}$ as the signature.

The Verification algorithm is much simpler:

1. Recover ${\displaystyle z}$ from index ${\displaystyle I_z}$.
2. Compute ${\displaystyle s_1=H{z}^T}$ with the public key ${\displaystyle H}$.
3. Compute ${\displaystyle s_2=h(h(d)|i_0)}$.
4. Compare ${\displaystyle s_1}$ and ${\displaystyle s_2}$. If they are the same the signature is valid.

The index ${\displaystyle I_z}$ of ${\displaystyle z}$ can be derived using the formula below, where ${\displaystyle i_1<\cdots <i_9}$ denote the positions of non-zero bits of ${\displaystyle z}$.$${\displaystyle I_z=1+\sum _{n=1}^9(\genfrac{}{}{0ex}{}{i_n}{n})}$$The number of bits necessary to store ${\displaystyle i_0}$ is not reducible. On average it will be ${\displaystyle lo{g}_2(9!)\approx 18.4}$ bits long. Combined with the average ${\displaystyle 125.5}$ bits necessary to store ${\displaystyle I_z}$, the signature will on average be ${\displaystyle 125.5+18.4\approx 144}$ bits long.