過去・現在・未来

 【 Shorのアルゴリズムの秘密 】　 かつて暗号の世界を震撼させたShorのアルゴリズムには秘密があった。それは、隠しておきたい秘密ではない。なぜ、それがそんなにも速いのかという秘密である。　 Shorのアルゴリズムでは、普通のコンピューターがn個の計算をするときに、量子コンピューターは2^n個の計算をする。普通のコンピューターが10歩進めば、量子コンピューターは、1,024歩も進むのだ。こうした「指数関数的高速化」がなぜ可能かという秘密である。 「そもそも、量子コンピューターには 2^n個の計算をパラレルに実行する能力がある」と考えている人も多いと思うのだが、それは微妙な間違いだ。 確かに「量子の世界」では、そうした計算は可能である。ただ、その計算結果を量子コンピューターは、2^n個の計算結果の量子状態の「重ね合わせ」として返すのだ。 その計算結果を「現実の世界」に取り出そうとすると（それを量子状態の「観測」という）、2^n個の量子状態の「重ね合わせ」は一瞬にして消え去り、一個の状態だけが観測されることになる。 目の前には、といっても「量子の世界」のことだが、2^n個の計算結果があるのに、それがうまくは取り出せないのだ。 「観測することで、量子コンピューターの2^n倍の計算能力が消えてしまうのなら、観測なんてやめればいいだろう。」 それも実は一理はある。「量子の世界」は、我々人間の観測とは無関係に存在し、運動しているのだから。それはそうなのだが、それは量子コンピューターを走らせても、計算結果を求めないということになる。それでは量子コンピューターの意味がない。 それでは、Shorのアルゴリズムでは、なぜ、2^n倍の高速化を実現できるのだろうか？ まず、Shorのアルゴリズムでは、2^n個の量子状態の「重ね合わせ」を観測しようとしないのだ。 2^n個の量子状態の「重ね合わせ」を生み出す計算は、副作用として、量子の「位相 phase」を微妙に変化させる。これをphase kickbackと言う。Shorのアルゴリズムでは、この位相の変化に注目する。 驚くべきことに、この位相の変化の評価から、2^n個の情報が復元できるのである。フーリエ変換を使う。それは、結果的には、2^n倍の高速化を実現したことになる。 目の前にあるのに使えない、使おうとすると使えなくなるという禅問

【 「ポスト量子暗号」の心理学 】 「量子暗号のあと」を指すものでも、「量子のあと」をイメージしたものでもない「ポスト量子暗号」という言葉は、僕には、少し奇妙なものに思われます。 量子暗号と呼ばれるものは現実的な技術としては存在しません。量子コンピューターは世界中でまだラボの中にしかなく、量子通信の利用者（もちろん実験的）は、多く見積もっても一万人を超えないでしょう。量子の時代は、まだ、始まっていないのです。 では、なぜ、「ポスト量子暗号」という言葉が使われるのでしょうか？ ただ、特に暗号の世界で、「量子」が強く意識されるのには理由があります。それは、「量子コンピュータを使えば、現在の暗号は簡単に破れる」という「Shorのアルゴリズム」が発見されたからです。 その衝撃的な発見から40年が経とうとしているのですが、幸か不幸か、量子コンピュータはいまだShorのアルゴリズムを実行する能力を持たず、多くの人の日常的な意識の中では、暗号技術が危ないという危機意識はほとんど共有されていません。 むしろ、「暗号通貨」や「暗号資産」といった形での暗号を利用した技術への関心は高く、その利用も、かつてなく広がっています。 Shorの警告が風化したという意味では、現在は “Post Shor” の時代です。 ただ、もう一つの "Post Shor" の時代もあります。 暗号資産の未来を謳歌しようとする層に比べて、過去のトラウマを抱えている暗号の世界の専門家の意識は、すこし複雑です。彼らは、しばらくの間ですが、トラウマを癒し克服する確信を見つけられないでいたのです。 現代暗号の理論的基礎が、計算複雑性の理論であることは理解していても、現実に利用されている暗号は、「素因数分解問題」「離散対数問題」にしろ、いずれも経験的に見つけ出されたものでした。 そのいずれもが、理論的には、「Shorのアルゴリズム」の攻撃の射程内にあることを、彼らは、よく知っていました。 かといって、その理論上の脆弱性を現実的な問題として提起するのにも躊躇があったとおもいます。解決策が見えなかったからです。 こうした状況を大きく変えたのは、 Regev でした。 Regev に先行して、Ajitaiは、暗号理論の基礎に、ラティス問題を置くことを提案しました。 Regev は、この道を理論的に飛躍的に

