1
$\begingroup$

In Niederreiter cryptosystem, we require the message to be a vector of weight $t$ in $F_q^n$ in encryption, assume $t$ is the error-correction ability of the code. But what is the mapping? One possible way is mapping the message of length $k$ to a codeword of a constant weight $t$ linear code, e.g., $[n,k]_q$ code. In this way, the message space is $q^k$. Is there other better way to do that, e.g., the larger message space?

$\endgroup$

1 Answer 1

1
$\begingroup$

Fun question! We can, in fact, efficiently realise the maximum message space of size $(q-1)^t({n\atop t})$.

Let us begin with the case $q=2$. We want to generate a bit string of length $n$ and Hamming weight exactly $t$. There are $C:=({n\atop t})$ such strings and we would like to map an integer message from the interval $[0,C-1]$ to this set bijectively. Combinatorially speaking, the set of bit strings correspond to combinations (specifically $t$-combinations of the integers 0 through $n-1$). We can bijectively rewrite our string as a strictly decreasing sequence of $t$ values $n-1\ge c_t>c_{t-1}>\ldots>c_1\ge 0$ by writing down the indices of the location of the 1s.

Now, an elegant theorem of mathematics that Knuth attributes to the 19th century mathematician Ernesto Pascal says that every number $N$ can be represented in the combinatorial number system $$N=\left({c_t\atop t}\right)+\cdots+\left({c_1\atop 1}\right)$$ and this ordering steps through combinations is lexicographic order (for our purposes, the first $({n\atop t})$ entries list weight $t$ strings of length $n$). Therefore if we have an integer $N\in [0,C-1]$ we can use a greedy algorithm to recover the $N$th weight $t$ binary string given by the combinatorial number system. Here's some pseudo-code:

Initialise i:=n-1, j:=t, remainder=N
while i>=0
   if Binomial(i,j) > remainder
      set bit i of the string to 0
   else
      set bit i of the string to 1
         j--
         remainder -= Binomial(i,j)
   i--

The reverse map is straightforward.

For example, with $n=10$, $t=3$ there are 120 possible combinations, let us find the 17th (counting 0-up). We first find the smallest tetrahedral number not greater than 17; this is $({5\atop 3})=10$; we mark the 5th spot and have 7 left over. We now find the smallest triangular number not greater than 7; this is $({4\atop 2})=6$; we mark the 4th spot and have 1 left over. We now find the smallest number not greater than 1; this $({1\atop 1})=1$; we mark the 1st spot and have nothing left over. Our string is 0000110010. If we receive the string we compute $({5\atop 3})+({4\atop 2})+({1\atop 1})=10+6+1=17$.

For more general alphabets, we can use the above process to generate the error locations and then choose from the $q-1$ possible error values for each location. Concretely let $M=C(q-1)^t$ be the size of our message space. Given a message $m\in[0,M-1]$ we let $N=[m/(q-1)^t]$ so that $N\in[0,C-1]$ and generate a list of locations as above. We then let $B=m\mod{(q-1)^t}$ and write $B$ as a $t$-digit number in base $(q-1)$ (allowing leading zeroes) and assign the values digit+1 to each location. Again the reverse map is straightforward.

For example suppose we have a decimal alphabet and consider strings of length 10 with 3 errors. There are 120*729=87480 possible messages; let us find the 12707th. We find $N=[12707/729]=17$ and so generate the same bits string as above. We find $B=12707\mod{729}=314$ which is 378 in base 9. Our message converts to the error string 0000480090. Again if we receive this string, we pull out the non-zero digits in order and subtract one from each to give the base-9 number 378 so that $B=314$ likewise we know that $N=17$ from the error locations and can compute $m=729N+B=12707$.

Chapter 7.2.1.3 "Generating all Combinations" of Donald Knuth's definitive "The Art of Computer Programming" is an excellent, comprehensive (albeit distracting) account of other algorithms for generating combinations.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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