SABER的理論研究與推廣

Abstract

Saber是一個基於模上的learning with rounding難題假設的密碼系統，因此可以抵禦後量子電腦的攻擊。在這篇論文中，我們首先研究Saber的密文分布與解密失敗機率。藉由分析Saber中所使用的環的代數性質，我們可以證明Saber中的密文分布是均勻的，但是其所發布的解密失敗機率的估計使用了錯誤的假設。我們也會給出一個Saber解密失敗機率的上界。再來我們考慮Saber的一種名為「NTT-friendly Saber」的變體。藉由把原本2的冪次的模數改為一些特定的質數，我們可以讓NTT-friendly Saber的實作速度更快。我們接著討論NTT-friendly Saber的參數選擇、密文分布與解密失敗機率。最後，由於NTT-friendly Saber的設計理念和另一個也是大家所熟知的Kyber十分類似，我們會討論一些和Kyber的比較。

Saber is a cryptosystem based on the hardness of the module-learning with rounding problem, hence has resistance against quantum computers. In this paper, we first examine the ciphertext distribution and error rate of Saber. By some algebraic analysis of the rings used in Saber, we will see that the ciphertext distribution is uniform in Saber, while the proposed error rate estimations contain a false assumption and thus lead to questionable results. We also give an upper bound of the error rates of Saber. We then consider a variance of Saber called ”NTT-friendly Saber.” By changing the moduli from power-of-2 to some specific primes, this NTT-friendly Saber will have a faster implementation speed. We then discuss the parameters choosing, ciphertext distribution, and error rate. At last, since the design rationales are pretty similar to another known cryptosystem named Kyber, we will compare our NTT-friendly Saber and Kyber.