Embodiments of an invention for a compact, low power Advanced Encryption Standard circuit are disclosed. In one embodiment, an apparatus includes an encryption unit having a substitution box and an accumulator. The substitution box is to perform a substitution operation on one byte per clock cycle. The accumulator is to accumulate four bytes and perform a mix-column operation in four clock cycles. The encryption unit is implemented using optimum Galois Field polynomial arithmetic for minimum area.