リケラボ論文検索は、全国の大学リポジトリにある学位論文・教授論文を一括検索できる論文検索サービスです。

リケラボ 全国の大学リポジトリにある学位論文・教授論文を一括検索するならリケラボ論文検索大学・研究所にある論文を検索できる

リケラボ 全国の大学リポジトリにある学位論文・教授論文を一括検索するならリケラボ論文検索大学・研究所にある論文を検索できる

大学・研究所にある論文を検索できる 「New Algorithms of Public Key Agreement Based on Non-Commutative Algebra and Framework of Strongly Asymmetric Public Key Agreement」の論文概要。リケラボ論文検索は、全国の大学リポジトリにある学位論文・教授論文を一括検索できる論文検索サービスです。
リケラボ

コピーが完了しました

URLをコピーしました

論文の公開元へ論文の公開元へ
書き出し

New Algorithms of Public Key Agreement Based on Non-Commutative Algebra and Framework of Strongly Asymmetric Public Key Agreement

神保 洸貴 Koki Jimbo 東京理科大学 DOI:info:doi/10.20604/00003699

2022.06.17

概要

本学位論文は,非可換代数を用いた高速かつ安全な鍵共有アルゴリズムの考案,および従来の鍵共有アルゴリズムを,鍵生成に要する計算量が暗号文送受信者間で非対称になるよう改良するための条件の導出を目的とする.

本論文は5章から構成される.

第1 章では, 本研究の背景と研究目的, 本論文の構成を述べる. 公開鍵共有とは, 秘密鍵暗号におftる共通鍵を,安全でない通信路を通して暗号文送信者(Alice)と受信者(Bob)間で安全に共有する手法のことを指している.実社会で使用されている公開鍵共有アルゴリズムの代表的なものとして1976年に考案されたDiffie-Hellman鍵共有法などがあり,インターネット上で個人情報を保護するための重要な役割を担っている.しかし,近年の計算機科学の発展とそれに伴う攻撃者の使用する計算機の能力向上によって,従来の公開鍵共有アルゴリズムの安全性が危惧されている.一般的に,公開鍵共有アルゴリズムの安全性は生成する共通鍵(以後SSKと表記)のサイズに依存するが,攻撃者の計算機の能力が日々向上している現在,安全基準となるSSKのサイズもそれに伴い単調に増加している.SSKのサイズの増加は,鍵生成に必要な計算コストの増大につながり,高速な暗号通信の阻害を招く.結果として現在,安全基準を下回るサイズのSSKを使用するユーザーが増加傾向にある.また,近い将来実用化が予想されている量子計算機を用いた攻撃も従来の公開鍵共有アルゴリズムに対する大きな脅威となることが指摘されている.これらの問題に対して本学位論文では,(1)非可換代数を用いた高速かつ安全な鍵共有アルゴリズムの考案と,(2)Alice, Bob間でSSK生成に必要な計算量が非対称となるような鍵共有アルゴリズムの考案という 2 つのアプローチにて解決を試みる. 本学位論文の2 章, 3 章が⑴のアプロ 1 チに該当し,4 章が( 2 ) のアプローチに該当する. また, 2 章から4 章全てに共通する背景として, 2011年にローマII大学のAccardiらによって考案された, Strongly Asymmetric Public Key Agreement (SAPKA)と呼ばれる強非対称鍵共有フレームワークがあり,本章でその数理と SAPKAとアプローチ⑴⑵との関連を述べる.

