山口和彦研究室
情報学専攻・Ⅱ類
場所東３号館 ９階 居室919号室
研究室911号室他
研究内容 「雑音や不正からの情報保護」をキーワードに 、
雑音からの情報保護「誤り訂正符号」の研究、著作権保護にも用いる「電子透かし」、「電子指紋（処理追跡）・結託耐性符号」等のセキュリティ技術などの研究を行います。
■
昨年度の誤り訂正符号に関する研究抜粋
ü
信頼度を考慮したq 元線形符号における誤り検出率と復号アルゴリズム
（誤り訂正符号の代数的な構造（仕組み）は暗号分野のアルゴリズムと密接な関係がたくさんあります。この研究は詳細な性能評価法の提案とそれにより新しい誤り訂正のアルゴリズムができることを示しています。）
ü
数独による誤り訂正符号の理解についての研究
（数独パズルは消失通信路での復号の問題と捉えられます。誤り訂正符号を理解するのに役立つ研究です。）
■
昨年度電子透かしに関する研究抜粋
ü
堂浦による二値画像用電子透かし手法の検証及び検討
（電子透かし技術は既に様々なところで用いられているセキュリティ技術です。暗号と異なりアルゴリズムを公開しすると削除や、改ざんなどの不正が容易になるのであまり知られていません。画像・音声などのコンテンツタイプに応じた方式の検討が必要な点も課題です。二値画像は白黒で濃淡の無い画像でちょっとした変更も目立つため、透かしの埋め込みは工夫が必要です。）
ü
Tardos 符号のスコア分布特性を考慮した閾値最適化
（結託耐性符号は利用者のIDを埋め込むタイプの電子透かし技術です。複数人での不正を防止する方式の研究です。）
■
もう少し丁寧な解説
ü
誤り訂正符号とは
誤り訂正符号はみんなが使っている携帯・スマホ（通信分野）だけでなく様々な分野で利用されています。ハードディスク、CD、DVD、BDなどの記録メディアでは、開発された年代により異なる誤り訂正方式が用いられています。皆さんにも身近な商品についているバーコードには誤りを訂正することはできませんが奇数個の誤りは必ず検出できる様になっています。よりたくさんのデータを保持しているQRコードは訂正できる誤りのレベルを設定できるようになっています。新しい通信システムではそれにあった方式を検討する必要があります。誤り訂正符号は誤りを取り除くため、代数的な性質を利用します。その性質は、暗号の設計や解析などとも関連しています。
図 バーコードは読み取ったデータの誤りの検査、QRコードは誤りの訂正が可能になっている
ü 数独パズルと誤り訂正符号
「数独」 、「ナンプレ」などとも呼ばれるパズルを解くことは「誤り訂正符号の誤りを訂正すること」とに対応しています。
数独の答えは670903752021072936960≒6.671×1021
あることが知られていますが、「数独の問題」は、数独の答えの一つを送信したものを受信したときに、一部の数字が消えたという「誤り」と捉えられます。「数独パズルを解く」ことは、空白を含んだ受信データから、元のデータを復元する「誤り訂正」といえるのです。
0または1を連続して送信文字として送信する通信を考えましょう。正しく0,1を受信するできればよいのですが、0を送っても1と間違える、1を送っても0と間違えることもあります。これが誤りです。また、判断を間違えないためにこの信号は0とも1とも判断できないとすることがあります。これは消失と呼ばれます。こうした送受信の状況は下左図の様な表現で荒らすことができます。これは二元誤り消失通信路モデルと言います。二元(=0,1を送信する)誤り消失(=誤りと消失が起こる)通信路というわけです。数独の答えがあって問題を作成することを考えましょう。81か所のマス目には1~9の数字が入っていてその一部分を残して空白を作ります。数字を書き換えることはありません。これは、送信文字が1~9（9種類）で、誤りは無く、消失（=空白）が起こりえる通信路、「9元消失通信路」にほかなりません（下右図）。
図 通信の基本二元誤り消失通信路（左）と数独に対応した９元消失通信路モデル（右）
説明を簡単にするため数字｛１，２，３、４｝を用いる4×4のミニ数独（右図）を使いましょう。
ミニ数独の答えの総数は「288個」 です。その答えがどれだけ似ているかを調べます。
下左はひとつのミニ数独の答えになっています。下中央は左の答えと赤数字の部分４か所だけ違っています。この違う部分を空白にしたもの下右の図は、下左と下中央の２つの答えがあるので、適切なミニ数独の問題とは言えません。
|
１ |
２ |
３ |
４ |
|
１ |
２ |
３ |
４ |
|
１ |
２ |
３ |
４ |
|
３ |
４ |
１ |
２ |
|
４ |
３ |
１ |
２ |
|
|
|
１ |
２ |
|
２ |
１ |
４ |
３ |
|
２ |
１ |
４ |
３ |
|
２ |
１ |
４ |
２ |
|
４ |
３ |
２ |
１ |
|
３ |
４ |
２ |
１ |
|
|
|
２ |
１ |
図 ミニ数独の答え（左）、左に類似した別の答え（中央） 、ミニ数独の不適切な問題（右）
上右の図は不適切な問題を作るのに最も少ない空白の個数で、これは誤り訂正符号の世界では何個まで確実に訂正できるかという訂正能力と関係した値（最小距離）になっています。上の左と中央の様に２つの答えがどれだけ似ているかということは、誤り訂正符号の性能を詳しく調べる尺度になります。
表 ミニ数独の距離の分布
|
i |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
|
Bi |
1 |
0 |
0 |
0 |
8 |
0 |
0 |
0 |
14 |
0 |
64 |
0 |
104 |
0 |
64 |
0 |
33 |
注：Biはi に対してBi の値×288個の距離となる（異なる箇所がある）ペアがあったことを意味しています。距離0～3と5,6,7,9,11,13,15のペアはないということもわかります。
9×9=81のマス目がある、本来の数独についても関連調査をおこなうと、i=5までは同様でミニ数独と異なり i=6以上において、ペアが存在することを具体的に示しました。誤り訂正の理解にも役立つ研究と評価されました。学外でも発表しました。（i=4までについては以前に信州大西新らにより発表されています。）
以下に、数独の２つの答えが距離6となっている（6か所だけ数字が異なっている）例を示します。
■ 2017
June 30 updated by 山口