プロジェクト報告書(最終) Project Final Report
提出日(Date) 2023/1/17

N0.17 暗号と数理とセキュリティ プロジェクト報告書
No.17 Cryptography, Mathematics, and Security project report

猪股莉記 Riki Inomata
1.背景

長は 2048 ビットが推奨されることが多い。しかし、楕[GroupA(格子暗号班)]

円曲線暗号は 256 ビットの鍵長で 3072 ビットの鍵長のインターネットが普及し、ネットワーク社会と化した

RSA 暗号と同等の高い安全性を実現できる。鍵長が短現代において、様々なサービスのセキュリティを確保ければ、暗号の計算を高速化が可能であり、また、鍵するための基盤技術として暗号技術が用いられている。の保管に必要な容量も小さくなる。楕円曲線暗号の主中でも、公開鍵暗号方式と呼ばれる仕組みの暗号技術な用途としては、SSH や SSL/TLS のような安全な通信は、電子署名や暗号通信など私たちの身の回りの様々プロトコルや、デジタル署名が挙げられる。

な場面で活用されている。一方で、量子コンピュータ

デジタル署名は、公開鍵暗号に類似した改ざん防止手によって RSA 暗号や楕円曲線暗号などの主流な公開鍵法である。デジタル署名の大きな特徴は本人証明と、暗号の安全性が危殆化されている。実際に、米国立標署名したメッセージの内容が改ざんされていないこと準技術研究所は 2030 年までに現在主流である鍵長がの証明を同時に行うことができる点である。デジタル2048bit の RSA 暗号の使用の停止を推奨しており[1]、署名では、署名者の秘密鍵とメッセージを用いて署名日本でも同様の基準を設けている[2]。そこで、私たちを生成するので、他のメッセージに同じデジタル署名は量子コンピュータが発達した社会でも活躍されるとを用いることはできない。これは、紙の書類への署名考えられる耐量子計算機暗号に注目した。中でも格子や捺印では実現できないデジタル署名特有の利点であ暗号と呼ばれる暗号技術は量子アルゴリズムへの耐性る。楕円曲線暗号を用いたデジタル署名アルゴリズムを有するのみならず、暗号化状態処理技術という特性の例としては ECDSA や BLS 署名が挙げられ、前者はを持ち、実用化が期待されている。私たちは格子暗号

Bitcoin、後者は Ethereum という暗号資産に利用されによるテキストの暗号化と復号を可能とすることを目ている。

的とした。

ブロックチェーンは分散型のデジタル台帳と呼ばれる技術であり、ある一定の期間内の取引情報をまとめた[GroupB(楕円曲線暗号班)]台帳を 1 つのブロックとして、そのブロックをつなげ楕円曲線暗号にかかわるものとして、暗号、楕円曲線たものである。ブロックチェーンの最大の特徴は改ざ

暗号、デジタル署名、ブロックチェーンについて説明

んが実質的に不可能ということである。このようなブし、現在存在する利用例についても紹介する。

ロックチェーンの安全性を保証する技術の一つがデジ

現在用いられている暗号は、共通鍵暗号と公開鍵暗号タル署名である。ブロックチェーンの活用例としては、の 2 種類に大別することができる。共通鍵暗号は、暗Bitcoin や Ethereum といった暗号資産が挙げられる。

号化と復号に同一の鍵を用いる方式であり、公開鍵暗ブロックチェーンの問題点は、新たにブロックチェー

号は、公開鍵と秘密鍵という 2 種類の鍵を用いて暗号ンに参加するユーザーに専用のソフトウェアのダウン化と復号を行う方式である。

ロードと、大容量のストレージを要求することである。

楕円曲線暗号は公開鍵暗号の中で主流と呼ばれるもの

大容量のストレージはブロックチェーンに記録されての 1 つで、楕円曲線と呼ばれる曲線を用いた暗号であいる過去から現在までの取引情報をダウンロードしてる。公開鍵暗号の他の例としては素因数分解の困難性保持するために要求される。例えば、Bitcoin では、を用いた RSA 暗号が存在するが、RSA 暗号の安全性は、Bitcoin Core と呼ばれるソフトウェアを公式に提供し鍵の長さに強く依存している。現在では RSA 暗号の鍵ているが、このソフトウェアには過去の取引情報も含まれているため、ダウンロードには 350GB 以上のストために、本グループの目的はブロックチェーン技術とレージが要求される[3]。また、このダウンロードにはそれにかかわるマイニングなどの作業が体験できる1 週間以上の時間がかかる場合もある。もちろん、ブWeb アプリケーションを作成し人々に体験してもらう

