tags: crypto,lattice,HNP

勘误：Boneh-1996：MSB 定义错误

最近在学习格相关知识的时候，读到 Boneh 和 Venkatesan 1996年的论文 'Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes'，这篇论文第一次提出了 HNP(Hidden Number Problem) 。

其中提出的函数的定义似乎有一些小问题。

我找到了两个版本的论文, 内容基本一致：

https://crypto.stanford.edu/~dabo/pubs/abstracts/dhmsb.html

Let be a prime number and be its length in binary. We use to denote the unique interger a in the range satisfying . Given a prime , we define as the integer such that . For example, is either 0 or 1 depending on whether x is smaller than or greater than .

https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=c8f9439df73b065e124000e23a504d1dbe4ae79d

We will often refer to the function where . Given a prime the function is defined to be the integer such that . For example, is either 0 or 1 depending on whether x is smaller than or greater than .

其中的错误是很显然的，不可能为0，否则，与 x 的范围定义矛盾。

这是一个很小的错误，更可能是笔误，不影响全文任何结论。不过还是对我的学习造成了些许困扰。有可能 Boneh 后来发现了这个笔误，但经我简单搜索，未见公开资料说明这一问题。故在此记录，以供后来有相同困惑的同学参考。

另外，我发现 Steven Galbraith 教授的 crypto-book 'Mathematics of Public Key Cryptography' 中也支撑了我的观点, 他修正了 MSB 的定义：

https://www.math.auckland.ac.nz/~sgal018/crypto-book/ch21.pdf

Definition 21.7.1. Let be odd. Let . Define

For let be the integer such that

and define .

与 Boneh 原论文相比，这个定义要更明确、容易理解。

本文同步发表于