# Proof that Niederreiter Cryptosystem is correct

I read about Niederreiter Cryptosystem. I understood the Key Generator, encryption and decryption of the cryptosystem, but if I want to prove that is a correct cryptosystem, what should I do?

• Correctness of encryption scheme is just a simple property which means that after applying encryption algorithm, and then decryption, you will receive the original text. It's very simple to verify if you understand those algorithms. Ok, maybe you're interesting in security of the scheme? It's way more difficult to prove – Mikhail Koipish Jan 31 '20 at 16:01

## 1 Answer

To prove the correctness of an encryption scheme (not necessarily Niederreiter), you have to prove that for a honestly generated key pair, any honestly generated ciphertext decrypts correctly.

Formally, let $$(pk, sk) \leftarrow KeyGen(1^\lambda)$$ be the public and private key pair, and let $$m$$ be uniformally random in the (finite) plaintext space, and denote by $$c \leftarrow Encrypt(pk, m)$$ an encryption of message $$m$$ (pseudo-random in the ciphertext space) under the public key $$pk$$. Then you have to show that $$Decrypt(sk, c) == m$$ with overwhelming probability, meaning that either the decryption always succeeds if all steps were executed honestly, or it fails with probability negligible in the security parameter $$\lambda$$.

For instance, you prove the correctness of textbook RSA by showing that $$(m^e)^d == m \bmod n$$ for honestly generated $$n=pq$$, $$\varphi(n)=(p-1)(q-1)$$, $$e$$ coprime with $$\varphi(n)$$ and $$d = e^{-1} \bmod \varphi(n)$$.

• $$pk : (H_{pub}, t)$$ $$sk : (P, D_{G}, M)$$ $$H_{pub}=M\cdot H\cdot P$$ The message is: $$e\in \mathbb{F}^{n}_{2}$$. $$Encrypt(H^{pub},t,e^{T}) = c$$ $$Decrypt(P,D_{G},M,c)=H^{pub}\cdot e^{T}\overset{H^{pub}=M\cdot H\cdot P}{\rightarrow}M\cdot H\cdot P\cdot e^{T}\overset{M^{-1}}{\rightarrow}H\cdot P\cdot e^{T}\overset{D_{G}}{\rightarrow}P\cdot e^{T}\overset{P^{-1}}{\rightarrow}e^{T}\rightarrow e$$ Is that correct? – CodingGuy Jan 9 '20 at 19:23
• Almost, there is an important property that you use to claim that the result of $D_G$ applied to $HPe^T$ will be $Pe^T$, and that I don't see in your comment, which is that $e$ has weight at most $t$. Your notation for the message is a bit confusing since you write that "the message is $e\in \mathbb{F}_2^n$", in particular there is no restriction over $e$'s weigth, and then you use that $e$ has weight at most $t$. Otherwise, I think that you got it. Also notice that most of the time, the matrix $M$ is denoted $S$ (and referred to as a "scrambling" matrix). – jchd Jan 10 '20 at 9:49
• Thanks a lot! I forgot to mention the weight, that' s true – CodingGuy Jan 14 '20 at 2:27