【 双対の世界 】 ラティス問題の複雑性を考える時、重要なアプローチがあります。 それは、あるラティスの双対形 Dual ラティスで問題を考える事です。 少し単純化して言うと、あるラティスの双対形は、元のラティスより目の細かいラティスになります。いくつかのラティス問題にとっては、この性質は役に立ちます。 LWE問題の複雑性を論じたRegevの有名な論文も、この手法の繰り返しにひとつの特徴があります。 ここでは、Dualなラティスについて、基本的なことをまとめました。 -------------------　 動画「Dual ラティス」を公開しました。ご利用ください。 https://youtu.be/zxam-hf1WTM?list=PLQIrJ0f9gMcPtw-6OwIOO2rFKu_A-7OfF この動画のpdf は、こちらからアクセスできます。 https://drive.google.com/file/d/1CgDSoGvIFK2hMNQFT9UiBTwM87gSNKJU/view?usp=sharing セミナーの申し込み受付始めました。申し込みはこちらからお願いします。 https://cipher3.peatix.com/view 「ラティス暗号入門」のまとめページはこちらです。 https://www.marulabo.net/docs/cipher3/ blog 「双対の世界 」のURLはこちらです。　 https://maruyama097.blogspot.com/2022/09/blog-post_23.html

【 電子署名は安全か？ 】 現代の暗号では、公開暗号キー方式と併用して、メッセージが正しいものであることを示すために、電子署名を用います。基本的には、次のようなストーリーです。 Aliceは、自分の送ったメッセージが真正のものであることを示す為に、自分の秘密キーを使って電子署名を行い、それをメッセージに添付します。Bobは、Aliceからのメッセージが真正であることを確かめる為に、Aliceの公開キーを用いて、その電子署名を検証します。 70年代の半ばの現代暗号技術の確立を画するこのストーリーは、とても良くできていて素晴らしいものです。 ただ、このストーリーには、いくつかの前提、この技術が適用される現実についての理想化ないしは単純化された想定が含まれています。 80年代の終わりになって、Goldwasser たちは、現実の複雑さを反映した電子署名の安全性についての論文を発表します。現実の複雑さを反映するということで、彼女らが取ったのは、電子署名への攻撃を詳しく分析するという手法でした。 "A digital signature scheme secure against adaptive chosen-message attacks.", Shafi Goldwasser, Silvio Micali, and Ronald Rivest. SIAM Journal on Computing, 17(2):281–308, Apr. 1988. https://people.csail.mit.edu/rivest/GoldwasserMicaliRivest-ADigitalSignatureSchemeSecureAgainstAdaptiveChosenMessageAttacks.pdf 現実は、複雑なだけではなく、攻撃者の脅威にさらされた過酷なものだということです。 自分が自分であることを他人に証明するのは本当は難しいことです。それが可能となるのは、そのこと以外に、自分と他人との間に、何らかの現実についての「合意」が存在しうるからです。ただ、そうした可能的な合意は無数に存在しうるし、逆に、合意に達することができないことも無数にあり得ます。 電子署名の安全性についての「現実的な議論」が、ある種の社会的ルールづくりに向かうのは、やむを得ない

【 Ajtai とは何者か？ 】 ラティスを暗号に応用するというアイデアを最初に提供したのは、Ajitaiです。 今回のセッションでは、このブレイク・スルーを引き起こした彼に敬意を表して、Ajitaiの仕事を要約してみました、 Ajitai を、僕は「アジタイ」と読んでいたんですが、「アイタイ」と呼ぶらしいことに気づいたことは以前にも書きました。 最近、彼の名前について、もう一つのことに気づきました。(wikiにも注意がありました。) 彼は、Miklós Ajtai という名前で論文を発表しているのですが、彼はハンガリー人です。ハンガリー語では、日本語と同じで、「姓」＋「名」の順に、名前を表記します。ですので、彼のハンガリーでの名前は、Miklós Ajtai ではなく、Ajtai Miklós だということになります。 僕の名前が、不二夫 丸山 ではなく、丸山 不二夫 だというのと同じです。  Ajitai 氏については、もう一つ、失礼なことをしたかもしれません。 彼の写真をネットで探したのですが、実は、間違っていたのかも。間違っていたら、かさねがさね、申し訳ない。 ------------------- 動画「Ajtaiの仕事」を公開しました。ご利用ください。 https://youtu.be/w0gV2xD0jPw?list=PLQIrJ0f9gMcPtw-6OwIOO2rFKu_A-7OfF この動画のpdf は、こちらからアクセスできます。 https://drive.google.com/file/d/1CbsXFBbbmkwF_mLlMNYx53764CknabWQ/view?usp=sharing セミナーの申し込み受付始めました。申し込みはこちらからお願いします。 https://cipher3.peatix.com/view 「ラティス暗号入門」のまとめページはこちらです。 https://www.marulabo.net/docs/cipher3/ blog 「Ajtai とは何者か？ 」のURLはこちらです。　 https://maruyama097.blogspot.com/2022/09/ajtai.html