2章では,Strongly Asymmetric Algorithm 5 (SAA-5)と呼ぶ新しいアルゴリズムの考案とSAA-5の安全性の検証を行う.本章ではまず,アプローチ⑴におftる「安全な鍵共有アルゴリズム」とは,攻撃者がどのような手法を用いても一意にSSKを導出することができない鍵共有アルゴリズムである,ということを説明する.上記安全性を満たす鍵共有アルゴリズムの開発を目指す研究は,2011年にSAPKAが考案されて以降行われており,2015年にはSAPKAクラスの具体アルゴリズムとしてStrongly Asymmetric Algorithm 3 (SAA- 3)と呼ばれる鍵共有アルゴリズムがAccardi, Regoli(ローマII大学)によって考案された. SAA-3の鍵生成規則は主に非可換代数演算を用いて構成されており,適切にパラメータが設定されている場合,攻撃者が用いる計算機の性能が無限大であると仮定しても55Kをー意に導出可能な攻撃法はこれまでに見つかっていない.しかし一方で,AliceとBob間で等しいSSKを生成できるとは限らず, その際, AliceとBobはお互いの計算結果を確認することができないという問題点が明らかになっており,SAA-3を用いて正しく暗号通信を行えない可能性が判明していた. 本章では, AliceとBobの選択し得る全ての秘密鍵に対し,両者のSSKが等しくなるようにSAA-3の鍵生成規貝J,秘密鍵等の初期パラメータを変更し, SAA-5と呼ばれる新たな鍵共有アルゴリズムを考案する. さらに, SAA-5の安全性の検証を攻撃者の計算機の能力が無限大であることを仮定し行う.具体的に本章では,(2-1)攻撃者が公開鍵から得られる行列の積のみからSSKを一意に導出できる条件の検証と(2-2)攻撃者が公開鍵からAliceとBobの秘密鍵を一意に導出可能か検証を行う.検証(2-1)について,SAA-5はSAA-3と同様に,有限体上の行列演算をもとに鍵生成規則が構成されていることから,公開鍵から得られる行列の積のみでSSKを求めるという手法は,最も単純な攻撃法の一つである.また,公開鍵から秘密鍵を一意に導出可能であれば,攻撃者は得られた秘密鍵を使用してSSKを導出することができるため,SAA-5が本章で定義した「安全性」を満たすか判定するために(2-2)は必要な検証である・(2-1)の検証により,攻撃者が公開鍵から得られる行列の積からSSKを導出可能な条件が得られており,この条件をもとにBobの秘密鍵生成規則が定義された.さらに検証(2-2)から,攻撃者は公開情報から成る連立方程式に対していかなる攻撃を行なったとしても,Bob, Aliceの各秘密鍵を特定することが不可能になるという結果が得られた.SAA-5が「安全」なアルゴリズムであるかどうかを判定することは,上記検証のみでは不十分であるため,今後行われるべき検証内容を,実装実験により計算効率を確認する必要性と併せて本章最後で述べる.

3 章では, SAA- 5 を用いてどの程度高速に鍵共有を行えるかを, Diffie-Hellmanと計算
速度を比較することによって検証し,さらにSAA-5を記述可能な新しい鍵共有フレームワークを, SAPKAを一般化することによって構築する. SAA-5とDiffie-Hellmanの計算速度の比較に関して, 両者の共通鍵のビット数を512から5120まで徐々に拡大したとき, 両者の計算速度がビット数に対してどのように増加するかを実装実験により確かめる.実験の結果,Diffie-Hellmanの計算速度は共通鍵のビット数に対して指数関数的に上昇するのに対し, SAA- 5 は線形に上昇することが確認された. また, 共通鍵が5120 ビットの場合, SAA-5の計算速度はDiffie-HeUmanの15倍ほど高速であることが明らかになった.SAA- 5 を記述可能な鍵共有フレームワークに関して, 本章では1 章で説明したSAPKAをAliceの秘密鍵数に関して一般化することによりSAPKA with Multiple Keys (SAPKA-MK)と呼ばれるフレームワークを構築した.SAA-5はSAPKA-MKのパラメータ(ある半群から自分自身への写像)で記述できることが示され,さらにSAA-5を記述する各写像から複雑な行列演算を省くことでSAA-5-noSEと呼ばれるアルゴリズムを記述した.EVeの持つ計算機の能力が無限大であると仮定したとき,SAA-5-no-SEの安全性はSAA-5と同等であることも同時に示している. また, 全ての0 SKビット長に対してSAA 5 no- SEの計算速度はSAA- 5より高速であることが実装実験により明らかになっており,この点からSAPKA-MKクラスにSAA- 5 と同等の安全性を持ち, より高速なアルゴリズムが存在することが言え, SAPKA-MKを今後考察していくことの利点の一つが説明できる.

