An encryption apparatus for block data, comprises a first processing unit randomizing the block data in units of first portions obtained by dividing the block data, and a second processing unit diffusing the block data output from the first processing unit with respect to a second portion of the block data which is wider than the first portion. The first processing unit comprises first nonlinear processing units nonlinearly transforming the block data in units of the first portions. The second processing unit comprises a first linear diffusion processing unit linearly diffusing the second portion of the block data. At least one of the first nonlinear processing units comprises second nonlinear processing units nonlinearly transforming the block data in units of the first portions, and a second linear diffusion processing unit linearly diffusing the second portion of the block data.