自然言語処理で暗号文生成

テキスト秘密分散　Text Secret Sharing
山村明弘 滝澤修 独立行政法人通信総合研究所
SCIS 2002 The 2002 Symposium on Cryptography and Information Security

1 はじめに

複数のメンバーが分散して保有する情報を合わせた場合にのみ秘密情報を復号できる秘密分散法（secretsharing）[How to share a secret][Safeguading cryptographic keys]の一つの実現形態として、
Naorら[Visual Cryptography]によって提案された視覚復号型秘密分散法（Visual Cryptography)は、計算機を使わず人間の視認によって復号可能な新しい暗号として、研究や実用化が進められている[視覚復号型秘密分散法の拡張構成方式][積み重ね順序を鍵とする視覚暗号方式]

つまり、鍵なしで複合復号する暗号です。

ところで有史以来の古典的な暗号は、自然言語テキストを対象とするものがほとんどを占めていた。画像におけるピクセルに対応するのは、自然言語テキストの場合は文字である。
しかし自然言語テキストを情報隠蔽媒体とするに
は、文字コードには冗長性が全く無く　また言葉は意味をもつことから、情報を隠蔽するために文字を改変すれば僅かな改変でも露見してしまう難点がある。そのため、画像におけるピクセル単位の操作のような方法は文字には単純には適用できない。
また自然言語テキストは、画像等の他の媒体と比べて情報量が少ないため、隠蔽できる情報量も少なく、実用的に不十分な場合が多い。
そのため、自然言語テキストを情報ハイディングや秘密分散などの情報隠蔽媒体とする研究は、一部の例外を除き、あまり多く見られない。

しかし、マルチメディア化が進んでいる現代においても電子メールなど自然言語テキストでの情報交換は主流の位置を占めており、情報伝達手段としての自然言語テキストの重要性は今後も変わらないと考えられる。
従って自然言語テキストを情報隠蔽媒体として扱う暗号法には、多くの応用が期待できる。そこで本稿では、自然言語テキストを情報隠蔽媒体とする秘密分散法（Text Secret Sharing）の実現の可能性について検討し、一つの簡単な方法を提案する。

2 テキスト秘密分散の考え方

テキスト秘密分散法は、秘密テキスト(secret text)を複数の分散テキスト(share text)に分散して隠蔽し、テキストを“重ね合わせて”秘密テキストを復号するもの、と定義できる。視覚復号型秘密分散法では、分散画像はノイズのような無意味画像が使われることが多い。
従ってテキスト秘密分散法の場合も分散テキストが無意味な文字列であっても構わないが、
そうすると秘密分散を使っていることを見抜かれる懸念があり、
それは既に脅威となりえることなので、自然言語処理的な工夫により、できるだけ自然な文にすることが望ましいといえる。

これが、重要なのです。
秘密が存在していることに気づかれたら、
その秘密はもうバレたも同然...ということです。

（方法１）
分散テキストを複数枚重ね合わせて、一致している文字を拾い読みすると、秘密テキストになっているようにする方法が考えられる。図１にイメージを示す。


この方法は、文字をイメージとして扱っている点で、視覚復号型秘密分散法の一種に位置づけることができ、視覚復号型秘密分散法のように視認で復号できる特長がある。

※画像でもこのような技術はありますが

凸版印刷、2枚のシートを重ね合わせると隠れた文字や画像が現れる
「あわすとでーるネオ(R)」のオンデマンドプリンタへの対応を実現

（方法２）
複数枚の分散テキストを重ね合わせて、冒頭文字の位置を合わせ、1 文字目を上層から下層、2 文字目を上層から
下層、…に順次並べていくと、その文字列の中に秘密テキストが現れるようにする方法が考えられる。図２にイメージを示す。

暗号文はこういう感じ

「最近は、本来の電離層を介する伝搬よりも、むしろ宇宙通信に対して電離層が与える影響に関する研究の方が活発になっている傾向がある。
もっとも内側の太線の円は衛星軌道を地球上に投影したものを表わすと同時に半径方向の臨界周波数目盛の０ＭＨｚを示す。」

