In this paper, we propose a new method for constructing the public-key cryptosystems based on the error-correcting code and the probabilistic structure. The constructed PKCs are referred to as K(HI)SE(1)PKC and K(IV)SE(1)PKC. In K(III)SE(1)PKC, one of the two sets of the check symbols for one message sequence is randomly chosen at the sender, yielding the high security due to the probabilistic structure of random choice. In K(IV)SE(1)PKC, a large class of small size error correcting codes such as (7,4,3) cyclic Hamming code and (3,1,3) code {(000), (111)} is used, yielding a simple process of decryption as well as high security. The K(IV)SE(1)PKC has a remarkable feature that the coding rate can take on 1.0. We show that the members of the class of perfect codes such as (7,4,3) cyclic Hamming code, and the code {000,111} realize the PKC with the coding rate of exactly 1.0. Besides the size of the public key for K(IV)SE(1)PKC can be made smaller than that of the McEliece's PKC.
展开▼