ロックチェーン上での取引が続けば、それらの取引情ことで、ブロックチェーン技術を啓蒙することである。

報も記録する必要があるため、ブロックチェーンの取既存の暗号資産のようなブロックチェーンに新たに参引に必要なストレージは今後も増え続けていくことが加するために必要な、専用のソフトウェアの導入や大わかる。また、ソフトウエアのダウンロードといった容量のストレージを要求しない Web 上で完結したアプ

行為は技術的な知識のない人々にとっては容易なこと

リケーションを作成することで、人々が手軽にブロッではなく、PC に関する基礎的な知識がない人がブロッ

クチェーン技術を体験できるようになることを目指す。

クチェーンに参加して取引を行うことは難しい。以上の理由から、ブロックチェーンは新規参入のための障3.課題解決のプロセスとその結果壁が低いとは言えず、ブロックチェーン技術の普及を[GroupA(格子暗号班)]行うためには、これらの問題点を解決する必要がある。

今回 web 上での暗号化に利用した方式の一つである

そして、これらの問題点に加えて、暗号資産の抱えるGGH 方式は最近ベクトル問題の困難性を利用した格子問題点として、人々の持つ暗号資産に対する漠然とし暗号の方式の一つである。我々はこの方式を用いて文た不安がある。日本においてこの漠然とした不安を生字列の暗号化を行うことを目指した。具体的なアルゴみ出した要因の一つとして、暗号資産取引所リズムとして、直交基底を秘密鍵、非直交基底を公開「Coincheck(コインチェック)」が受けたハッキングに鍵として、平文に乱数を加えたモノを暗号文として扱よる暗 号資産の流出 が挙げられ る。この事件 は、う。この暗号文を復号するする際には、秘密鍵によっCoincheck に対する不正アクセスが原因で発生したとて最も近い格子点を発見し、公開鍵によって連立方程されていて、この事件で流出した暗号資産自体の安全式を解くことで復号を行っている。

性はその原因ではない[4]。取引所の安全性と暗号資産

ここからは、どのように文字を座標に当てはめて、GGH自体がもつ安全性を切り分けて考える必要があること

方式を用いて暗号化し復号してるのか、具体例を使いを、人々に啓蒙していく必要がある。

ながら説明していく。例えば、「あいう」という文字列を暗号化する場合、まず「あいう」を整数値に変換2.課題の設定と到達目標

すると、「4196743176255353094534」となる。この整[GroupA(格子暗号班)]

数列を 2 桁ずつに分割して「41,96,74,‥,45,34」のよ

本プロジェクトでは次世代の暗号である格子暗号を用うし、配列にこの順番で格納する。その後に、この「配いてテキストの暗号化/復号を可能にすることを目標列の長さ」を頭に、「バイト列の長さ」と「整数列のとした。目標を達成する上での課題が 2 つある。一つ長さ」を順に配列の後ろに格納する。例を用いると、目は今現在標準化が推進されている途中である格子暗「13,41,96,74,‥,45,34,22,9」のようになる。その後号について研究をすすめることと、web アプリケーシに、格子の次元に合わせるために 0 を格納していく。

ョンの作成技術を身に着けることである。二つ目は格例を用いると、「13,41,96,74,‥,45,34,22,9,0,0,0

子暗号の方式の一つである GGH 方式が整数を、LWE 方‥,0」となる。その後に、この配列を暗号化する。復式がビットを暗号化/復号の対象としているためそれ号した後の処理では、配列から、「配列の長さ」、「バらをどのようにテキストの暗号化/復号と結びつけるイト列の長さ」、「整数列の長さ」の値を排を行った。

かというものがあげられる。

更に余分な 0 を排除して、「41,96,74,‥,45,34」という状態に戻し、これらを結合することによって日本語[GroupB(楕円曲線暗号班)]に戻している。また、格子基底の次元は 200 と設定し本グループの課題は、ユーザーすなわち人々にソフトた。GGH 方式は最近ベクトル問題の困難性を利用したウェアのダウンロードや大容量のストレージを要求す格子暗号の方式の一つである。我々はこの方式を用いることなく、ブロックチェーン上での取引を体験してて文字列の暗号化を行うことを目指した。具体的なアもらうことである。疑似的な暗号資産を用いたブロッルゴリズムとして、直交基底を秘密鍵、非直交基底をクチェーン上での取引を体験することで、人々のブロ