4 章では非対称性と呼ばれる, Alice, Bob両者で鍵生成規則が異なるというSAPKAの特徴を用いて,従来の鍵共有アルゴリズムをAlice, Bobどちらか一方の鍵空間を小さくしても攻撃に要する計算量が変化しないよう改良するための条件の導出を行う.本章では,まずDiffie-Hellmanアルゴリズムを,SAPKAを用いて各鍵生成規則を非可換台数上に拡張し非対称性を持たせ,Alice側の秘密鍵空間をビット数に関して狭めた状況下で攻撃に要する計算量を導出した. その結果, Aliceの秘密鍵空間のビット数を, 秘密鍵空間に対する全探索攻撃が現実的時間で不可能になる範囲内で縮めても,攻撃計算量に影響を与えないことが明らかになった. この時, Aliceが鍵生成に必要な計算量は, Bobのそれと比較して下げることができ, 実装実験により通常のDiffie-Hellmanより高速に鍵生成を行えること (24倍程度) が判明した. さらに, Diffie- Hellmanに対して行った, Alice側の秘密鍵空間をビット数に関して狭めた状況下での攻撃をSAPKA自体に対して行うことで,上記検証結果をSAPKAクラス内に一般化した. 具体的に, 複数のSAPKAサブクラス間におftる包含関係を導出し,その結果をもとに任意の鍵共有アルゴリズムをAliceの計算量が'Bobの計算量より下回るように改良するための必要条件を導出している.

5章では,本研究の結論を述べる.

論文の公開元へ

関連論文

関連論文をもっと見る

参考文献

[1] Shannon, C.E. Communication Theory of Secrecy Systems. Bell Syst. Tech. J., 1949, 28, pp. 656–715.

[2] NIST, Announcing the ADVANCED ENCRYPTION STANDARD (AES), Federal Information Processing Standards Publication 197, November, 26, 2001.

[3] Diffie, W.; Hellman, M. New directions in cryptography. IEEE Trans. Inf. Theory, 1976, 22, pp. 644–654.

[4] Rivest, R.L.; Shamir, A.; Adleman, L. A method for obtaining digital signa- tures and public-key cryptosystems, Commun. ACM, 1978, 21, pp. 120–126.

[5] Merkle, R.C. Secure communication over an insecure channel, Common. ACM, 1978, 21, pp. 294–299.

[6] Pollard, J. Monte Carlo Methods for Index Computation (modp). Math. Com- put.,1978, 32, pp. 918–924.

[7] Pohlig, S.; Hellman, M. An improved algorithm for computing logarithms over GF (p) and its cryptographic significance (Corresp.). IEEE Trans. Inf. Theory, 1978, 24, pp. 106–110. DOI:10.1109/TIT.1978.1055817.

[8] Adrian, D.; Bhargavan, K.; Durumeric, Z.; Gaudry, P.; Green, M.; Halder- man, J.A.; Heninger, N.; Springall, D.; Thom´e, E.; Valenta, L.; et al. Imper- fect Forward Secrecy: How Diffie-Hellman Fails in Practice. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA, 12–16 October 2015; pp. 5–17.

[9] NIST, Recommendation for Key Management: Part 1 - General. May, 2020. https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST. SP.800-57pt1r5.pdf (accessed on 12 August 2021).

[10] 情報処理推進機構; 情報通信研究機構, TLS 暗号設定ガイドライン, July, 2020, https://www.ipa.go.jp/security/ipg/documents/ipa-cryptrec-gl- 3001-3.0.1.pdf. (Acceced on 4 August 2021)

[11] Shor, P.W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comput. 1997, 26, pp. 1484– 1509.

[12] Dridi, R.; Alghassi, H. Prime Factorization Using Quantum Annealing and Computational Algebraic Geometry, 2016, https://arxiv.org/abs/1604. 057962v2.

[13] Martin-L´opez, E.; Laing, A.; Lawson, T.; Alvarez, R.; Zhou, X.-Q.; O ’Brien, J.L. Experimental Realization of Shor ’s Quantum Factoring Algorithm Using Qubit Recycling, Nature Photonics, volume 6, number 11, 2012, pp. 773–776.

[14] Ajtai, M.; Dwork, C. A public-key cryptosystem with worst-case/average- case equivalence. In Proceedings of the 50th ACM Symposium on Theory of Computing, El Paso, TX, USA, 4–6 May 1997; pp. 284–293.