「この現象は雷放電による電波が電離層上部の多種類のイオンと作用し、特に重水素イオンと共鳴作用をすることによって生じたものと考え、これを重水素ホイッスラと呼ぶことにした。
卒直に言って、当所は一般へのＰＲという面で、その施策が不十分であったと認めざるを得ない現況である。」
..............

（方法２）よりも（方法１）の方が暗号文の量も少なく、また複合方法も簡単に済みそうですが
（方法２）で暗号文を生成したほうが、暗号文が多く不自然に感じられるかもしれませんが...



（方法２）は具体的にどうやって作るのかというと




自然言語テキストを用いた秘密分散法
山村明弘 滝澤修 独立行政法人通信総合研究所
情報処理学会論文誌 45(1), 2004

秘密テキストEとは、文字列＜e1,e2,...,e_ε ＞から成る順序集合と定義する。

テキストデータベースDは、テキストの集合{ T1,T2....}とする
Dの一要素Txは、文字列＜tx1,tx2,...＞から成る順序集合とする。


１　秘密文字を含むテキストをデータベースから抽出

１≦i≦ε であるすべてのiについて、文字eiを要素に含むテキストTxiを、Dから選ぶ
そして、ei＝t_xi,zi（∈Txi）とする

その結果、
＜e1,e2,...,e_ε ＞
≡＜ t_x2,z2 , t_x2,z2 , ... t_x2,z2 ＞
となる。


２　文字数合わせ処理

次に、
Twi＝＜ t_wi,1 ,t_wi,2 ,...t_wi,yi ＞
であり、

y1+z1 = y2+z2 = ... = yε+zε
（そして、この値をjとする）

を満たす{Twi}(∈D,1≦i≦ε)を、Dから選ぶ
ただし、各Twiは1文またはそれ以上とする。


３ 分散テキストの合成

分散テキスト ＜S1,S2,...Sε＞を、

Si=＜Twi,Txi＞

とする。

TwiとTxiを結合したものを分散テキストSiとする。



以上の処理の原理は、 1≦i≦εのすべてのiについて、Siのj番目の文字がei(=t_xi,zi)
となるように{Si}を合成するものである。
{Twi}は、文字数合わせのためにのみ挿入されることになる。



４ 秘密テキストの抽出

本論文では、暗号化だけでなく複合化も電子計算機で自動で出来ると述べています。
縦読みしたとき、
その文字列が形態素の並びとして尤もらしいかどうかを計算する...という方法です。







秘密分散法の方が分かりやすく簡単ですが、
個人的にはアナグラム暗号の方が面白そうですが.........






引用とアナグラムによる物語生成に関する試論
土橋賢　日本インフォメーション
小方孝　岩手県立大学
人工知能学会全国大会　2009

1. まえがき―問題意識と目的―

広い意味でのアナグラムは，様々な文学作品の中で利用されている．延原謙によって訳された『グロリア・スコット号』(『シャーロック・ホームズの思い出』に収録)では，

「万 雉の 静穏なる 事 ロンドン 市の 休 日の 如く ハドスン 河の 上流は 凡て 雌雉 住むと 語れり 蠅取紙の 保存は 生命 ある もの を 危険 なる 状態より 直ちに 救いて よく 脱出せよ．」

と
いう暗号文がある．これは語と語の間に分解された語が潜んでいる手法が使用されており，先ほどの文を2 語ずつ飛ばして読むと

「万事休す．ハドスン凡て語れり．生命危険，直ちに脱出せよ．」

となる．






アナグラムでは，自然言語による表現の中に別の表現が存在する．
また間テクスト的な物語生成では，複数のテクストの諸要素が組み合わされることで，複合的な物語が生成されると考えられる．
そこで本研究では，このふたつ（アナグラムとしてはアクロスティック）を組み合わせたシステムを試作することで，物語の表現の複合に接近してみようと考えた．
以下，既存の小説からの文の引用によって物語を作り，且つその中の各文の冒頭の語をつなげると意味のある単語や単文になるという，試作システムを示す．