公開鍵として、平文に乱数を加えたモノを暗号文としックチェーン上での取引とブロックチェーン技術そのて扱う。この暗号文を復号するする際には、秘密鍵にものに対する理解促進を図る。以上の課題を解決する

よって最も近い格子点を発見し、公開鍵によって連立方程式を解くことで復号を行っている。

工夫した点は、入力されたテキストについて、unicode

ここからは、どのように文字を座標に当てはめて、GGH文字で 暗号分を出力 できるよう にし、入力さ れた方式を用いて暗号化し復号してるのか、具体例を使いunicode 暗号文を復号できるようにした点である。具ながら説明していく。例えば、「あいう」という文字体的には、入力された文字をビット列に変換し、ビッ列を暗号化する場合、まず「あいう」を整数値に変換ト一つ一つについて暗号化と復号を行った。その際、すると、「4196743176255353094534」となる。この整従来の暗号化方法だと暗号文が整数で出力されるので、数列を 2 桁ずつに分割して「41,96,74,‥,45,34」のよ

それをさらに Unicode 化することで暗号文を Unicodeうし、配列にこの順番で格納する。その後に、この「配テキスト出力できるようにした。復号の際は、入力さ列の長さ」を頭に、「バイト列の長さ」と「整数列のれた Unicode 暗号文を一つのビットを暗号化すること長さ」を順に配列の後ろに格納する。例を用いると、によってできる整数暗号文のサイズごとに区切り、そ「13,41,96,74,‥,45,34,22,9」のようになる。その後

れぞれで復号することによりもともとの整数暗号文をに、格子の次元に合わせるために 0 を格納していく。

導出し、従来の LWE 方式の復号方法を用いることでビ例を用いると、「13,41,96,74,‥,45,34,22,9,0,0,0

ット列を導出した。最後にビット列をテキストに変換‥,0」となる。その後に、この配列を暗号化する。復することで復号を可能とした。

号した後の処理では、配列から、「配列の長さ」、「バイト列の長さ」、「整数列の長さ」の値を排を行った。

[GroupB(楕円曲線暗号班)]

更に余分な 0 を排除して、「41,96,74,‥,45,34」といブロックチェーン技術について理解しないまま、そのう状態に戻し、これらを結合することによって日本語実装を行うことは容易ではないため、我々はブロックに戻している。また、格子基底の次元は 200 と設定しチェーンに関する情報収集を十分に行ったうえで、どた。のようにブロックチェーンを実装するべきかを検討し、また、もう一つの方式である LWE 方式は LWE 問題とい実装を行った。

う数学問題の困難性を安全性の根拠としている。座標

まず、ブロックチェーンに関する情報収集は主に情報が整数全体で表される格子ではなく素数 q により制限ライブラリーで関連書籍を検索することから始めた。

された、有限体上の格子を利用している。米国立標準

複数の関連書籍が見つかったので、グループメンバー

技術研究所は耐量子暗号アルゴリズムとしてこの LWEが各々別の書籍を借りて読み、それぞれの情報を共有問題の一つを利用した方式を標準化することを発表しすることで、学びを深めた。その後、現状のブロックている。[5]

チェーンの応用例である暗号資産やサプライチェーン

LWE 問題とはノイズが入った連立合同式を解くことをマネジメントなどについて主にインターネットを活用指す(図 1)。これを行列とベクトルで表すと図 2 のよして調べた。一般の人々にはブロックチェーンと暗号うになり、つまり LWE 問題とは素数 q を法とする有限資産はほぼ同じものであると認識されていることから、

体 Zq 上からとった誤差 e を付加した連立合同式についその誤解を解いたうえでブロックチェーン技術の啓蒙て、A,b が与えられたとき、As + e ≡ b (mod q) をを行うには暗号資産に関する製品を作る必要があると満たすベクトル s を求める問題と言える。

私たちは考えた。しかし、実際に使われている通貨と対応させた暗号資産を扱うのは簡単ではないため、実際に使われている通貨とは関係ない疑似的な暗号資産を実装することが望ましいという結論に達した。そして、暗号資産の応用例や暗号資産の実装例について調べることで、どのような手法でブロックチェーン、そ図 1.LWE 問題の例して独自の暗号資産を実装するべきかを理解した。既存のライブラリ、例えばデジタル署名のライブラリなどを用いることで、簡単なブロックチェーンを実装することは難しくないことが分かったため、ライブラリを用いずにデジタル署名を実装することと、ブロックチェーンの全体を実装することを切り分けて考えるこ

