To achieve one-pass and one-rate authenticated encryption capable of performing parallel processings and totally performing encryption and decode processings by only one encryption function. An authenticated encryption device comprises an authenticated encryption means for applying a two-round Feistel structure using an encryption function assigned with an auxiliary variable for a round function per two blocks to an input plaintext or encrypted text thereby to generate an encrypted text or decoded plaintext. The authenticated encryption means finds an encrypted text chunk CC[i]=(C[i_1], C[i_2]) corresponding to an i-th plaintext chunk MC[i]=(M[i_1], M[i_2]) when dividing a plaintext into chunks per two blocks as: C[i_1]=F_K((N,Tw_i_1),M[i_1])xor M[i_2], C[i_2]=F_K((N,Tw_i_2),C[i_1])xor M[i_1].