【  LWE暗号解読の難しさ 】 LWE暗号解読の難しさは、その難しさを「ラティス問題」を解くことの難しさに「還元 reduction 」することによって証明されます。 第一部で、基本的なラティス問題である二つの問題、あるラティスが与えられた時、ラティス上の点で互いに一番近い二点を求める「最短ベクトル問題　Shortest vector problem (SVP)」と、ラティスの点以外の点 xが与えられた時、xに一番近いラティスの点を求める「最接ベクトル問題　Closest vector problem (CVP)」を紹介してきました。 このセッションでは、それらに加えて、いくつかのラティス問題を紹介します。 これらの問題は、次元が高くなると一般には解くのが難しくなります。その難しさは、計算複雑性の「複雑性」で定式化できます。 ここではラティス問題の複雑性を概観しようと思います。 ある種のラティス問題は、最も難しいNP-困難のクラスに属することがわかっています。また、ある種のラティス問題は、多項式時間で解けることもわかっています。ただ、今回のセミナーでは、さまざまなラティス問題が属する複雑性について、詳しく述べることはできません。 今回のセミナーでは、基本的に、ラティス暗号LWEが、どのようにラティス問題に「還元」されたかにフォーカスできればと思います。この還元を初めて行って、LWE暗号の解読の難しさを理論的に証明したのが、Oded Regev です。 トリビアです。 今回紹介した ラティスL のゼロでない最小のベクトルの長さを表す λ(L) について基本的な定理を定式化したのは、ミンコフスキーです。アインシュタインに数学の手ほどきをし、「ミンコフスキー空間」にその名を残している、あのミンコフスキーです。 僕は、ラティス暗号の勉強を始めるまで、ミンコフスキーがラティスの理論でも重要な貢献をおこなっていること、全く知りませんでした。　 ------------------- 動画「ラティス問題と複雑性」を公開しました。ご利用ください。 https://youtu.be/bCCEwYInPeQ?list=PLQIrJ0f9gMcPtw-6OwIOO2rFKu_A-7OfF この動画のpdf は、こちらからアクセスできます。 https://drive.google.co

【 公開キーから漏れる情報？ 】 公開キー暗号は、暗号の歴史の中で、最も重要な発明の一つです。暗号を解読するためには、暗号のキーが必要なのですが、そのキーをどうやって安全確実にかつ秘密裏に通信相手に届けるかは、とても重要な問題でした。 公開キー暗号方式は、大胆にキーを公開します。もっとも、公開されるのは、キーの一部です。もう一方のキーは秘密キーとして、各人の責任で各人が管理します。公開キーは、誰に知られてもいいという前提ですので、キーの配布・共有の敷居は格段に低くなります。 秘密キーと公開キーの二つが揃って、初めて、公開キー暗号のシステムは機能します。その辺りは、みなさんよくご存知だと思います。 ポスト量子暗号と呼ばれる一群の暗号システムも、公開キー暗号方式を利用します。この間取り上げている、ラティス暗号LWEも、公開キー暗号のシステムです。 ただ、量子暗号の世界でよく知られているBB84というシステムは、量子の働きを使って暗号のエンコード・デコードをするのではなく、量子の働きを使ってキーを配布するプロトコルです。量子通信が一般化する未来では、暗号システムにとって重要なキー配布のスタイルは、今とは違うものになるのかもしれません。 公開キーについて、一つ注意したいことがあります。それは、公開キーというのは、誰に知られても構わない、どうでもいいデータでは決して無いということです。 少し単純化していますが、現在の主要な暗号技術であるRSA暗号では、大きな二つの素数 pとqを掛けた数nを公開キ ーとします。（正確には、もう一つの数 eを選んで、{e, n}のペアが公開 キーになります。）公開キーを作った2つの素数 p, qは、暗号文の復号に使用する秘密鍵 s の生成にも使用されます。（ s = 1/e ( mod (p-1)(q-1) )　） 要するに、公開キーには、重要な情報が含まれているということです。 公開キー暗号の公開キーは、そこから情報が漏れ出さないように設計されなければなりません。RSA暗号の場合には、公開キー（の一部）n が与えらても、それを因数分解して、素数pとqを得ることが、実際には難しいことが利用されています。 公開キーは、誰の目にも触れるものですので、攻撃者の最大のターゲットになります。公開キーの設計には、その暗号化技術のエッセンスが表現されています。