An information processing apparatus, comprising: a tangible memory unit that stores key data necessary for Feistel-type cryptographic processing; a processor configured to execute various programs and to control starting and ending of the Feistel-type cryptographic processing; and an encryption processing apparatus configured to perform the Feistel-type cryptographic processing, the encryption processing apparatus including a first encryption processing section operating in a round n of the Feistel-type cryptographic processing and including a first nonlinear transformation section configured to transform input information into first nonlinear transformed information, and a first linear transformation section configured to transform the first nonlinear transformed information into 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 configured to transform the input information into second nonlinear transformed information, and a second linear transformation section configured to transform the second nonlinear transformed information into second linear transformed information; and an exclusive-or section (142, 143, 144) configured to perform an exclusive-or operation based on the second linear transformed information and the first linear transformed information, characterized in that when the first nonlinear transformed information is expressed as a first sequence vector, the first linear transformed information is expressed as a second sequence vector, the second nonlinear transformed information is expressed as third sequence vector, and the second linear transformed information is expressed as a fourth sequence vector, then a first row vector chosen from a first inverse matrix of a first square MDS matrix that transforms the first sequence vector to the second sequence vector, and a second row vector chosen from a second inverse matrix of a second square MDS matrix that transforms the third sequence vector to the fourth sequence vector and that is different from the first square MDS matrix, are linearly independent. a tangible memory unit that stores key data necessary for Feistel-type cryptographic processing; a processor configured to execute various programs and to control starting and ending of the Feistel-type cryptographic processing; and an encryption processing apparatus configured to perform the Feistel-type cryptographic processing, the encryption processing apparatus including a first encryption processing section operating in a round n of the Feistel-type cryptographic processing and including a first nonlinear transformation section configured to transform input information into first nonlinear transformed information, and a first linear transformation section configured to transform the first nonlinear transformed information into 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 configured to transform the input information into second nonlinear transformed information, and a second linear transformation section configured to transform the second nonlinear transformed information into second linear transformed information; and an exclusive-or section (142, 143, 144) configured to perform an exclusive-or operation based on the second linear transformed information and the first linear transformed information, a first encryption processing section operating in a round n of the Feistel-type cryptographic processing and including a first nonlinear transformation section configured to transform input information into first nonlinear transformed information, and a first linear transformation section configured to transform the first nonlinear transformed information into 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 configured to transform the input information into second nonlinear transformed information, and a second linear transformation section configured to transform the second nonlinear transformed information into second linear transformed information; and an exclusive-or section (142, 143, 144) configured to perform an exclusive-or operation based on the second linear transformed information and the first linear transformed information, characterized in that when the first nonlinear transformed information is expressed as a first sequence vector, the first linear transformed information is expressed as a second sequence vector, the second nonlinear transformed information is expressed as third sequence vector, and the second linear transformed information is expressed as a fourth sequence vector, then a first row vector chosen from a first inverse matrix of a first square MDS matrix that transforms the first sequence vector to the second sequence vector, and a second row vector chosen from a second inverse matrix of a second square MDS matrix that transforms the third sequence vector to the fourth sequence vector and that is different from the first square MDS matrix, are linearly independent.