為什麼lattice KEX不需要高精度採樣？
我正在閱讀 NewHope論文，我看到他們使用的是二項分佈，而不是 BCNS 使用的離散高斯分佈。我還記得在某處聽說格密鑰交換不需要非常高精度的採樣，而簽名方案需要高精度採樣。為什麼會有這種區別？使用的採樣算法如何影響這些方案的安全性？
高斯在密鑰交換和數字簽名中的使用方式和目的是完全不同的。
在公鑰加密（和密鑰交換）中，當 A 是隨機矩陣（在某個環上）並且 (s,e) 是同一環上的小係數向量時，我們需要 (A,As+e) 的計算不可區分性。為了根據最壞情況的困難問題獲得最嚴格的安全性降低，s 和 e 應該是高斯的，這就是為什麼有時（錯誤地）認為 s 和 e 應該是高斯的安全性。實際上，它們不需要是 - 當 s 和 e 是“更簡單的樣本”分佈（例如均勻或二項式）時，可區分性問題在實踐中似乎同樣困難。
在數字簽名中（使用 Fiat-Shamir 變換），簽名計算為 z=Sc+y，其中 S 是小係數的秘密矩陣，c 是挑戰向量（具有非常小的係數），y 是某個向量在簽名時選擇。為了安全起見，需要 z 具有較小的係數並且獨立於密鑰 S。要使 z 具有較小的係數，y 需要具有較小的係數。為了使 z 獨立於 S，我們需要使用拒絕抽樣，以便 y 的分佈“掩蓋”了 Sc 的偏移。如果我們在這裡不使用足夠高的精度，那麼我們可能無法得到在統計上獨立於 S 的 z 的分佈，這對於安全性來說將是災難性的。
在最近的一些論文中，表明獲得盡可能短的 z 的方法需要將 y 設為離散高斯，因此您需要能夠以高精度對離散高斯進行採樣。需要說明的是，您也可以通過簡單的均勻分佈來創建數字簽名，但是會稍長一些。
對於散列和簽名簽名，這又是與 Fiat-Shamir 相同的高級想法。您要確保簽名獨立於密鑰。我們知道如何創建此類簽名的最有效方法是讓它們來自離散高斯分佈。