図 2.LWE 問題を行列とベクトルで表した図とで独自の暗号資産を実装するに至るのではないかと

今回 LWE 方式を Web アプリケーションに導入する上でいう考えに至った。最後に、ブロックチェーンの全体を実装することについては、クラウド上に疑似的なブ今後の展望としては、EC-Shcnorr を本プロジェクトでロックチェーンを構築することで、取引やブロックが実装したブロックチェーンに組み込むことが挙げられ可視化するようにした。クラウド上のブロックチェーる。これにより、一人で複数の秘密鍵や公開鍵を利用ンについては研究があまり進んでいないこともあり、することがあっても、鍵を線形和でまとめて用いるこ

様々な文献を参考にしながら実装をした。デジタル署とができる。また、ECDSA にはある条件を満たす 2 つ名のライブラリを用いない実装は、主に[6]と[7]を参の署名が同一の正しい署名として認識されてしまう脆考にした。ライブラリを用いないデジタル署名の具体弱性が存在するが、EC-Schnorr にはその脆弱性が存在例について学んだ後、その具体例を応用してブロックしないため従来のブロックチェーンよりも優れた安全チェーンにはほとんど用いられていないが有望なデジ性を持ったブロックチェーンを実装できる可能性があ

タル署名を自らの手で実装した。

る。

4. 今後の課題

参考文献[GroupA(格子暗号班)][1]経済産業省(2022) 暗号強度要件(アルゴリズム及全体の課題として「テキストファイルを介さず web 上び鍵長選択)に関する設定基準.

で格子暗号の暗号化、復号をするシステムを作成」がhttps://www.cryptrec.go.jp/list/cryptrec-ls-0003

挙げられる。後期に作成した格子暗号を用いての web-2022.pdf (2023/07/14 アクセス)上での文字の復号に関して、現在は暗号化情報のテキストファイルを選び、秘密鍵のテキストファイルを選[2]NIST(2020) Recommendation for Key Management.

んでからでないと平文への復号はできない。現在のこhttps://nvlpubs.nist.gov/nistpubs/SpecialPublicaのシステムをファイルを介さずに行うことが課題であtions/NIST.SP.800-57pt1r5.pdf(2023/07/14 ア ク セる。

ス)

次は GGH 方式における課題で、一つ目は実行時間の長さである。公開鍵の作成においての実行時間がとて[3] Bitcoin.org, "Bitcoin Core のダウンロード",も長くなってしまっているためこの問題を解決する必

https://bitcoin.org/ja/download (参照要がある。二つ目は乱数の設定に関してである。送信2023/12/22)

者が送る最近ベクトル問題の暗号化に用いられる乱数の範囲が短すぎると容易に解読されてしまうが、大き[4] Coincheck, "暗号資産 NEM の不正送金に関する質

すぎても復号に時間がかかってしまう。この乱数の扱

問", https://coincheck.com/ja/info/faq\_nem (参照いについて考える必要がある。三つ目は暗号文への変2023/12/22)換についてである。私たちは文字列を暗号化する際に、文字列全体を整数化し、その値を 2 桁ずつ分割して平[5] digicert(2023) 米国商務省標準化技術研究所

文を作成することで文字列の大きさを小さくしたが、（NIST）が耐量子暗号標準を発表：最新の状況.

これでは文字列が長かった場合に、二つの暗号文を送https://www.digicert.com/jp/blog/nist-pqc-standa

らなければならない。しかし、一文字ずつ座標の値とrds-are-here(2023/8/26 アクセス)してしまえば、暗号文の長さを大きくしてしまう。この暗号文の大きさにバランスについて考察していかな[6] Jimmy Song 著, 星野靖子訳 (2020) "プログラミければならないと考える。

ング・ビットコイン : ゼロからビットコインをプログ

最後に LWE 方式ページについての今後の課題が 2 つラムする方法", オライリー・ジャパン

ある。1 つ目は暗号文のサイズが非常に大きくなってしまうことである。二つ目の課題はパラメータの適切[7] 山崎重一郎, 安土茂亨, 金子雄介, 長田繁幸

な設定についてである。今後、別種類の LWE 暗号につ(2021) "ブロックチェーン技術概論 : 理論と実践",

いて研究を進め、暗号文のサイズや鍵長を小さくした講談社

り、パラメータを変更させたりしながら、安全性の評価を行うことで最適なパラメータを発見したい。
[GroupB(楕円曲線暗号班)]