2. システム


まず，ユーザが潜ませたい文字列と，使用する物語の「機能」に対応する番号を入力し，それらをもとに文を検索する．
ここで機能とはプロップの昔話形態学[Propp 1969]における概念で，物語の統語規則に沿った行為系列の種類を意味する．

第一のフェーズである，
......

文の検索処理は次の
手順で行う―
①ユーザが設定した潜ませたい文字列から一文字を抽出する．
②ユーザが設定した機能に対応する文を，検索キー(動詞)をもとにファイルを検索する．
③検索された文の読みの一文字目と手順①で抽出した一文字が一致したらその文を選択する．
なお各機能についてひとつの文のみを現在は検索している．
以上の処理を入力した文字列中の文字数だけ繰り返し，最終的に決定された複数の文が次の変換処理の入力となる．
なお，プロップにおける各機能にひとつの文を対応させるため，潜ませることが可能な文字数は機能に補助的機能ひとつを加えた32個となる．





第二のフェーズである

名詞の変換処理は次の手順で行う（図3）―
①処理対象となる文について，構文解析の結果得られた京大テクストフォーマットから，名詞の中で最後の動詞に係っているものを抽出する．
②名詞の次の単語を調べ，それが助詞であれば，作成した「サンプルDB」（各機能を表現する構文に沿って，その構成要素に入るべき情報のタイプを設定したデータ）における対応する機能のサンプル文を参照し，名詞の部分を助詞が一致する要素に変換する．
対象が複数ある場合は，そのすべてを変換する．また場合によっては原文中の名詞を，生成する文章における固有名に設定する．
③変換された要素名の部分を，作成したデータベースを利用して固有名に変換する．




3. 実行結果の評価


個々の文の名詞変換処理については，単文の場合，条件1に関しては79％，条件2 に関しては95％の文で修正の必要がなかった．複文の場合は，大部分で係り先が文末ではない名詞（名詞句）の修正が必要となった．

また，一貫性の感覚に関する定量的な評価は行っていないが，筆者らの主観的な印象では，選択する機能数が多い程，一貫性がよりあるように感じられた．

暗号文はこういう感じ

今度はイワンはヨーロッパの宮廷に仕事に出かける．そこでイワンは王女に出会った．王女は蛇に誘われていた．こうイワンは王女に毒薬のことをたずねました．真面目な王女がイワンに答えた．「ではさっそく，宮廷へ毒薬を買ってあげる．」 かっこいいイワンはマルセイユの領事館で王女に毒薬を買ってもらった．イワンは蛇に毒薬を飲ませた．蛇は怒った．部外者の蛇は王女を奪う．老婆はそのことを知った．かっこいい老婆はナポリ，ローマ，ミラノ，ヴェネチア，フィレンツェ，ロンドン，それからパリでも嘆きの歌を歌いました．几帳面なイワンはその時にはもう大体王女の奪還を決めていた．かっこいいイワンは，イワンの国の宮廷を出立しました．イワンは老婆を誘いました．主人がそれを断りました．「いかん？そりゃ困る．」 力持ちのイワンは老婆を助けました．字引きをイワンは老婆から受け取った．まず老婆と字引きは二人で蛇の国へイワンを案内した．使いっぱしりの蛇ともイワンは戦います．いかしたイワンはとうとう蛇に勝った．王女は嘆きの歌を歌っていた．背の高いイワンはこうした王女の悲しい状況を救った．几帳面なイワンはイワンの国へ着いた．王女は喜んだ．蚊帳の内にも王女は飛んでいた．笑い上戸のイワンは一人の母のお供で小さい息子と岩に隠れている．いよいよ十二月八日，イワンが宮廷に到着した．