第９４号コラム： 辻井 重男 会長 （中央大学 研究開発機構 教授）
題：「現場レポート 暗号研究から電子政府構築まで 」
目次
Ⅰ部
１ ２０１０年１月 高松から
２ 暗号の２０１０年問題とは —— 朝日新聞記事から
３ 日本発祥の多変数公開鍵暗号の研究現場から
４ 国際会議PQC２０１０から － 量子コンピュータ時代の暗号
５ 創る人と批判する人
５．１ 哲学の場合
５．２ 暗号の安全性検証
６ ヒルベルト的世界観からゲーデル・ブラウアー的世界観へ
Ⅱ部
７ 電子政府の構築へ向けて
８ 矛盾の超克――国民安心番号とプライバシー
９ ２０１０年４月、韓国の電子政府を訪ねて
１０ ２０１０年５月１９日 韓国の先進事例に学ぶシンポジウムから
１１ 文理軸―理念・現実軸の平面上で考える人材育成
１ ２０１０年１月 高松から
今年の１月１９日から２２日にかけて、毎年恒例の「暗号と情報セキュリティシンポジウム、SCIS２０１０」が、四国高松で、約６００名の参加者、３００件余りの論文発表という活況の下に開催された。１９８４年、今井秀樹横浜国大教授（当時）の企画により、浜名湖で旗揚げしたときの参加者は６０余名、論文数は３５件位であったから、２７回目の今年は、不況にも拘らず、発足当初の約１０倍ということになる。筆者、及び、筆者の研究室からも研究発表を行った。
内容的にも大きな変化が見られる。発足から１０年位の間は、暗号理論研究が主であった。インターネット元年と言われる１９９５年以前は、情報セキュリティが実感をもって語られる状況ではなく、情報セキュリティと暗号は同義語に近かったが、今年のシンポジウムは、図１（IDFのURL参照、他の図表も同様）に示すように、セキュリティポリシーにまで及ぶ広い範囲について活発な議論が展開された。一口に暗号理論・技術といっても、今や多くの専門分野を擁し、国際的にも、それぞれ特徴を有する各種のシンポジウムが毎年、世界各地で開催されている。
会期中、特許庁とその委託を受けている富士通（株）の下山氏等から、暗号と特許に関するヒアリングを受けた。また、毎回、企業などの展示も行われているが、今回は、ある方が米国のオークションで入手されたナチスドイツの暗号機「エニグマ」を筆者が譲り受けたので、特別展示して多くの方に動かして頂いた。
２ 暗号の２０１０年問題とは—–朝日新聞記事から
現在、普及している公開鍵暗号は、RSA暗号、及び楕円暗号である。これらの暗号は、多くの暗号研究者による２０年～３０年に及ぶ解読攻撃に耐えて、その安全性に対する信頼を獲得し、電子社会を支えている。２０１０年、１月２４日の朝日新聞には、「ネット暗号に２０１０年問題、次世代規格への対応難題」と題する記事が大きく掲載されたが、少なくともRSA暗号に関しては、理論的（アルゴリズム的）な面での本質的な安全性が低下している訳ではなく、コンピュータの進歩に追随するために、鍵長を大きくする必要があり、そのための、コストなどが、電子政府や産業界で問題となっているということである。
この点について少し解説しておこう。RSA暗号は、素因数分解という数学的問題が難しいという仮定の下に構築されている。７１×９７＝６８８７は簡単に計算できるが、逆に、６８８７を７１と９７の積に分解することは難しいということである。この程度の桁数（４桁）なら中学生でも出来るが、現在使用されているRSA暗号の桁数（鍵長）は約３００桁（１０２４ビット）である。約１５０桁の２つの素数を掛け合わせた合成数の桁が約３百桁と言う訳である。２つの素数を掛ける計算は、容易に出来るが、素因数分解は、この位の桁数になるとスーパーコンピュータでも多くの年数を要すると見積もられている。しかし、３年で４倍というムーアの法則による半導体の進歩をベースに、コンピュータの速度も速くなる。総務省と経済産業省の下に、電子政府での使用する暗号方式の候補を選定するために設置されている、CRYPTRECと呼ばれる委員会の見積もりでは、２０１５年には世界トップレベルのスーパーコンピュータを用いれば、約１年で素因数分解可能と見積もられている。従って、２０１４年までには、鍵長を、２０４８ビットにすることを、CRYPTRECは、各省庁、自治体に勧告しているのである。
筆者も記者から質問され、情報資産の価値や、暗号更改に掛るコストなどとの兼ね合いで、一概には言い難いのだが、早めの対応が望ましいとコメントしておいた。
３ 日本発祥の多変数公開鍵暗号の研究現場から
さて、RSA暗号や、楕円暗号以外の公開鍵暗号は考えられないのだろうか。人類史上、火薬の発明にも劣らない画期的は発明とも言われている公開鍵暗号の概念が提案された１９７０年代以降、RSAに続いて、ナップザック暗号、誤り訂正符号応用暗号、多変数公開鍵暗号など多くの具体的な公開鍵暗号方式が提案され、それらの安全性を廻って研究が深められているが、十分な信頼感を持たれる実用的な方式は未だ提案されていない状況である。
これらの中で、現在、筆者の研究室で取り組んでいる多変数公開鍵暗号を例にとって、暗号の安全性をどのように考えたらよいか、専門外の方にも理解して頂けるよう、説明してみよう。
誰でも、中学や高校で勉強したことを覚えておられる筈の連立方程式を思い出して貰いたい。線形連立方程式の場合は容易に解けるが、高次連立方程式になると、その解を求めるのは、NP困難という難しい問題になる。これを公開鍵暗号の構成に利用するのが多変数公開鍵暗号である。次数を大きくするに従って、鍵の長さが非常に長くなるので、通常、２次の多変数公開鍵暗号を対象としている。変数xを平文に、yを暗号文に対応させると、方程式にxを代入してyの値を定めることは容易だから、平文から暗号文を作成するのは簡単である。従って、ある多変数多項式を公開鍵として公開しておけば、誰でも、暗号文は容易に作成できる。しかし、平文に戻すことは難しい。受信した暗号文（yの値）から平文（xの値）を求めるには、方程式を解かねばならないからである。このような対応関係を１方向性と呼ぶ。RSA暗号の場合は、２つの素数を掛け合わせるのは容易だが、その逆の素因数分解は難しいという１方向性が利用されている。
このように、公開鍵暗号の構成には、何らかの１方向性関数が必須である。しかし、単なる１方向性関数では、解読者（攻撃者）が解読できないのと同様に、複号者、即ち、正規の受信者も受け取った暗号文を平文に戻せないことになる。これでは暗号にならない。暗号方式構築の難しさと面白さは、解読者と複号者の間に、如何に大きな情報格差を埋め込むかにかかっている。このような情報格差が埋め込まれた１方向性関数を、落とし戸付き１方向性関数と言う。RSA暗号の場合は、正規の複号者は（実際にはICカードなどが）２つの素因数を知っているということが情報格差となっている。
多変数多項式にどのような落とし戸を埋め込むか。その研究は、１９８３年頃、横浜国立大の今井研究室（当時）、続いて、８４年、東工大の辻井研究室（当時）において始められた。
松本、今井によるは、国際的には１９８８年、EUROCRYPTにおいて発表され、現在も多くの文献に引用されており、MI暗号と呼ばれている。Patarinは１９９５年、MI暗号を解読し、翌９６年、MI暗号を拡張し、HFE暗号と呼ぶ方式を提案した。HFE方式は、複号時間などを厳しく設定しなければ、パラメータ設定によっては、現在も生き残っていると言える。
他方、筆者は、東工大時代、回路理論の順序解析からヒントを得て、１９８５年、順序解法暗号と名づける多変数公開鍵暗号を提案した。これは、８７年、金子らによって解読された。順序解法型暗号は国内の学会論文誌に日本語では発表したものであるが、海外では、１９９３年、Shamir等が、同様の方式を署名に利用した方式を国際会議CRYPTOにおいて提案し、CopperSmithにより、解読されている。筆者等は、１９８７年、順序解法暗号を改良した方式を、やはり国内学会誌に掲載し、２００４年、只木による英訳を、IACRのe-Printに登載した。これは、２００８年、Dingによって、国際会議「量子コンピュータ時代の暗号」で、その解読法が発表されている。
その後、我が国では、笠原等によって、順序解法を一般化した方式が提案されているが、２０００年前後から、国内より、海外で研究が活発に展開され、表１に示すような多様な提案がなされている。
多変数公開鍵暗号には、２つの目的がある。
（１）暗号化・署名、複号・検証の高速化への期待
RSAは、べき乗計算が必要なため、暗号化・署名、複号・署名検証を高速に行えないという欠点がある。そこで、多変数公開鍵暗号により、高速な暗号方式が実現できないかという期待がある。MI暗号を署名に応用したS-Flashという暗号があり、その高速性を評価されて、ヨーロッパの標準(NESSIE)として採用されたが、２００７年、シャミアによって、解読されている。
（２）量子コンピュータの出現に対抗できる公開鍵暗号の候補としての期待
１９９４年、RSA暗号や楕円暗号は、量子コンピュータが実現できた場合には、解読されることが示された。量子コンピュータの実現がいつになるか、予想し難いが、現時点で、CRYPTRECにより次世代暗号を選定するに当たって、考慮する必要があるほど、早い時期ではないことは確かであろう。
４ 国際会議PQC２０１０――量子コンピュータ時代の暗号
一口に暗号といっても、専門分野や地域など、多岐に亘る国際会議が毎年、いくつも開かれている。主な国際会議を列挙すれば、表２の通りである。
小文では、筆者がプログラム委員を務めているPQCrypt（Post Quantum Crypt）について紹介しておこう。上に述べたように、量子コンピュータの実用化は近い将来ではないにしても、その出現に備えておく必要はあるだろうということで、２００６年以来、隔年開催されている。２０１０年は、５月２５日から２８日にかけて、ドイツのダルムシュタットで開催される筆者もプログラム委員を務めている。RSA暗号、楕円暗号などのように素因数分解や離散対数問題に依拠せずに、NP困難問題に基礎をおく多変数公開鍵暗号、格子暗号、誤り訂正符号応用暗号、ナップザック暗号などの公開鍵暗号が主な対象となっている。量子物理系暗号や無線通信においてインパルスレスポンスを共有する通信方式暗号との混乱を避けるため、「量子コンピュータ時代の暗号に関する国際会議」と呼ぶこととする。
５ 創る人と批判する人
５．１ 哲学の場合
専門外の方にとっては、馴染みのない話が続いたので、話題を哲学の世界に転じよう。暗号の問題を考えるのに、大哲学者を引き合いに出すのは気が引けるが、私が胸を打たれた逸話を紹介しよう。西田幾多郎は、終戦直前の１９４５年（昭和２０年）６月、７５歳の生涯を終える１週間ほど前に書き残した日記に「私の論理と云うのは学界からは理解せられない。否、一顧も与えられてないと云ってよいのである。・・・」と述べている。西田幾多郎の悲哀に満ちた人生を象徴にするような話で、ジーンとさせられる。しかし、西田幾多郎は、我が国では、自分の哲学を創った数少ない一人であり、その哲学は西田哲学と呼ばれて、今なお海外でも評価されているようだから、一顧も与えられてないどころではないのだが、後継者の田辺元をはじめ多くの哲学者から、批判を受けたこともよく知られている。左右田喜一郎も、西田の思想を初めて西田哲学と名づけた上で、厳しい批判を展開している。しかし、それらの批判は、勿論、西田の思想を評価すればこそのことであった。創る人がいなければ、批判する人もいないのである。
哲学に限らず、小説、演劇、絵画など、創る人と批判する人が切磋琢磨して、新たな展開があることは言うまでもない。
５．２ 暗号の安全性検証
さて、暗号理論の場合はどうだろうか。もう、２０年も前のことになるが、あるシンポジウムで、暗号の現状について話したとき、ある出席者から、「暗号って、解きつ解かれつで、酷い事になっているのですね」と言われて参ったことがある。この拙文を読んでおられる方も、上に述べた多変数公開鍵の展開を見てそのように感じられたかも知れない。暗号の歴史は、確かに解きつ解かれつの繰り返しであった。
上記の、エニグマも、ナチスドイツは、解かれないという自信があったのだろうが、天才数学者チューリングが率いるグループによって解読され、それによって、敗北寸前の祖国イギリスが救われたのみでなく、世界の歴史も変わってしまった。
１９７０年代に始まる現代暗号理論では、解きつ解かれつは極力小さくし、可能な限り厳密な安全性証明に基づいて方式を構成しようということが、我々暗号研究者の、いわば申し合わせになっている。そのことをRSA暗号について考えてみよう。量子コンピュータが実現されると素因数分解が可能になると述べたが、現在のコンピュータでも、不可能である（大きな桁数の場合）という証明は出来ていない。しかし、素因数分解は、ギリシャ時代以来、考察されてきた問題であり、特に、RSA暗号の提案以来、約３０年に及ぶ、多くの研究者による探求にも拘らず成功していない。そこで、暗号研究者達は、「現在のコンピュータでは、素因数分解は不可能である」と仮定しているのである。更に言えば、「素因数分解以外に、RSA暗号を解く手段はない」ということも証明できていないが、この問題も、多くの研究にも拘らず、素因数分解以外に、RSA暗号を解く手段が発見されていないことから、一般に「素因数分解以外に、RSA暗号を解く手段はない」と仮定している。これをRSA仮定という。
さて、このような仮定の下では、例えば、「解読攻撃者が、様々な暗号文（解きたい暗号文以外の）に対応する平文を数多く得られたとしても、攻撃者は目的とする平文を得ることは出来ない」ことが、ある安全性モデルの下で、背理法を用いて厳密に証明されている。このように、広く信じられていることを仮定した上で、厳密な議論を展開するのが、有力な暗号研究手法の一つとなっている。 しかし、多くの場合、如何なる未知の攻撃に対しても、安全であるという証明を付すことは難しい。そこで、新しい暗号方式を提案する場合には、少なくとも、既知の攻撃法の全てに対して安全であることを証明することが要請されている。共通鍵暗号の場合には、十指に余る攻撃法が知られており、それらの全てについて、鍵の総当りの計算量より、各攻撃に要する計算量が大きいことを証明することが出来なければ、CRYPTRECの候補となることは出来ない。鍵の総当り回数は、鍵の長さが１２８ビットであれば、２の１２８乗回（約１０の４０乗）となる。そのような意味で安全性が保証された上で、暗号化・複号に要する速度や実装性の良さが問われる。
多変数公開鍵暗号に関しては、共通鍵暗号ほど多くの攻撃法は知られておらず、代表的な攻撃法は３種類程度であるが、上に述べた、シャミアはS-flashについて考察した論文において、
「多変数公開鍵暗号に関しては、未だ数学的構造が十分解明されていないから、安全性が厳しく問われる用途に使うべきではない」
と述べているが、筆者も同じ考えに基づいて研究を進めている。高速性や効率性よりも、先ずは安全性に十分は信頼が置ける方式を追求すべきである。筆者等が、上記のPQC２０１０に応募して、採択された方式も、順序解法型公開鍵暗号を抱き合わせた強化型STS構造とし、既知の攻撃法を含めて安全性を確認し、査読者の信頼を得たようである。
提案者の心理vs解読者の心理
筆者の経験から言えば、自分が考案した方式は、解読されないと信じたい気持ちが強く働き、安全性についてチェックはしても甘くなりがちである。従って、先ずは、同じ研究者グループ岡目八目的批判と検証が必要である。仲間に解読され、改善策のアイデアが浮かぶのは、先ずは提案者であり、解読した仲間ではないことが多い。その理由は
（１）自分の生んだ子は可愛い。たとえ、医者が見離したとしても、何とか育てたいと思って提案者は夜半目覚めても考え続ける。解読者は、同じ仲間でも、提案された方式に、それほど愛着は感じないから、解読した後、考え続けないことが多い。
（２）暗号の分野でも、創るのが好きで得意な人と、批判し、解読するのが性に合っている人に分かれる傾向がある。両方に能力のある研究者も勿論いるが、そのような人も、提案する時と解読する時とで、（１）のように心理状態が異なる。
従って、大きな組織であれば、提案者グループと解読者グループに分かれて、方式構成を進めるのが望ましい。１９７０年代、DESが提案されたときは、IBM内でそのような体制がとられたと聞いている。１９９０年頃、シャミア等により、発表された差分解析法は予想していたが、それにより解読されるまでには、可なりの年月を要すると判断していたと仄聞している。しかし、１９９３年、松井により考案された線形解析法については予想していなかったようである。いずれにしても、DESは２０年以上に亘って、歴史的役割を果たした。
仲間内、あるいは組織内で充分検証した後、学会で発表し、批判をうけるという順番になる。提案された方式について、解析あるいは解読する場合、間違うことは少ないから、安定した精神状態で発表できるので、得な立場である。他方、解読者は、良いアイデアの萌芽見られる提案方式に対しては、それを抹殺しないように記述・表現に注意が必要である。
他の研究分野であれば、その成果は、６０点位から９０点位にばらつくことが多い。しかし、暗号の場合は、合格点か、零点になると考えられるかも知れない。提案者もそのように感じて落ち込んでしまうことも少なくない。しかし、現在、内外から発表されている多変数公開鍵暗号の多くは、MI暗号、あるいは順序解法型暗号を源とする二つの流れに集約される。従って、提案される暗号に対しては安全性と合わせて、アイデアの斬新さも評価されるべきであろう。
６ ヒルベルト的世界観からゲーデル・ブラウアー的世界観へ
多変数公開鍵に関するある論文の中で、J. Ding 等は，下記のように述べている：
“We stress that it is still an original sin that no list of possible attacks can be exhaustive”（文献）
この表現は，ゲーデルの不完全性定理を連想させる．この定理を物理学者オッペンハイマーは「人間の理性の限界を示すもの」と評したが，筆者は、むしろ，「自然の摂理を人間の理性が解き明かしたもの」と解釈すべきであろうと考えている。
我々の対象としている暗号は自然科学なのだろうか。多くの（特に欧米の）自然科学者は、神は自然を矛盾なく創っている筈であるという信念に基づいて、仮説検証を進めつつ学問を構築している。
数学はどうだろうか。数学的世界は、無矛盾・完全であると一般には思われている。しかし、１９世紀末から２０世紀前半にかけて偉業を成し遂げた大数学者ヒルベルトが、同じケーニヒスク生まれで尊敬していた哲学者カントの影響もあったのか、数学は無矛盾・完全であるという信念の下にヒルベルト計画を推進し、１９３０年、ある授章式での「自然認識と論理」と題する記念講演を「我々は知らねばならない。知るであろう」と言う有名な言葉で結んだことは良く知られている。しかし、数学史も、時として皮肉なドラマを生む。その直前、ある学会で、ヒルベルト学派による数学の形式化という手法を忠実に実行したゲーデルが、ヒルベルトの予想を裏切る結果、即ち、「決定不能な数学的命題の存在」を証明したことはヒルベルトには伝えられていなかった。決定不能な数学的命題の存在とは簡単に言えば、真であるとも偽であるとも証明できない問題があると言うことであり、ゲーデルの不完全性定理として知られている。
これは、ギリシャ時代以来の自己言及の矛盾（あるクレタ人が、「クレタ人は皆嘘つきである」と言ったというような）に淵源が見られる特異なケースであって、現在でも多くの数学者は、「ゲーデルの不完全性定理など辺境地帯の国境紛争くらいにしか見ていない」（数学者ワイル）のは事実である。
しかし、数学者と違い、暗号技術や情報システムの研究者・技術者は、ゲーデルの定理自体ではないが、それを連想させるような矛盾、即ち、正しいのか正しくないのか、人間には不明な難問を抱えながら、現代社会の安全性を高めていかねばならないと言う宿命を背負っている。
我々は、神の無矛盾性を信ずるわけにもいかず、さりとて、ゲーデル（的なるもの）など知るものかと無視するわけにもいかない状況の中で、安全と強く信じられる暗号を設計しなければならない。上に述べたように、部分的には、数学の定理のように、厳密な証明を付すことが出来るが、耐タンパー攻撃まで含めれば、自然科学のように、PDCAサイクルをまわしながら、暗号技術の信頼感を高めていく他に道はない。（以下、Ⅱ部に続く。）
【著作権は、辻井氏に属します。】
