在Niederreiter密码体制中，如何将消息映射到权值的向量？

Question

在Niederreiter密码体制中，我们要求消息在加密中成为权值t的向量，假定t是码的纠错能力。但是地图是什么呢？一种可能的方法是将长度k的消息映射到一个恒定权重的t线性码字，例如[n,k]_q码。这样，消息空间就是q^k。还有其他更好的方法来做到这一点，例如，更大的消息空间吗？

Answer 1

有趣的问题！实际上，我们可以有效地实现(q-1)^t({n\atop t})大小的最大消息空间。

让我们从案例q=2开始。我们想要生成一个长度n和Hamming重量的位串，确切地说是t。有C:=({n\atop t})这样的字符串，我们希望将一个整数消息从间隔[0,C-1]映射到这个集合。综合而言，一组位字符串对应于组合 (特别是整数0到n-1的t-combinations )。我们可以通过写下1s位置的索引，将字符串重写为严格递减的t值序列n-1\ge c_t>c_{t-1}>\ldots>c_1\ge 0。

现在，Knuth认为19世纪数学家Ernesto的一个优雅的数学定理说，每一个数字N都可以用组合数系统 N=\left({c_t\atop t}\right)+\cdots+\left({c_1\atop 1}\right)来表示，并且这个通过组合的排序步骤是字典顺序(为了我们的目的，第一个({n\atop t})条目列出了权重t字符串的长度n)。因此，如果我们有一个整数N\in [0,C-1]，我们可以使用贪婪算法来恢复组合数系给出的N第四权t二进制串。下面是一些伪代码：

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--

相反的地图是直接的。

例如，使用n=10，t=3有120个可能的组合，让我们找到第17条(计数为0-up)。我们首先找出最小的四面体数不大于17，这是({5\atop 3})=10，我们标记第五个点，剩下7个。现在我们发现最小的三角形数不大于7；这是({4\atop 2})=6；我们标记第四个点，剩下1。我们现在发现最小的数不大于1；这个({1\atop 1})=1；我们标记第一个点，没有剩余的东西。我们的字符串是0000110010。如果我们接收到字符串，就会计算({5\atop 3})+({4\atop 2})+({1\atop 1})=10+6+1=17。

对于更一般的字母，我们可以使用上面的过程生成错误位置，然后从每个位置的q-1可能的错误值中进行选择。具体来说，让M=C(q-1)^t成为我们消息空间的大小。给出一个消息m\in[0,M-1]，我们让N=[m/(q-1)^t]这样做，以便N\in[0,C-1]和生成一个位置列表，如上面所示。然后，我们让B=m\mod{(q-1)^t}将B写成基(q-1)中的t-digit数字(允许前导零)，并将digit+1值赋给每个位置。同样，反向地图也是简单明了的。

例如，假设我们有一个十进制字母表，并考虑长度为10的字符串，其中包含3个错误。有一些120*729=87480可能的消息，让我们找到12707。我们找到了N=[12707/729]=17，因此生成了与上面相同的位字符串。我们在基9中找到了B=12707\mod{729}=314，它是378。我们的消息转换为错误字符串0000480090。同样，如果我们接收到这个字符串，我们按顺序提取出非零的数字，并从每个数字中减去一个，给出基-9数字378，这样B=314同样我们知道错误位置的N=17，并且可以计算m=729N+B=12707。

第7.2.1.3章“生成所有组合”的唐纳德·库特的权威“计算机编程艺术”是对生成组合的其他算法的一个极好的、全面的(尽管令人分心)的描述。