Construction of New Classes of Product-sum Type Public Key Cryptosystem, K(Ⅳ)SnPKC, Constructed Based on Maximum Length Code

摘要

著者は最近新しい積和型公開鍵暗号，k(Ⅱ)ΣΠPKCを最大周期系列に基づいて構成した.k(Ⅱ)ΣΠPKCは,(i)送信者ポブが，符号化率（情報レート)0.01～0.2を満たしつつ，アリスの公開鍵集合の非常に小さな部分集合をランダムに選択した上で，暗号文を導くことが可能であること，および（ii)従来方式に共通にみられる超増加型、あるいは超減少型の秘密系列を用いるのではなく、非増減型のユニフォーム•サイズの秘密系列を用いていること等の特徴を有していた.本論文では，従来，K(Ⅱ)ΣΠPKC方式に対してこれを一般化したK(Ⅳ)ΣΠPKCを提案するとともに,k(Ⅱ)ΣΠPKCに対して提案されていた復号法DA(Ⅰ)を改善した新しい復号法DA(Ⅰ)，DA(Ⅲ)を提案する.新しい復号法を応用したK(Ⅳ)ΣΠPKCにおいては以下のことが実現されることを示す.1.レートを2/3に近づけ得ること2.安全性を改善することが可能であること3.公開鍵サイズを小さくすることが可能となること4.任意の二組の秘密鍵の共通因数率r_Fを0に近づけ得ること.%The author recently proposed a new class of knapsack type PKC referred to as K(Ⅱ)ΣΠPKC. In K(Ⅱ)ΣΠPKC, Bob randomly constructs a very small subset of Alice's set of public key whose order is very large, under the condition that the coding rate ρ satisfies 0.01< ρ < 0.2. In K(Ⅱ)ΣΠPKC, no secret sequence such as super-increasing sequence or shifted-odd sequence but the sequence whose component is constructed by a product of the same number of many prime numbers of the same size, is used. In this paper we present a new algorithm, DA(Ⅱ) for decoding K(Ⅱ)ΣΠPKC. We show that with new decoding algorithm, DA(Ⅱ), for K(Ⅱ)ΣΠPKC yields a higher coding rate, a smaller size of public key and a higher security compared with K(Ⅱ)ΣΠPKC using old decoding algorithm, DA(Ⅰ). We further present a generalized version of K(Ⅱ)ΣΠPKC, referred to as K(Ⅳ)ΣΠPKC, along with present a new decoding algorithm DA(Ⅲ).