非一様なデータに対し安全性と効率を両立する情報理論的に安全な暗号技術に関する研究

点击翻译按钮获取中文摘要

昨年度考案した以下の4条件を満たす符号化方式 (L,L+1,L)-UPE (UPE: Uniform Prefix Encoding)の構成アルゴリズムの正当性を数学的に証明した．(1) 符号化前の入力データのビット長が L，(2) 符号語のビット長 L+1，(3) 任意の確率分布に対して符号語の先頭Lビットは一様に分布する(このとき，符号化方式は確率分布を知っていることを仮定する)，(4) 符号語は一意復号可能である．(L,L+1,L)-UPEの構成は，次のような入出力対応表を作成することによって行う．(1)入力されうるデータのうち，生起確率pが最も低いデータに符号語c0を割り当てる．ただし，c0は今まで割り当てられていない符号語であり，最下位ビットが0となるものとする．この符号語の生起確率をpとする．(2)入力されうるデータのうち，生起確率Pが最も高いテータsに符合語c1を割り当てる．ただし，c1の最下位ビットは1であり，上位Lビットはc0と一致するものとする．c1の生起確率p1を p1=1/2^L-p0 とし，sの生起確率をP-p1に更新する．以上のステップを全ての入力に符号語が割り当てられるまで繰り返すことにより，(L,L+1,L)-UPEが構成される．構成された符号が上記4条件を満たすことは，符号の構成に関する帰納法で証明される．また，構成された(L,L+1,L)-UPEを用いることで，従来よりも効率の良い情報理論的に安全な秘匿機能つき認証符号が構成できることを示した．情報理論的に安全な秘匿機能つき認証符号において，平文の確率分布が非一様である場合にも安全である方式を構成するためには，平文の3倍のビット長の鍵が必要であった．これに対し，提案したUPEを平文の事前処理として用いることで，平文のビット長の2倍+2ビットの鍵で安全な方式が構成できることを示した．