Paper 2013/180

A New Class of Product-sum Type Public Key Cryptosystem,K(V)$\mathrm{\Sigma }\mathrm{\Pi }$PKC,Constructed Based on Maximum Length Code

Masao KASAHARA

Abstract

The author recently proposed a new class of knapsack type PKC referred to as K(II)$\mathrm{\Sigma }\mathrm{\Pi }$PKC [1]. In K(II)$\mathrm{\Sigma }\mathrm{\Pi }$PKC with old algorithm DA[I], 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 $\rho$ satisfies $0.01<\rho <0.2$. In K(II)$\mathrm{\Sigma }\mathrm{\Pi }$PKC, no secret sequence such as super-increasing sequence or shifted-odd sequence but the sequence whose components are 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(II) for decoding K(II)$\mathrm{\Sigma }\mathrm{\Pi }$PKC.We show that with new decoding algorithm, DA(II), K(II)$\mathrm{\Sigma }\mathrm{\Pi }$PKC yields a higher coding rate and a smaller size of public key compared with K(II)$\mathrm{\Sigma }\mathrm{\Pi }$PKC using old decoding algorithm, DA(I). We further present a generalized version of K(II) $$PKC, referred to as K(\v)$$PKC. We finally present a new decoding algorithm DA(III) and show that, in K(V)$$PKC with DA(III), the relation, $$ holds, where $$ is the factor ratio that will be defined in this paper. We show that K(V)$$PKC yields a higher security compared with K(II) $$PKC.