[15] Matsumoto, T.; Imai, H. Public Quadratic Polynomial-Tuples for Effi- cient Signature-Verification and Message-Encryption. Proceedings of EURO- CRYPT, LNCS 330, Springer-Verlag, 1988, pp.419–453.

[16] McEliece, R.J. A Public-Key Cryptosystem based on Algebraic Coding The- ory. Jet Propulsion Laboratory DSN Progress Report, 42-44, 1978, pp.114– 116.

[17] Gentry, C. Fully homomorphic encryption using ideal lattices. In Proceedings of the 41st ACM Symposium on Theory of Computing (STOC), Bethesda, MD, USA, 31 May - 2 June 2009, Volume 9, pp. 169–178.

[18] Regev, O. On lattices, learning with errors, random linear codes, and cryp- tography. Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005, pp. 84-93.

[19] Peikert, C. Public-key cryptosystems from the worst-case shortest vector prob- lems: extended abstract. In Proc. 41st ACM Symp. on Theory of Computing- STOC 2009, ACM, 2009, pp. 333–342.

[20] Ajtai, M. The shortest vector problem in L2 is NP-hard for randomized re- ductions. Proceedings of the thirtieth annual ACM symposium on Theory of computing. Dallas, Texas, United States: ACM, 1998, pp. 10–19.

[21] Regev, O. On lattices, learning with errors, random linear codes, and cryp- tography. J. ACM, 2009, 56, pp. 1–40.

[22] Peikert, C.; Vaikuntanathan V.; Waters, B. A Framework for Efficient and Composable Oblivious Transfer. Proceedings of CRYPTO, LNCS 5157, Springer-Verlag, 2008, pp. 554–571.

[23] Lyubashevsky, V.; Peikert, C.; Regev, O. On Ideal Lattices and Learning with Errors over Rings. In Advances in Cryptology-EUROCRYPT 2010, Springer LNCS 6110, 2010, pp. 1–23.

[24] Brakerski, Z.; Gentry, C.; Vaikuntanathan, V. (Leveled) fully homomorphic encryption without bootstrapping. In Shafi Goldwasser, editor, ITCS 2012, ACM, January, 2012, pp. 309–325.

[25] Alkim, E.; Ducas, L.; Poppelmann, T.; Schwabe, P. Post-quantum key exchange—A new hope. In Proceedings of the 25th USENIX Security Sym- posium (USENIX Security 16), Austin, TX, USA, 10–12 August, 2016, pp. 327–343.

[26] 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. In Proceedings of the 2018 IEEE European Sym- posium on Security and Privacy (EuroS and P), London, UK, 24–26 April, 2018, pp. 353–367.

[27] Post-Quantum Cryptography Competition Round 2 Submissions. Available online: https://csrc.nist.gov/projects/post-quantum-cryptography/ round-2-submissions (accessed on 13 August 2021).

[28] PQC Standardization Process: Third Round Candidate Announce- ment. Available online: https://csrc.nist.gov/News/2020/ pqc-third-round-candidate-announcement (accessed on 13 August 2021).

[29] Hoffstein, J.; Pipher, J.; Silverman, J.H. NTRU: A Ring-Based Public Key Cryptosystem. Proceedings of Algorithmic Number Theory (ANTS), LNCS 1423, Springer-Verlag, 1998, pp.267–288.

[30] Hu¨lsing, A.; Rijneveld, J.; Schanck, J.; Schwabe, P. High-Speed Key Encap- sulation from NTRU, Proceedings of Cryptographic Hardware and Embedded Systems (CHES) 2017, Lecture Notes in Computer Science, 10529, Springer- Verlag, 2017, pp. 232–252.

[31] Micciancio, D.; Regev. O, Worst-case to Average-case Reductions based on Gaussian Measures. Journal of Computing, 37(1), 2007, pp.267–302.

[32] Laine, K.; Lauter,K. Key Recovery for LWE in Polynomial Time. IACR Cryp- tology ePrint Archive, no.176, 2015.

[33] Aono, Y.; Boyen, X.; Phong, L.T.; Wang, L. Key-Private Proxy Re- Encryption under LWE. Proceedings of INDOCRYPT, LNCS 8520, Springer- Verlag, 2013, pp.1–18.

