一般情報源を一様乱数に変換する方法およびその暗号への適用に関する研究

一般信息源转换为均匀随机数的方法及其在密码学中的应用研究

基本信息

批准号：
13750325
负责人：
古賀弘樹
金额：
$ 1.34万
依托单位：
University of Tsukuba
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2001
资助国家：
日本
起止时间：
2001 至 2002
项目状态：
已结题

项目摘要

Homophonic Coding(以下HCと略記)は,シンボルの生起確率に偏りのある情報源の出力を,近似的に一様乱数とみなせるように変換する符号化法である.HCの出力からはもとの情報源の統計的性質が失われるので,一般には,もとの情報源出力を直接暗号化するよりもHC出力を暗号化した方が,暗号文は安全になる.本研究で考える情報源は,無記憶性やマルコフ性などの仮定のない一般の情報源であり,一般の情報源に対するHCの基本的な性質を調べることが本研究の目的であった.昨年度の研究において,一般情報源に対する固定長のHCの基本的な性質が明らかになったので,本研究では今年度はHCを秘密鍵暗号系に組み込んだ新しい暗号系を考えて,その新しい秘密鍵暗号系のもつ基本的な性質を議論した.新しい秘密鍵暗号系の性能を決定する要素には3つの量,すなわち,暗号文のレートR_C,鍵のレートR_K,HCで用いる一様乱数のレートR_V,があり,(1)HC出力が近似的に一様分布と見倣せて,(2)ある許容範囲以上の情報が暗号文から漏れない,という2つの条件のもとで,3つのレートR_C,R_K,R_Vの取り得る値の限界を考えた.今年度の研究成果は,R_C,R_K,R_Vの取り得る値の限界を完全に明らかにしたことである.実際,R_Cの下限は情報源の圧縮限界であり,R_Kの下限は条件(2)で許容範囲を決めるパラメータで決まり,R_Vの下限は固定長HCで現れる基本的な量となることが示された.求めた下限は,十分大きな符号語長で情報源をブロック符号化すれば達成可能である.

谐音编码（以下称为HC）是一种编码方法，它转换了以符号出现的概率为近似均匀的随机数的源的源输出。由于原始源的统计属性因HC的输出而丢失，因此当对HC输出进行加密而不是直接加密原始源输出时，密文通常更安全。这项研究中考虑的来源是一般信息源，没有任何假设，例如无记忆力或马尔可波，而本研究的目的是研究HC对于一般信息源的基本特性。在去年的研究中，揭示了通用信息源的固定长度HC的基本特性。在这项研究中，今年，我们考虑了一个新的密码系统，将HC纳入私有密钥密码系统，并讨论了新的私有密钥密码系统的基本属性。决定私有密钥密码系统性能的因素包括三个数量，即密文R_C的速率，密钥R_K的速率以及HC中使用的均匀随机数速率。在两个条件下，（1）HC输出可以看作是近似均匀的分布，（2）超过一定公差范围的信息不会从密文中泄漏。今年的研究结果已经完全揭示了R_C，R_K和R_V的可能值的限制。实际上，R_C的下限是源的压缩极限，R_K的下限由确定条件下允许范围的参数确定（2），R_V的下限是在固定长度HC处出现的基本量。可以通过以足够大的代码字长度对源进行块编码来实现所获得的下限。