中心二项分布(CBD)——为什么 Kyber 不使用高斯分布
《应用后量子密码学》本章的全部代码:共 5 段,其中 5 段可在此运行。编辑任意单元格,然后点击运行。
书中的代码片段在一章之内层层相依,但 Sage Cell 内核每次只运行一个单元格,运行后不保留任何状态,因此每个单元格都会用 apqc_book 重放此前的代码。这一调用是在书中原有代码之外唯一添加的内容。
代码 1:一个简单的 Sage 实现
下面是一个非常小的 Python 版本。
代码 2:一个简单的 Sage 实现
一个快速测试如下:
代码 3:直方图视角
要真正理解 CBD,应当看一看它的直方图。
代码 4:直方图视角
该分布趋向于集中在零附近,并且越来越呈钟形。这正是它常被描述为高斯分布的离散近似的原因。
用 matplotlib 可以做一个非常简单的可视化:
代码 5:对玩具版 Kyber 代码的一个小升级
如果我们之前写过一个用简单例程生成小值的玩具版采样器,那么现在就可以把它替换为 CBD 式的采样。
例如,我们可以写成这样: