請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/85812完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 陳君明(Jiun-Ming Chen) | |
| dc.contributor.author | Ho-Chien Chen | en |
| dc.contributor.author | 陳和謙 | zh_TW |
| dc.date.accessioned | 2023-03-19T23:25:09Z | - |
| dc.date.copyright | 2022-04-26 | |
| dc.date.issued | 2022 | |
| dc.date.submitted | 2022-03-24 | |
| dc.identifier.citation | 1. D'Anvers, J.-P., Karmakar, A., Sinha Roy, S., Vercauteren, F.: Saber: Module-LWR based key exchange, CPA-secure encryption and CCA-secure kem. Progress in Cryptology – AFRICACRYPT 2018. 282–305 (2018). 2. Basso, A., Bermudo Mera, J.M., D' Anvers, J.-P., Karmakar, A., Sinha Roy, S., Van Beirendonck, M., Vercauteren, F.: SABER: Mod-LWR based KEM (Round 3 Submission), (2020). 3. Cusick, T.W., Stanica, P.: Fourier analysis of boolean functions. Cryptographic Boolean Functions and Applications. 7–29 (2017). 4. Jin, Z., Zhao, Y.: Optimal key consensus in presence of noise, https://arxiv.org/abs/1611.06150. 5. Chung, C.-M.M., Hwang, V., Kannwischer, M.J., Seiler, G., Shih, C.-J., Yang, B.-Y.: NTT multiplication for NTT-unfriendly rings. IACR Transactions on Cryptographic Hardware and Embedded Systems. 159–188 (2021). 6. Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J.M., Schwabe, P., Seiler, G., Stehle, D.: Crystals - Kyber: A CCA-secure module-lattice-based KEM. 2018 IEEE European Symposium on Security and Privacy (EuroS\&P). (2018). | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/85812 | - |
| dc.description.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的比較。 | zh_TW |
| dc.description.abstract | 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. | en |
| dc.description.provenance | Made available in DSpace on 2023-03-19T23:25:09Z (GMT). No. of bitstreams: 1 U0001-2303202219252300.pdf: 559326 bytes, checksum: 4b2ac4e2bcced57a871fa1feca645591 (MD5) Previous issue date: 2022 | en |
| dc.description.tableofcontents | 1 Introduction 1 2 Preliminaries 3 2.1 Lattice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 Rounding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.3 Computational hardness assumptions . . . . . . . . . . . . . . . . . . . . . . 5 2.4 Number-theoretic transform . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3 Saber 7 3.1 Introduction to Saber . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.2 Preliminaries and notations . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.3 Parameters and constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.4 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.4.1 Key generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.4.2 Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.4.3 Decryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.4.4 Parameter sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4 Ciphertext Distribution and Error Rate of Saber 12 4.1 Algebraic structure of the rings used in Saber . . . . . . . . . . . . . . . . . 12 4.2 Ciphertext distribution of Saber . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.3 Error rate of Saber . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.3.1 Some important lemmas . . . . . . . . . . . . . . . . . . . . . . . . 22 4.3.2 Flaw of the original estimation . . . . . . . . . . . . . . . . . . . . . 24 4.3.3 A correct bound of the error rate of Saber . . . . . . . . . . . . . . . 27 5 NTT-friendly Variance of Saber 37 5.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5.2 Number theoretic transform (NTT) . . . . . . . . . . . . . . . . . . . . . . . 37 5.3 Notations and parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 5.4 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5.4.1 Key generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5.4.2 Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.4.3 Decryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.4.4 Parameter sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 ii 5.5 Ciphertext distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.6 Error rate estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 5.7 Comparison with the original Saber . . . . . . . . . . . . . . . . . . . . . . 47 5.8 Comparison with Kyber . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 6 Conclusion 50 A Code to Estimate the Error Rates of Saber 52 B Code to Estimate the Error Rates of NTT-Friendly Saber 56 | |
| dc.language.iso | en | |
| dc.subject | 快速數論變換(NTT) | zh_TW |
| dc.subject | 後量子密碼學 | zh_TW |
| dc.subject | Saber | zh_TW |
| dc.subject | learning with rounding | zh_TW |
| dc.subject | post-quantum cryptography | en |
| dc.subject | number theoretic transform (NTT) | en |
| dc.subject | learning with rounding | en |
| dc.subject | Saber | en |
| dc.title | SABER的理論研究與推廣 | zh_TW |
| dc.title | Theoretical Survey of Saber and Its Generalizations | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 110-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 陳榮傑(Rong-Jaye Chen),楊柏因(Bo-Yin Yang),謝致仁(Jyh-Ren Shieh),陳君朋(Jiun-Peng Chen) | |
| dc.subject.keyword | 後量子密碼學,Saber,learning with rounding,快速數論變換(NTT), | zh_TW |
| dc.subject.keyword | post-quantum cryptography,Saber,learning with rounding,number theoretic transform (NTT), | en |
| dc.relation.page | 60 | |
| dc.identifier.doi | 10.6342/NTU202200657 | |
| dc.rights.note | 同意授權(全球公開) | |
| dc.date.accepted | 2022-03-25 | |
| dc.contributor.author-college | 理學院 | zh_TW |
| dc.contributor.author-dept | 數學研究所 | zh_TW |
| dc.date.embargo-lift | 2022-04-26 | - |
| 顯示於系所單位： | 數學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| U0001-2303202219252300.pdf | 546.22 kB | Adobe PDF | 檢視/開啟 |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。