A method of providing anti-replay protection, authentication, and encryption with minimal data overhead is provided. A sender uses an arbitrary-length pseudorandom permutation to encrypt messages that include plaintext and successively increasing sequence numbers, to produce ciphertext messages. The sender transmits the ciphertext messages. A receiver receives the ciphertext messages and, for each received ciphertext message, performs the following operations. The receiver decrypts the given ciphertext message to recover plaintext and a candidate sequence number from the message. The receiver determines if the candidate sequence number is in any one of multiple acceptable sequence number windows having respective sequence number ranges that are based on at least one of a highest sequence number previously accepted and a last sequence number that was previously rejected, as established based on processing of previously received ciphertext messages.