學術產出-Theses
Article View/Open
Publication Export
-
題名 基於同源密碼學之簽章方案相關研究
Supersingular Isogeny-Based Signatures: A survey作者 李立瑜
Lee, Li-Yu貢獻者 蔡炎龍
Tsai, Yen-lung
李立瑜
Lee, Li-Yu關鍵詞 後量子密碼學
同源密碼學
橢圓曲線
數位簽章
Post-quantum Cryptography
Isogeny Based Cryptography
elliptic curve
signature schemes日期 2023 上傳時間 1-Sep-2023 15:26:23 (UTC+8) 摘要 自2016年起，美國國家標準與技術局(NIST)提出了後量子密碼學標準化競賽，公開徵求面對量子電腦時代的公鑰加密和數位簽章系統。隨著競賽尾聲的來臨，特別是公鑰加密方案的標準化清單釋出和二次徵求數位簽章系統方案，後量子密碼學的研究重心逐漸轉向數位簽章方案的制定和安全性分析。基於同源性的密碼學，作為後量子密碼學中最新穎的分支，運用了大量的代數和橢圓曲線知識，與其他領域方案相比，極小的金鑰大小是一大優勢，且使用方法與現行的橢圓曲線密碼學相似。 本研究旨在透過基於同源性的後量子數位簽章方案的調查，從NIST PQC競賽的現況出發，介紹基礎密碼學的數學背景、同源密碼學所需的數學知識，並分析這些數位簽章方案的內容、安全性和實作效能考量，期望能促使更多人投入同源密碼學的研究。
Since 2016, the U.S. National Institute of Standards and Technology (NIST) initiated the post-quantum cryptography standardization competition, publicly soliciting public key encryption and digital signature systems for the quantum computing era. As the competition draws to a close, especially with the release of the standardization list for public key encryption schemes and the second call for digital signature system proposals, the research focus of post-quantum cryptography has gradually shifted to the formulation and security analysis of digital signature schemes. Isogeny-based cryptography, as the most novel branch in post-quantum cryptography, employs a wealth of algebraic and elliptic curve knowledge. Compared to schemes from other domains, its extremely small key size is a significant advantage, and its usage is similar to current elliptic curve cryptography. This study aims to investigate post-quantum digital signature schemes based on isogenies. Starting from the current status of the NIST PQC competition, we introduce the mathematical background of basic cryptography, the mathematical knowledge required for isogeny-based cryptography, and analyze the content, security, and implementation performance considerations of these digital signature schemes. We hope to encourage more people to delve into research in this field.參考文獻 [1] Shahla Atapoor, Karim Baghery, Daniele Cozzo, and Robi Pedersen. Csi-shark: Csi-fish with sharing-friendly keys. Cryptology ePrint Archive, Paper 2022/1189, 2022. https: //eprint.iacr.org/2022/1189. [2] Ward Beullens, Lucas Disson, Robi Pedersen, and Frederik Vercauteren. Csi-rashi: Distributed key generation for csidh. Cryptology ePrint Archive, Paper 2020/1323, 2020. https://eprint.iacr.org/2020/1323. [3] Ward Beullens, Thorsten Kleinjung, and Frederik Vercauteren. Csi-fish: Efficient isogeny based signatures through class group computations. Cryptology ePrint Archive, Paper 2019/498, 2019. https://eprint.iacr.org/2019/498. [4] Dan Boneh, Jiaxin Guan, and Mark Zhandry. A lower bound on the length of signatures based on group actions and generic isogenies. Cryptology ePrint Archive, Paper 2023/250, 2023. https://eprint.iacr.org/2023/250. [5] WouterCastryckandThomasDecru.Anefficientkeyrecoveryattackonsidh.Cryptology ePrint Archive, Paper 2022/975, 2022. https://eprint.iacr.org/2022/975. [6] Wouter Castryck, Tanja Lange, Chloe Martindale, Lorenz Panny, and Joost Renes. Csidh: An efficient post-quantum commutative group action. Cryptology ePrint Archive, Paper 2018/383, 2018. https://eprint.iacr.org/2018/383. [7] Jean-Marc Couveignes. Hard homogeneous spaces. Cryptology ePrint Archive, Paper 2006/291, 2006. https://eprint.iacr.org/2006/291. [8] Daniele Cozzo and Nigel P. smart. Sashimi: Cutting up csi-fish secret keys to produce an actively secure distributed signing protocol. Cryptology ePrint Archive, Paper 2019/1360, 2019. https://eprint.iacr.org/2019/1360. 38 [9] Thomas Decru, Lorenz Panny, and Frederik Vercauteren. Faster seasign signatures through improved rejection sampling. Cryptology ePrint Archive, Paper 2018/1109, 2018. https://eprint.iacr.org/2018/1109. [10] W. Diffie and M. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644–654, 1976. [11] Luca De Feo, Tako Boris Fouotsa, Péter Kutas, Antonin Leroux, Simon-Philipp Merz, Lorenz Panny, and Benjamin Wesolowski. Scallop: scaling the csi-fish. Cryptology ePrint Archive, Paper 2023/058, 2023. https://eprint.iacr.org/2023/058. [12] Luca De Feo and Steven D. Galbraith. Seasign: Compact isogeny signatures from class group actions. Cryptology ePrint Archive, Paper 2018/824, 2018. https://eprint. iacr.org/2018/824. [13] LucaDeFeo,DavidJao,andJérômePlût.Towardsquantum-resistantcryptosystemsfrom supersingular elliptic curve isogenies. Cryptology ePrint Archive, Paper 2011/506, 2011. https://eprint.iacr.org/2011/506. [14] LucaDeFeo,DavidJao,andJérômePlût.Towardsquantum-resistantcryptosystemsfrom supersingular elliptic curve isogenies. Journal of Mathematical Cryptology, 8(3):209–247, 2014. [15] LucaDeFeo,DavidKohel,AntoninLeroux,ChristophePetit,andBenjaminWesolowski. Sqisign: compact post-quantum signatures from quaternions and isogenies. Cryptology ePrint Archive, Paper 2020/1240, 2020. https://eprint.iacr.org/2020/ 1240. [16] Luca De Feo and Michael Meyer. Threshold schemes from isogeny assumptions. Cryptology ePrint Archive, Paper 2019/1288, 2019. https://eprint.iacr.org/ 2019/1288. [17] Steven D. Galbraith, Christophe Petit, and Javier Silva. Identification protocols and signature schemes based on supersingular isogeny problems. Cryptology ePrint Archive, Paper 2016/1154, 2016. https://eprint.iacr.org/2016/1154. 39 [18] Shah Muhammad Hamdi, Syed Zuhori, Firoz Mahmud, and Biprodip Pal. A compare between shor’s quantum factoring algorithm and general number field sieve. 04 2014. [19] Ali El Kaafarani, Shuichi Katsumata, and Federico Pintore. Lossy csi-fish: Efficient signature scheme with tight reduction to decisional csidh-512. Cryptology ePrint Archive, Paper 2020/124, 2020. https://eprint.iacr.org/2020/124. [20] David Kohel, Kristin Lauter, Christophe Petit, and Jean-Pierre Tignol. On the quaternion l-isogeny path problem. Cryptology ePrint Archive, Paper 2014/505, 2014. https: //eprint.iacr.org/2014/505. [21] Vadim Lyubashevsky. Fiat-shamir with aborts: Applications to lattice and factoring-based signatures. In Mitsuru Matsui, editor, Advances in Cryptology – ASIACRYPT 2009, pages 598–616, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg. [22] Luciano Maino, Chloe Martindale, Lorenz Panny, Giacomo Pope, and Benjamin Wesolowski. A direct key recovery attack on sidh. Cryptology ePrint Archive, Paper 2023/640, 2023. https://eprint.iacr.org/2023/640. [23] Rodney Van Meter, Kohei M. Itoh, and Thaddeus D. Ladd. Architecture-dependent execution time of shor’s algorithm, 2006. [24] Damien Robert. Breaking sidh in polynomial time. Cryptology ePrint Archive, Paper 2022/1038, 2022. https://eprint.iacr.org/2022/1038. [25] Joseph H Silverman. The Arithmetic of Elliptic Curves. Graduate texts in mathematics. Springer, Dordrecht, 2009. [26] Anton Stolbunov. Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves, 2010. [27] Anton Stolbunov. Cryptographic Schemes Based on Isogenies. PhD thesis, 01 2012. [28] J.TATE.Endomorphismsofabelianvarietiesoverfinitefields.Inventionesmathematicae, 2:134–144, 1966. [29] J. Vélu. Isogénies entre courbes elliptiques. Comptes-Rendus de l’Académie des Sciences, Série I, 273:238–241, juillet 1971. 40 [30] Lawrence C. Washington. Elliptic curves : number theory and cryptography. CRC Press, 2003. [31] Thom Wiggers, Lance Roy, and stefanritterhoff. Pq signatures zoo. [32] Youngho Yoo, Reza Azarderakhsh, Amir Jalali, David Jao, and Vladimir Soukharev. A post-quantum digital signature scheme based on supersingular isogenies. Cryptology ePrint Archive, Paper 2017/186, 2017. https://eprint.iacr.org/2017/186. 描述 碩士
國立政治大學
應用數學系
110751007資料來源 http://thesis.lib.nccu.edu.tw/record/#G0110751007 資料類型 thesis dc.contributor.advisor 蔡炎龍 zh_TW dc.contributor.advisor Tsai, Yen-lung en_US dc.contributor.author (Authors) 李立瑜 zh_TW dc.contributor.author (Authors) Lee, Li-Yu en_US dc.creator (作者) 李立瑜 zh_TW dc.creator (作者) Lee, Li-Yu en_US dc.date (日期) 2023 en_US dc.date.accessioned 1-Sep-2023 15:26:23 (UTC+8) - dc.date.available 1-Sep-2023 15:26:23 (UTC+8) - dc.date.issued (上傳時間) 1-Sep-2023 15:26:23 (UTC+8) - dc.identifier (Other Identifiers) G0110751007 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/147040 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 應用數學系 zh_TW dc.description (描述) 110751007 zh_TW dc.description.abstract (摘要) 自2016年起，美國國家標準與技術局(NIST)提出了後量子密碼學標準化競賽，公開徵求面對量子電腦時代的公鑰加密和數位簽章系統。隨著競賽尾聲的來臨，特別是公鑰加密方案的標準化清單釋出和二次徵求數位簽章系統方案，後量子密碼學的研究重心逐漸轉向數位簽章方案的制定和安全性分析。基於同源性的密碼學，作為後量子密碼學中最新穎的分支，運用了大量的代數和橢圓曲線知識，與其他領域方案相比，極小的金鑰大小是一大優勢，且使用方法與現行的橢圓曲線密碼學相似。 本研究旨在透過基於同源性的後量子數位簽章方案的調查，從NIST PQC競賽的現況出發，介紹基礎密碼學的數學背景、同源密碼學所需的數學知識，並分析這些數位簽章方案的內容、安全性和實作效能考量，期望能促使更多人投入同源密碼學的研究。 zh_TW dc.description.abstract (摘要) Since 2016, the U.S. National Institute of Standards and Technology (NIST) initiated the post-quantum cryptography standardization competition, publicly soliciting public key encryption and digital signature systems for the quantum computing era. As the competition draws to a close, especially with the release of the standardization list for public key encryption schemes and the second call for digital signature system proposals, the research focus of post-quantum cryptography has gradually shifted to the formulation and security analysis of digital signature schemes. Isogeny-based cryptography, as the most novel branch in post-quantum cryptography, employs a wealth of algebraic and elliptic curve knowledge. Compared to schemes from other domains, its extremely small key size is a significant advantage, and its usage is similar to current elliptic curve cryptography. This study aims to investigate post-quantum digital signature schemes based on isogenies. Starting from the current status of the NIST PQC competition, we introduce the mathematical background of basic cryptography, the mathematical knowledge required for isogeny-based cryptography, and analyze the content, security, and implementation performance considerations of these digital signature schemes. We hope to encourage more people to delve into research in this field. en_US dc.description.tableofcontents 致謝 ii 中文摘要 iii Abstract iv Contents v List of Tables vii List of Figures viii 1 Introduction 1 2 Mathematical Cryptography 3 2.1 SymmetricandAsymmetricCiphers....................... 3 2.1.1 SymmetricCiphers............................ 4 2.1.2 AsymmetricCiphers ........................... 5 2.2 DigitalSignature ................................. 6 2.3 EllipticCurves .................................. 8 2.4 TheQuantumThreats............................... 10 3 Isogeny-based Cryptography Background 15 3.1 EllipticCurvesandIsogenies........................... 15 3.2 EndomorphismringsandIsogenygraphs..................... 17 3.3 QuaternionAlgebrasandIdealClassGroup ................... 18 3.4 ProofSystems................................... 19 3.4.1 Zero-knowledge ............................. 19 3.4.2 AttackModels .............................. 22 3.5 Fiat-ShamirTransform .............................. 23 3.6 SIDH ....................................... 24 3.7 CSIDH ...................................... 25 4 Supersingular Isogeny-based Digital Signature 27 4.1 SIDH-based.................................... 27 4.1.1 PublicParameters............................. 28 4.1.2 Keygeneration .............................. 28 4.1.3 Signing.................................. 28 4.1.4 Verification................................ 29 4.2 GPS........................................ 30 4.3 SeaSign...................................... 30 4.4 CSI-FiSh ..................................... 30 4.5 SQISign...................................... 31 5 Implementation Analysis 32 5.1 ChoiceParameter................................. 33 6 Conclusion 35 Bibliography 38 zh_TW dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0110751007 en_US dc.subject (關鍵詞) 後量子密碼學 zh_TW dc.subject (關鍵詞) 同源密碼學 zh_TW dc.subject (關鍵詞) 橢圓曲線 zh_TW dc.subject (關鍵詞) 數位簽章 zh_TW dc.subject (關鍵詞) Post-quantum Cryptography en_US dc.subject (關鍵詞) Isogeny Based Cryptography en_US dc.subject (關鍵詞) elliptic curve en_US dc.subject (關鍵詞) signature schemes en_US dc.title (題名) 基於同源密碼學之簽章方案相關研究 zh_TW dc.title (題名) Supersingular Isogeny-Based Signatures: A survey en_US dc.type (資料類型) thesis en_US dc.relation.reference (參考文獻) [1] Shahla Atapoor, Karim Baghery, Daniele Cozzo, and Robi Pedersen. Csi-shark: Csi-fish with sharing-friendly keys. Cryptology ePrint Archive, Paper 2022/1189, 2022. https: //eprint.iacr.org/2022/1189. [2] Ward Beullens, Lucas Disson, Robi Pedersen, and Frederik Vercauteren. Csi-rashi: Distributed key generation for csidh. Cryptology ePrint Archive, Paper 2020/1323, 2020. https://eprint.iacr.org/2020/1323. [3] Ward Beullens, Thorsten Kleinjung, and Frederik Vercauteren. Csi-fish: Efficient isogeny based signatures through class group computations. Cryptology ePrint Archive, Paper 2019/498, 2019. https://eprint.iacr.org/2019/498. [4] Dan Boneh, Jiaxin Guan, and Mark Zhandry. A lower bound on the length of signatures based on group actions and generic isogenies. Cryptology ePrint Archive, Paper 2023/250, 2023. https://eprint.iacr.org/2023/250. [5] WouterCastryckandThomasDecru.Anefficientkeyrecoveryattackonsidh.Cryptology ePrint Archive, Paper 2022/975, 2022. https://eprint.iacr.org/2022/975. [6] Wouter Castryck, Tanja Lange, Chloe Martindale, Lorenz Panny, and Joost Renes. Csidh: An efficient post-quantum commutative group action. Cryptology ePrint Archive, Paper 2018/383, 2018. https://eprint.iacr.org/2018/383. [7] Jean-Marc Couveignes. Hard homogeneous spaces. Cryptology ePrint Archive, Paper 2006/291, 2006. https://eprint.iacr.org/2006/291. [8] Daniele Cozzo and Nigel P. smart. Sashimi: Cutting up csi-fish secret keys to produce an actively secure distributed signing protocol. Cryptology ePrint Archive, Paper 2019/1360, 2019. https://eprint.iacr.org/2019/1360. 38 [9] Thomas Decru, Lorenz Panny, and Frederik Vercauteren. Faster seasign signatures through improved rejection sampling. Cryptology ePrint Archive, Paper 2018/1109, 2018. https://eprint.iacr.org/2018/1109. [10] W. Diffie and M. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644–654, 1976. [11] Luca De Feo, Tako Boris Fouotsa, Péter Kutas, Antonin Leroux, Simon-Philipp Merz, Lorenz Panny, and Benjamin Wesolowski. Scallop: scaling the csi-fish. Cryptology ePrint Archive, Paper 2023/058, 2023. https://eprint.iacr.org/2023/058. [12] Luca De Feo and Steven D. Galbraith. Seasign: Compact isogeny signatures from class group actions. Cryptology ePrint Archive, Paper 2018/824, 2018. https://eprint. iacr.org/2018/824. [13] LucaDeFeo,DavidJao,andJérômePlût.Towardsquantum-resistantcryptosystemsfrom supersingular elliptic curve isogenies. Cryptology ePrint Archive, Paper 2011/506, 2011. https://eprint.iacr.org/2011/506. [14] LucaDeFeo,DavidJao,andJérômePlût.Towardsquantum-resistantcryptosystemsfrom supersingular elliptic curve isogenies. Journal of Mathematical Cryptology, 8(3):209–247, 2014. [15] LucaDeFeo,DavidKohel,AntoninLeroux,ChristophePetit,andBenjaminWesolowski. Sqisign: compact post-quantum signatures from quaternions and isogenies. Cryptology ePrint Archive, Paper 2020/1240, 2020. https://eprint.iacr.org/2020/ 1240. [16] Luca De Feo and Michael Meyer. Threshold schemes from isogeny assumptions. Cryptology ePrint Archive, Paper 2019/1288, 2019. https://eprint.iacr.org/ 2019/1288. [17] Steven D. Galbraith, Christophe Petit, and Javier Silva. Identification protocols and signature schemes based on supersingular isogeny problems. Cryptology ePrint Archive, Paper 2016/1154, 2016. https://eprint.iacr.org/2016/1154. 39 [18] Shah Muhammad Hamdi, Syed Zuhori, Firoz Mahmud, and Biprodip Pal. A compare between shor’s quantum factoring algorithm and general number field sieve. 04 2014. [19] Ali El Kaafarani, Shuichi Katsumata, and Federico Pintore. Lossy csi-fish: Efficient signature scheme with tight reduction to decisional csidh-512. Cryptology ePrint Archive, Paper 2020/124, 2020. https://eprint.iacr.org/2020/124. [20] David Kohel, Kristin Lauter, Christophe Petit, and Jean-Pierre Tignol. On the quaternion l-isogeny path problem. Cryptology ePrint Archive, Paper 2014/505, 2014. https: //eprint.iacr.org/2014/505. [21] Vadim Lyubashevsky. Fiat-shamir with aborts: Applications to lattice and factoring-based signatures. In Mitsuru Matsui, editor, Advances in Cryptology – ASIACRYPT 2009, pages 598–616, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg. [22] Luciano Maino, Chloe Martindale, Lorenz Panny, Giacomo Pope, and Benjamin Wesolowski. A direct key recovery attack on sidh. Cryptology ePrint Archive, Paper 2023/640, 2023. https://eprint.iacr.org/2023/640. [23] Rodney Van Meter, Kohei M. Itoh, and Thaddeus D. Ladd. Architecture-dependent execution time of shor’s algorithm, 2006. [24] Damien Robert. Breaking sidh in polynomial time. Cryptology ePrint Archive, Paper 2022/1038, 2022. https://eprint.iacr.org/2022/1038. [25] Joseph H Silverman. The Arithmetic of Elliptic Curves. Graduate texts in mathematics. Springer, Dordrecht, 2009. [26] Anton Stolbunov. Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves, 2010. [27] Anton Stolbunov. Cryptographic Schemes Based on Isogenies. PhD thesis, 01 2012. [28] J.TATE.Endomorphismsofabelianvarietiesoverfinitefields.Inventionesmathematicae, 2:134–144, 1966. [29] J. Vélu. Isogénies entre courbes elliptiques. Comptes-Rendus de l’Académie des Sciences, Série I, 273:238–241, juillet 1971. 40 [30] Lawrence C. Washington. Elliptic curves : number theory and cryptography. CRC Press, 2003. [31] Thom Wiggers, Lance Roy, and stefanritterhoff. Pq signatures zoo. [32] Youngho Yoo, Reza Azarderakhsh, Amir Jalali, David Jao, and Vladimir Soukharev. A post-quantum digital signature scheme based on supersingular isogenies. Cryptology ePrint Archive, Paper 2017/186, 2017. https://eprint.iacr.org/2017/186. zh_TW
