Encryption processing apparatus for performing Feistel-type cryptographic processing, the encryption processing apparatus comprising: a first encryption processing section operating in a round n of the Feistel-type cryptographic processing and including a first nonlinear transformation section for transforming from input information to first nonlinear transformed information, and a first linear transformation section for transforming from said nonlinear transformed information to first linear transformed information, a second encryption processing section operating in a round n+2 of the Feistel-type cryptographic processing and including a second nonlinear transformation section for transforming from input information to second nonlinear transformed information, and a second linear transformation section for transforming from said nonlinear transformed information to second linear transformed information, an exclusive-or section (142, 143, 144) for performing exclusive-or operation based on said second linear transformed information and said first linear transformed information, characterized in that, if said first nonlinear transformed information is expressed as a first sequence vector, said first linear transformed information is expressed as a second sequence vector, said second nonlinear transformed information is expressed as a third sequence vector, and said second linear transformed information is expressed as a fourth sequence vector, a first row vector chosen from an inverse matrix of a first square MDS matrix, which indicates transformation from said first sequence vector to said second sequence vector, and a second row vector chosen from an inverse matrix of a second square MDS matrix, which indicates a transformation from said third sequence vector to said fourth sequence vector and which is different from said first square MDS matrix, are linearly independent. a first encryption processing section operating in a round n of the Feistel-type cryptographic processing and including a first nonlinear transformation section for transforming from input information to first nonlinear transformed information, and a first linear transformation section for transforming from said nonlinear transformed information to first linear transformed information, a first nonlinear transformation section for transforming from input information to first nonlinear transformed information, and a first linear transformation section for transforming from said nonlinear transformed information to first linear transformed information, a second encryption processing section operating in a round n+2 of the Feistel-type cryptographic processing and including a second nonlinear transformation section for transforming from input information to second nonlinear transformed information, and a second linear transformation section for transforming from said nonlinear transformed information to second linear transformed information, a second nonlinear transformation section for transforming from input information to second nonlinear transformed information, and a second linear transformation section for transforming from said nonlinear transformed information to second linear transformed information, an exclusive-or section (142, 143, 144) for performing exclusive-or operation based on said second linear transformed information and said first linear transformed information, characterized in that, if said first nonlinear transformed information is expressed as a first sequence vector, said first linear transformed information is expressed as a second sequence vector, said second nonlinear transformed information is expressed as a third sequence vector, and said second linear transformed information is expressed as a fourth sequence vector, said first nonlinear transformed information is expressed as a first sequence vector, said first linear transformed information is expressed as a second sequence vector, said second nonlinear transformed information is expressed as a third sequence vector, and said second linear transformed information is expressed as a fourth sequence vector, a first row vector chosen from an inverse matrix of a first square MDS matrix, which indicates transformation from said first sequence vector to said second sequence vector, and a second row vector chosen from an inverse matrix of a second square MDS matrix, which indicates a transformation from said third sequence vector to said fourth sequence vector and which is different from said first square MDS matrix, are linearly independent.