[34] Albrecht, M.R.; Cid, C.; Faug`ere, J.C.; Fitzpatrick, R.; Perret, L. Algebraic Algorithms for LWE Problems. IACR Cryptology ePrint Archive, no.1018, 2014.

[35] Micciancio, D. The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, FOCS ’98, IEEE Computer Society, 1998, pp. 92–98.

[36] Coppersmith, D.; Shamir, A. Lattice Attacks on NTRU. In Advances in Cryptology—EUROCRYPT ’97; Lecture Notes in Computer Science; Fumy, W., Ed.; Springer: Berlin, Germany; 1997, Volume 1233.

[37] Accardi, L.; Iriyama, S.; Regoli, M.; Ohya, M. Strongly Asymmetric Public Key Agreement Algorithms. ; Technical Report ISEC2011-20; IEICE: Tokyo, Japan, 2011; pp. 111–114.

[38] Accardi, L.; Regoli, M. On a class of strongly asymmetric PKA algorithms. J. Math. Crypt, 2015

[39] Accardi, L.; Iriyana, S.; Jimbo, K.; Regoli, M. A New Class of Strongly Asymmetric PKA Algorithms: SAA-5, Cryptography, 2019, 3(1), 9.

[40] Jimbo, K.; Iriyana, S.; Regoli, M. Implementation of a New Strongly- Asymmetric Algorithm and Its Optimization, Cryptography, 2020, 4(3), 21.

[41] Iriyana, S.; Jimbo, K.; Regoli, M. New Subclass Framework and Concrete Examples of Strongly Asymmetric Public Key Agreement, Appl. Sci. 2021, 11(12), 5540.

[42] Buchberger, B. Theoretical Basis for the Reduction of Polynomials to Canon- ical Forms. ACM SIGSAM Bulletin. ACM. 10 (3), August, 1976, pp. 19–29. DOI:10.1145/1088216.1088219.

[43] Ottaviani, V.; Zanoni, A.; Regoli, M. Conjugation as public key agreement protocol in mobile cryptography. In Proceedings of the 2010 International Conference on Security and Cryptography (SECRYPT), Athens, Greece, 26– 28 July 2010; pp. 1–6.

[44] Jimbo, K.; Iriyama, S.; Regoli, M. Project Name: Implementation of a New Strongly Asymmetric Algorithms and Its Optimization. GitHub Repository. 2020. Available online: https://github.com/jimbobmij/project_KSM (ac- cessed on 29 July 2020)

[45] ElGamal, T. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory, 1985, 31, pp. 469–472.

[46] Koblitz, N. Elliptic curve cryptosystems. Math. Comput., 1987, 48, pp. 203– 209.

[47] Großsch¨adl, J.; Kizhvatov, I. Performance and security aspects of client-side SSL/TLS processing on mobile devices. In Proceedings of the International Conference on Cryptology and Network Security, Kuala Lumpur, Malaysia, 12–14 December 2010, Springer: Berlin/Heidelberg, Germany, 2010, pp. 44– 61.

[48] Okeyinka, A.E. Computational speeds analysis of RSA and ElGamal algo- rithms on text data. In Proceedings of the World Congress on Engineering and Computer Science, San Francisco, CA, USA, 21–23 October 2015, Volume 1.

[49] Lamport, L. Constructing Digital Signatures from a One-Way Function. Tech- nical Report CSL-98, SRI International: Menlo Park, CA, USA, 1979, Volume 238.

[50] Merkle, R.C. A Certified Digital Signature, Conference on the Theory and Application of Cryptology. Springer: New York, NY, USA, 1989.

[51] Cooper, D.; Santesson, S.; Farrell, S.; Boeyen, S.; Housley, R.; Polk, W. Internet X. 509 Public Key Infrastructure Certificate and Certificate Re- vocation List (CRL) Profile, RFC 5280, 2008, pp. 1–151. Available online: https://datatracker.ietf.org/doc/html/rfc5280 (accessed on 14 June 2021).

参考文献をもっと見る

全国の大学の
卒論・修論・学位論文
を
一発検索！

この論文の関連論文を見る